# Comp111 -- Midterm Exam Answers

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

First, we know that p4 will need to be last, becasue it needs all resources. So we can safely list it last and consider the rest without it.

Next, consider process 1, which has all of its resources. Thus it will go first, and we can safely consider p2 and p3 without p1 and p4.

Of p2 and p3, p3 needs the least resources and can go first.

Thus one order is p1, p3, p2, p4 and the configuration is safe.

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;
semaphore avail = 0;
semaphore unused = SIZE-1;
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(free);
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.
The semWait(excl) and semSignal(excl) are redundant and can be eliminated. They should be eliminated rather than the mutexes, because semaphores are slower than mutexes.
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.
This is a tricky one. The key is that whenever there is a danger of a buffer overrun, we should block either producer or consumer until it is over. This is the purport of the "avail" and "free" semaphores. We've eliminated the "mutex" semaphore, so that all we have to do is to replace "avail" and "free" and we're done.

First, we note that each semaphore can be replaced by a pair of mutexes and an integer variable, as follows:

```
struct sem {
int semValue;
mutex semExcl, semDelay;
};
typedef struct sem Sem;
void mySemInit(Sem *s, int value) {
s->semvValue=value;
s->semExcl=1;  // unlocked
s->semDelay=0; // locked
}
void mySemWait(Sem *s) {
lock(s->semExcl);			// lock for mutual exclusion
s->semValue = s->semValue - 1;	// the following actions are atomic (!)
/* if there were no units available, release semValue and join the queue */
if (s->semValue <= -1) {
unlock(s->semExcl);
lock(s->semDelay);	// blocks until someone unlocks it!
} else {
unlock(s->semExcl);
}
}
void mySemSignal(Sem *s) {
lock(s->semExcl);			// lock for mutual exclusion
s->semValue = s->semValue + 1;	// increment semaphore
/* if there were waiters in the queue, release one */
if (semValue <= 0) unlock(semDelay);
unlock(s->semExcl);			// no more mutual exclusion
}
```
All we have to do is to implement this for a semaphore, and we're done. Rewrite example 2 as:
```
mutex mutex = 1;
Sem avail;
Sem unused;
void init() {
semInit(&avail,0);
semInit(&unused,SIZE-1);
}

void producer() {
while (1) {
int thing = produce();
mySemWait(&unused);
enqueue(thing);
mySemSignal(&avail);
}
}
void consumer() {
while (1) {
int thing;
mySemWait(&avail);
thing = dequeue();
mySemSignal(&unused);
consume(thing);
}
}
```
and we're done! Alternatively, we could write this into the code, but that's a bit less clear.