Dining Philosophers

Dining Philosophers is one of those classical problems to understand (and resolve) deadlocks in software. Lets look at examples were we cause deadlocks, come up with a solution to avoid deadlocks and finally come up with a solution to avoid starvation. Also, here is a great link describing many more ways to solving the Dining Philosophers problem.

Here is a simple class to represent a fork on the table.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Fork {
 int forkid;
 Semaphore mutex=new Semaphore(1, true);
 public Fork(int forkid) {
    this.forkid = forkid;
  }
  public String toString() {
    return String.valueOf(forkid);
  }
  public void pickUpFork() throws InterruptedException {
    mutex.acquire();
  }
  public void putDownFork() {
    mutex.release();
  }
}

Deadlock Philosopher
This guy blindly picks up the left fork and then the right fork. We create a circular wait condition. Imagine scenario where all philosophers have a left fork and waiting for the right fork.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class DeadlockPhilosopher implements Philosopher {
 String philosopher;
 Fork left;
 Fork right;
 public DeadlockPhilosopher(String philosopher, Fork left, Fork right) {
  this.philosopher = philosopher;
  this.left = left;
  this.right = right;
 }
 @Override
 public void run() {  
  while( true ) {   
   try {    
    left.pickUpFork();
    System.out.println(philosopher + " picked up " + left);
    Thread.sleep(5000); // this will just cause the deadlock quicker!  
    right.pickUpFork();
    System.out.println(philosopher + " picked up " + right);
    System.out.println(philosopher + " is eating...");
    right.putDownFork();
    System.out.println(philosopher + " put down " + right);
    left.putDownFork();
    System.out.println(philosopher + " put down " + left);   
    System.out.println(philosopher + " is thinking...");
    Thread.sleep(5000); // think!   
   } catch (InterruptedException e1) {
    // TODO Auto-generated catch block
    e1.printStackTrace();
   }   
  }
 }
 @Override
 public String getPhilosopher() {
  return philosopher;
 }
}

2. Sensible Philosopher (No deadlocks)
Ok how do we break deadlocks? We get rid of the circular wait condition. We give forks (or resources) numbers. We make sure that philosophers access lowered numbered resources over higher numbered resources. In this solution all philosophers are right handed except E who is left handed. That’s enough to break the circular wait. Another solution could also be to make two adjacent philosophers request forks in different orders (i.e. make them right handed and left handed). The 5th and the 1st philosopher will be same handed however other philosopher being different handed, the circular wait will be broken.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

class OrderlyPhilosopher implements Philosopher {
 
  String philosopher;
  Fork left;
  Fork right;
 
  public OrderlyPhilosopher(String philosopher, Fork left, Fork right) {
    this.philosopher = philosopher;
    this.left = left;
    this.right = right;
  }
 
  @Override
  public void run() {
 
    while( true ) {
 
      try {
 
        Fork pickUpFirst = null;
        Fork pickUpSecond = null;
 
        if ( left.forkid < right.forkid ) {
          pickUpFirst = left;
          pickUpSecond = right;
        } else {
          pickUpFirst = right;
          pickUpSecond = left;
        }
 
        pickUpFirst.pickUpFork();
        System.out.println(philosopher + " picked up " + pickUpFirst);
        Thread.sleep(5000);  // this will just cause the deadlock quicker!
        pickUpSecond.pickUpFork();
        System.out.println(philosopher + " picked up " + pickUpSecond);
        System.out.println(philosopher + " is eating...");
        pickUpSecond.putDownFork();
        System.out.println(philosopher + " put down " + pickUpSecond);
        pickUpFirst.putDownFork();
        System.out.println(philosopher + " put down " + pickUpFirst);      
        System.out.println(philosopher + " is thinking...");
        Thread.sleep(5000);  // think!
 
      } catch (InterruptedException e1) {
        // TODO Auto-generated catch block
        e1.printStackTrace();
      }
 
    }
 
  }
 
  @Override
  public String getPhilosopher() {
    return philosopher;
  }
}

3. Fair Philosopher (No deadlocks, No Starvation, Average Performance)
Ok, so in all these cases there are chances that starvation might occur, i.e. some philosopher might not get a chance to eat as often. How do we tackle this? Well instead of having semaphores on the forks, why not have semaphores on philosophers themselves Check if both forks are empty at any point of time, if not wait, else use. Make sure neighbors are not eating. Look at Solution #7: Preventing Starvation A Little Better to know what i am talking about.

1. Ok, we know in order to avoid spurious wake ups we should put wait() in a while loop but what happens when you wake a philosoper up and its a spurious wake up? He waits() again and goes back to end of waiting list. That’s not good, instead lets 1.) make sure we don’t have spurious wake ups and 2.) Output an error (and return from function) if he wakes up but cannot eat so that we know we are causing spurious wakeup’s in the code.

2. So you MUST wait if people are waiting (even if you can eat). You will only be awakened, by a thread if you can eat. So when you are awakened, as a safety measure check if you can eat, output error message (and return) if you can’t and go ahead and eat!

3. Check most waiting thread when a philosopher finished eating or starts eating. In both scenarios, there is a possibility of the most waiting thread to start eating. Remember, until the most waiting thread cant eat, nobody behind him can eat too.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

class Conductor {
 
  Philosopher philosophers[];
  List<String> eating;
  List<String> waiting;
  Lock lock=new ReentrantLock(true);
  Condition con=lock.newCondition();
 
  public Conductor(Philosopher philosophers[]) {
    this.philosophers = philosophers;
    this.eating = new ArrayList<String>();
    this.waiting = new ArrayList<String>();
  }
 
  public void eat(String philisopher) throws InterruptedException {
    if ( !validPhilosopher(philisopher) )
      return;
    //System.out.println(philisopher + " wants to eat...");
    //System.out.println(eating.size() + " people eating...");
    lock.lock();
    try {
      if ( waiting.size() > 0 || eating.contains(philisopher) || eating.contains(getLeftNeighbhor(philisopher)) || eating.contains(getRightNeighbhor(philisopher)) ) {
        System.out.println(philisopher + " blocked...");
        waiting.add(philisopher);
        con.await();
        //System.out.println(philisopher + " awakened...");
        waiting.remove(philisopher);
 
        if ( eating.contains(philisopher) || eating.contains(getLeftNeighbhor(philisopher)) || eating.contains(getRightNeighbhor(philisopher)) ) {
          System.out.println(philisopher + " awakened however he cant eat! Problem!!!");
          return;
        } 
      }
      System.out.println(philisopher + " eating...");
      eating.add(philisopher);
 
      // CHECK for WAITING threads Q, and signal last waiting thread, if you can handle it!
      if ( waiting.size() > 0 ) {
        String waitingPhil = waiting.get(0);
        if ( !eating.contains(waitingPhil) && !eating.contains(getLeftNeighbhor(waitingPhil)) && !eating.contains(getRightNeighbhor(waitingPhil)) ) {
          //System.out.println(philisopher + " eat signalling awake to " + waitingPhil);
          con.signal();
        }
      }
    } catch ( Exception e ) {
 
    } finally {
      lock.unlock();
    }
  }
 
  public void finisheat(String philisopher) throws InterruptedException {
    lock.lock();
    if ( !validPhilosopher(philisopher) || !eating.contains(philisopher) )
      return;
    eating.remove(philisopher);
 
    // CHECK for WAITING threads Q, and signal last waiting thread, if you can handle it!
    if ( waiting.size() > 0 ) {
      String waitingPhil = waiting.get(0);
      if ( !eating.contains(waitingPhil) && !eating.contains(getLeftNeighbhor(waitingPhil)) && !eating.contains(getRightNeighbhor(waitingPhil)) ) {
        //System.out.println(philisopher + " finisheat signalling awake to " + waitingPhil);
        con.signal();
      }
    }
    lock.unlock();
  }
 
  public boolean validPhilosopher(String philisopher) {
    for ( int i = 0 ; i < philosophers.length ; i++ )
      if ( philosophers[i].getPhilosopher().equals(philisopher) )
        return true;
    return false;
  }
 
  public String getLeftNeighbhor(String philisopher) {
    int i = 0;
    for ( ; i < philosophers.length ; i++ ) {
      if ( philosophers[i].getPhilosopher().equals(philisopher) )
        break;
    }
 
    if ( i == 0 )
      return philosophers[philosophers.length-1].getPhilosopher();
    else
      return philosophers[i-1].getPhilosopher();    
  }
 
  public String getRightNeighbhor(String philisopher) {
    int i = 0;
    for ( ; i < philosophers.length ; i++ ) {
      if ( philosophers[i].getPhilosopher().equals(philisopher) )
        break;
    }
 
    if ( i == philosophers.length-1 )
      return philosophers[0].getPhilosopher();
    else
      return philosophers[i+1].getPhilosopher();      
  }
}
 
class ConductorPhilosopher implements Philosopher {
  String philosopher;
  Conductor c;
  public ConductorPhilosopher(String philosopher, Conductor c) {
    this.philosopher = philosopher;
    this.c = c;
  }
 
  @Override
  public String getPhilosopher() {
    return philosopher;
  }
 
  @Override
  public void run() {
    try {  
      while ( true ) {
        //System.out.println(philosopher + " wants to eat...");
        c.eat(philosopher);
        //System.out.println(philosopher + " eating...");
        Thread.sleep(new Random().nextInt(2000));
        c.finisheat(philosopher);
        Thread.sleep(new Random().nextInt(2000));
        //System.out.println(philosopher + " thinking...");
      }
    } catch (InterruptedException e) {
      // TODO Auto-generated catch block
      e.printStackTrace();
    }    
  }
}

Here is the philosophers table and main method for running the code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

class PhilosphersTable {
 
  ExecutorService executorService;
  Philosopher philosophers[];
 
  public PhilosphersTable(Philosopher philosophers[]) {    
    this.philosophers = philosophers;
    this.executorService = Executors.newFixedThreadPool(5);
 
    for ( int i = 0 ; i < philosophers.length ; i++ )
      executorService.submit(philosophers[i]);
  }
 
  public static Philosopher[] getConductorPhilosophers() {
 
    ConductorPhilosopher philosophers[]=new ConductorPhilosopher[5];
    Conductor conductor=new Conductor(philosophers);
 
    philosophers[0] = new ConductorPhilosopher("A", conductor);
    philosophers[1] = new ConductorPhilosopher("B", conductor);
    philosophers[2] = new ConductorPhilosopher("C", conductor);
    philosophers[3] = new ConductorPhilosopher("D", conductor);
    philosophers[4] = new ConductorPhilosopher("E", conductor);
 
    return philosophers;
 
  }
 
  public static Philosopher[] getOrderlyPhilosophers() {
 
    Fork forks[]=new Fork[5];
    forks[0]=new Fork(1);
    forks[1]=new Fork(2);
    forks[2]=new Fork(3);
    forks[3]=new Fork(4);
    forks[4]=new Fork(5);
 
    OrderlyPhilosopher philosophers[]=new OrderlyPhilosopher[5];    
    philosophers[0] = new OrderlyPhilosopher("A", forks[0], forks[4]);
    philosophers[1] = new OrderlyPhilosopher("B", forks[1], forks[0]);
    philosophers[2] = new OrderlyPhilosopher("C", forks[2], forks[1]);
    philosophers[3] = new OrderlyPhilosopher("D", forks[3], forks[2]);
    philosophers[4] = new OrderlyPhilosopher("E", forks[4], forks[3]);
 
    return philosophers;
 
  }
 
  public static Philosopher[] getDeadlockPhilosophers() {
 
    Fork forks[]=new Fork[5];
    forks[0]=new Fork(1);
    forks[1]=new Fork(2);
    forks[2]=new Fork(3);
    forks[3]=new Fork(4);
    forks[4]=new Fork(5);
 
    DeadlockPhilosopher philosophers[]=new DeadlockPhilosopher[5];    
    philosophers[0] = new DeadlockPhilosopher("A", forks[0], forks[4]);
    philosophers[1] = new DeadlockPhilosopher("B", forks[1], forks[0]);
    philosophers[2] = new DeadlockPhilosopher("C", forks[2], forks[1]);
    philosophers[3] = new DeadlockPhilosopher("D", forks[3], forks[2]);
    philosophers[4] = new DeadlockPhilosopher("E", forks[4], forks[3]);
 
    return philosophers;
 
  }
 
}
 
public class DiningPhilosphers {
 
  public static void main(String args[]) {
 
    //PhilosphersTable philosopherstable=new PhilosphersTable(PhilosphersTable.getDeadlockPhilosophers());
    //PhilosphersTable philosopherstable=new PhilosphersTable(PhilosphersTable.getOrderlyPhilosophers());
    PhilosphersTable philosopherstable=new PhilosphersTable(PhilosphersTable.getConductorPhilosophers());
  }
 
}

softwareeveryday

[Programming Problem] Subsets II
Read More
[Programming Problem] Flatten Binary Tree to Linked List
Read More
[Programming Problem] Largest Number
Read More