Deadlock Example - 5 Dining Philosophers

Java Tutorials - Herong's Tutorial Examples

∟Deadlock Example - 5 Dining Philosophers

This section provides a Java program that simulates the deadlock example - 5 Dining Philosophers.

The story of 5 dining philosophers is the most interesting illustration of the deadlock problem. Here is the version of the story from the "The Java Tutorial" by Sun Microsystems.

"Five philosophers are sitting at a round table. In front of each philosopher is a bowl of rice. Between each pair of philosophers is one chopstick. Before an individual philosopher can take a bite of rice, he must have two chopsticks, one taken from the left, and one taken from the right. The philosophers must find some way to share chopsticks such that they all get to eat. "

Deadlock will occur in this story, if all philosophers are taking the chopstick from the left side at the same time, and no one is willing to put down the chopstick until he gets the chopstick on the right side.

Here is a Java program to simulate the story:

/* DinerThread.java
 * Copyright (c) HerongYang.com. All Rights Reserved.
 */
import java.util.*;
public class DinerThread extends Thread {
   public static final int numberOfThreads = 5;
   public static Object[] listOfLocks = new Object[numberOfThreads];
   public static char[] dinerTable = new char[4*numberOfThreads];
   public static char[] lockedDiner = new char[4*numberOfThreads];
   public static Random randomGenerator = new Random();
   public static int unitOfTime = 500;
   private int threadIndex;
   public static void main(String[] a) {
      for (int i=0; i<numberOfThreads; i++) listOfLocks[i] =
         new Object();
      for (int i=0; i<numberOfThreads; i++) {
         dinerTable[4*i] = '|';
         dinerTable[4*i+1] = ' ';
         dinerTable[4*i+2] = '-';
         dinerTable[4*i+3] = ' ';
         lockedDiner[4*i] = ' ';
         lockedDiner[4*i+1] = '|';
         lockedDiner[4*i+2] = '=';
         lockedDiner[4*i+3] = ' ';
      }
      for (int i=0; i<numberOfThreads; i++) {
         Thread t = new DinerThread(i);
         t.setDaemon(true);
         t.start();
      }
      String lockedString = new String(lockedDiner);
      System.out.println("The diner table:");
      long step = 0;
      while (true) {
         step++;
         System.out.println((new String(dinerTable))+"   "+step);
         if (lockedString.equals(new String(dinerTable)))
            break;
         try {
            Thread.sleep(unitOfTime);
         } catch (InterruptedException e) {
            System.out.println("Interrupted.");
         }
      }
      System.out.println("The diner is locked.");
   }
   public DinerThread(int i) {
      threadIndex = i;
   }
   public void run() {
      while (!isInterrupted()) {
         try {
            sleep(unitOfTime*randomGenerator.nextInt(6));
         } catch (InterruptedException e) {
            break;
         }
         // Try to get the chopstick on the left
         Object leftLock = listOfLocks[threadIndex];
         synchronized (leftLock) {
            int i = 4*threadIndex;
            dinerTable[i] = ' ';
            dinerTable[i+1] = '|';
            dinerTable[i+2] = '=';
            try {
               sleep(unitOfTime*1);
            } catch (InterruptedException e) {
               break;
            }
            // Try to get the chopstick on the right
            Object rightLock =
               listOfLocks[(threadIndex+1)%numberOfThreads];
            synchronized (rightLock) {
               dinerTable[i+2] = 'o';
               dinerTable[i+3] = '|';
               dinerTable[(i+4)%(4*numberOfThreads)] = ' ';
               try {
                  sleep(unitOfTime*1);
               } catch (InterruptedException e) {
                  break;
               }
               dinerTable[i] = '|';
               dinerTable[i+1] = ' ';
               dinerTable[i+2] = '-';
               dinerTable[i+3] = ' ';
               dinerTable[(i+4)%(4*numberOfThreads)] = '|';
            }
         }
      }
   }
}

In the program, the diner table is represented by an array of characters. '|' represents a chopstick, '-', '=' and 'o' represent a philosopher with no chopstick, one chopstick and two chopsticks respectively.

There are 5 threads representing the 5 philosophers. Each of them will pause for some time before trying to synchronize with the lock that is associated with the chopstick on the left side. Once passed the first synchronization, the thread will take the chopstick on the left side, and continue to try to synchronize with the lock that is associated with the chopstick on the right side. Once passed the second synchronization, the thread will take the chopstick on the right side, and hold both chopsticks for a moment. The threads will then put back both chopsticks and release both locks.

Execute the program several times. You will see that it behaves differently each time. But soon or later, the diner table will be locked with each thread holding a lock that is needed by the thread on the left side, and waiting for a lock that is held by the thread on the right side.

One of my executions gave the following output:

The diner table:
| - | - | - | - | -    1
| -  |=  |= | - | -    2
| -  |=  |o|  - | -    3
 |= | - | -  |= | -    4
 |o|  - | -  |o|  -    5
| -  |= | - | -  |=    6
  -  |o|  -  |=  |o|   7
| - | -  |=  |o|  -    8
| -  |=  |o|  - | -    9
 |=  |o|  - | - | -    10
 |o|  - | - | - | -    11
| - | - | - | -  |=    12
 |= | - | -  |=  |=    13
 |o|  -  |=  |=  |=    14
| - | -  |=  |o|  -    15
| -  |=  |o|  -  |=    16
  -  |o|  - | -  |o|   17
| - | -  |= | - | -    18
 |= | -  |o|  - | -    19
 |o|  - | -  |= | -    20
| -  |=  |=  |o|  -    21
| -  |=  |= | -  |=    22
  -  |=  |o|  -  |o|   23
 |= | - | - | - | -    24
 |=  |= | -  |= | -    25
 |=  |o|  -  |o|  -    26
| - | - | - | - | -    27
| -  |=  |= | -  |=    28
  -  |=  |o|  -  |o|   29
| -  |o|  - | - | -    30
| - | -  |=  |= | -    31
 |=  |=  |=  |o|  -    32
 |=  |=  |o|  -  |=    33
 |=  |o|  - | -  |=    34
 |o|  -  |= | -  |=    35
  -  |=  |o|  -  |o|   36
 |=  |o|  -  |= | -    37
 |o|  - | -  |=  |=    38
  - | - | -  |=  |o|   39
 |= | -  |=  |o|  -    40
 |=  |=  |o|  - | -    41
 |=  |o|  - | - | -    42
 |o|  - | - | - | -    43
| -  |= | - | - | -    44
 |=  |=  |= | -  |=    45
 |=  |=  |=  |=  |=    46
The diner is locked.