# Comp111 -- Midterm Exam

### Mon Nov 6, 2006open book and notes No electronics of any kind allowed.

1. (30 points) Consider the resource matrices given as follows:
```
Requested
r1  r2  r3  r4
p1   3  10   3   4
p2  10   0   6   4
p3   1   1   2   2
p4  10  10  10  10

Allocated
r1  r2  r3  r4
p1   3  10   3   4
p2   7   0   3   4
p3   0   0   2   2
p4   0   0   0   0

Total resources
r1  r2  r3  r4
10  10  10  10
```
Is this state safe? If so, give an order in which processes can complete their work. If not, identify a process that cannot finish.
2. Consider two producer-consumer examples described in class:

Example 1:
```
#define SIZE 100
int bot=0, top=0;
mutex incoming, outgoing;
int queue[SIZE];
void enqueue(int c) {
lock(incoming);
if ((top+1)%SIZE!=bot) { queue[top]=c; top=(top+1)%SIZE; }
unlock(incoming);
}
int dequeue() {
int out;
lock(outgoing);
if (bot!=top) { out = queue[bot]; bot=(bot+1)%SIZE; }
else { out = 0; }
unlock(outgoing);
return out;
}
```

Example 2:
```
semaphore excl = 1; // used as binary semaphore
semaphore avail = 0;  // number used
semaphore unused = SIZE-1; // number free/available
void producer() {
while (1) {
int thing = produce();
semWait(unused);
semWait(excl); enqueue(thing); semSignal(excl);
semSignal(avail);
}
}
void consumer() {
while (1) {
int thing;
semWait(avail);
semWait(excl); thing = dequeue(); semSignal(excl);
semSignal(unused);
consume(thing);
}
}
```
1. (20 points) Suppose that these two examples are used together. Are all the locks necessary or not? If so, explain why. If not, identify locks that can be removed. If there are two possibilities for which locks can be removed, eliminate the ones with the slowest runtimes. Justify your answer.
2. (20 points) Rewrite all code above to eliminate all semaphores and utilize only binary mutexes. The behavior should be exactly the same as before.
3. (30 points) In class there was some discussion of states of a process between which there cannot be transitions. For the case of UNIX/Linux, identify the state transitions that cannot occur for a process, and explain why each of these transitions is impossible.