[9]

Deadlocks

Whenever two or more processes are waiting for something that never comes about, we say they're in a deadlock. Let's say a process requests for resources and if the resources are not available at that time, the process enters a waiting state. Sometimes, a waiting process is never again able to change it's state, because the resources it has requested for are held up by other waiting processes. This situation is called a Deadlock.

Deadlock Characterization

Deadlock can arise if four things happen simultaneously in a system:

Mutual Exclusion: It states that, at least one resource must be held in a non-sharable mode, that is, only one process at a time can use the resource. If another process requests for the same resource, that requesting process must be delayed until the resource has been released by the previously acquired process. Printers are examples of resources that can only be used by one process at a time.
Hold and Wait: The condition here is that a process should be holding at least one resource and should be waiting to acquire additional resources that are currently being held by other processes.
No Preemption: It states that, once a resource has been allocated to a process, it can not be preempted. The process must release the resource voluntarily by itself.
Circular Wait: A set of processes that are waiting for each other in a circular or cyclic manner where the last process waits for the resources acquired by the first process.

Occurrence of Deadlock requires all four of these conditions to hold simultaneously.

The Dining Philosophers Problem

The dining philosophers problem is a classic synchronization problem in a multi-threaded environment used to assess situations which requires the allocation of multiple resources to multiple processes like computer accessing tape drive peripherals. Okay so the story goes like this, There once were five philosophers gathered around a circular dining table, each with their own plate of noodles. But, alas, there were only five forks to share among them.

Imagine our philosophers are deep in thought, contemplating the mysteries of the universe, when suddenly, hunger strikes! The philosopher needs two forks (left and right) to eat when he's hungry. But if their neighboring philosophers have already snagged the forks, they've got to wait until the forks are free again. In the case of a philosopher without a fork (thanks to greedy neighbors), they start contemplating again. Each fork can be held by only one philosopher at a time. After one philosopher finishes eating he needs to put down both the forks and those forks become available for others.

Solution

while(true) { 
    // Initially, THINKING
    think();

    // Hunger Strikes In! Time to eat
    pick_up_left_fork();
    pick_up_right_fork();
    eat();
    put_down_right_fork();
    put_down_left_fork();

    // Not hungry anymore, Back to thinking!
}

The above pseudo code describes that, each philosopher starts off thinking and after some time, the philosopher gets hungry and wants to eat. At this point, the philosopher reaches for the forks on either side of him. Once he has both, he starts eating and after finishing his meal, he puts those forks back down so his neighbors can use them.

Implementation

class Philosopher implements Runnable {
    // The forks on either side of the this Philosopher
    private Object leftFork;
    private Object rightFork;

    public Philosopher(Object leftFork, Object rightFork) {
        this.leftFork = leftFork;
        this.rightFork = rightFork;
    }

    public void run() {
        // Populating code
    }
}

Each philosopher is modeled as a class that implements the Runnable interface so that we can run them separately. Each Philosopher has access to two forks on his left and right sides.

class Philosopher implements Runnable {
    // The forks on either side of the this Philosopher
    private Object leftFork;
    private Object rightFork;

    public Philosopher(Object leftFork, Object rightFork) {
        this.leftFork = leftFork;
        this.rightFork = rightFork;
    }

    private void doAction(String action) throws InterruptedException {
        System.out.println(Thread.currentThread().getName() + " " + action);
        Thread.sleep(((int) (Math.random() * 100)));
    }

    public void run() {
        // Populating code
    }
}

We also define a method that tells a philosopher to perform an action—either eat, think, or pick up forks to get ready for eating. In the above code, each action is simulated by suspending the invoking thread for a random amount of time. This way, the execution order isn't determined just by time.

Next, let's implement the philosopher's logic. To simulate acquiring a fork, we need to lock it so that no two philosopher threads can grab it at the same time. We do this by using the synchronized keyword to lock the fork object and prevent other threads from accessing it simultaneously. Now, let's implement the run() method in the Philosopher class:

class Philosopher implements Runnable {
    // Earlier implementation

    public void run() {
        try {
            while (true) {
                // Thinking
                doAction(System.nanoTime() + ": Thinking");
                synchronized (leftFork) {
                    doAction(System.nanoTime() + ": Picked up left fork");
                    synchronized (rightFork) {
                        // Eating
                        doAction(System.nanoTime() + ": Picked up right fork, now eating");
                        doAction(System.nanoTime() + ": Put down right fork");
                    }

                    // Back to Thinking
                    doAction(System.nanoTime() + ": Put down left fork, back to thinking");
                }
            }
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
            return;
        }
    }
}

This scheme follows the process described earlier: a philosopher thinks for a while and then decides to eat. He then picks up the forks on his left and right to start eating. Once he's done, he puts the forks back down. We can also added timestamps to each action to help us track the order of events.

To get the process going, we need a client that creates 5 philosophers as threads and starts them all. Here’s the complete code for your reference:

class Philosopher implements Runnable {
    // The forks on either side of the this Philosopher
    private Object leftFork;
    private Object rightFork;

    public Philosopher(Object leftFork, Object rightFork) {
        this.leftFork = leftFork;
        this.rightFork = rightFork;
    }

    private void doAction(String action) throws InterruptedException {
        System.out.println(Thread.currentThread().getName() + " " + action);
        Thread.sleep(((int) (Math.random() * 100)));
    }

    public void run() {
        try {
            while (true) {
                // Thinking
                doAction(System.nanoTime() + ": Thinking");
                synchronized (leftFork) {
                    doAction(System.nanoTime() + ": Picked up left fork");
                    synchronized (rightFork) {
                        // Eating
                        doAction(System.nanoTime() + ": Picked up right fork, now eating");
                        doAction(System.nanoTime() + ": Put down right fork");
                    }

                    // Back to Thinking
                    doAction(System.nanoTime() + ": Put down left fork, back to thinking");
                }
            }
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
            return;
        }
    }
}

public class DiningPhilosopher {
    public static void main(String args[]) throws Exception {
        Philosopher[] philosophers  = new Philosopher[5];
        Object[] forks = new Object[philosophers.length];

        for(int i = 0; i < forks.length; i++) {
            forks[i] = new Object();
        }

        for(int i = 0; i < philosophers.length; i++) {
            Object leftFork = forks[i];
            Object rightFork = forks[(i + 1 ) % forks.length];

            philosophers[i] = new Philosopher(leftFork, rightFork);

            Thread t = new Thread(philosophers[i], "Philosopher " + (i + 1));
            t.start();
        }
    }
}

Modelling each of the forks as a generic Java object and creating one fork for each of the philosopher. Each philosopher is given references to their left and right forks, which they attempt to lock using the synchronized keyword.

Running this code results in an output similar to the following. Your output will most likely differ due to the varying intervals in the sleep() method:

All the philosophers initially start off thinking. In this scenario, each philosopher picks up his left fork but can't pick up his right fork because his neighbor has already taken it. This leads to a situation known as circular wait, which is one of the conditions that leads to a deadlock (which we just read above), preventing the system from making any progress. You can confirm that by running the above code a few times and checking that some times it just hangs.

Resolving the Deadlock

Deadlock on the dining philosophers problem can happen if each philosopher picks up their left fork and then their right fork, causing a circular wait. You break this circular dependency by making the last philosopher pick up the right fork first.

class Philosopher implements Runnable {
    // Earlier code...
}

public class DiningPhilosopher {
    public static void main(String args[]) throws Exception {
        // Earlier code...

        for(int i = 0; i < philosophers.length; i++) {
            Object leftFork = forks[i];
            Object rightFork = forks[(i + 1 ) % forks.length];
            // Observe here
            if(i == philosophers.length - 1) {
                philosophers[i] = new Philosopher(rightFork, leftFork); // The last philosopher picks up the right fork first
            } else {
                philosophers[i] = new Philosopher(leftFork, rightFork);
            }

            Thread t = new Thread(philosophers[i], "Philosopher " + (i + 1));
            t.start();
        }
    }
}

For all philosophers except the last one, the left fork is picked up first, then the right fork. The order is reversed for the last philosopher. Having them pick up different forks at the same time keeps deadlocks at bay.

The reasoning behind the code's behavior:

Philosophers 1 to 4 pick up the left fork first and then the right fork.
Philosopher 5 picks up the right fork first and then the left fork.

This staggered approach ensures that at least one philosopher can always proceed to eat, which keeps the system running without entering a deadlock state.

Let's take a look at common ways to handle deadlocks in a system now that we've seen how to prevent and solve the circular wait problem.

How to handle Deadlocks?

Deadlock Prevention

A deadlock prevention method makes sure at least one of the necessary conditions doesn't hold. To prevent a deadlock from occurring, it's essential to ensure that at least one of the four necessary conditions cannot hold:

Make Mutual Exclusion False

By allowing resource sharing between the processes we can make Mutual Exclusion false. Read-only files are a good example of a sharable resource. We cannot prevent deadlocks by denying the mutual-exclusion condition because some resources, such as printers, are inherently non-sharable.

Make Hold and Wait False

It must guarantee that whenever a process requests a resource, it doesn't hold anything else. There can be two solutions here let's understand them by considering an example of a process that involves copying data from a DVD drive to a file on disk, sorting the file content, and then printing the results to a printer.

Solution 1 mandates that a process must request and be allocated all its required resources before it begins execution. Essentially, the process needs to gather all necessary resources before commencing execution to avoid waiting. So, with respect to our example above, the process must initially request the DVD drive, disk file, and printer. It will hold the printer for its entire execution, even though it needs the printer only at the end.
Solution 2 says that, a process is permitted to request resources only when it has none. Before requesting additional resources, the process must release all currently allocated resources, thereby avoiding holding resources unnecessarily. This solution permits the process to initially request only the DVD drive and disk file. It copies from the DVD drive to the disk and then releases both the DVD drive and the disk file. Subsequently, the process must request the disk file and the printer.

Of course, there are caveats here. The resource utilization might lower down because resources that were allocated might remain unused for extended periods and also, starvation is possible because a process requiring several essential resources may have to wait indefinitely.

Make No Preemption False

If a process requests resources, we first check whether they are available. If they are, we allocate them. If not, we check if those resources are already allocated to another process that is waiting for additional resources. If so, we preempt the desired resources from the waiting process and allocate them to the requesting process.

Make Circular Wait False

Each process can request resources only in an increasing order of their enumeration. This means that after requesting a resource R(i), a process can request R(j) only if F[R(j)] > F[R(i)].

For example:

F(tape drive) = 1
F(disk drive) = 5
F(printer) = 12

In this case, a process could request a tape drive first, followed by a disk drive, and then a printer. This ensures that resources are requested in a specific order to prevent deadlocks.

Deadlock Avoidance

This requires the Operating System to have additional information in advance, concerning which resources a process will request and use during its lifetime. A deadlock-avoidance algorithm dynamically examines the resource allocation state to ensure that a circular-wait condition can never exist. Here are a few key algorithms:

Safe State: A state where the system can allocate resources to each process in some order and still avoid a deadlock.
Resource-Allocation-Graph Algorithm: Uses a graph to represent processes and resources, ensuring no cycles exist.
Banker’s Algorithm: Allocates resources only if it leaves the system in a safe state.

I'm painting in broad strokes here, we can cover these algorithms in detail in another dedicated article, as this one has already become quite lengthy.

Conclusion

In this article, we explored the famous Dining Philosophers problem and the concepts of circular wait and deadlock. We coded a basic solution that resulted in a deadlock and then made a simple change to break the circular wait, thus avoiding the deadlock. This is just the beginning—there are plenty of more advanced solutions out there.

Deadlock and the Dining Philosophers

Table of contents