In the finite state model of a process, a deadlocked state is, simply, a state with no outgoing transitions. A process in such a state can engage in no further actions. In FSP this deadlocked state is represented by the local process STOP. An example of a process which can lead to a deadlocked state is depicted in Figure 6.1.

The MOVE process of Figure 6.1 can engage in alternating north and south actions. However, an action sequence of north followed by north leads to a deadlocked state in which no further actions are possible. This can be seen using the Animator. We can ask the LTSA analyzer tool to find deadlock states and to produce a sample trace of how these states can be reached from the start state. By performing a breadth-first search of the LTS graph, the LTSA tool guarantees that the sample trace is the shortest trace to the deadlock state. In the example of Figure 6.1, LTSA produces the following output:

Trace to DEADLOCK:
          north
          north

In general, the deadlocks which interest us are not those that are declared explicitly in primitive processes using STOP as above, but those that arise from the parallel composition of a number of interacting primitive processes. The deadlock check that the analyzer performs for composite processes is, of course, the same as the check it performs for primitive processes since a composition is also described by an LTS graph. The check remains a search for states with no outgoing transitions.

Figure 6.1. MOVE process.

The example of Figure 6.2 is a system in which two processes, P and Q, perform the same task, that of scanning a document and printing it, by using a shared printer and shared scanner. Each process acquires both the printer and the scanner, performs the scanning and printing and then releases the scanner and printer resources. The LTS diagrams for process P and for the shared printer are given in Figures 6.3 and 6.4 respectively.

The only difference between the processes P and Q is that P acquires the printer first and Q acquires the scanner first. This system satisfies the four necessary and sufficient conditions for deadlock which were outlined in the introduction to this chapter: the scanner and printer resources are serially reused; each process holds on to either the scanner or printer while waiting to get the second resource it requires; these resources are not preempted; and the wait-for cycle is apparent from the following deadlock discovered by LTSA:

Trace to DEADLOCK:
          p.printer.get
          q.scanner.get

Figure 6.2. Printer–scanner system.

Figure 6.3. LTS for process P.

This is the situation in which the process P has the printer and is waiting for the scanner and the process Q has the scanner and is waiting for the printer. The deadlock is easily fixed in the example by ensuring that both processes ask for the printer and the scanner in the same order. (The reader should verify, using LTSA, that if the model of Figure 6.1 is modified in this way, deadlock no longer occurs.) In fact, where processes share different classes of resources, such as printers and scanners, a general-purpose strategy for avoiding deadlock is to order the resource classes; i.e. if processes use resources from different classes, all processes acquire these resources in the same order. For our example, this can be achieved by, for example, always requesting printers before scanners.

Figure 6.4. LTS for the shared printer process.

Another solution to avoiding deadlock, in this example, is to set a timeout on waiting for the second resource. If the resource has not been acquired within the timeout period then the first resource is released and the process starts afresh as shown below:

P          = (printer.get-> GETSCANNER),
     GETSCANNER = (scanner.get->copy->printer.put
                              ->scanner.put->P
                  |timeout -> printer.put->P
                  ).
     Q          = (scanner.get-> GETPRINTER),
     GETPRINTER = (printer.get->copy->printer.put
                              ->scanner.put->Q
                  |timeout -> scanner.put->Q
                  ).

This denies the second deadlock condition of incremental acquisition. The solution can be implemented in Java using a timed wait. However, it is not a good solution as both processes can continually acquire the first resource, time out and then repeat this cycle without making any progress towards accomplishing the copy action. LTSA detects this progress problem, returning the following:

Progress violation for actions:
     {p.scanner.get, p.copy, p.scanner.put,
     q.printer.get, q.copy, q.printer.put}

We deal with this class of problems in the next chapter.

The Dining Philosophers problem (Dijkstra, 1968a) is a classic concurrent-programming problem in which the deadlock is not quite so apparent as in the previous examples. We develop both the model and Java implementation. The problem is stated as follows: five philosophers share a circular table (as depicted in Figure 6.5) at which they have allotted seats. Each philosopher spends his life alternately thinking and eating. In the center of the table is a large plate of tangled 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 forks to his immediate right and left.

Figure 6.5. The Dining Philosophers table.

The resources in this system are the forks shared between the philosophers. We model a fork in the same way that we modeled the scanner and printer resources in the previous section:

FORK = (get -> put -> FORK).

To use a fork, a philosopher must first pick up (get) that fork and when finished with the fork, the philosopher puts it down (put). Each philosopher is modeled by the process:

PHIL = (sitdown->right.get->left.get
               ->eat->left.put->right.put
               ->arise->PHIL).

In other words, when a philosopher becomes hungry, he (or she) sits down at the table, picks up the fork to his right, if it is free, and then picks up the fork to his left, if it is free. The philosopher can then eat. When finished eating, the philosopher releases the forks and leaves the table. The Dining Philosophers system can now be described by the composition of five fork processes and five philosopher processes as depicted in Figure 6.6.

Figure 6.6. Dining Philosophers composite model.

The diagram of Figure 6.6 can be expressed concisely as the composite process:

||DINERS(N=5)=
        forall [i:0..N-1]
        (phil[i]:PHIL
        || {phil[i].left,phil[((i-1)+N)%N].right}::FORK).

The expression ((i-1)+N)%N is subtraction modulo N so that, for example, a fork is shared between phil[0] and phil[4]. Analysis of this system reveals the following deadlock:

Trace to DEADLOCK:
          phil.0.sitdown
          phil.0.right.get
          phil.1.sitdown

phil.1.right.get
          phil.2.sitdown
          phil.2.right.get
          phil.3.sitdown
          phil.3.right.get
          phil.4.sitdown
          phil.4.right.get

This is the situation where all the philosophers become hungry at the same time, sit down at the table and then each philosopher picks up the fork to his (or her) right. The system can make no further progress since each philosopher is waiting for a fork held by his neighbor. In other words, a wait-for cycle exists, as described in the introduction.

Dining Philosophers Implementation

It is generally not a good idea to implement an erroneous model. However, in this section, our objective is to show that, while deadlock can be detected easily in a model, it is not so apparent in the running program which corresponds to that model. In translating the Dining Philosophers model into an implementation, we must consider which processes in the model will be represented by passive objects (monitors) and which by active objects (threads), as outlined in the previous chapter. The decision is reasonably obvious; forks are the passive entities and philosophers are the active entities in this system.

The relationships between the various classes involved in the Dining Philosophers program is shown in the class diagram of Figure 6.7.

Figure 6.7. Dining Philosophers class diagram.

Example 6.1. Outline of PhilCanvas class.

class PhilCanvas extends Canvas {

  // set state of philosopher id to display state s,
  // method blocks calling thread if display is frozen
  synchronized void setPhil(int id,int s)
        throws java.lang.InterruptedException{}

  // "freeze" display
  synchronized void freeze(){}

  // "un-freeze" display
  synchronized void thaw() {}

  // set state of fork id to taken
  synchronized void setFork(int id, boolean taken){}
}

The display is implemented by the PhilCanvas class. The interface offered by this class is given in Program 6.1.

The Java implementation of the Fork monitor is listed in Program 6.2. The boolean variable, taken, encodes the state of the fork. When the fork is on the table, taken is false. When the fork has been picked up by a philosopher, taken is true.

Example 6.2. Fork monitor.

class Fork {
  private boolean taken=false;
  private PhilCanvas display;
  private int identity;

  Fork(PhilCanvas disp, int id)
    { display = disp; identity = id;}

  synchronized void put() {
    taken=false;
    display.setFork(identity,taken);
    notify();
  }

synchronized void get()
   throws java.lang.InterruptedException {
  while (taken) wait();
  taken=true;
  display.setFork(identity,taken);
 }
}

The code for the Philosopher thread is listed in Program 6.3. It follows directly from the model. The detail of the philosopher sitting down and leaving the table has been omitted; philosophers think while sitting at the table.

The time that a philosopher spends thinking and eating is controlled by the slider in the applet display (Figure 6.8).

Example 6.3. Philosopher thread class.

class Philosopher extends Thread {
  private int identity;
  private PhilCanvas view;
  private Diners controller;
  private Fork left;
  private Fork right;

  Philosopher(Diners ctr,int id,Fork l,Fork r){
    controller = ctr; view = ctr.display;
    identity = id; left = l; right = r;
  }

  public void run() {
    try {
      while (true) {
         // thinking
         view.setPhil(identity,view.THINKING);
         sleep(controller.sleepTime());
         // hungry
         view.setPhil(identity,view.HUNGRY);
         right.get();
         // gotright fork
         view.setPhil(identity,view.GOTRIGHT);
         sleep(500);
         left.get();

// eating
         view.setPhil(identity,view.EATING);
         sleep(controller.eatTime());
         right.put();
         left.put();
      }
    } catch (java.lang.InterruptedException e){}
  }
}

Figure 6.8. Dining Philosophers applet – executing.

The code to create the Philosopher threads and Fork monitors is:

for (int i =0; i<N; ++i)
  fork[i] = new Fork(display,i);
for (int i =0; i<N; ++i){
  phil[i] =
    new Philosopher(this,i,fork[(i-1+N)%N],fork[i]);
  phil[i].start();
}

Figure 6.8 depicts the Dining Philosophers applet running. The applet may run for a long time before deadlock occurs. To ensure deadlock occurs eventually, the slider control may be moved to the left. This reduces the time philosophers spend thinking and eating and this "speedup" increases the probability of deadlock occurring. Figure 6.9 depicts the applet when deadlock occurs. It is clear that each philosopher is holding on to the fork on his right.

Figure 6.9. Dining Philosophers applet – deadlocked.

FORK = (get -> put -> FORK).

     PHIL(I=0)
         = (when (I%2==0) sitdown
              ->left.get->right.get
              ->eat->left.put->right.put->arise->PHIL
           |when (I%2==1) sitdown
              ->right.get->left.get
              ->eat->left.put->right.put->arise->PHIL
           ).

     ||DINERS(N=5)=
        forall [i:0..N-1]
        (phil[i]:PHIL(i)
        || {phil[i].left,phil[((i-1)+N)%N].right}::FORK).

In this chapter, we have seen that deadlock is a system state in which all of the processes in a system are blocked and the system can consequently make no further progress. Deadlock is modeled by a state with no outgoing transitions. Deadlock analysis of a model involves performing an exhaustive search of the labeled transition system for such states. If none are found, the model is shown to be deadlock-free.

We identified four necessary and sufficient conditions for deadlock. Strategies for dealing with deadlock involve ensuring that at least one of these conditions does not hold. The conditions are:

The Dining Philosophers problem was used to illustrate the point that while deadlocks are easily found in models, they are not so readily apparent in programs. Indeed, the reason for modeling is to remove problems such as deadlock during design.

The Dining Philosophers problem has been widely used to compare both process synchronization primitives and strategies for dealing with deadlock. The problem was introduced by Dijkstra (1968a) in a paper which shows how to use semaphores to solve a variety of synchronization problems. We have used asymmetry to avoid deadlock. A second way to avoid deadlock is to allow at most four philosophers to sit down together at the table. Another approach is to ensure that the act of picking up both forks is atomic. Chandy and Misra (1984) proposed a fully distributed solution which passes tokens between philosophers. All of these approaches to the Dining Philosophers problem are deterministic: each process takes a predetermined set of actions. Lehman and Rabin (1981) showed that any deterministic solution has to be asymmetric or use an outside agent (such as the butler in exercise 6.2). They also presented a probabilistic solution to the problem which is perfectly symmetric. Philosophers toss a coin to determine the order of picking up forks and defer to a neighbor if it has used the fork less recently.