Dinning Philosopher – C#

 

This post demonstrates another threading problem. There are many solutions for dinning philosopher problem. The famous one is to introduce a waiter for the table. Where the waiter acts as the monitor and the philosophers have to ask the waiter to take a fork. Another solution is that let the philosophers talk with themselves.

But this solution has a another simple mechanism, which avoids the dead lock by it’s own by randomizing the time a philosopher can hold a single fork. Having both the forks is not randomized, since having the both forks is a ready state for eating. So even the dead lock is about to occur it never lasts. And another threshold value is used as starvation count, which represents the maximum number of continuous thinking a philosopher can bare without considered being starved.

When running this algorithm you can notice that the philosophers may get starved (mainly if the starvation count is low) but it is almost impossible for a philosopher to starve forever.

Pure object orientation and C# techniques are used in developing this code. It is true that this code is not the best one when it comes to efficiency. This code can be improved in other ways. But still it provides a self time slicing feature for the dinning philosophers problem.

using System;
using System.Threading;

namespace DinningPhilosophers
{
    class Program
    {   
        static void Main(string[] args)
        { 
            Philosopher aristotle = new Philosopher(Table.Plastic,Table.Platinum,"Aristotle",4); 
            Philosopher palto = new Philosopher(Table.Platinum, Table.Gold,"Plato",5);
            Philosopher john = new Philosopher(Table.Gold, Table.Silver,"John Dewey",6);
            Philosopher augustine = new Philosopher(Table.Silver, Table.Wood, "Augustine",4);
            Philosopher thomas = new Philosopher(Table.Wood, Table.Plastic,"Thomas Aquinas",7);

            new Thread(aristotle.Think).Start();
            new Thread(palto.Think).Start();
            new Thread(john.Think).Start();
            new Thread(augustine.Think).Start();
            new Thread(thomas.Think).Start();

            Console.ReadKey();
        }

    }



    enum PhilosopherState { Eating, Thinking }


    class Philosopher
    {
        public string Name { get; set; }

        public PhilosopherState State { get; set; }

        // determines number of continuose thinkings, without being considered starving
        readonly int StarvationThreshold;

        // defines the right and the left side fork of a philosopher
        public readonly Fork RightFork;
        public readonly Fork LeftFork;

        Random rand = new Random();

        int contThinkCount = 0;

        public Philosopher(Fork rightFork, Fork leftFork, string name, int starvThreshold)
        {
            RightFork = rightFork;
            LeftFork = leftFork;
            Name = name;
            State = PhilosopherState.Thinking;
            StarvationThreshold = starvThreshold;
        }

        public void Eat()
        {
            // take the fork in the right hand
            if (TakeForkInRightHand())
            {
                // if got the fork in the right hand immediatley try to take the fork in the left hand
                if (TakeForkInLeftHand())
                {
                    // if got both forks then eat
                    this.State = PhilosopherState.Eating;
                    Console.WriteLine("(:::) {0} is eating..with {1} and {2}", Name, RightFork.ForkID, LeftFork.ForkID);
                    Thread.Sleep(rand.Next(5000, 10000));

                    contThinkCount = 0;

                    // place the forks back
                    RightFork.Put();
                    LeftFork.Put();
                }
                // got the right fork but not the left one
                else
                {
                    // wait for a small random period and try agian to get left fork
                    Thread.Sleep(rand.Next(100, 400));
                    if (TakeForkInLeftHand())
                    {
                        // if got the left fork then eat
                        this.State = PhilosopherState.Eating;
                        Console.WriteLine("(:::) {0} is eating..with {1} and {2}", Name, RightFork.ForkID, LeftFork.ForkID);
                        Thread.Sleep(rand.Next(5000, 10000));

                        contThinkCount = 0;

                        RightFork.Put();
                        LeftFork.Put();
                    }
                    // if couldn't get the fork even after the wait, out the right fork on the table
                    else
                    {
                        RightFork.Put();
                    }
                }
            }
            // if couldn't get fork on the right hand
            else
            {
                // get a fork the left hand
                if (TakeForkInLeftHand())
                {
                    // wait for a small random time period and then try acquire the right one
                    Thread.Sleep(rand.Next(100, 400));
                    if (TakeForkInRightHand())
                    {
                        // if got the right one then eat
                        this.State = PhilosopherState.Eating;
                        Console.WriteLine("(:::) {0} is eating..with {1} and {2}", Name, RightFork.ForkID, LeftFork.ForkID);
                        Thread.Sleep(rand.Next(5000, 10000));

                        contThinkCount = 0;

                        RightFork.Put();
                        LeftFork.Put();
                    }
                    else
                    {
                        // else put the left fork back on the table
                        LeftFork.Put();
                    }
                }
            }

            Think();
        }

        public void Think()
        {
            this.State = PhilosopherState.Thinking;
            Console.WriteLine("^^*^^ {0} is thinking...on {1}", Name, Thread.CurrentThread.Priority.ToString());
            Thread.Sleep(rand.Next(2500,20000));
            contThinkCount++;

            if (contThinkCount > StarvationThreshold)
            {
                Console.WriteLine(":ooooooooooooooooooooooooooooooooooooooooooooooo: {0} is starving", Name);
            }

            Eat();
        }

        private bool TakeForkInLeftHand()
        {
            return LeftFork.Take(Name);
        }

        private bool TakeForkInRightHand()
        {
            return RightFork.Take(Name);
        }

    }




    enum ForkState { Taken, OnTheTable }
    

    class Fork
    {
        public string ForkID { get; set; }
        public ForkState State { get; set; }
        public string TakenBy { get; set; }

        public bool Take(string takenBy)
        {
            lock (this)
            {
                if (this.State == ForkState.OnTheTable)
                {
                    State = ForkState.Taken;
                    TakenBy = takenBy;
                    Console.WriteLine("||| {0} is taken by {1}", ForkID, TakenBy);
                    return true;
                }

                else
                {
                    State = ForkState.Taken;
                    return false;
                }
            }
        }

        public void Put()
        {
            State = ForkState.OnTheTable;
            Console.WriteLine("||| {0} is place on the table by {1}", ForkID, TakenBy);
            TakenBy = String.Empty;   
        }
    }



    class Table
    {
        internal static Fork Platinum = new Fork () { ForkID = "Platinum Fork", State = ForkState.OnTheTable};
        internal static Fork Gold = new Fork() { ForkID = "Gold Fork", State = ForkState.OnTheTable };
        internal static Fork Silver = new Fork() { ForkID = "Silver Fork", State = ForkState.OnTheTable };
        internal static Fork Wood = new Fork() { ForkID = "Wood Fork", State = ForkState.OnTheTable };
        internal static Fork Plastic = new Fork() { ForkID = "Plastic Fork", State = ForkState.OnTheTable };
    }
}

Advertisements

One thought on “Dinning Philosopher – C#

  1. a friend asked me a question while we were discussing about this algorithm, whether this is a complete one. This is not a complete algorithm, bcoz the concurrency algorithms should eliminate the problems of interleaving, deadlocks, mutual exclusion and starvation. In this algorithm there is no situation for interleaving or deadlocks and mutual exclusion is guranteed.
    But concpetually there is no any prevention for the starvation problem. I’ll improve the algorithm and repost it soon. 🙂 thanx.

Comments are closed.

Powered by WordPress.com.

Up ↑

%d bloggers like this: