Circular Deadlock

Description

Dinning Philosophers is a classic computer science problem that happens in concurrent programming. Dinning philosophers problem will result in circular deadlock problem. Circular deadlock is a variant of deadlock problem. Once deadlock happens, 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. 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”