Dining Philosophers in C#

There are numerous solutions to the dining philosophers problem on the internet and I will not be reciting the story. You can find it at one of the following two links:
A few notes. Each philosopher is marked with a circle and can pick a chopstick on the left and on the right before he can eat. So, if philosopher 1 picks chopstick #5, philosopher #5 must wait for philosopher 1 to finish eating before he can pick the chopstick.
Application of this pattern could be transferring of money from one account A to another account B. Similarity would be where you have to acquire locks on A and B before money could exchange hands. That is necessary to ensure that only one transaction could go through both accounts at the same time.
Once the problem is understood the code becomes very clear. We pass in left and right chopsticks and acquire locks on them, then a philosopher can eat. It is critical in such design that objects used for locking are always passed in the same order. Here chopsticks are numbered from 1 to 5 and must always be passed in ascending order. The consequence of mixing order, for example passing chopsticks 4 to left and 3 to right for philosopher 3 randomly could cause the code to deadlock at runtime.
static public void Eat( 
    object leftChopstick,  
    object rightChopstick,  
    int philosopherNumber 
    ) 
{ 
    lock (leftChopstick)                // Grab utencil on the left 
    { 
        lock (rightChopstick)           // Grab utencil on the right 
        { 
            // Eat here 
            Console.WriteLine("Philosopher {0} eats.", philosopherNumber); 
        } 
    } 
}
What’s left is to create objects that we will use for synchronization, these are the chopsticks:
const int numPhilosophers = 5; 

// 5 utencils on the left and right of each philosopher. Use them to acquire locks. 
var chopsticks = new Dictionary<int, object>(numPhilosophers); 

for (int i = 0; i < numPhilosophers; ++i) 
{ 
    chopsticks.Add(i, new object()); 
}
Allocate tasks, one for each philosopher. Here’s an interesting part, I am using loop local variable ix instead of loop global i variable. That is due to how variables are captured by lambdas in c#. Try using i instead of ix.
Task[] tasks = new Task[numPhilosophers]; 

tasks[0] = new Task(() => Philoshoper.Eat(chopsticks[0], chopsticks[numPhilosophers - 1], 0 + 1, 1, numPhilosophers)); 

for (int i = 1; i < chopsticks.Count; ++i) 
{ 
    int ix = i; 
    tasks[ix] = new Task(() => Philoshoper.Eat(chopsticks[ix - 1], chopsticks[ix], ix + 1, ix, ix + 1)); 
}
And that’s all there is to it. Now we can execute the tasks and wait for all of them to complete:
// May eat! 
Parallel.ForEach(tasks, t => 
{ 
    t.Start(); 
}); 

// Wait for all philosophers to finish their dining 
Task.WaitAll(tasks);
I have used Parallel.ForEach loop instead of a simple for loop in order to demonstrate the task parallel library and also to randomize execution of each task without adding delay which could be done inside Eat function’s inner lock like this:
Task.Delay(5000);
And here is a possible output:
/* 
   Philosopher 2 picked 1 chopstick. 
   Philosopher 4 picked 3 chopstick. 
   Philosopher 3 picked 2 chopstick. 
   Philosopher 4 picked 4 chopstick. 
Philosopher 4 eats. 
   Philosopher 4 released 4 chopstick. 
   Philosopher 4 released 3 chopstick. 
   Philosopher 3 picked 3 chopstick. 
Philosopher 3 eats. 
   Philosopher 3 released 3 chopstick. 
   Philosopher 3 released 2 chopstick. 
   Philosopher 5 picked 4 chopstick. 
   Philosopher 5 picked 5 chopstick. 
Philosopher 5 eats. 
   Philosopher 5 released 5 chopstick. 
   Philosopher 5 released 4 chopstick. 
   Philosopher 2 picked 2 chopstick. 
Philosopher 2 eats. 
   Philosopher 2 released 2 chopstick. 
   Philosopher 2 released 1 chopstick. 
   Philosopher 1 picked 1 chopstick. 
   Philosopher 1 picked 5 chopstick. 
Philosopher 1 eats. 
   Philosopher 1 released 5 chopstick. 
   Philosopher 1 released 1 chopstick. 
*/

Summary

I hope the code will help some of you to learn concepts of thread synchronization and parallel programming.
You can download code here.

2 comments

  1. Why are you passing all the extra parameters to Eat method?

  2. You should always prefer local parameters to global. This is a simple example while in the real world you may want to be able to manipulate parameters of different types (double, complex number, etc.). You should always encapsulate.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: