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()); } } |