open book and notes

No electronics of any kind allowed.

- (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. - 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); } }

- (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.
- (20 points) Rewrite all code above to eliminate all semaphores and utilize only binary mutexes. The behavior should be exactly the same as before.

- (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.