Solving the Dining Philosophers Problem with the Concurrency Explorer

Introduction

In computer science, the Dining Philosophers problem is an example problem often used in concurrent algorithm design to illustrate synchronization issues and techniques for resolving them.The Dining Philosophers problem was originally formulated in 1965 by Edsger Dijkstra as a student exam exercise and was soon thereafter put into its current formulation by Tony Hoare. Wikipedia describes the problem as follows:

“Five silent philosophers sit at a round table with bowls of spaghetti. Forks are placed between each pair of adjacent philosophers.

Each philosopher must alternately think and eat. However, a philosopher can only eat spaghetti when they have both left and right forks. Each fork can be held by only one philosopher and so a philosopher can use the fork only if it is not being used by another philosopher. After an individual philosopher finishes eating, they need to put down both forks so that the forks become available to others. A philosopher can take the fork on their right or the one on their left as they become available, but cannot start eating before getting both forks.

Eating is not limited by the remaining amounts of spaghetti or stomach space; an infinite supply and an infinite demand are assumed.

The problem is how to design a discipline of behavior (a concurrent algorithm) such that no philosopher will starve; i.e., each can forever continue to alternate between eating and thinking, assuming that no philosopher can know when others may want to eat or think.”

Before rushing off to code your own solution, consider solving the Dining Philosophers problem using the Concurrency Explorer (ConcX), a free, open source tool from the Avian Computing Project. ConcX is an interactive tool designed to help us think about parallel problems; ConcX encourages us to imagine a parallel problem/program as resembling a flock of birds where each bird behaves and operates independently but also cooperates with the other birds in the flock. ConcX maps the various thread states into the natural behaviors of a bird, such as hatching (thread.start), napping (thread.sleep), death (thread.stop) and so on to make it easier to think about and describe each thread’s actions. The mental process of breaking down a program’s tasks into a set of atomic actions that can be independently performed, one per bird, produces a scalable parallel solution to the program.

Set-up ConcX to Run Dining Philosophers Problem

The following screenshot shows the ConcX GUI used to select the types of birds and how to configure them. The GUI also allows the flock of birds or individual birds to be started or stopped while viewing in real time each bird’s activity on its progress bars.

To solve the Dining Philosophers problem, five “birds” were added (tabs #2 - #6) to create a new flock. Each bird gets its own tab so it can be independently configured. In this case, each bird was configured to “eat” two food types which are called Fork1Pod through Fork5Pod. To set the table, a “waiter” bird was also added (who disappears after the table is set, which seems typical of waiters around the world).

Note that the ConcX download comes with all the bird and food objects needed to solve the Dining Philosophers problem and a variety of other parallel problems, such as Producer-Consumer, Calculating Pi in parallel, the Sleeping Barber problem, and more.

Solving the Dining Philosophers Problem

Click the Start All button (lower left corner) and a SwingWorker thread will be started for each bird in the flock. The philosophers (birds/threads) will all begin eating, as indicated by their individually growing Activity progress bars. After 30 seconds (their default lifetimes), the philosophers will all die, having reached the end of their (configurable) lifetimes, and their threads will all terminate. If you’re impatient, you can also click the Stop All button and they will all stop eating, terminating their individual threads.

There, that’s it. Problem solved. ConcX provided all the tools and the necessary framework to solve the Dining Philosophers problem. The philosophers all shared their forks and got to eat an approximately even number of times and none of them starved.

“Wait!!” I can almost hear you saying, “it can’t be that simple. Show me how that worked.”

Details of Dining Philosophers Solution

The following screenshot shows the progress of all the philosophers shortly after they were all started. Each of the progress bars was individually updated in real-time based on how many times their assigned philosopher ate. In this case, their progress bars are all about the same length, showing that they were sharing fairly equally, although Bacon was slightly less successful than the others at eating.

This solution to the Dining Philosophers problem works because each philosopher is a BasicBird in ConcX, which allowed them to all inherit the standard Avian lifecycle. As shown in the lifecycle diagram, once a BasicBird is hatched, it looks for its assigned type of food, digests any of its food that it found, stores the appropriate type of food and then takes a nap. It repeats this loop until it dies of old age, starves to death, or you push the stop button.

The lifecycle of a BasicBird just happens to map into the Dining Philosophers description: each philosopher trying to pick up two forks maps to the bird's Looking for Food stage, eating spaghetti is performed during the Digest Food stage, putting down their forks happens during the Store Food stage, and thinking is done during the Nap stage (which is when I do all my best thinking).

Back to our example run where Bacon didn’t eat as often as the other philosophers. Note that each individual philosopher can be started using the Start Me button on his tab. If you’d like to see Bacon eat more, click on his tab (#3) and then click his Start Me button; he will start eating and be the only philosopher whose progress bar is growing. It will actually grow faster than before because he doesn’t have to share.

The following screenshot shows the results of what happens after Bacon was given the opportunity to make a pig of himself; his Activity tab progress bar is now longer than the other progress bars.

“Wait,” I can almost hear you saying, “growing progress bars don’t prove anything. I want to see some kind of evidence that something actually happened.”

To really get a feeling for what was happening during the run, on the GUI screen, click on the TupleTree tab at the upper right side of the screen. This will display the “history” of each ForkPod (see the following screenshot). The history of each food pod is always recorded so you can always review and analyze the events that happened to the food pod during it latest run.

In this enlarged portion of the screen, Fork2Pod is shared by Aristotle and Bacon; the TupleTree tab allows you to view the individual history of each food pod down to the millisecond. Note that Fork2Pod is shared evenly by Aristotle and Bacon at the beginning of the run but then about mid-screen Aristotle gets “greedy” and monopolizes Fork2Pod before sharing more evenly at the bottom of this screen. If you scroll down through the history of Fork2Pod, you can view the time when Bacon is the only active Philosopher and the only one who uses the Fork2Pod, matching up with his progress bar being longer. You can also scroll down and view the histories of all the other food pods in the TupleTree.

TupleTree Discussion

The TupleTree in ConcX is a simplified version of a tuplespace, a concept originally developed for the Linda coordination language; a tuplespace is shared associative memory used as a repository for tuples of data. Linda was started in 1986 by Sudhir Ahuja, David Gelernter, Nicholas Carriero and others. Linda was the basis for several major products, including Sun’s JavaSpaces, IBM’s TSpaces, and many more in a variety of languages.

In ConcX, the TupleTree actively manages all shared objects (food pods). In this problem, when a philosopher attempts to pick up a fork, he is actually requesting a specific type of food pod from the TupleTree. If the TupleTree doesn’t contain the requested type of food pod, the philosopher gets nothing, which means he failed to pick up a fork and goes back to thinking (napping) for a random length of time.

However, if the TupleTree does contain the requested type of food pod (Fork1Pod, Fork4Pod, etc.), the TupleTree removes the requested pod and gives it to the philosopher who requested it, who now has exclusive possession of the one and only instance of that food pod (fork). No other philosopher can access, change or modify that fork until the philosopher puts it down (stores it back in the TupleTree).

An interesting and extremely convenient by-product of the TupleTree is that the code for the BasicBird doesn’t contain parallel programming logic, such as mutexes, semaphores, locks, etc. All of the parallel programming code/logic has been factored out of the BasicBirds (users of data) and exists only in the TupleTree code (repository of data). The TupleTree has exclusive access to the data repository and manages all of the locking code so you don’t have to.

Preventing Deadlocks in ConcX

Back to the original problem description: after a philosopher has successfully picked up his first fork, he then attempts to pick up his second fork. This is the point where deadlocks typically can happen because the situation could arise where every philosopher will be holding their first fork and be unable to get their second fork because it is being held by their neighboring philosopher.

ConcX avoids deadlock situations by default because BasicBirds will give up after failing to get their second food (fork) a configurable number of attempts and put down the first fork, making it available to their neighbor. The reason that BasicBirds can be so well behaved is because they never block and wait for their fork. Instead, they only have to wait for a millisecond or so until the TupleTree responds with either the requested food pod or an empty food pod, meaning that the requested food pod wasn’t in the TupleTree. Receiving an empty food pod is a normal condition in ConcX; just like real life birds, BasicBirds that don’t find food just go on with their lifecycle and look for food the next time through their lifecycle.

To demonstrate how the deadlock prevention works, view the lifecycle events for a particular bird by clicking on its numbered tab and then click on its individual History tab. In ConcX, each bird always records the events that happened to the bird during its latest run. The following screenshot shows a portion of Aristotle’s history from a recent run. The portion shown of its history begins with him looking for food and finding nothing so he takes a nap of 160ms. When he wakes up, he looks for food, gets the Fork1Pod and then tries three times before getting the Fork2Pod (his second fork). He then eats, digests and puts down his forks (stores them back in the TupleTree) so other philosophers can use them. After all that exertion, he takes a nap for 50ms (note the random duration of this nap) before looking for food again. And every event is timestamped so you can cross-check them with the food pod events on the TupleTree tab.

ConcX was specifically designed to be an interactive environment for experimenting: at this point, you have enough information where you could download ConcX and start experimenting with the Dining Philosophers problem. For example, you could easily make the following experiments:

• Change the lifetime of one or more birds to 100 seconds or 10 minutes or as long as desired
• Reduce the “patience” (a configurable value) of one philosopher so he tries only once to get the second fork before giving up and putting down his first fork
• Increase a philosopher’s patience to see how the results are changed if he tries 10 times to get the second fork instead of the default 5 times.
• Reduce a philosopher’s Nap length to see what happens if he checks more frequently for available forks. Will his eagerness (greed) result in more frequent eating? How will a greedier philosopher affect his neighbors? What happens if the neighbors also become greedy?

These experiments and more can be run just by changing the philosophers’ configurations, clearing the previous activities/results and restarting the philosophers. Many more experiments can be run by adding more philosophers. For example:

• Add a sixth philosopher without adding another fork. Just click the Add New Bird button, give it a name, select a type of bird, and then pick which forks to eat and store and restart the simulation.
• Add five more philosophers (10 total) without adding more forks so each plate at the table has two philosophers who share the same two forks
• What about a bigger table with 10 philosophers and 10 forks?
• What is the maximum number of philosophers that can be fed without any of them starving and without also increasing the number of forks?

ConcX makes it easy to explore these possibilities and more, all without coding. And if you like the simulation or results, you can save them to a new flock file so you can reload and rerun the them later.

If you’re willing to do some coding, the possibilities are endless. For example, what about an opportunistic philosopher who will use any forks and will eat any time he can find two unused forks? What if one or more forks was bent or twisted so the philosophers also tried to trade their forks to get the better forks?

Background

Parallel programs take too long to develop. Multi-core machines have been the standard CPUs for most modern computers for almost a decade but most software struggles to make full and balanced use of those cores. If software could have kept up with hardware, it is likely that 16-core or 128-core CPUs would be the norm.

The Avian Computing Project began with the idea that if we can better visualize and describe how a parallel program should operate, we can reduce the length of time it takes to develop that parallel program. This insight lead to a search for a model that could naturally and intrinsically exhibit parallel behavior; a flock of birds was selected as the model for the project, although a school of fish or a hive of bees or pack of dogs could just as easily been selected.

These models allow us to easily think about the required actions of one individual and then just as easily think about the whole group and how the changes made to one could affect the whole group. Further, using a model from nature makes it easier to create mental images of the operation of individual threads because the various stages in a thread's lifecycle can be mapped into easily understood stages in an animal's lifecycle. Want proof? Try explaining how a multi-threaded program works to a 5-year old. Now try explaining how a flock of birds might do some useful actions to that same 5-year old and the child will understand.

Contrast the Avian model with the standard way of writing parallel code where mutexes and locks get sprinkled throughout the code anywhere we suspect multiple threads might access some shared resource. Typically, we can't predict when the various threads will access the shared resources or when the system will interrupt a thread so all we can do is try to imagine all the possible conditions that would cause problems and then test and hope we find any actual failure conditions that we hadn't anticipated.

ConcX was developed to provide an interactive environment that allows developers to leverage the Avian model (flock of birds) to easily represent individual members of a group and then experiment with how the individuals work together to accomplish the program's goals in parallel. ConcX provides a variety of pre-built objects that can easily be customized to accomplish most any program requirements, streamlining and speeding up the job for developers. ConcX also structures and confines all locking and synchronizing to the shared TupleTree object, limiting any issues with inappropriate access of objects to just the TupleTree.

Using the Code

The following code demonstrates how a new type of bird is created, which is typically done by extending BasicBird and then overriding the appropriate methods. In the Dining Philosophers problem, the Waiter is a special purpose bird whose only work is to put five forks onto the table (into the TupleTree). The complete code is listed below and requires only 47 lines (including comments and blank lines), only 38 after blank lines are removed, and only 24 lines when comments and blank lines are removed and stand-alone curly braces moved onto other lines.

public class Waiter extends BasicBird {

   /**
    * The waiter sets the table for the philosophers by putting forks
    * into the TupleTree
    */
   @Override
   public void findFood() { //overridden so will store the forks in TupleTree
       Fork1Pod f1 = new Fork1Pod(); //creates a new instance of a Fork1Pod
       f1.setEmpty(false);           //The ForkxPods are all predefined food
       mEatBeak1.storeItem(f1, this);//pods that are used as forks

       Fork2Pod f2 = new Fork2Pod();
       f2.setEmpty(false);
       mEatBeak1.storeItem(f2, this);

       Fork3Pod f3 = new Fork3Pod();
       f3.setEmpty(false);
       mEatBeak1.storeItem(f3, this);

       Fork4Pod f4 = new Fork4Pod();
       f4.setEmpty(false);
       mEatBeak1.storeItem(f4, this);

       Fork5Pod f5 = new Fork5Pod();
       f5.setEmpty(false);
       mEatBeak1.storeItem(f5, this);

       addToBirdHistory("Table is Set - Ready to Terminate", Level.INFO);
       setStopNow(true); //this thread can now be terminated
   }

   /**
    * This method does nothing and prevents the regular digestFood method
    * from making any changes to any of the forks.
    */
   @Override
   public void digestFood() { }

   /**
    * This method does nothing and prevents the regular storeFood method from
    * storing any additional forks.
    */
   @Override
   public void storeFood () { }
}

Creating new food pods (ForkxPod) is similarly simple because it extends the BasicPod and assigns it unique identifiers. The following is the complete code to create the Fork9Pod.

package com.avian.foods.philos;
import com.avian.foods.basefoods.BasicPod;

public class Fork9Pod extends BasicPod {

   /**
    * Default (and only) constructor for this food, it calls the BasicPod
    * constructor with reasonable values for its variables
    */
   public Fork9Pod()
       super("phl09","Fork9Pod"); //constructor params = treeID, desc
       this.setPodType("Fork9Pod");
   }
}

The BasicBird code contains numerous stub methods to provide convenient ways of customizing the behavior of any bird inherits from BasicBird. For example, methods such as beforeDigesting and afterStoring, can be overriden to get exactly the desired behavior without having to modify the BasicBird code.

To learn more about Avian Computing and about programming for ConcX, download Getting Started with Avian Computing - Exploring Parallel Programming with ConcX available at aviancomputing.net or from the Avian Computing pages at SourceForge.

Points of Interest

Perhaps one of the most interesting aspects of ConcX is the absence of a main() function that sets up and/or controls the threads as is typical of most parallel programs. This has some interesting ramifications:

• The threads of the ConcX program can be individually started and stopped at will because they are not pre-defined or compiled into the main() function or some setup method. They run as independent threads and will continue to run as long as they meet their own personal criteria to continue running.
• ConcX threads are very loosely coupled. They are unaware of other threads and never directly communicate with other threads; instead data chunks (food pods) are shared asynchronously through the TupleTree. This means that the code never has to be modified to add or delete threads.
• Loosely coupled threads also allows flock behavior to be changed or rearranged simply by changing the foods that the birds eat and store. For example, in the Dining Philosophers problem, instead of sharing forks with their neighbors, the philosophers could just as easily share forks with the philosophers seated across from them, just by changing the foods the philosophers eat.
• Loosely coupled semi-autonomous threads raises the possibility that a market for special purpose bird objects could develop. For example, someone could develop and sell an Address Formatting bird that takes customer information as input and produces a properly formatted address as an output.

Conclusion

Hopefully, this article has demonstrated that it is relatively simple to solve the Dining Philosophers problem using the objects, tools, and features of ConcX. Unlike most solutions to the Dining Philosopher problem, ConcX also provides the following:

• Real-time visual feedback about how successful each individual philosopher is at eating so it is easy to verify that none of them is starving and that they are sharing the forks
• A truly asynchronous solution where each of the threads can be started/stopped independently without interrupting (or crashing) the program
• Event-recording tools to automatically capture runtime information so detailed post mortem analyses can be performed
• Ability to re-configure the various philosophers and immediately re-run the Dining Philosophers to test the impact of the configuration changes

ConcX is a general purpose solution that was built to provide developers with an environment to help them think about their parallel programs. ConcX was designed to allow developers to focus on what their program needs to do instead of being preoccupied on how to write the code that safely shares data and resources.

History

• May 7, 2018: Initial submission