CSE 451 - Winter 1999

Chapter 7, Silberschatz and Galvin, 5th edition

1. Three examples of deadlock not related to a computer system:
• Traffic deadlock is an easy one. There's a picture on page 232.
• A filibuster in the Senate is an example of deliberate deadlock: the majority party holds one resource (enough votes to pass a particular bill) while the dissenters hold another resource (the floor). Usually this type of deadlock is broken by introducing resource preemption. That is, the dissenters release the floor before getting enough votes to block the bill, because they are hoarse.
• Two shy people like each other, but neither will admit it until the other one does. Tragically, they live long and lonely lives as a result. Isn't deadlock a terrible thing?

2. Yes, it is possible to have deadlock with only one process (and you don't have to play any games with multithreading to make it happen, either). Recall the program that Brian wrote on the board a few lectures ago:

  semaphore_t sem;
  main() {
      printf("Hello.");
      sem->P();
      sem->P();
  }
  

3. Is it possible to have a deadlock involving the resources of CPU time, memory, and disk space? I don't think so, for the following reasons.

• There is preemption on the CPU: no process can hold the CPU indefinitely, because the clock interrupt will take it away.
• There is also preemption on memory: the operating system can take memory away from a process either a little at a time (paging it out) or all at once (swapping it out), and then give that memory to another "more worthy" process.
• That leaves only the disk. Hold and wait doesn't seem to exist on the disk, because a request for disk space does not block if it cannot be satisfied. Instead, you just get "no space left on device."

4. a. The four necessary conditions for deadlock hold in traffic gridlock:

1. Mutual exclusion: The presence of one car in the intersection precludes another car from moving through.
2. Hold and wait: An eastbound car can hold the southwest corner of the grid; a southbound car can hold the northwest corner of the grid; and so forth.
3. No preemption: It's illegal to operate your car in reverse in the middle of the street, and anyway there's probably another car right behind you. Once you're in the intersection, you have to go all the way through.
4. Circular wait: Eastbound cars wait for northbound cars wait for westbound cars wait for southbound cars wait for eastbound cars...

b. A simple rule to prevent gridlock is that no car may enter an intersection until there is room for it to go all the way through to the other side.

5. Take the example scenario involving tape drives outlined on pages 218 and 219. In particular, note the first few lines on page 219: "[Process P0] may then request 5 more tape drives. Since they are unavailable, process P0 must wait. Similarly, process P2 may request an additional 6 tape drives and have to wait, resulting in a deadlock."

What if P0 doesn't request 5 more tape drives, and meanwhile P2 releases the extra one it just took, returning the system to a safe state? Then the system has crossed into unsafe territory and returned unscathed. The whole idea behind the unsafe state is merely that deadlock is possible, not that it is inescapable.

10. The cost to operate the computer system under the current scheme is 5000 jobs * $2/job + 2 deadlocks * 10 jobs/deadlock * $1/job, or about $10000 in real costs and $20 in deadlock costs, neglecting the extra cost of paying the operator to identify and terminate the deadlock.

a. The advantages of installing the deadlock avoidance system is that the entire system will run in a more trouble-free manner, allowing the operator to get more important work done, and providing more consistent and reliable turnaround times. By the calculations above, it would seem that you save some small amount of CPU time since jobs never need to be restarted due to deadlock.

b. The disadvantages of installing the deadlock avoidance system is that all jobs run 20% slower, and the amount of CPU time saved is dwarfed by the $10000*10% = $1000 worth of CPU time now spent calculating the banker's algorithm.