Java Concurrency - DeadLock, LiveLock, Starvation

Deadlock

---

It occurs when two threads are waiting for each other's resources, but at the same time, neither thread releases the resources it already holds, resulting in eternal blocking.

 

public class DeadLock {
    static Object lock1 = new Object();
    static Object lock2 = new Object();

    public static void main(String[] args) {
        new Thread(()->{
            try{
                synchronized (lock1) {
                    Thread.sleep(500);
                    synchronized (lock2) {
                        System.out.println("Thread 1 successfully started execution");
                    }
                }
            }catch (InterruptedException e) {
                e.printStackTrace();
            }
        }).start();

        new Thread(()->{
            try{
                synchronized (lock2) {
                    Thread.sleep(500);
                    synchronized (lock1) {
                        System.out.println("Thread 2 successfully started execution");
                    }
                }
            }catch (InterruptedException e) {
                e.printStackTrace();
            }
        }).start();
    }
}

 

Once you start the execution, you will find that the program is running all the time, but you never get the output results of thread 1 and thread 2, indicating that both of them are stuck. If you don't force the process to end, they will keep waiting.

 

The Necessary Conditions for Deadlock

---

The four conditions are indispensable.

1. Mutual exclusion condition: Only one thread or process may use a resource at once.

2. Request and hold condition: The first thread requests the second lock while holding the first lock.

3. None-interference condition: The lock is not deprived by external interference. That is, there is not external interference to end the deadlock.

4. Circular wait condition: Two or more threads wait for each other or circularly wait for the release of locks.

 

To prevent Deadlock

---

1. Obtain locks in a certain order
You need to ensure that the order in which the two obtain locks is consistent to avoid a deadlock.

2. Give up after timeout
In this situation, you can set a specific time to wait for the lock by using the boolean tryLock(long time, TimeUnit unit) method offered by the Lock interface.

 

Livelock

---

Compared to a deadlock, when two or more threads are executing, they mutually defer resources, resulting in none of them being able to obtain the resources and the program not being able to run normally.

 

public class LiveLock {

    private Lock lock1 = new ReentrantLock(true);
    private Lock lock2 = new ReentrantLock(true);

    public static void main(String[] args) {
        LiveLock lock = new LiveLock();
        new Thread(lock::operation1, "T1").start();
        new Thread(lock::operation2, "T2").start();
    }

    public void operation1() {
        while(true) {
            lock1.tryLock();
            System.out.println("Acquired lock1, trying to acquire lock2.");
            sleep(50);

            if(lock2.tryLock()){
                System.out.println("Acquired lock2.");
            }else {
                System.out.println("Unable to acquire lock2, releasing lock1");
                lock1.unlock();
                continue;
            }

            System.out.println("Executing operation1.");
            break;
        }
        lock2.unlock();;
        lock1.unlock();
    }

    public void operation2() {
        while(true) {
            lock2.tryLock();
            System.out.println("Acquired lock2, trying to acquire lock1.");
            sleep(50);

            if(lock1.tryLock()){
                System.out.println("Acquired lock1.");
            }else {
                System.out.println("Unable to acquire lock1, releasing lock2");
                lock2.unlock();
                continue;
            }

            System.out.println("Executing operation2.");
            break;
        }
        lock1.unlock();;
        lock2.unlock();
    }

    private void sleep(long millis) {
        try {
            Thread.sleep(millis);
        }catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

 

As we can see in the output logs, both threads are repeatedly acquiring and releasing locks. Therefore, none of the threads can complete the operation.

 

To prevent Livelock

---

We can wait for a random time when attempting to acquire a lock. Since the waiting times are different, the timing of releasing the lock that  you already hold will also be different. Therefore, when you release the lock you already hold, another thread may still be trying to acquire the lock you just released, and it may run successfully, thereby breaking the deadlock.

Starvation

---

It refers to a situation where a thread is always unable to obtain certain resources, especially CPU resources, resulting in the thread not being able to run and causing problems. It may result in poor responsiveness.

 

To prevent Starvation

---

1. Be aware of logical errors in the program where locks are not released after use.
2. Set reasonable priorities, or try not to set priorities for threads.