15,178,605 members
Articles / Programming Languages / C#
Article
Posted 18 Apr 2018

33.8K views
18 bookmarked

Dining Philosophers Problem

Rate me:
27 Apr 2018CPOL10 min read
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>
private readonly Philosophers _allPhilosophers;

/// <summary>Regulates the duration of eating</summary>
private readonly Random _rnd;
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)
Task.Factory.StartNew(() => ph.EatingHabit(stopDiningToken), stopDiningToken)
.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="Philosopher Count" value="5" />
<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
 Interestingly enough, I changed the `Task.Delay().Wait(..)` with `Thread.Sleep(..)` but `AquireEatPermissionSlip.WaitAsync().Wait(); ...` with C#Copy Code ```AquireEatPermissionSlip.WaitAsync().ContinueWith(_ => { Console.WriteLine(\$"{DateTime.Now:HH:mm:ss.ffff} Philosopher Ph{Name} will ... Attempt: {i}."); bool isOkToEat; lock (Sync) { // Check for Fork availability isOkToEat = IsForksAvailable(); if (isOkToEat) AquireForks(); // May throw an exception } if (isOkToEat) { PhilosopherEat(); ReleaseForks(); // May throw an exception } else ++ConflictCount; }); ``` and the result I got is: Copy Code ```22:11:01.1575 Asking philosophers to stop eating 22:11:01.1685 Ph4 IS ASKED TO STOP THE DINING EXPERIENCE 22:11:01.1695 Ph3 IS ASKED TO STOP THE DINING EXPERIENCE 22:11:01.1695 Ph1 IS ASKED TO STOP THE DINING EXPERIENCE 22:11:01.1695 Ph4 HAS LEFT THE TABLE ... 22:11:01.1695 Ph2 IS ASKED TO STOP THE DINING EXPERIENCE 22:11:01.1695 Ph1 HAS LEFT THE TABLE ... 22:11:01.1695 Ph2 HAS LEFT THE TABLE ... 22:11:01.1695 Ph0 IS ASKED TO STOP THE DINING EXPERIENCE 22:11:01.1695 Ph3 HAS LEFT THE TABLE ... 22:11:01.1705 Ph0 HAS LEFT THE TABLE ... Done. Philosopher Ph0 ate 12 times. For a total of 7,589 milliseconds. Conflicts: 942 Philosopher Ph1 ate 14 times. For a total of 7,010 milliseconds. Conflicts: 940 Philosopher Ph2 ate 22 times. For a total of 9,471 milliseconds. Conflicts: 931 Philosopher Ph3 ate 11 times. For a total of 5,768 milliseconds. Conflicts: 943 Philosopher Ph4 ate 16 times. For a total of 9,080 milliseconds. Conflicts: 937 Collectively philosophers ate 75 times. For a total of 38,918 milliseconds. Total conflict count: 4693 Press any key to exit 22:11:01.5285 Philosopher Ph2 is thinking after eating yummy spaghetti for 379 milliseconds. 22:11:01.5285 Philosopher Ph2 released forks: (F1, F2). 22:11:01.6155 Philosopher Ph4 is thinking after eating yummy spaghetti for 593 milliseconds. 22:11:01.6155 Philosopher Ph4 released forks: (F3, F4).``` It looks to me that philosophers Ph2 and Ph4 finished after the main thread because I allowed it to happen with the `AquireEatPermissionSlip.WaitAsync().ContinueWith(_ => {..});` Not wanting to rearrange the code too much and not being able to move the C#Copy Code ```if (stopDining.IsCancellationRequested) { Console.WriteLine(\$"{DateTime.Now:HH:mm:ss.ffff} Ph{Name} IS ASKED TO STOP ..."); stopDining.ThrowIfCancellationRequested(); } ``` inside the try block, I changed the `AquireEatPermissionSlip.WaitAsync().ContinueWith(..)` with `AquireEatPermissionSlip.Wait();` Thank you for your keen eye. Avi
 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
 Last Visit: 31-Dec-99 19:00     Last Update: 26-Jan-22 22:18 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

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