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
return to thinking mode.
* 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
and return to thinking mode.
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.
public class Fork
{
public Fork(int name)
{
Name = name;
IsInUse = false;
WhichPhilosopher = null;
}
public int Name { get; }
public bool IsInUse { get; set; }
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:
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);
}
static readonly SemaphoreSlim AquireEatPermissionSlip = new SemaphoreSlim(2);
private static readonly object Sync = new object();
public int Name { get; }
private Fork LeftFork { get; }
private Fork RightFork { get; }
private PhilosopherStatus Status { get; set; } = PhilosopherStatus.Thinking;
private readonly Philosophers _allPhilosophers;
private readonly Random _rnd;
private readonly int _maxThinkDuration = 1000;
private readonly int _minThinkDuration = 50;
public void EatingHabit(CancellationToken stopDining)
{
var durationBeforeRequstEatPermission = 20;
for (var i = 0;; ++i)
{
if (stopDining.IsCancellationRequested)
{
Console.WriteLine($"Ph{Name} IS ASKED TO STOP THE DINING EXPERIENCE");
stopDining.ThrowIfCancellationRequested();
}
try
{
AquireEatPermissionSlip.WaitAsync().Wait();
Console.WriteLine($"Philosopher Ph{Name} will attempt to eat. Attempt: {i}.");
bool isOkToEat;
lock (Sync)
{
isOkToEat = IsForksAvailable();
if (isOkToEat)
AquireForks();
}
if (isOkToEat)
{
PhilosopherEat();
ReleaseForks();
}
}
finally
{
AquireEatPermissionSlip.Release();
}
Task.Delay(durationBeforeRequstEatPermission).Wait();
}
}
private bool IsForksAvailable()
{
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;
}
}
return true;
}
private void PhilosopherEat()
{
var eatingDuration = _rnd.Next(_maxThinkDuration) + _minThinkDuration;
Console.WriteLine($"Philosopher Ph{Name} is eating.");
Thread.Sleep(eatingDuration);
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):
var philosophers = new Philosophers().InitializePhilosophers();
var phEatTasks = new List<Task>();
using (var stopDiningTokenSource = new CancellationTokenSource())
{
var stopDiningToken = stopDiningTokenSource.Token;
foreach (var ph in philosophers)
phEatTasks.Add(
Task.Factory.StartNew(() => ph.EatingHabit(stopDiningToken), stopDiningToken)
.ContinueWith(_ => {
Console.WriteLine($"ERROR... Ph{ph.Name} FALTED ...");
}, TaskContinuationOptions.OnlyOnFaulted)
.ContinueWith(_ => {
Console.WriteLine($" Ph{ph.Name} HAS LEFT THE TABLE ...");
}, TaskContinuationOptions.OnlyOnCanceled)
);
Task.Delay(20000).Wait();
stopDiningTokenSource.Cancel();
Task.WaitAll(phEatTasks.ToArray());
}
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: {%..%}.
<appSettings>
<add key="Philosopher Count" value="5" />
<add key="Fork Count" value="{%Philosopher Count%}" />
</appSettings>
In order to process the special construct: {%..%} we employ a regular expression in the ConfigValue class, like so:
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:
var m = _reValue.Match(text);
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:
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:
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.
EatingHabit()
loop forever
if (CancellationToken is signalled_as_cancelled) then return
AquireEatingPermissionSlip()
if (Forks are available)
AquireForks()
PhilosopherEat( duration of eat is random up to 1 sec and 50 millisec )
ReleaseForks()
ReleaseEatingPermissionSlip()
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
