Click here to Skip to main content
13,737,646 members
Click here to Skip to main content
Add your own
alternative version

Tagged as

Stats

13.4K views
274 downloads
18 bookmarked
Posted 18 Apr 2018
Licenced CPOL

Dining Philosophers Problem

, 27 Apr 2018
Rate this:
Please Sign up or sign in to vote.
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
      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;
    }

    /// <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:

    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.
                Task.Delay(durationBeforeRequstEatPermission).Wait();
            }
        }

        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
            //
            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)
            );

        // Allow philosophers to dine for DurationAllowPhilosophersToEat
        // milliseconds, 20000. Original problem have philosophers dine 
        // forever, but we are not patient enough to wait until 
        // forever...
        Task.Delay(20000).Wait();

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

    // 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: {%..%}.

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

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:

// 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:

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.

/*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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Avi Farah
United States United States
avifarah@gmail.com

You may also be interested in...

Pro

Comments and Discussions

 
SuggestionTask.Wait in cases Task.Delay SemaphoseSlim.WaitAsync is blocking operation Pin
ipavlu25-Apr-18 11:49
professionalipavlu25-Apr-18 11:49 
GeneralRe: Task.Wait in cases Task.Delay SemaphoseSlim.WaitAsync is blocking operation Pin
Avi Farah26-Apr-18 13:45
memberAvi Farah26-Apr-18 13:45 
GeneralRe: Task.Wait in cases Task.Delay SemaphoseSlim.WaitAsync is blocking operation Pin
Avi Farah26-Apr-18 16:40
memberAvi Farah26-Apr-18 16:40 
QuestionNice Tight Solution to Dining Philosophers Pin
nchamberlain24-Apr-18 20:11
membernchamberlain24-Apr-18 20:11 
AnswerRe: Nice Tight Solution to Dining Philosophers Pin
Avi Farah26-Apr-18 23:17
memberAvi Farah26-Apr-18 23:17 
GeneralRe: Nice Tight Solution to Dining Philosophers Pin
nchamberlain27-Apr-18 20:30
membernchamberlain27-Apr-18 20:30 
GeneralRe: Nice Tight Solution to Dining Philosophers Pin
Avi Farah28-Apr-18 6:14
memberAvi Farah28-Apr-18 6:14 
AnswerRe: Nice Tight Solution to Dining Philosophers Pin
Avi Farah26-Apr-18 23:44
memberAvi Farah26-Apr-18 23:44 
GeneralRe: Nice Tight Solution to Dining Philosophers Pin
nchamberlain27-Apr-18 21:23
membernchamberlain27-Apr-18 21:23 
GeneralRe: Nice Tight Solution to Dining Philosophers Pin
Avi Farah28-Apr-18 7:03
memberAvi Farah28-Apr-18 7:03 
AnswerRe: Nice Tight Solution to Dining Philosophers Pin
Avi Farah27-Apr-18 0:31
memberAvi Farah27-Apr-18 0:31 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

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

Permalink | Advertise | Privacy | Cookies | Terms of Use | Mobile
Web01-2016 | 2.8.180920.1 | Last Updated 27 Apr 2018
Article Copyright 2018 by Avi Farah
Everything else Copyright © CodeProject, 1999-2018
Layout: fixed | fluid