### Comp111 Midterm Exam Nov 3, 2009 - open books and notes

No electronic devices of any kind allowed, including cellphones, calculators, pagers, etc. Please turn these off before beginning the exam.

Please show all work on these pages. Make sure that your work for each problem is clearly marked. These pages will be graded and returned electronically, like exercises.

1. (30 points) Consider the following code, simplified by using high-level subroutines for `lock` and `unlock` actions:
```
mutex A, B; // two binary mutex locks
void foo() {
lock(A);
lock(B);
something_critical();
unlock(A);
unlock(B);
lock(B);
lock(A);
something_else_critical();
unlock(B);
unlock(A);
}
```
Suppose that multiple threads are invoked, all of which execute `foo()`. Based upon these locks alone, can these threads deadlock? If so, how?
2. (20 points) Suppose that in the above code, `lock` and `unlock` are implemented using binary kernel semaphores rather than user mutexes. Then how many context switches are needed to execute one instance of `foo()` above? Explain your answer.

3. (30 points) Present C code that opens a file for input and dups it to the standard input of your process. Explain each step.
4. (20 points) Suppose we have a classical ring queue as discussed in class:
```
int full() {
int ret;
lock(A);
ret = ((last+1)%SIZE==first);
unlock(A);
return ret;
}
int empty() {
int ret;
lock(A);
ret=(first==last);
unlock(A);
return ret;
}
void enqueue(int i) {
if (!full()) {
lock(A);
queue[last] = i;
last = (last+1)%SIZE;
unlock(A);
}
}
int dequeue() {
if (!empty()) {
lock(A);
int out = queue[first];
first = (first+1)%SIZE;
unlock(A);
return out;
}
}
```
This has a bug. Explain what happens when `enqueue` and `dequeue` are used in different threads, and why.