Deadlocks represent a significant challenge in multi-threaded applications. For an introduction, refer to Deadlocks in Java: Understanding the Concurrency Nightmare. They happen when two or more threads become indefinitely blocked, each waiting for the other to release resources. This article digs into effective strategies for preventing deadlocks in Java applications.
🍥What is a Deadlock?
A deadlock happens when several threads are waiting for resources that are held by one another, forming a circular dependency. For instance:
- Thread 1 holds Lock A and waits for Lock B
- Thread 2 holds Lock B and waits for Lock A
As a result, neither thread can move forward, leading to a complete halt.
✨Prevention Strategies
1. Lock Reordering
Lock reordering is a simple but effective strategy where we ensure that all threads acquire locks in the same order. This prevents the circular wait condition necessary for deadlocks to occur.
Implementation
public class DeadlockPreventionLockRunnableA implements Runnable{
private Lock lock1;
private Lock lock2;
public DeadlockPreventionLockRunnableA(Lock lock1, Lock lock2) {
this.lock1 = lock1;
this.lock2 = lock2;
}
@Override
public void run() {
String name = Thread.currentThread().getName();
System.out.println(name + " is attempting to lock lock1");
lock1.lock();
System.out.println(name + " has locked lock1");
try {
Thread.sleep(3000);
} catch (InterruptedException e) {
}
System.out.println(name + " is attempting to lock lock2");
lock2.lock();
System.out.println(name + " has locked lock2");
lock2.unlock();
System.out.println(name + " is attempting to unlock lock2");
lock1.unlock();
System.out.println(name + " is attempting to unlock lock1");
}
}
public class DeadlockPreventionLockRunnableB implements Runnable{
private Lock lock1;
private Lock lock2;
public DeadlockPreventionLockRunnableB(Lock lock1, Lock lock2) {
this.lock1 = lock1;
this.lock2 = lock2;
}
@Override
public void run() {
String name = Thread.currentThread().getName();
System.out.println(name + " is attempting to lock lock1");
lock1.lock();
System.out.println(name + " has locked lock1");
try {
Thread.sleep(3000);
} catch (InterruptedException e) {
}
System.out.println(name + " is attempting to lock lock2");
lock2.lock();
System.out.println(name + " has locked lock2");
lock2.unlock();
System.out.println(name + " is attempting to unlock lock2");
lock1.unlock();
System.out.println(name + " is attempting to unlock lock1");
}
}
public class DeadlockPreventionLockReordering {
public static void main(String[] args) {
Lock lock1 = new ReentrantLock();
Lock lock2 = new ReentrantLock();
// depends on order which they acquire lock not when they release
Runnable r1 = new DeadlockPreventionLockRunnableA(lock1, lock2);
Runnable r2 = new DeadlockPreventionLockRunnableB(lock1, lock2);
Thread.ofPlatform().name("thread 1").start(r1);
Thread.ofPlatform().name("thread 2").start(r2);
}
}
Both classes acquire locks in the same order
2. Timeout and Back-off Strategy
Sometimes lock ordering isn’t feasible due to application requirements. In such cases, we can implement a timeout and back-off strategy where threads:
- Attempt to acquire locks with a timeout
- Release all held locks if they can’t acquire all needed locks
- Wait for a random period before retrying
Implementation :
public class DeadlockPreventionTimeoutBackOff {
public static void main(String[] args) {
Lock lock1 = new ReentrantLock();
Lock lock2 = new ReentrantLock();
// depends on order which they acquire lock not when they release
Runnable r1 = new DeadlockPreventionTimeoutBackOffRunnableA(lock1, lock2);
Runnable r2 = new DeadlockPreventionTimeoutBackOffRunnableB(lock1, lock2);
Thread.ofPlatform().name("thread 1").start(r1);
Thread.ofPlatform().name("thread 2").start(r2);
}
}
public class DeadlockPreventionTimeoutBackOffRunnableA implements Runnable{
private Lock lock1;
private Lock lock2;
public DeadlockPreventionTimeoutBackOffRunnableA(Lock lock1, Lock lock2) {
this.lock1 = lock1;
this.lock2 = lock2;
}
@Override
public void run() {
while(true){
int failures = 0;
while(!lockBothLocks()){
failures++;
System.err.println(Thread.currentThread().getName() + " is not able to lock both locks failure attempt no " + failures);
sleep(100L * (long) Math.random());
}
if(failures>0){
System.out.println(Thread.currentThread().getName() + " is able to lock both locks after " + failures+ " attempts");
}
lock2.unlock();
lock1.unlock();
}
}
private boolean lockBothLocks() {
try {
boolean lock1Locked = lock1.tryLock(1000, TimeUnit.MILLISECONDS);
if(!lock1Locked){
return false;
}
} catch (InterruptedException e) {
return false;
}
try {
boolean lock2Locked = lock2.tryLock(1000, TimeUnit.MILLISECONDS);
if(!lock2Locked){
lock1.unlock();
return false;
}
} catch (InterruptedException e) {
lock1.unlock();
return false;
}
return true;
}
private static void sleep(long millis) {
try {
Thread.sleep(millis);
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}
}
public class DeadlockPreventionTimeoutBackOffRunnableB implements Runnable {
private Lock lock1;
private Lock lock2;
public DeadlockPreventionTimeoutBackOffRunnableB(Lock lock1, Lock lock2) {
this.lock1 = lock1;
this.lock2 = lock2;
}
@Override
public void run() {
while (true) {
int failures = 0;
while (!lockBothLocks()) {
failures++;
System.err.println(Thread.currentThread().getName() + " is not able to lock both locks failure attempt no " + failures);
sleep(100L * (long) Math.random());
}
if (failures > 0) {
System.out.println(Thread.currentThread().getName() + " is able to lock both locks after " + failures + " attempts");
}
lock1.unlock();
lock2.unlock();
}
}
private boolean lockBothLocks() {
try {
boolean lock2Locked = lock2.tryLock(1000, TimeUnit.MILLISECONDS);
if (!lock2Locked) {
return false;
}
} catch (InterruptedException e) {
return false;
}
try {
boolean lock1Locked = lock1.tryLock(1000, TimeUnit.MILLISECONDS);
if (!lock1Locked) {
lock2.unlock();
return false;
}
} catch (InterruptedException e) {
lock2.unlock();
return false;
}
return true;
}
private static void sleep(long millis) {
try {
Thread.sleep(millis);
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}
}
Key features of this implementation:
- Uses tryLock() with timeout instead of blocking lock().
- Implements exponential back-off with random sleep as that will increase chance of one thread acquiring lock.
- Releases all acquired locks if unable to acquire all needed locks.
3. Deadlock Detection
For complex systems, implementing deadlock detection can be valuable. The basic approach involves:
- Maintaining a graph of lock acquisitions
- Checking for cycles in this graph before granting new locks
- Taking corrective action if a potential deadlock is detected
Graph 1
Here we have Lock and threads node which represent our locks and threads in a graph. we have lock 1 locked by thread 1 and so on . Threads 3 has to check before locking lock 1 if it will make graph cyclic . If it does then it will become deadlock like graph 2
Graph 2
🧰Best Practices for Deadlock Prevention
- Always acquire locks in a consistent order across your application
- Use timeout mechanisms instead of indefinite waiting
- Implement back-off strategies for retry attempts
- Keep lock holding times as short as possible
- Consider using higher-level concurrency utilities like java.util.concurrent collections
- Implement monitoring and detection mechanisms for production systems
✍️Conclusion
Deadlock prevention has to be systematically approached with good design. The best that could be hoped for is the best possible approximation under given conditions; lock ordering, timeouts, and back-off mechanisms can go a long way toward preventing deadlocks in your applications.
Remember that best practice often depends on your specific use case sometimes lock ordering is all you need, and at other times you require more elaborate timeout and retry mechanisms.
Top comments (0)