Description

Dining Philosophers is a classic computer science problem that happens in concurrent programming. Dining philosophers problem will result in circular deadlock problem. Circular deadlock is a variant of deadlock problem. Once deadlock happens, the only way to recover from the situation is to restart JVM.

Please refer to above diagram. In the diagram, you can see that

  • “Thread-0” is holding lock L1 and waiting on lock L2.
  • “Thread-1” is holding lock L2 and waiting on lock L3.
  • “Thread-2” is holding lock L3 and waiting on lock L4.
  • “Thread-3” is holding lock L4 and waiting on lock L1.

Since each thread is holding a lock, for which other thread waits upon – this will ultimately result in a circular deadlock. The code has to be re-engineered to break this circular deadlock pattern.

Example

Below is a thread dump of a JVM instance from a dining philosopher problem which was suffering from a circular deadlock problem.

"Thread-4" prio=6 tid=0x0000000007466800 nid=0x158f5c waiting on condition [0x0000000008fcf000]
   java.lang.Thread.State: WAITING (parking)
	at sun.misc.Unsafe.park(Native Method)
	- parking to wait for  0x00000007ac3b2718 (a java.util.concurrent.locks.ReentrantLock$NonfairSync)
	at java.util.concurrent.locks.LockSupport.park(Unknown Source)
	at java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInterrupt(Unknown Source)
	at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireQueued(Unknown Source)
	at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquire(Unknown Source)
	at java.util.concurrent.locks.ReentrantLock$NonfairSync.lock(Unknown Source)
	at java.util.concurrent.locks.ReentrantLock.lock(Unknown Source)
	at com.tier1app.dinning.Philosopher.pickUpRightChopstick(DiningPhilosophers.java:110)
	at com.tier1app.dinning.Philosopher.run(DiningPhilosophers.java:78)
	at java.lang.Thread.run(Unknown Source)

   Locked ownable synchronizers:
	- 0x00000007ac3b27d8 (a java.util.concurrent.locks.ReentrantLock$NonfairSync)

"Thread-3" prio=6 tid=0x0000000007465800 nid=0x158f58 waiting on condition [0x0000000008e0f000]
   java.lang.Thread.State: WAITING (parking)
	at sun.misc.Unsafe.park(Native Method)
	- parking to wait for  0x00000007ac3b27d8 (a java.util.concurrent.locks.ReentrantLock$NonfairSync)
	at java.util.concurrent.locks.LockSupport.park(Unknown Source)
	at java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInterrupt(Unknown Source)
	at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireQueued(Unknown Source)
	at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquire(Unknown Source)
	at java.util.concurrent.locks.ReentrantLock$NonfairSync.lock(Unknown Source)
	at java.util.concurrent.locks.ReentrantLock.lock(Unknown Source)
	at com.tier1app.dinning.Philosopher.pickUpRightChopstick(DiningPhilosophers.java:110)
	at com.tier1app.dinning.Philosopher.run(DiningPhilosophers.java:78)
	at java.lang.Thread.run(Unknown Source)

   Locked ownable synchronizers:
	- 0x00000007ac3b27a8 (a java.util.concurrent.locks.ReentrantLock$NonfairSync)

"Thread-2" prio=6 tid=0x0000000007465000 nid=0x158f54 waiting on condition [0x000000000895e000]
   java.lang.Thread.State: WAITING (parking)
	at sun.misc.Unsafe.park(Native Method)
	- parking to wait for  0x00000007ac3b27a8 (a java.util.concurrent.locks.ReentrantLock$NonfairSync)
	at java.util.concurrent.locks.LockSupport.park(Unknown Source)
	at java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInterrupt(Unknown Source)
	at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireQueued(Unknown Source)
	at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquire(Unknown Source)
	at java.util.concurrent.locks.ReentrantLock$NonfairSync.lock(Unknown Source)
	at java.util.concurrent.locks.ReentrantLock.lock(Unknown Source)
	at com.tier1app.dinning.Philosopher.pickUpRightChopstick(DiningPhilosophers.java:110)
	at com.tier1app.dinning.Philosopher.run(DiningPhilosophers.java:78)
	at java.lang.Thread.run(Unknown Source)

   Locked ownable synchronizers:
	- 0x00000007ac3b2778 (a java.util.concurrent.locks.ReentrantLock$NonfairSync)

"Thread-1" prio=6 tid=0x0000000007462000 nid=0x158f50 waiting on condition [0x0000000008cce000]
   java.lang.Thread.State: WAITING (parking)
	at sun.misc.Unsafe.park(Native Method)
	- parking to wait for  0x00000007ac3b2778 (a java.util.concurrent.locks.ReentrantLock$NonfairSync)
	at java.util.concurrent.locks.LockSupport.park(Unknown Source)
	at java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInterrupt(Unknown Source)
	at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireQueued(Unknown Source)
	at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquire(Unknown Source)
	at java.util.concurrent.locks.ReentrantLock$NonfairSync.lock(Unknown Source)
	at java.util.concurrent.locks.ReentrantLock.lock(Unknown Source)
	at com.tier1app.dinning.Philosopher.pickUpRightChopstick(DiningPhilosophers.java:110)
	at com.tier1app.dinning.Philosopher.run(DiningPhilosophers.java:78)
	at java.lang.Thread.run(Unknown Source)

   Locked ownable synchronizers:
	- 0x00000007ac3b2748 (a java.util.concurrent.locks.ReentrantLock$NonfairSync)

"Thread-0" prio=6 tid=0x0000000007461800 nid=0x158f4c waiting on condition [0x0000000008ace000]
   java.lang.Thread.State: WAITING (parking)
	at sun.misc.Unsafe.park(Native Method)
	- parking to wait for  0x00000007ac3b2748 (a java.util.concurrent.locks.ReentrantLock$NonfairSync)
	at java.util.concurrent.locks.LockSupport.park(Unknown Source)
	at java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInterrupt(Unknown Source)
	at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireQueued(Unknown Source)
	at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquire(Unknown Source)
	at java.util.concurrent.locks.ReentrantLock$NonfairSync.lock(Unknown Source)
	at java.util.concurrent.locks.ReentrantLock.lock(Unknown Source)
	at com.tier1app.dinning.Philosopher.pickUpRightChopstick(DiningPhilosophers.java:110)
	at com.tier1app.dinning.Philosopher.run(DiningPhilosophers.java:78)
	at java.lang.Thread.run(Unknown Source)

   Locked ownable synchronizers:
	- 0x00000007ac3b2718 (a java.util.concurrent.locks.ReentrantLock$NonfairSync)

From the above thread dump, one could see

  • “Thread-4” is waiting for 0x00000007ac3b2718 which is held by “Thread-0”
  • “Thread-0” is waiting for 0x00000007ac3b2748 which is held by “Thread-1”
  • “Thread-1” is waiting for 0x00000007ac3b2778 which is held by “Thread-2”
  • “Thread-2” is waiting for 0x00000007ac3b27a8 which is held by “Thread-3”
  • “Thread-3” is waiting for 0x00000007ac3b27d8 which is held by “Thread-4”