{"id":813,"date":"2013-02-13T10:32:20","date_gmt":"2013-02-13T10:32:20","guid":{"rendered":"http:\/\/www.softwareeverydayblog.com\/?p=813"},"modified":"2013-02-14T05:12:22","modified_gmt":"2013-02-14T05:12:22","slug":"dining-philosphers","status":"publish","type":"post","link":"https:\/\/www.softwareeverydayblog.com\/?p=813","title":{"rendered":"Dining Philosophers"},"content":{"rendered":"

Dining Philosophers<\/a> 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<\/a> describing many more ways to solving the Dining Philosophers problem.<\/p>\n

Here is a simple class to represent a fork on the table.<\/p>\n

\r\nclass Fork {\r\n int forkid;\r\n Semaphore mutex=new Semaphore(1, true);\r\n public Fork(int forkid) {\r\n    this.forkid = forkid;\r\n  }\r\n  public String toString() {\r\n    return String.valueOf(forkid);\r\n  }\r\n  public void pickUpFork() throws InterruptedException {\r\n    mutex.acquire();\r\n  }\r\n  public void putDownFork() {\r\n    mutex.release();\r\n  }\r\n}\r\n<\/pre>\n
Deadlock Philosopher<\/strong>
\nThis 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.<\/p>\n
\r\nclass DeadlockPhilosopher implements Philosopher {\r\n String philosopher;\r\n Fork left;\r\n Fork right;\r\n public DeadlockPhilosopher(String philosopher, Fork left, Fork right) {\r\n  this.philosopher = philosopher;\r\n  this.left = left;\r\n  this.right = right;\r\n }\r\n @Override\r\n public void run() {  \r\n  while( true ) {   \r\n   try {    \r\n    left.pickUpFork();\r\n    System.out.println(philosopher + \" picked up \" + left);\r\n    Thread.sleep(5000); \/\/ this will just cause the deadlock quicker!  \r\n    right.pickUpFork();\r\n    System.out.println(philosopher + \" picked up \" + right);\r\n    System.out.println(philosopher + \" is eating...\");\r\n    right.putDownFork();\r\n    System.out.println(philosopher + \" put down \" + right);\r\n    left.putDownFork();\r\n    System.out.println(philosopher + \" put down \" + left);   \r\n    System.out.println(philosopher + \" is thinking...\");\r\n    Thread.sleep(5000); \/\/ think!   \r\n   } catch (InterruptedException e1) {\r\n    \/\/ TODO Auto-generated catch block\r\n    e1.printStackTrace();\r\n   }   \r\n  }\r\n }\r\n @Override\r\n public String getPhilosopher() {\r\n  return philosopher;\r\n }\r\n}\r\n<\/pre>\n
2. Sensible Philosopher (No deadlocks)<\/strong>
\nOk 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.<\/p>\n
\r\nclass OrderlyPhilosopher implements Philosopher {\r\n\r\n  String philosopher;\r\n  Fork left;\r\n  Fork right;\r\n  \r\n  public OrderlyPhilosopher(String philosopher, Fork left, Fork right) {\r\n    this.philosopher = philosopher;\r\n    this.left = left;\r\n    this.right = right;\r\n  }\r\n  \r\n  @Override\r\n  public void run() {\r\n    \r\n    while( true ) {\r\n      \r\n      try {\r\n        \r\n        Fork pickUpFirst = null;\r\n        Fork pickUpSecond = null;\r\n        \r\n        if ( left.forkid < right.forkid ) {\r\n          pickUpFirst = left;\r\n          pickUpSecond = right;\r\n        } else {\r\n          pickUpFirst = right;\r\n          pickUpSecond = left;\r\n        }\r\n          \r\n        pickUpFirst.pickUpFork();\r\n        System.out.println(philosopher + \" picked up \" + pickUpFirst);\r\n        Thread.sleep(5000);  \/\/ this will just cause the deadlock quicker!\r\n        pickUpSecond.pickUpFork();\r\n        System.out.println(philosopher + \" picked up \" + pickUpSecond);\r\n        System.out.println(philosopher + \" is eating...\");\r\n        pickUpSecond.putDownFork();\r\n        System.out.println(philosopher + \" put down \" + pickUpSecond);\r\n        pickUpFirst.putDownFork();\r\n        System.out.println(philosopher + \" put down \" + pickUpFirst);      \r\n        System.out.println(philosopher + \" is thinking...\");\r\n        Thread.sleep(5000);  \/\/ think!\r\n      \r\n      } catch (InterruptedException e1) {\r\n        \/\/ TODO Auto-generated catch block\r\n        e1.printStackTrace();\r\n      }\r\n      \r\n    }\r\n    \r\n  }\r\n  \r\n  @Override\r\n  public String getPhilosopher() {\r\n    return philosopher;\r\n  }\r\n}\r\n<\/pre>\n
3. Fair Philosopher (No deadlocks, No Starvation, Average Performance)<\/strong>
\nOk, 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<\/a> to know what i am talking about.<\/p>\n
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.<\/p>\n
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!<\/p>\n
 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.<\/p>\n
\r\nclass Conductor {\r\n  \r\n  Philosopher philosophers[];\r\n  List eating;\r\n  List waiting;\r\n  Lock lock=new ReentrantLock(true);\r\n  Condition con=lock.newCondition();\r\n  \r\n  public Conductor(Philosopher philosophers[]) {\r\n    this.philosophers = philosophers;\r\n    this.eating = new ArrayList();\r\n    this.waiting = new ArrayList();\r\n  }\r\n  \r\n  public void eat(String philisopher) throws InterruptedException {\r\n    if ( !validPhilosopher(philisopher) )\r\n      return;\r\n    \/\/System.out.println(philisopher + \" wants to eat...\");\r\n    \/\/System.out.println(eating.size() + \" people eating...\");\r\n    lock.lock();\r\n    try {\r\n      if ( waiting.size() > 0 || eating.contains(philisopher) || eating.contains(getLeftNeighbhor(philisopher)) || eating.contains(getRightNeighbhor(philisopher)) ) {\r\n        System.out.println(philisopher + \" blocked...\");\r\n        waiting.add(philisopher);\r\n        con.await();\r\n        \/\/System.out.println(philisopher + \" awakened...\");\r\n        waiting.remove(philisopher);\r\n        \r\n        if ( eating.contains(philisopher) || eating.contains(getLeftNeighbhor(philisopher)) || eating.contains(getRightNeighbhor(philisopher)) ) {\r\n          System.out.println(philisopher + \" awakened however he cant eat! Problem!!!\");\r\n          return;\r\n        } \r\n      }\r\n      System.out.println(philisopher + \" eating...\");\r\n      eating.add(philisopher);\r\n      \r\n      \/\/ CHECK for WAITING threads Q, and signal last waiting thread, if you can handle it!\r\n      if ( waiting.size() > 0 ) {\r\n        String waitingPhil = waiting.get(0);\r\n        if ( !eating.contains(waitingPhil) && !eating.contains(getLeftNeighbhor(waitingPhil)) && !eating.contains(getRightNeighbhor(waitingPhil)) ) {\r\n          \/\/System.out.println(philisopher + \" eat signalling awake to \" + waitingPhil);\r\n          con.signal();\r\n        }\r\n      }\r\n    } catch ( Exception e ) {\r\n      \r\n    } finally {\r\n      lock.unlock();\r\n    }\r\n  }\r\n  \r\n  public void finisheat(String philisopher) throws InterruptedException {\r\n    lock.lock();\r\n    if ( !validPhilosopher(philisopher) || !eating.contains(philisopher) )\r\n      return;\r\n    eating.remove(philisopher);\r\n    \r\n    \/\/ CHECK for WAITING threads Q, and signal last waiting thread, if you can handle it!\r\n    if ( waiting.size() > 0 ) {\r\n      String waitingPhil = waiting.get(0);\r\n      if ( !eating.contains(waitingPhil) && !eating.contains(getLeftNeighbhor(waitingPhil)) && !eating.contains(getRightNeighbhor(waitingPhil)) ) {\r\n        \/\/System.out.println(philisopher + \" finisheat signalling awake to \" + waitingPhil);\r\n        con.signal();\r\n      }\r\n    }\r\n    lock.unlock();\r\n  }\r\n    \r\n  public boolean validPhilosopher(String philisopher) {\r\n    for ( int i = 0 ; i < philosophers.length ; i++ )\r\n      if ( philosophers[i].getPhilosopher().equals(philisopher) )\r\n        return true;\r\n    return false;\r\n  }\r\n  \r\n  public String getLeftNeighbhor(String philisopher) {\r\n    int i = 0;\r\n    for ( ; i < philosophers.length ; i++ ) {\r\n      if ( philosophers[i].getPhilosopher().equals(philisopher) )\r\n        break;\r\n    }\r\n    \r\n    if ( i == 0 )\r\n      return philosophers[philosophers.length-1].getPhilosopher();\r\n    else\r\n      return philosophers[i-1].getPhilosopher();    \r\n  }\r\n  \r\n  public String getRightNeighbhor(String philisopher) {\r\n    int i = 0;\r\n    for ( ; i < philosophers.length ; i++ ) {\r\n      if ( philosophers[i].getPhilosopher().equals(philisopher) )\r\n        break;\r\n    }\r\n    \r\n    if ( i == philosophers.length-1 )\r\n      return philosophers[0].getPhilosopher();\r\n    else\r\n      return philosophers[i+1].getPhilosopher();      \r\n  }\r\n}\r\n\r\nclass ConductorPhilosopher implements Philosopher {\r\n  String philosopher;\r\n  Conductor c;\r\n  public ConductorPhilosopher(String philosopher, Conductor c) {\r\n    this.philosopher = philosopher;\r\n    this.c = c;\r\n  }\r\n  \r\n  @Override\r\n  public String getPhilosopher() {\r\n    return philosopher;\r\n  }\r\n\r\n  @Override\r\n  public void run() {\r\n    try {  \r\n      while ( true ) {\r\n        \/\/System.out.println(philosopher + \" wants to eat...\");\r\n        c.eat(philosopher);\r\n        \/\/System.out.println(philosopher + \" eating...\");\r\n        Thread.sleep(new Random().nextInt(2000));\r\n        c.finisheat(philosopher);\r\n        Thread.sleep(new Random().nextInt(2000));\r\n        \/\/System.out.println(philosopher + \" thinking...\");\r\n      }\r\n    } catch (InterruptedException e) {\r\n      \/\/ TODO Auto-generated catch block\r\n      e.printStackTrace();\r\n    }    \r\n  }\r\n}\r\n<\/pre>\n
Here is the philosophers table and main method for running the code.<\/p>\n
\r\nclass PhilosphersTable {\r\n  \r\n  ExecutorService executorService;\r\n  Philosopher philosophers[];\r\n  \r\n  public PhilosphersTable(Philosopher philosophers[]) {    \r\n    this.philosophers = philosophers;\r\n    this.executorService = Executors.newFixedThreadPool(5);\r\n    \r\n    for ( int i = 0 ; i < philosophers.length ; i++ )\r\n      executorService.submit(philosophers[i]);\r\n  }\r\n  \r\n  public static Philosopher[] getConductorPhilosophers() {\r\n    \r\n    ConductorPhilosopher philosophers[]=new ConductorPhilosopher[5];\r\n    Conductor conductor=new Conductor(philosophers);\r\n    \r\n    philosophers[0] = new ConductorPhilosopher(\"A\", conductor);\r\n    philosophers[1] = new ConductorPhilosopher(\"B\", conductor);\r\n    philosophers[2] = new ConductorPhilosopher(\"C\", conductor);\r\n    philosophers[3] = new ConductorPhilosopher(\"D\", conductor);\r\n    philosophers[4] = new ConductorPhilosopher(\"E\", conductor);\r\n    \r\n    return philosophers;\r\n    \r\n  }\r\n  \r\n  public static Philosopher[] getOrderlyPhilosophers() {\r\n    \r\n    Fork forks[]=new Fork[5];\r\n    forks[0]=new Fork(1);\r\n    forks[1]=new Fork(2);\r\n    forks[2]=new Fork(3);\r\n    forks[3]=new Fork(4);\r\n    forks[4]=new Fork(5);\r\n    \r\n    OrderlyPhilosopher philosophers[]=new OrderlyPhilosopher[5];    \r\n    philosophers[0] = new OrderlyPhilosopher(\"A\", forks[0], forks[4]);\r\n    philosophers[1] = new OrderlyPhilosopher(\"B\", forks[1], forks[0]);\r\n    philosophers[2] = new OrderlyPhilosopher(\"C\", forks[2], forks[1]);\r\n    philosophers[3] = new OrderlyPhilosopher(\"D\", forks[3], forks[2]);\r\n    philosophers[4] = new OrderlyPhilosopher(\"E\", forks[4], forks[3]);\r\n    \r\n    return philosophers;\r\n    \r\n  }\r\n  \r\n  public static Philosopher[] getDeadlockPhilosophers() {\r\n    \r\n    Fork forks[]=new Fork[5];\r\n    forks[0]=new Fork(1);\r\n    forks[1]=new Fork(2);\r\n    forks[2]=new Fork(3);\r\n    forks[3]=new Fork(4);\r\n    forks[4]=new Fork(5);\r\n    \r\n    DeadlockPhilosopher philosophers[]=new DeadlockPhilosopher[5];    \r\n    philosophers[0] = new DeadlockPhilosopher(\"A\", forks[0], forks[4]);\r\n    philosophers[1] = new DeadlockPhilosopher(\"B\", forks[1], forks[0]);\r\n    philosophers[2] = new DeadlockPhilosopher(\"C\", forks[2], forks[1]);\r\n    philosophers[3] = new DeadlockPhilosopher(\"D\", forks[3], forks[2]);\r\n    philosophers[4] = new DeadlockPhilosopher(\"E\", forks[4], forks[3]);\r\n    \r\n    return philosophers;\r\n    \r\n  }\r\n  \r\n}\r\n\r\npublic class DiningPhilosphers {\r\n\r\n  public static void main(String args[]) {\r\n    \r\n    \/\/PhilosphersTable philosopherstable=new PhilosphersTable(PhilosphersTable.getDeadlockPhilosophers());\r\n    \/\/PhilosphersTable philosopherstable=new PhilosphersTable(PhilosphersTable.getOrderlyPhilosophers());\r\n    PhilosphersTable philosopherstable=new PhilosphersTable(PhilosphersTable.getConductorPhilosophers());\r\n  }\r\n  \r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-813","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/813","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=813"}],"version-history":[{"count":22,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/813\/revisions"}],"predecessor-version":[{"id":815,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/813\/revisions\/815"}],"wp:attachment":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=813"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=813"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=813"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}