Concurrency 2 – The Dining Philosophers Problem Solution



The Dining Philosophers Problem was proposed by Dijkstra in 1965, when dinosaurs ruled the earth. It appears in a number of variations, but the standard features are a table with five plates, five forks (or chopsticks), and a big bowl of spaghetti. Five philosophers, who represent interacting threads, come to the table and execute the following loop:


while True:






Assuming that the philosophers know how to think() and eat(), write a solution to this problem

There are several synchronization constraints that we need to enforce to make this system work correctly:

* A single fork can only be held by a single philosopher

* It must be impossible for deadlock to occur

* Starvation is disallowed

* More than a single philosopher must be capable of eating simultaneously

* All must be alive at program termination. This means no implementing the solution where philosophers murder their neighbors.

* Only adjacent forks are accessible to a given philosopher.

* Both adjacent forks are required to eat.

Write concurrent code which implements a solution which satisfies the above description. A few important details:

* Each bowl of noodles is infinite.

* Eating takes a random amount of time in the range of 2-9 seconds.

* Thinking takes a random amount of time in the range of 1-20 seconds.

* The program should run indefinitely until the user kills it.

* You must have output that makes sense, and shows the correctness of your solution.

* This includes the status of all forks at all times.

* The status of each philosopher, as well.

* You are welcome to name your philosophers whatever you want, so long as they are named after real people.

* Use whatever synchronization construct you feel is appropriate.

* While you are not constrained to any given language, it is required to run on os2. There is an (older) installation of mono on os2 in /scratch/bin (–prefix=/scratch, for reference). In other words, C#, C++, C, python, ruby, perl, etc. are all usable. That said, your program *must* truly run concurrently!

* Parallelism is also up to you. pthreads, C++threads, Boost.Thread, OpenMP, Intel TBB, whatever. It’s all up to you. Again, just make sure it runs on os2.