14,027,472 members
alternative version

#### Stats

7.3K views
8 bookmarked
Posted 25 Apr 2018
Licenced CPOL

# Solving the Dining Philosophers' Problem

, 5 May 2018

## 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.

```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
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.

```while (!isEating)
{
//monitor the two forks every few millisecs to see if they are in use
//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

```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

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.

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

// the 'while' loop ends when the cancellation token cancels Task.Delay
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
Mode=PhilosopherMode.Hungry;
while (!isEating)
{
//monitor the two forks every few millisecs to see if they are in use
//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;
//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.

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

cts = new CancellationTokenSource();
CancellationToken token = cts.Token;
Random random = new Random();
foreach (Philosopher philosopher in philosophers)
{
//start all the async methods and store the returned tasks
}

try
{
//asynchronously wait for all the tasks to end
//the cancellation token will cancel them all
}
{
IsStarted = false;
InitialisePhilsMode();
InitialiseForks();

}

}
```

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

```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.

## Share

 Student Wales
No Biography provided

## You may also be interested in...

 Pro

 First Prev Next
 This problem got me thinking Super Lloyd5-May-18 4:37 Super Lloyd 5-May-18 4:37
 This is a classic programming problem. --CELKO--28-Apr-18 12:01 --CELKO-- 28-Apr-18 12:01
 Summary Avi Farah28-Apr-18 10:58 Avi Farah 28-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
 Re: Summary George Swan5-May-18 23:50 George Swan 5-May-18 23:50
 Last Visit: 20-Apr-19 6:22     Last Update: 20-Apr-19 6:22 Refresh 1