Consider the following situation: Suppose that two processes (A and B) are running on the same machine, and both processes require the use of the local printer and tape drive. Process A may have been granted access to the machine's printer but be waiting for the tape drive, while process B has access to the tape drive but is waiting for the printer [Brookshear 1997]. Such a condition is known as deadlock. Since both processes hold a resource the other process needs, the processes will wait indefinitely for the resources to be released and neither will finish executing.

In order for deadlock to be possible, the following three conditions must be present in the computer [Dichev 2000]:

1.  Mutual exclusion:
only one process may use a resource at a time

2.  Hold-and-wait:
a process may hold allocated resources while awaiting assignment of others

3.  No preemption:
no resource can be forcibly removed from a process holding it

In the example given above, the printer and tape drive represent mutually exclusive resources. Since these resources cannot be space-multiplexed, processes using them are granted complete control of the resources until they are finished. If the operating system allows process A and process B to hold-and-wait, and it does not forcibly remove any resources from these processes, then deadlock is possible. Note, however, that the three conditions do not guarantee deadlock. They are necessary, but not sufficient, for the occurrence of deadlock.

One solution to this problem is to allow deadlock to occur, detect it, and then correct the problem. Usually this correction involves forcibly deallocating resources from deadlocked processes. Notice that this solution to deadlock involves removing the third condition, that is, the operation system now allows for preemption of resources whenever deadlock occurs. Another solution to the problem of deadlock is to remove the second condition by requiring processes to request all of their resources at the same time. Yet another solution is to remove the first condition by converting nonshareable resources into shareable ones. Brookshear [1997] illustrates:

"Suppose the resource in question is a printer and a variety of processes require its use. Each time a process requests the printer, the operating system grants the request. However, instead of connecting the process to the printer's device driver, the operating system connects it to a device driver that stores the information to be printed on a disk rather than sending it to the printer. Thus each process, thinking it has access to the printer, executes in its normal way. Later, when the printer is available, the operating system can transfer the data from the disk to the printer. In this manner the operating system has made the nonshareable resource appear shareable by creating the illusion of more than one printer."

A famous illustration of the problem of deadlock was given by the Edgar Dijkstra in 1968. The problem, known as the Dining Philosophers, is illustrated in the applet below.

Five philosophers sit around a circular table. Each philosopher spends his life alternatively thinking and eating. In the center of the table is a large plate of spaghetti. A philosopher needs two forks to eat a helping of spaghetti. Unfortunately, as philosophy is not as well paid as computing, the philosophers can only afford five forks. One fork is placed between each pair of philosophers and they agree that each will only use the fork to his immediate right and left [Magee and Kramer 1999].

The slider in the applet below controls the amount of time that a philosopher spends eating and thinking. Philosophers are depicted in yellow when they are thinking, blue when hungry and green when eating. Use the "Freeze" and "Restart" buttons to control the simulation. Try moving the slider to the far left and note what happens to the simulation.

Thinking Hungry Eating
Copyright notice

After a few seconds, each of the philosophers becomes hungry and grabs a single fork. Since no more forks are available and two forks are required for eating, the philosophers all wait for another fork and deadlock occurs. Note that the Dining Philosophers problem meets all three of the conditions presented earlier. Only one philosopher can use a fork at a time so the fork resource is mutually exclusive. Hungry philosophers with only one fork will hold this resource until another fork becomes available, thus resulting in hold-and-wait. And since the philosophers are peaceful and courteous, no one is willing to forcibly remove a fork from his neighbor.

To solve the deadlock problem, a second version of the applet is presented below. This version avoids the possibility of deadlock by making even numbered philosophers pick up the forks in a different order from the rest. That is, left first rather than right first [Magee and Kramer 1999]. Notice that this solution differs from the other approaches presented. Rather than attacking one of the necessary conditions for deadlock, the solution imposes a particular resource allocation order which makes it impossible for all five philosophers to be holding a single fork.

Thinking Hungry Eating
Copyright notice

References