# Midterm topics

• Stallings chapters 1-6, with emphasis on 4-6.
• Assignments 1-4.
• Lectures 1-12.

All review questions in the book are fair game, as well as questions similar to assigned or auxiliary problems. The exam is open book and notes.

1. Explain exactly why monitors are preferable to semaphores, with examples.
The key is actually really subtle. A monitor is "stateless", which means that it does not retain a state between firings. This makes enumeration proofs of freedom from deadlock easier than for stateful things like semaphores, which often have a state explosion during the proof! For example, if we rewrite producer-consumer in terms of monitors, the assumable states are not proportional to the number of monitors!
2. Compare overhead of the banker's algorithm with overhead of deadlock detection and kill. In which situations is each superior?
The key is to figure out what you want to preserve. Suppose we want optimal throughput. Then the banker's algorithm is better than detect-and-kill, because in the latter case processes must be started over in order to complete. On the other hand, consider a time-sharing environment in which programs often have "runaway" bugs. Then the banker's algorithm is inferior to "detect and kill" because its assumptions are incorrect. Particularly, the assumption that all processes actually require what they request is incorrect in a situation where a student is debugging and is just as likely to interrupt a program with control-C as to keep it running!
3. Consider the following resource allocation graph. Is the system deadlocked? If so, which processes are involved?

Yes, it is deadlocked. There is a cycle P2,R3,P3,R2.
4. Suppose for the banker's algorithm described in class, we have the following scheme:
```
requested     allocated
r1 r2 r3 r4   r1 r2 r3 r4
process 1   2  5  3  2    1  0  3  2
process 2   1  5  1  1    1  1  0  0
process 3   3  3  3  3    3  3  3  3
```
and suppose that the total of available resources is
```
r1 r2 r3 r4
12 12 7  9
```
Is this a safe state? Why or why not?
It is safe if all processes can complete, one at a time. Let's start with process 3, which has resources to complete. After removing process 3, the resource matrix is:
```
requested     allocated
r1 r2 r3 r4   r1 r2 r3 r4
process 1   2  5  3  2    1  0  3  2
process 2   1  5  1  1    1  1  0  0
```
And remaining resources include:
```
r1 r2 r3 r4
10  9  4  7
```
At this point, process 2 can run. This results in the matrix:
```
requested     allocated
r1 r2 r3 r4   r1 r2 r3 r4
process 1   2  5  3  2    1  0  3  2
```
and available resources are:
```
r1 r2 r3 r4
10 12  4  7
```
At this point, process 1 can run, so the state is safe.
5. What is the impact upon deadlock if one forces a set of otherwise unconstrained processes to allocate one resource unit at a time, even if they need a large number of resource units?