15,167,425 members
Articles / Programming Languages / C#
Article
Posted 18 Apr 2018

33.7K views
18 bookmarked

# Dining Philosophers Problem

Rate me:
Solution to the Dining Philosophers using Semaphore (SemaphoreSlim)

## Introduction

The Dining Philosopher problem is an old problem and in the words of Wikipedia: "In computer science, the dining philosophers problem is an example problem often used in concurrent algorithm design to illustrate synchronization issues and techniques for resolving them.

"It was originally formulated in 1965 by Edsger Dijkstra as a student exam exercise, presented in terms of computers competing for access to tape drive peripherals. Soon after, Tony Hoare gave the problem its present formulation.

"Five silent philosophers sit at a round table with bowls of spaghetti. Forks are placed between each pair of adjacent philosophers.

"Each philosopher must alternately think and eat. However, a philosopher can only eat spaghetti when they have both left and right forks. Each fork can be held by only one philosopher and so a philosopher can use the fork only if it is not being used by another philosopher. After an individual philosopher finishes eating, they need to put down both forks so that the forks become available to others. A philosopher can take the fork on their right or the one on their left as they become available, but cannot start eating before getting both forks.

"Eating is not limited by the remaining amounts of spaghetti or stomach space; an infinite supply and an infinite demand are assumed.

"The problem is how to design a discipline of behavior (a concurrent algorithm) such that no philosopher will starve; i.e., each can forever continue to alternate between eating and thinking, assuming that no philosopher can know when others may want to eat or think."

## Background

The straight forward solution consisting of:

```* if left fork is available
then
pick it up
else
* if right fork is available
then
pick right fork up
initiate eating for some duration of time
then put both forks down
and returning to thinking mode
else
put left fork down

This algorithm leaves a theoretical possibility that all five (5) philosophers will pick their respective left fork, then be unable to pick right fork so return the left fork to its place and return to think, then repeat these steps forever. This is not a practical problem since we can randomize both eating and thinking times.

However, there is another path to the solution of the Dining philosophers and it is allowing an external, third party player, in our case: the operating system, to pick the next philosopher to eat using the equivalent of two (2) "allowed to eat slip" and when done eating, the philosopher will give up the "allowed to eat slip". This third party, external player, is the keeper of the "allowed to eat slip"s.

This "allowed to eat slip" can be simulated with a `Mutex`, but since we have two (2) of them, a `Semaphore` is the more appropriate choice. In our case, we will use the .NET `SemaphoreSlim`.

## Using the Code

We need to define a fork, since each philosopher needs both her/his left and right forks to eat.

C#
```public class Fork
{
public Fork(int name)
{
Name = name;
IsInUse = false;
WhichPhilosopher = null;
}

/// <summary>Name of fork</summary>
public int Name { get; }

/// <summary>Is fork in use</summary>
public bool IsInUse { get; set; }

/// <summary>If the fork is in use then keep the philosopher using it.</summary>
public Philosopher WhichPhilosopher { get; set; }
}
```

The `Philosopher` class is a bit more involved, it keeps the eating habits of the philosophers. The `EatingHabit(..)` method is the method used by each philosopher to consume spaghetti. This `EatingHabit(..)` method is the one to run concurrently for all five (5) philosophers.

The `EatingHabit(..)` method essentially begins with a wait for an "allowed to eat slip" (simulated with `SemaphoreSlim.Wait()`) then it checks for fork availability. The external entity (in our case, the operating system) grants up to 2 non-eating philosophers the permission to eat. However, if an adjacent philosopher is eating, then at least one or both forks are not available to our philosopher and as such the philosopher needs to return the "allowed to eat slip" (`SemaphoerSlim.Release()`) back to the keeper of the "allowed to eat slip"s. On the other hand, if both forks are available, then the philosopher can start consuming spaghetti, then eat for a duration of time, then release the forks and return the "allowed to eat slip" back.

A point of interest: If we employ a `SemaphoreSlim.Wait()` in our `EatingHabit(..)` method, then the thread of execution will block until the operating system will grant the philosopher permission to eat. The thread of execution can perform no other work during the wait. Using `SemaphoreSlim.WaitAsync()`, the routine will not wait and return a Task.  So it will be possible to call `SemaphoreSlim.WaitAsync().ContinueWith(..)`,  Using it this way we will allow other tasks to be serviced while we are waiting.  However, doing so meant that at the very end the `Main` routine ran to completion before one or two of the philosophers got to finish her/his last meal.  As such we will use the blocking call of `SemaphoreSlim.Wait()` or `SemaphoreSlim.WaitAsync().Wait()`.

The `Philosopher` class is as follows:

C#
```    public class Philosopher
{
public Philosopher(int name, Fork leftFork, Fork rightFork, Philosophers allPhilosophers)
{
Name = name;
LeftFork = leftFork;
RightFork = rightFork;
_allPhilosophers = allPhilosophers;

_rnd = new Random(Name); // Randomize eating time differently or each philosopher
}

/// <summary>Two (2) philosophers may eat at the same time</summary>
static readonly SemaphoreSlim AquireEatPermissionSlip = new SemaphoreSlim(2);

/// <summary>Synchronization object for acquiring forks and change status.</summary>
private static readonly object Sync = new object();

/// <summary>
/// Name of philosopher
/// The philosophers are OK with a numeric name. Philosophers are good that way.
/// </summary>
public int Name { get; }

/// <summary>Track philosopher left fork</summary>
private Fork LeftFork { get; }

/// <summary>Track philosopher right fork</summary>
private Fork RightFork { get; }

private PhilosopherStatus Status { get; set; } = PhilosopherStatus.Thinking;

/// <summary>A philosopher may inquire about other dining philosophers</summary>

/// <summary>Regulates the duration of eating</summary>
private readonly int _maxThinkDuration = 1000;
private readonly int _minThinkDuration = 50;

/// <summary>
/// The routine each Task employs for the eating philosophers
/// </summary>
/// <param name="stopDining"></param>
public void EatingHabit(CancellationToken stopDining)
{
// After eat permission was granted. The philosopher will wait for a
// duration of durationBeforeRequstEatPermission before the routine
// will repeat by waiting for an eat permission again.
var durationBeforeRequstEatPermission = 20;

for (var i = 0;; ++i)
{
// If calling routine is asking for dining to stop then comply and stop.
if (stopDining.IsCancellationRequested)
{
Console.WriteLine(\$"Ph{Name} IS ASKED TO STOP THE DINING EXPERIENCE");
stopDining.ThrowIfCancellationRequested();
}

try
{
// Wait for eating permission.
AquireEatPermissionSlip.WaitAsync().Wait();
Console.WriteLine(\$"Philosopher Ph{Name} will attempt to eat. Attempt: {i}.");

bool isOkToEat;
lock (Sync)
{
// Check for Fork availability
isOkToEat = IsForksAvailable();
if (isOkToEat)
AquireForks();
}

if (isOkToEat)
{
PhilosopherEat();
ReleaseForks();
}
}
finally
{
AquireEatPermissionSlip.Release();
}

// Wait for a duration of durationBeforeRequstEatPermission
// before waiting for eat permission.
}
}

private bool IsForksAvailable()
{
// Note that this Sync is superfluous because to be effective
// the entire method should be called under a lock (sync).
// Otherwise, after the lock when the method checks for fork
// availability and before the return, one or both forks may
// be snatched by another philosopher.
lock (Sync)
{
if (LeftFork.IsInUse)
{
Console.WriteLine(\$"Philosopher Ph{Name} cannot eat. Left fork is in use");
return false;
}

if (RightFork.IsInUse)
{
Console.WriteLine(\$"Philosopher Ph{Name} cannot eat. Right fork is in use");
return false;
}
}

// Both forks are available, philosopher may commence eating
return true;
}

private void PhilosopherEat()
{
// Eating duration is randomized
var eatingDuration = _rnd.Next(_maxThinkDuration) + _minThinkDuration;

// Display who is eating
Console.WriteLine(\$"Philosopher Ph{Name} is eating.");

//
// Simulate our philosopher eating yummy spaghetti
//

Console.WriteLine(\$"Philosopher Ph{Name} is thinking after eating yummy spaghetti.");
}

private void AquireForks()
{
lock (Sync)
{
LeftFork.IsInUse = true;
LeftFork.WhichPhilosopher = this;
RightFork.IsInUse = true;
RightFork.WhichPhilosopher = this;

Status = PhilosopherStatus.Eating;
Console.WriteLine(\$"Philosopher Ph{Name} acquired forks: " +
\$"(F{LeftFork.Name}, F{RightFork.Name}).");
}
}

void ReleaseForks()
{
lock (Sync)
{
LeftFork.IsInUse = false;
LeftFork.WhichPhilosopher = null;
RightFork.IsInUse = false;
RightFork.WhichPhilosopher = null;

Status = PhilosopherStatus.Thinking;
Console.WriteLine(\$"Philosopher Ph{Name} released forks: " +
\$"(F{LeftFork.Name}, F{RightFork.Name}).");
}
}
}```

The `Main()` routine asks the philosophers (all of them) to stop eating using a `CancellationTokenSource` construct. Since all philosophers use the same `CancellationTokenSource.Token`, a single cancellation cancels all of them. The `Main()` routine is as follows (asking the philosophers to stop dining is emboldened):

C#
```    var philosophers = new Philosophers().InitializePhilosophers();

using (var stopDiningTokenSource = new CancellationTokenSource())
{
var stopDiningToken = stopDiningTokenSource.Token;
foreach (var ph in philosophers)
.ContinueWith(_ => {
Console.WriteLine(\$"ERROR...   Ph{ph.Name} FALTED ...");
.ContinueWith(_ => {
Console.WriteLine(\$"            Ph{ph.Name} HAS LEFT THE TABLE ...");
);

// Allow philosophers to dine for DurationAllowPhilosophersToEat
// milliseconds, 20000. Original problem have philosophers dine
// forever, but we are not patient enough to wait until
// forever...

// After a duration of DurationAllowPhilosophersToEat we
// ask the philosophers to stop dining.
stopDiningTokenSource.Cancel();
}

// Done--so say so
Console.WriteLine("Done.");```

## Results

The code does not show the statistical data accumulation for simplicity's sake. The attached code is the complete code and does show the accumulation of statistical information. The following is extracted from running the simulation of the dining philosophers (tests are done on a 4-core machine):

```Philosopher Ph0 ate 15 times. For a total of 9,822 milliseconds. Eating conflicts: 9.
Philosopher Ph1 ate 14 times. For a total of 7,010 milliseconds. Eating conflicts: 21.
Philosopher Ph2 ate 17 times. For a total of 7,746 milliseconds. Eating conflicts: 15.
Philosopher Ph3 ate 15 times. For a total of 7,584 milliseconds. Eating conflicts: 13.
Philosopher Ph4 ate 11 times. For a total of 5,998 milliseconds. Eating conflicts: 22.
Collectively philosophers ate 72 times. For a total of 38,160 milliseconds. Eating conflicts: 80 ```

We should note that no philosopher starved and no philosopher ate considerably more than the other philosophers.

The total running time is 20 seconds before the `Main()` routine asked the philosophers to stop eating and step away from the table.

The total clock time for the duration of the dining experience is 20 seconds. Therefore, since there are two (2) eating philosophers, the theoretical total eating time is 40 seconds. This 40 seconds is not an exact figure, because of the nuance of the Cancellation Token. The total eating time is 43 sec and 150 millisec. (I will explain this extra 3 sec and 150 millisec at an endnote).

For simplicity's sake, we will use the value of 40 seconds as the theoretical upper limit of total eating time. The above statistical information gives us 38+ seconds of total eating time and 80 conflicts. Meaning 2- seconds were spent in conflict resolution and Task switching. Conflict, in our case, means that a philosopher who could not eat was granted eating permission, therefore the philosopher is in conflict with another philosopher. Running the program multiple times, I got total eating times as low as 35+ seconds and as high as 39+ seconds.

## Points of Interest

The full software, attached, uses the configuration file to store the constants and allow the user to change them as need be.

For the purpose, we centralized accessing the config file in a `ConfigValue` singleton class. One thing we needed is to set the number of forks to equal that of the number of philosophers. For this purpose, I set a construct, with the App.Config file like so: `{%..%}`.

XML
```<appSettings>
<add key="Fork Count" value="{%Philosopher Count%}" />

<!-- Other values -->
</appSettings>
```

In order to process the special construct: `{%..%}` we employ a regular expression in the `ConfigValue` class, like so:

C#
```private readonly Regex _reValue = new Regex(@"\{\%(?<val>.*?)\%\}", RegexOptions.Singleline);
```

This regular expression captures everything between the `{%` and the `%}` constructs in a `val` group name. One would access this group like so:

C#
```// Evaluate (match) the regular expression with the text
var m = _reValue.Match(text);

// Access the "val" group
var key = m.Groups["val"].Value;
```

This regular expression construct is not perfect, it will not evaluate nested `{%..%}` constructs correctly. But I felt that we can live with this restriction.

Digression: In order to allow for nested `{%..%}` constructs, we would have to:

• replace the text containing the delimiters `{%` and `%}` with single character value that is not used in the text (for example: `\u0001` and `\u0002`)
• the new regular expression pattern is like so: `new Regex(@"\{\%(?<val>[^\u0001\u0002]*)\%\}", ...);`.
• Then replace the single characters (`\u0001` and `\u0002` in our example) back with the `{%` and the `%}` constructs.

I felt, however, that this is needless and an overkill.

For the interested reader, you may see that solution in code. See: `Nested_config_value.linq` attached. To run it, you will need LinqPad (a freely downloadable C# interpreter). Or else, paste the code in the file `try.dot.net` into the top area of the C# fiddler in https://try.dot.net.

Back on track: So back to evaluating `appSettings` in the app.config file. We employ two methods that each access to the `appSettings` value (in the `ConfigValue` class) will call the `GetConfigValue(string key)` method:

C#
```private string GetConfigValue(string key)
{
var rawValue = _appSettings[key];
if (string.IsNullOrEmpty(rawValue)) return string.Empty;

for (; ; )
{
var m = _reValue.Match(rawValue);
if (!m.Success) return rawValue;

rawValue = _reValue.Replace(rawValue, ReplaceKey);
}
}

private string ReplaceKey(Match m)
{
var key = m.Groups["val"].Value;
if (string.IsNullOrEmpty(key)) return string.Empty;

var rawValue = _appSettings[key];
return rawValue ?? string.Empty;
}
```

Note that the raw value is captured in the `rawValue` variable which comes from an `_appSettings` construct as opposed to a `ConfigurationManager.AppSettings[key]` construct. `_appSettings` is defined in the configuration file:

C#
```private ConfigValue()
{
_appSettings = ConfigurationManager.AppSettings.AllKeys
.ToDictionary(x => x, x => ConfigurationManager.AppSettings[x]);
}
```

The reason for that gymnastics is that testing the `GetConfigValue(string key)` and `ReplaceKey(Match m)` methods would be very difficult when we use the `ConfigurationManager.AppSettings[key]` construct.

## Endnote

#### Explanation of up to 3 seconds and 150 milliseconds beyond the 40 seconds upper limit.

The 40 seconds eating time is easily explained: the program ran for 20 seconds and since there are, at most, two (2) simultaneous eating philosophers, then we have an upper limit of 40 seconds of total eating time.

To explain the overtime, let's look at the pseudocode of the `EatingHabit(..)` method which runs simultaneously for each of the eating philosophers.

C#
```/*01*/    EatingHabit()
/*02*/        loop forever
/*03*/            if (CancellationToken is signalled_as_cancelled) then return
/*04*/
/*05*/            AquireEatingPermissionSlip()
/*06*/
/*07*/            if (Forks are available)
/*08*/                AquireForks()
/*09*/                PhilosopherEat( duration of eat is random up to 1 sec and 50 millisec )
/*10*/                ReleaseForks()
/*11*/
/*12*/            ReleaseEatingPermissionSlip()
/*13*/
/*14*/            WaitForShortDuration( wait for 20 millisec );```

Now say we have two (2) eating philosophers when the `Main()` routine signals the `CancellationToken` as cancelled. (The scenario starting with one (1) eating philosopher at the time when the cancellation token was signalled is no different.)

Each one of the two routines are processing lines 8, 9 or 10. So at this point, the two (2) eating philosophers will linger on up to 1 second and 50 milliseconds during eating on line 9 before releasing the permission slip on line 12. (Time not counted: our current philosopher will, after 20 milliseconds, loop back to line 3 and stop the dining experience.)

At this point, we have up to 3 philosophers (worst case scenario is 3 philosophers) that were waiting (on line 5) to receive an eating permission slip. So, two (2) of them will receive a permission to eat and we will wait an additional time of up to 1 seconds and 50 milliseconds. So now we have up to 2 seconds and 100 milliseconds beyond the theoretical maximum.

Now we have up to 1 philosopher that waits for an eating permission. So, another 1 second and 50 milliseconds for a total of extra 3 seconds and 150 milliseconds. Making the upper limit of eating time be 43 seconds and 150 milliseconds.

## Conclusion

We have achieved our goal of a simple and efficient solution for the Dining Philosophers.

A question that remains to be dealt with is: what will happen if we take away the `SemaphoreSlim` "allow to eat slip" and allow the philosophers to attempt eating constantly where now the forks are the only criteria allowing a philosopher to eat. To run such a trial, all we need to do is comment out the calls to `AquireEatPermissionSlip.WaitAsync().Wait()` and `AquireEatPermissionSlip.Release()`. Surprisingly enough, the results are not much worse:

```Philosopher Ph0 ate  13 times. For a total of 8,271 milliseconds. Eating conflicts: 319.
Philosopher Ph1 ate  14 times. For a total of 7,010 milliseconds. Eating conflicts: 326.
Philosopher Ph2 ate  18 times. For a total of 8,031 milliseconds. Eating conflicts: 329.
Philosopher Ph3 ate  11 times. For a total of 5,768 milliseconds. Eating conflicts: 382.
Philosopher Ph4 ate  15 times. For a total of 8,502 milliseconds. Eating conflicts: 304.
Collectively philosophers ate 71 times. For a total of 37,582 milliseconds. Eating conflicts: 1660```

We now have a whopping 1,660 conflicts and total eating time of 37+ seconds. Which means that the majority of the time lost (lost from the 40 seconds theoretical upper limit) is not taken up by conflict resolution, but rather by Task switching. To test this finding further, I ran the program on an 8-core machine and got the total eating time of the 5 philosophers to `42,267` milliseconds.

## Attachments

 Zip file Description `DiningPhilosophers1.zip` The code we have been discussing, a Visual Studio 2017 solution. `Nested_config_value.zip` If interested: the ability to process nested "`{%..%}`" constructs in the configuration processing. I included a .linq file that will require LinqPad to run or plain text that one may run in the fiddler https://try.dot.net.

## History

• 4/19/2018: First publication

## Share

 United States
avifarah@gmail.com

 First Prev Next
 Task.Wait in cases Task.Delay SemaphoseSlim.WaitAsync is blocking operation ipavlu25-Apr-18 12:49 ipavlu 25-Apr-18 12:49
 Re: Task.Wait in cases Task.Delay SemaphoseSlim.WaitAsync is blocking operation Avi Farah26-Apr-18 14:45 Avi Farah 26-Apr-18 14:45
 Re: Task.Wait in cases Task.Delay SemaphoseSlim.WaitAsync is blocking operation Avi Farah26-Apr-18 17:40 Avi Farah 26-Apr-18 17:40
 Nice Tight Solution to Dining Philosophers nchamberlain24-Apr-18 21:11 nchamberlain 24-Apr-18 21:11
 Re: Nice Tight Solution to Dining Philosophers Avi Farah27-Apr-18 0:17 Avi Farah 27-Apr-18 0:17
 Re: Nice Tight Solution to Dining Philosophers nchamberlain27-Apr-18 21:30 nchamberlain 27-Apr-18 21:30
 Re: Nice Tight Solution to Dining Philosophers Avi Farah28-Apr-18 7:14 Avi Farah 28-Apr-18 7:14
 Re: Nice Tight Solution to Dining Philosophers Avi Farah27-Apr-18 0:44 Avi Farah 27-Apr-18 0:44
 Re: Nice Tight Solution to Dining Philosophers nchamberlain27-Apr-18 22:23 nchamberlain 27-Apr-18 22:23
 Re: Nice Tight Solution to Dining Philosophers Avi Farah28-Apr-18 8:03 Avi Farah 28-Apr-18 8:03
 Re: Nice Tight Solution to Dining Philosophers Avi Farah27-Apr-18 1:31 Avi Farah 27-Apr-18 1:31
 nchamberlain, Your last section is most thought provoking so let’s take a close look. Let me rephrase the question(s) so if I miss your point please let me know. Qtn 1: How is it that changing the number of cores from 4 to 8 would increase the total "eating" time? Qtn 2: How can philosophers eat more than 40 seconds? Qtn 2: I answered this question in the Endnote section. But, I got it wrong in my original publication of the article and corrected it 2 days later. Potentially you read my first version of the article. Qtn 1: is more interesting. I will point a second mistake in the article that has a bearing on your question. When I used `Task.Delay(..)` and `AquireEatPermissionSlip.WaitAsync()`, I intended to allow the thread encountering those constructs to keep on servicing other tasks. However, what I needed to do is use `Task.Delay(..).Wait()` and `AquireEatPermissionSlip.WaitAsync().Wait()` and the moment I use the `.Wait()` I blocked the thread. I was wrong in my explanation and it is a careless blunder. I will correct this in the article. So, on a 4 core machine and having 5 philosophers and one main routine we have a set of 6 running threads that are serviced by 4 cores. Therefore, we necessitate appropriate task switching. On an 8 core machine we have 8 cores servicing 6 threads and as such no need for task switching. Now, on an 8 core machine, the Endnote consideration becomes more important. With 2 simultaneously eating philosophers we have a maximum of extra eating time of 3 seconds and 150 milliseconds (extra to our 40 seconds theoretical maximum). An 8 core machine, having less (or no) task switching, can reach the maximum + extra eating time more easily. Thank you for your thought provoking questions.
 Last Visit: 31-Dec-99 19:00     Last Update: 17-Jan-22 6:45 Refresh 1