Livelock: When Threads Dance But Never Progress

Link of the Image

Imagine two people in a hallway, both trying to pass by stepping aside, but every time one moves, the other moves too. They keep dodging each other but never manage to pass. This is similar to what happens in a livelock scenario in programming — threads keep reacting to each other’s actions but never actually move forward.

Unlike a deadlock, where everything freezes, a livelock is a situation where threads are still active but are stuck in a loop of ineffective action. Let’s dive into what livelock is, how it happens, and how to avoid it with a simple example.

What is a Livelock?

In a livelock, threads or processes are not blocked, but they are constantly changing their states in response to each other in such a way that no progress is made. This often happens in multithreading environments where threads are attempting to solve a problem but end up in a loop of unproductive behavior.

In simpler terms: they’re “alive” and doing things, but not getting anywhere — just like the two people trying to step out of each other’s way but constantly blocking one another.

A Simple Example of Livelock

Let’s imagine two threads in Java trying to avoid a collision by constantly checking if the other thread has moved. Here’s a simple example:

public class LivelockExample {

    static class Worker {
        private boolean hasWork;

        public Worker(boolean hasWork) {
            this.hasWork = hasWork;
        }

        public void work(OtherWorker otherWorker) {
            while (hasWork) {
                if (otherWorker.isWorking()) {
                    System.out.println("Worker: Other worker is busy, I'll wait.");
                    try { Thread.sleep(100); } 
                    catch (InterruptedException e) {}
                    continue;
                }
                System.out.println("Worker: I can do my work now!");
                this.hasWork = false; // Finished work
            }
        }

        public boolean isWorking() {
            return hasWork;
        }
    }

    static class OtherWorker {
        private boolean hasWork;

        public OtherWorker(boolean hasWork) {
            this.hasWork = hasWork;
        }

        public void work(Worker worker) {
            while (hasWork) {
                if (worker.isWorking()) {
                    System.out.println("OtherWorker: Worker is busy, I'll wait.");
                    try { Thread.sleep(100); } 
                    catch (InterruptedException e) {}
                    continue;
                }
                System.out.println("OtherWorker: I can do my work now!");
                this.hasWork = false; // Finished work
            }
        }

        public boolean isWorking() {
            return hasWork;
        }
    }

    public static void main(String[] args) {
        Worker worker1 = new Worker(true);
        OtherWorker worker2 = new OtherWorker(true);

        new Thread(() -> worker1.work(worker2)).start();
        new Thread(() -> worker2.work(worker1)).start();
    }
}

In this example, both Worker and OtherWorker are trying to finish their tasks. However, they’re being too polite: each waits for the other to finish before doing their work. As a result, neither thread progresses, even though they are both constantly checking and responding.

How Does Livelock Happen?

Livelock happens when threads (or processes) are constantly adjusting their actions based on each other’s state, without making real progress. Each thread thinks it’s being helpful by waiting or adjusting, but in reality, they’re stuck in a loop where they can never finish their work.

Common causes of livelock include:

1. Overreactive Threads: Threads that respond too eagerly to changes in other threads can fall into a pattern of constantly adjusting without making progress.
2. Faulty Backoff Mechanisms: Some algorithms use retry or backoff strategies (like exponential backoff) to avoid contention, but if implemented poorly, this can lead to livelock where threads endlessly retry without success.

How to Avoid Livelock

Avoiding livelock requires ensuring that threads are able to make progress rather than indefinitely reacting to each other. Here are some strategies:

Limit Reaction: Threads shouldn’t be overly reactive to others’ states. Implementing mechanisms like fixed delays or thresholds can prevent constant back-and-forth.

Introduce Randomness: Randomizing the retry intervals or actions can help break the cycle of livelock. For instance, instead of both threads checking each other’s state at fixed intervals, you can add a small random delay between checks.

Here’s an improved version of the previous example, introducing a random delay:

public void work(OtherWorker otherWorker) {
    Random random = new Random();
    while (hasWork) {
        if (otherWorker.isWorking()) {
            System.out.println("Worker: Other worker is busy, I'll wait.");
            try { Thread.sleep(random.nextInt(200)); } 
            catch (InterruptedException e) {}
            continue;
        }
        System.out.println("Worker: I can do my work now!");
        this.hasWork = false; // Finished work
    }
}

By introducing randomness, we decrease the chances that both threads will get stuck checking each other at the exact same times.

Time Limits or Deadlines: Implement a timeout or deadline for when threads should stop waiting and proceed with their work regardless of the other thread’s state. This ensures that threads don’t get stuck waiting indefinitely.

Conclusion: Livelock is a Dance, But No One’s Moving Forward

Livelock is a tricky multithreading problem where threads are technically “active,” but they’re just reacting to each other endlessly without making progress. It’s less obvious than a deadlock, but it can still cause significant performance problems in systems.

By limiting overreactions, introducing randomization, and setting time limits, you can avoid livelock scenarios and ensure that your threads move forward rather than getting stuck in an endless loop of politeness.

Remember: in multithreading, sometimes it’s better for your threads to be a little less considerate, and a little more decisive!