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”
Leave a Reply