Click here to Skip to main content
15,867,141 members
Articles / Programming Languages / C#

Solving the Dining Philosophers' Problem

Rate me:
Please Sign up or sign in to vote.
4.95/5 (8 votes)
5 May 2018CPOL4 min read 16.8K   392   8   4
This article illustrates how to solve the Dining Philosophers' Problem using the Task Based Asynchronous Pattern

Introduction

This is an alternative to the excellent Dining Philosophers Problem article.

The Scenario

Five philosophers sit around a table. They each have a fork on their left hand side and an inexhaustible bowl of spaghetti in front of them. Every philosopher spends their days either eating or thinking. The time spend eating or thinking on any one occasion is random but a philosopher can only eat when both the fork on their left and the fork on their right are not being used by anyone else. Both forks become available for others to use when the philosopher finishes eating and starts thinking. There are only five forks, so everyone cannot eat at the same time.

The Problem

The problem is to design a simulation that enables all philosophers to continue to eat and think without any form of communication between participants. It follows from this that nobody is allowed to die of starvation and that no deadlocks can occur.

Analysis of the Problem

Although the scenario mentions just two states that a philosopher can be in, namely, eating or thinking, there is a third state and that is, thinking but looking for an opportunity to eat. In other words, the philosopher is hungry. So the philosopher's activities can be broken down into three consecutive phases, Thinking, Hungry and Eating.

Solution

The Task-based Asynchronous Pattern enables a series of consecutive Tasks to be performed asynchronously for each philosopher with very little additional coding. All that's required is to have a Philosopher class and a Fork class. The Philosopher class needs to have an async method that implements the three phases that the philosopher goes through and uses the ability to await the completion of a Task to manage the transition from one phase to the next. The Fork class simply needs a property, IsNotInUse, to indicate the availability of a fork.

The Thinking Phase

This phase is the easiest to implement. It lasts for a random amount of time. The timing takes place asynchronously, this allows other philosophers to change their state. It also enables the availability of the forks on the table to be updated.

C#
while (true)
          {
              Mode=PhilosopherMode.Thinking;
              int thinkingTime = random.Next(Constants.ThinkingMin, Constants.ThinkingMax);
              int eatingTime = random.Next(Constants.EatingMin, Constants.EatingMax);
              //asynchronous wait  until thinking time has passed
              await Task.Delay(TimeSpan.FromSeconds(thinkingTime), ct);
              Mode=PhilosopherMode.Hungry;
              ...

What’s happening here is that most of the code is being run on the single-threaded UI thread. The bit that isn’t is the call to await Task.Delay(TimeSpan.FromSeconds(thinkingTime), ct). This call is a sort of asynchronous wait. The UI thread is released, allowing it to run delegates posted to it by other instances of the Philosopher class. After the delay period has passed, the thread is called back to the method and it runs the continuation, that's the part after the await statement. The ct parameter passed to Task.Delay is a CancellationToken. It enables the method to be cancelled.

The Hungry Phase

The hungry phase consists of a loop that asynchronously waits for a short period of time before determining if the two required Forks are available. If they are, the loop is broken and the eating phase begins.

C#
while (!isEating)
                {
                    //monitor the two forks every few millisecs to see if they are in use
                    await Task.Delay(Constants.MonitoringIntervalMilliSecs, ct);
                    //if the forks are not in use, grab them and start eating
                    if (LeftFork.IsNotInUse && RightFork.IsNotInUse)
                    {
                        LeftFork.IsNotInUse = false;
                        RightFork.IsNotInUse = false;
                        isEating = true;
                    }

                }
                 Mode=PhilosopherMode.Eating;

The Eating Phase

C#
await Task.Delay(TimeSpan.FromSeconds(eatingTime), ct);
              //when the eating time has passed, put down the forks and stop eating
              LeftFork.IsNotInUse = true;
              RightFork.IsNotInUse = true;
              isEating = false;

The forks are a shared resource so any change in their status will be reflected in one of the adjacent philosopher’s forks. In the demo app, the eating and thinking timeframe is set to about the same range but, in reality, the eating period would be much shorter. Unless, of course, the philosopher is an Epicurean.

The Application

Image 1

The demo is a WPF application. Each philosopher is represented by a pawn chess piece image. The image is actually an outline, it is placed over a backing Rectangle so that the Rectangle’s colour forms the background colour of the image. In the Xaml, the Fill Brush of each Rectangle is bound to a Philosopher.Mode property in the viewmodel and the Visibility of each fork image is bound to a Fork.IsNotInUse property which is also in the viewmodel. This arrangement enables both types of images to change their state.

The Philosopher Class

The Philosopher class has a ModeChangedEvent and a StartAsync mehod. The StartAsync mehod manages the phases of thinking, being hungry and eating by using a series of timed awaits within a while loop.

C#
public async Task StartAsync(Random random, CancellationToken ct)
       {
           bool isEating = false;

           // the 'while' loop ends when the cancellation token cancels Task.Delay
           //and a TaskCanceledException is thrown
           while (true)
           {
               Mode=PhilosopherMode.Thinking;
               int thinkingTime = random.Next(Constants.ThinkingMin, Constants.ThinkingMax);
               int eatingTime = random.Next(Constants.EatingMin, Constants.EatingMax);
               //asynchronous wait  until thinking time has passed
               await Task.Delay(TimeSpan.FromSeconds(thinkingTime), ct);
               Mode=PhilosopherMode.Hungry;
               while (!isEating)
               {
                   //monitor the two forks every few millisecs to see if they are in use
                   await Task.Delay(Constants.MonitoringIntervalMilliSecs, ct);
                   //if the forks are not in use, grab them and start eating
                   if (LeftFork.IsNotInUse && RightFork.IsNotInUse)
                   {
                       LeftFork.IsNotInUse = false;
                       RightFork.IsNotInUse = false;
                       isEating = true;
                   }

               }
                Mode=PhilosopherMode.Eating;
                await Task.Delay(TimeSpan.FromSeconds(eatingTime), ct);
               //when the eating time has passed, put down the forks and stop eating
               LeftFork.IsNotInUse = true;
               RightFork.IsNotInUse = true;
               isEating = false;
           }
       }

This method looks like it could be refractored. But the async keyword is a compiler instruction that leads to a lot of code being generated behind the scenes. In view of this, it’s best not to refractor async methods into a series of calls to other async methods.

The ViewModel

Most of the viemodel is concerned with defining the PhilosopherMode property for every philosopher and the IsNotInUse property for each fork. The simulation is started by calling the OnStartAsync method. This method begins by calling the async Task StartAsync(Random random, CancellationToken ct) method for all the philosophers and storing the returned Tasks in a List. It then asynchronously waits for all the Tasks to complete.

C#
private async void OnStartAsync(object arg)
   {
       IsStarted = true;

       cts = new CancellationTokenSource();
       CancellationToken token = cts.Token;
       Random random = new Random();
       List<Task> philosopherTasks = new List<Task>();
       foreach (Philosopher philosopher in philosophers)
       {
           //start all the async methods and store the returned tasks
           philosopherTasks.Add(philosopher.StartAsync(random, token));
       }

       try
       {
           //asynchronously wait for all the tasks to end
           //the cancellation token will cancel them all
           await Task.WhenAll(philosopherTasks);
       }
       catch (TaskCanceledException)
       {
           IsStarted = false;
           InitialisePhilsMode();
           InitialiseForks();

       }


   }

The simulation ends when it is cancelled by simply calling the CancellationTokenSource.Cancel method.

C#
private void OnCancel(object arg)
    {
        cts.Cancel();
        IsStarted = false;

    }

Conclusion

The Task-based Asynchronous Pattern is a powerful pattern for the sequencing and management of related events. Before using Timers and BackgroundWorkers and subscribing/unsubscribing to and from numerous events, it is worthwhile considering if a Task based solution would be both simpler to implement and result in more maintainable code.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Student
Wales Wales
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
GeneralThis problem got me thinking Pin
Super Lloyd5-May-18 4:37
Super Lloyd5-May-18 4:37 
QuestionThis is a classic programming problem. Pin
--CELKO--28-Apr-18 12:01
--CELKO--28-Apr-18 12:01 
SuggestionSummary Pin
Avi Farah28-Apr-18 10:58
Avi Farah28-Apr-18 10:58 
George,

I love the fact that you used your own synchronization context in a console app so you can use async and await. Brilliant.

I wish that your program published more statistics at the end, like:
* How long did each philosopher eat
* How many times did each philosopher ate
* How many collisions did each philosopher encounter.

Thank you for the article it is very good.
Avi
GeneralRe: Summary Pin
George Swan5-May-18 23:50
mveGeorge Swan5-May-18 23:50 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.