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);
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.
while (!isEating)
{
await Task.Delay(Constants.MonitoringIntervalMilliSecs, ct);
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);
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;
while (true)
{
Mode=PhilosopherMode.Thinking;
int thinkingTime = random.Next(Constants.ThinkingMin, Constants.ThinkingMax);
int eatingTime = random.Next(Constants.EatingMin, Constants.EatingMax);
await Task.Delay(TimeSpan.FromSeconds(thinkingTime), ct);
Mode=PhilosopherMode.Hungry;
while (!isEating)
{
await Task.Delay(Constants.MonitoringIntervalMilliSecs, ct);
if (LeftFork.IsNotInUse && RightFork.IsNotInUse)
{
LeftFork.IsNotInUse = false;
RightFork.IsNotInUse = false;
isEating = true;
}
}
Mode=PhilosopherMode.Eating;
await Task.Delay(TimeSpan.FromSeconds(eatingTime), ct);
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();
List<Task> philosopherTasks = new List<Task>();
foreach (Philosopher philosopher in philosophers)
{
philosopherTasks.Add(philosopher.StartAsync(random, token));
}
try
{
await Task.WhenAll(philosopherTasks);
}
catch (TaskCanceledException)
{
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.
