The Dining Philosophers

This is another concurrency classic, and although it may seem quite contrived — in the real world no one would starve because each philosopher would simply ask the adjacent philosophers for their forks — it accurately reflects real-world concurrency issues involving multiple shared resources. The point of the problem is to see whether you understand the concept of deadlock and know how to avoid it.

A naïve approach would be to have each philosopher wait until the left fork is available, pick it up, wait until the right fork is available, pick that fork up, eat, and then put down both forks. The following code implements this in Java using a separate thread for each philosopher:

public class DiningPhilosophers {
    // Each "fork" is just an Object we synchronize on
    private Object[]      forks;
    private Philosopher[] philosophers;
    // Prepare the forks and philosophers
    private DiningPhilosophers( int num ){
        forks = new Object[ num ];
        philosophers = new Philosopher[ num ];
        for ( int i = 0; i < num; ++i ){
            forks[i] = new Object();
            philosophers[i] = new Philosopher( i, i, ( i + 1 ) % num );
        }
    }
    // Start the eating process
    public void startEating() throws InterruptedException {
        for ( int i = 0; i < philosophers.length; ++i ){
            philosophers[i].start();
        }
        // Suspend the main thread until the first philosopher
        // stops eating, which will never happen -- this keeps
        // the simulation running indefinitely
        philosophers[0].join();
    }
    // Each philosopher runs in its own thread.
    private class Philosopher extends Thread {
        private int id;
        private int fork1;
        private int fork2;
        Philosopher( int id, int fork1, int fork2 ){
            this.id= id;
            this.fork1 = fork1;
            this.fork2 = fork2;
        }
        public void run() {
            status( "Ready to eat using forks " + fork1 +
                    " and " + fork2 );
            while ( true ){
                status( "Picking up fork " + fork1 );
                synchronized( forks[ fork1 ] ){
                    status( "Picking up fork " + fork2 );
                    synchronized( forks[ fork2 ] ){
                        status( "Eating" );
                    }
                }
            }
        }
        private void status( String msg ){
            System.out.println( "Philosopher " + id +
                                ": " + msg );
        }
    }

    // Entry point for simulation
    public static void main( String[] args ){
        try {
            DiningPhilosophers d = new DiningPhilosophers( 5 );
            d.startEating();
        }
        catch ( InterruptedException e ){
        }
    }
}

What will happen when you run this code? It’s not entirely deterministic because you don’t know exactly when the scheduler will have each thread running. (This is one of the challenges of debugging multithreaded code.) You do know that each philosopher will try to grab his or her left fork and will always hold it until he or she can pick up the right fork and eat. Any time there’s a fork on the table to the right of a philosopher who holds a left fork, you have a race condition that determines whether that philosopher gets the fork or the philosopher to his or her right picks it up. In the latter case, you have two philosophers with only left forks, and the first philosopher will have to wait until after the second eats before getting another shot at the fork. This will tend to lead to a lot of philosophers hungrily sitting around the table holding forks in their left hands.

At some point you would expect to reach a situation where four of the philosophers have forks in their left hands and only one fork remains on the table. (In practice, this is reached fairly quickly.) If this last fork is picked up as a right-handed fork, that philosopher eats, puts down both forks, and life goes on. If instead it’s picked up as a left-handed fork, then each philosopher has one fork that cannot be released until the philosopher to the right gets a second fork and eats. Because the philosophers are seated around a circular table, this will never happen, so you have five soon-to-be-dead philosophers in a deadlock. (Somewhat more formally: When each philosopher has a left fork, by induction, a given philosopher can’t get the right fork until after putting down the left fork but is required to get the right fork before putting down the left fork, so nothing happens.)

How can you avoid this deadlock? One solution is to add a timeout to the waiting: If a philosopher is not able to eat within a predetermined amount of time after acquiring the first fork, then the philosopher drops the fork and tries again. This doesn’t actually solve the problem, though: It may get some philosophers eating, but it doesn’t stop them from reaching a deadlock. Worse, there’s no way to know exactly which philosophers will get to eat — you could have a situation in which the interactions of the timeouts and the scheduler is such that some philosophers starve because they never acquire both forks. This is referred to as livelock.

Perhaps there’s a better solution that can avoid reaching deadlock in the first place. Deadlock occurs when each of the philosophers holds one fork in his or her left hand. What if one of the philosophers went for the right fork first? Then that philosopher would never hold just a left-hand fork (because he or she has to pick up a right fork first), so there’s no way to reach the all-left-forks deadlock condition. Another way to look at this is in terms of the order in which the forks are acquired. You know that deadlocks often result from locks (forks) being acquired in different orders. If you number each of the philosophers and forks counterclockwise around the table, then under the left-fork-first strategy, each philosopher tries to pick up first a lower numbered fork and then a higher numbered fork. This is true of every philosopher except for the last, who has fork n – 1 on the left and fork 0 on the right. Reversing the left-right order of acquisition for this philosopher means that all the philosophers acquire forks in the same order from a global perspective: lower number first. This can be implemented with a change to the constructor that changes the order in which one of the philosophers picks up forks:

    // Prepare the forks and philosophers
    private DiningPhilosophers( int num ){
        forks = new Object[ num ];
        philosophers = new Philosopher[ num ];
        for ( int i = 0; i < num; ++i ){
            forks[i] = new Object();
            int fork1 = i;
            int fork2 = ( i + 1 ) % num;
            if ( i == 0 ){
                philosophers[i] = new Philosopher( i, fork2, fork1 );
            } else {
                philosophers[i] = new Philosopher( i, fork1, fork2 );
            }
        }
    }

This solution avoids deadlock and would likely be adequate for most interviews, but it can be improved. Under the current implementation, each philosopher will eat, but will they all get an equal opportunity? Consider the philosopher sitting to the left of the right-hand-first philosopher (number 4, in the preceding implementation). This philosopher is in the unique position that neither neighbor takes one of his forks as a first fork; as a result it’s much easier for him to get forks, and he eats like a philosopher king. On the other hand (literally), the right-hand-first philosopher pays the price, frequently waiting for the series of left fork wielding philosophers to the right to eat and put down their forks. The exact ratio of number of times that the lucky philosopher eats to the number of times the unlucky philosopher beside him does will vary by system, but in informal tests of five philosophers on our machines, philosopher 4 eats about a hundred times more frequently than philosopher 0.

How can you make mealtimes more fair for the philosophers? You’ll want to preserve an ordering of the forks to avoid deadlocks. Consider whether you need to have all the forks ordered. A philosopher holds at most two forks, so you just need a rule that defines the order for each philosopher for acquisition of a maximum of two forks. One such rule would be that each philosopher must pick up an odd numbered fork before an even numbered fork. (If — as in this problem — there are an odd number of philosophers, then philosopher n sits between two even numbered forks: n – 1 and 0. It doesn’t matter in which order this philosopher picks up forks because he or she is the only one picking up two even forks.) A constructor that configures the philosophers under this scheme looks like:

// Prepare the forks and philosophers
    private DiningPhilosophers( int num ){
        forks = new Object[ num ];
        philosophers = new Philosopher[ num ];
        for ( int i = 0; i < num; ++i ){
            forks[i] = new Object();
            int fork1 = i;
            int fork2 = ( i + 1 ) % num;
            if ( ( i % 2 ) == 0 ){
                philosophers[i] = new Philosopher( i, fork2, fork1 );
            } else {
                philosophers[i] = new Philosopher( i, fork1, fork2 );
            }
        }
    }

This approach is completely fair for any even number of philosophers. For an odd number of philosophers, there’s still a “lucky” philosopher. Although it’s not completely fair in this case, it’s a marked improvement for five philosophers: The lucky philosopher eats only about ten times more often than the least lucky one. In addition, as the number of philosophers at the table increases, this approach becomes increasingly fair while the single right-hand-first philosopher algorithm becomes increasingly unfair.

Summary

Using multiple threads of execution within an application can make it more responsive and allow it to take full advantage of a multicore system but also makes programming more complicated. Synchronization is required to avoid data corruption whenever multiple threads access shared resources.

Synchronization is often achieved using monitors or semaphores. These facilities enable applications to control access to shared resources and to signal other threads when the resources are available for processing. Misuse of these constructs can halt threads through deadlock. Writing quality multithreaded code that avoids both data corruption and deadlock is challenging, requiring care and discipline.