## Comp111 -- Midterm Exam Review 3 Answers Midterm Mon Nov 6, 2006 Open book and notes

1. Suppose that one has the following resource tables for three resources:
allocatedresource 1resource 2resource 3
process 1352
process 2443
process 3111
• extra resources requested (not including allocated resources):
requestedresource 1resource 2resource 3
process 1121
process 2543
process 3112
• total resources available (including allocated and free resources):
availableresource 1resource 2resource 3
process 110127
1. (15 points) Is this situation "safe" according to Lamport's bankers' algorithm (is there a way for all processes to complete)? Why or why not?
From a quick estimate, process 1 can continue, while process 2 and 3 are blocked until process 1 completes. Process 1 completion takes 9 of 10 units of resource 1, 12 of 12 units of resource 2, and 7 of 7 units of resource 3. Neither process 2 nor process 3 can proceed until process 1 releases resources.
2. (15 points) If process 1 hangs indefinitely without releasing resources or allocating any more resources, can the other processes complete? Why or why not?
From part 1, no process other than process 1 can complete. If process 1 hangs, then regardless of whether allocations are done for it or not, the other processes are blocked awaiting resources and the whole scheme deadlocks. The banker's algorithm presumes that every process, with all needs satisfied, completes. Without this assumption, it fails to assure freedom from deadlock.
3. (10 points) Can the lock priority algorithm be applied to this situation? Why or why not?
Lock priority assumes that resource locks may be released before other locks are acquired. The banker's algorithm presumes that resources, once allocated, are allocated until completion. The programs for which the banker's algorithm functions cannot be changed to lock-priority without changing the programs according to the differing assumptions. The algorithms support distinct programming models and are not interchangeable.
2. Consider the following producer-consumer code:
```
#define SIZE 10
int begin=0, end=0, queue[SIZE];
mutex m;
int empty() { return begin==end; }
int full() { return begin==(end+1)%SIZE; }
void produce(int thing) {
while (full()) { /* do nothing */  }
mutex_lock(m);
queue[end]=thing; end=(end+1)%SIZE;
mutex_unlock(m);
}
int consume() {
while (empty()) { /* do nothing */ }
mutex_lock(m);
int ret = queue[begin];
begin=(begin+1)%SIZE;
mutex_unlock(m);
return ret;
}
```
Suppose that `produce` and `consume` are called independently and perhaps concurrently by multiple threads.
1. (15 points) Does this code have race conditions? Why or why not? If there are race conditions, how would one eliminate them, using just the one mutex lock (m)? Hint: consider only equivalent effects.
Consider the situation in which more than one thread has called produce or consume at the same time. Neither empty nor full is atomic. Thus it is possible that two threads would simultaneously get TRUE responses to !empty() or !full() even though there is only one element in the queue or left free, respectively.

To fix this requires considerable changes to the code: we must lock before allowing empty() to be called, and then unlock before each repeat of the loop (to allow producers to produce!)

```
int consume() {
while (1) {
mutex_lock(m);
if (!empty())  {
int ret = queue[begin];
begin=(begin+1)%SIZE;
mutex_unlock(m);
return ret;
} else {
mutex_unlock(m);
}
}
}
```
Produce must be changed in the same fashion.
2. (15 points) The above `while` loops are considered bad programming practice. Why?