Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
COMS W4118: Operating Systems I
Spring 2024 Midterm Exam
INSTRUCTIONS
This exam is closed book. You can have with you a double-sided letter-sized sheet of notes of your choosing. Complete the following questions. The order of the questions is random. Don't get stuck by insisting on doing them in order; you can answer the questions in any order you like. There are three problems with multiple parts. Write your solutions in the space provided. Answers written outside of the space provided will NOT be graded.
Make sure you write your name and UNI on the front page of your exam. If you are a CVN student, please write CVN on the front page.
You need not write a novel in order to get full credit. To avoid this problem, all explanations should be less than five lines of text or less. Explanations in excess of that will receive zero credit.
Unless explicitly stated, assume that all function and system calls succeed, i.e., you do not need to check for errors.
Please write your name and UNI below. If you are a CVN student please write CVN as well.
Return both the questions and the answer sheet once you are done. Write your name on the answer sheet as well.
Q1 (30 points)
1. Mention one advantage and two disadvantages of the Shortest Job First scheduling policy. How can you mitigate the disadvantages?
2. Explain briefly how processes differ from threads. Which abstraction would you choose if you cared (i) about performance and (ii) about security/isolation?
3. We have two threads that want to concurrently increment a counter 10 million times. Which of the variations of the increment function do you expect to finish execution faster and why? Assume that both threads always use the same function variation.
(a)
int counter = 0;
pthread_mutex_t mutex;
void add_million_fine() {
for (int i = 0; i < 1e7; ++i) {
pthread_mutex_lock(&mutex);
++counter;
pthread_mutex_unlock(&mutex);
}
}
(b)
int counter = 0;
pthread_mutex_t mutex;
void add_million_coarse() {
pthread_mutex_lock(&mutex);
for (int i = 0; i < 1e7; ++i)
++counter;
pthread_mutex_unlock(&mutex);
}
4. Is the read-copy-update (RCU) mechanism good for read-heavy workloads and why? What about write-heavy workloads?
5. How do we prevent userspace programs from executing privileged operations? Give an example of such an operation.
6. Briefly explain the race condition in the following
implementation of the sleep() function:
static void sig_alrm(int signo) {
/* nothing to do, just return to
* wake up from pause()*/
}
unsigned int sleep(int seconds) {
if (signal(SIGALRM, sig_alrm) = SIG_ERR)
return seconds;
alarm(seconds);
pause();
return alarm(0);
}
Q2 (36 points)
Consider the following C program, file0.c:
void writer(int fd, pid_t pid) {
char buf[3] = {'f', 'o', 'o'};
if (pid) sleep(1);
for (int i = 0; i < 3; ++i) {
write(fd, &buf[i], 1);
sleep(2);
}
if (pid) waitpid(pid, NULL, 0);
}
int main() {
pid_t pid = fork();
int fd = open("foo.txt", O_RDWR | O_CREAT, S_IRUSR | S_IWUSR);
writer(fd, pid);
close(fd);
return 0;
}
(2.1)-(2.5) present file1-file5, which are variations of file0. In the answer sheet, write the content of ‘foo.txt’ after executing each variation, including file0. If an output line varies from run to run, write "UNPREDICTABLE".
3Notes:
- Error-checking is omitted for brevity. Assume all calls succeed.
- Assume file0-file5 run on a lightly-loaded system.
- Assume that `foo.txt’ is always deleted between different program executions.
(2.1) file1’s writer() function is the same as file0’s. file1’s main function below switches the order of open() and fork()
from file0:
int main() {
int fd = open("foo.txt", O_RDWR | O_CREAT, S_IRUSR | S_IWUSR);
pid_t pid = fork();
writer(fd, pid);
close(fd);
return 0;
}
(2.2) file2’s writer() function is the same as file0’s.
file2’s main function below is similar to file1’s, but calls open()
twice:
int main() {
int fd1 = open("foo.txt", O_RDWR | O_CREAT, S_IRUSR | S_IWUSR);
int fd2 = open("foo.txt", O_RDWR | O_CREAT, S_IRUSR | S_IWUSR);
pid_t pid = fork();
writer(pid ? fd1 : fd2, pid);
close(fd);
return 0;
}
(2.3) file3’s writer() function is the same as file0’s.
file3’s main function below is similar to file2’s, but calls dup()
instead of the second open():
int main() {
int fd1 = open("foo.txt", O_RDWR | O_CREAT, S_IRUSR | S_IWUSR);
int fd2 = dup(fd1);
pid_t pid = fork();
writer(pid ? fd1 : fd2, pid);
close(fd);
4return 0;
}
(2.4) file4, shown in its entirety below, is similar to file0, but
reimplemented using the C standard I/O library:
void writer(FILE *fp, pid_t pid) {
char buf[3] = {'f', 'o', 'o'};
if (pid) sleep(1);
for (int i = 0; i < 3; ++i) {
fwrite(&buf[i], 1, 1, fp);
sleep(2);
}
if (pid) waitpid(pid, NULL, 0);
}
int main() {
pid_t pid = fork();
FILE *fp = fopen("foo.txt", “w+”);
writer(fp, pid);
fclose(fp);
return 0;
}
(2.5) file5’s writer function is the same as file4’s.
file5’s main() function below switches the order of fopen() and
fork() from file4:
int main() {
FILE *fp = fopen("foo.txt", “w+”);
pid_t pid = fork();
writer(fp, pid);
fclose(fp);
return 0;
}
5Q3
(34 points)
1a. (10 points) Consider a barbershop with one barber. The barber sleeps when there are no customers waiting. When a customer arrives, the barber wakes up and starts cutting the customer's hair. If a customer arrives while the barber is busy, they wait. Implement this functionality in the skeleton code below using semaphore synchronization mechanisms.
// your initialization here
void barber() {
while(1) {
// your implementation here
cut_hair();
// your implementation here
}
}
void customer() {
// your implementation here
get_haircut();
// your implementation here
}
1b. (10 points) Assume now that the barbershop has N seats (not including a customer getting a haircut). If a customer arrives when there are N other customers waiting, they leave by calling the leave() function. Implement this functionality using the same skeleton code and semaphore primitives again.
Some potentially useful semaphore-handling functions:
int sem_wait(sem_t *sem);
int sem_trywait(sem_t *sem);
int sem_post(sem_t *sem);
int sem_init(sem_t *sem, int pshared, unsigned value);
2a. (5 points) Assume that you run a banking exchange with a large number of concurrent transactions. One of your software engineers implements the following function for the atomic transfer of funds between accounts. Can the use of that function cause a deadlock? If not, explain why. If yes, give an example.
Assume that each account has a correctly-initialized associated mutex stored in the lock[] array and that money_xfer() transfers money between two accounts non-atomically.
pthread_mutex_t lock[N];
void money_xfer_atomic(int src, int dst, int amount) {
pthread_mutex_lock(&lock[src]);
pthread_mutex_lock(&lock[dst]);
money_xfer(src, dst, amount)
pthread_mutex_unlock(&lock[dst]);
pthread_mutex_unlock(&lock[src]);
}
2b. (9 points) If you found one or more deadlock situations in 2a, fix the code to avoid them.