Dining Philosopher Problem and AutoResetEvent.


Introduction

Full code can be downloaded from here.

I think we all know the famous classic problem of dining philosopher. In this problem, we consider n philosophers sitting in round table and n forks and all of them want to eat the spaghetti in front of each one. To eat spaghetti, philosopher must have two forks. The problem is philosopher 1 is taking one fork and waiting philosopher2 for second fork. Similarly, philosopher 2 is taking a fork and waiting philosopher3 for a fork. And philosopher n is taking a fork and waiting philosoper1 for a fork. So, what is actually happening is each philosopher cannot get the two forks at a time because each philosopher is taking a fork and waiting. So, here is the DEADLOCK.

For 5 philosophers we can assume the figure


Fig: Dining Philosopher Problem

Similar incident can be happens in our program and operating system where many processes are struggling to get the resources. There are certain criteria which must meet to cause the deadlock. They are:

1. Each resource can be used by only one thread or process.
2. Thread/Process is holding a resource and waiting for other resource to continue.
3. Resources those are granted previously cannot be forcibly taken away.
4. There must be chain of threads/processes (more than two); each is waiting for the resource held by next
thread/process.

To avoid deadlock, we can negate any of the above conditions. For dining philosopher problem, we will negate the second condition to avoid deadlock.

Code
Full code can be downloaded from here.
I have used AutoResetEvent to implement the dining philosopher problem. I have used one AutoResetEvent as mutex and n others as philosopher events.
There are three states of philosopher.

    enum State
    {
        Thinking,
        Eating,
        Hungry
    }

Let’s look at the code:

private void TakeForks(int i)
        {
            _mutex.WaitOne();
            _philosophersState[i] = State.Hungry;
            TryGetForks(i);
            _mutex.Set();
            _philosopherEvents[i].WaitOne();
        }

        private void TryGetForks(int i)
        {
            if (_philosophersState[i] == State.Hungry &&
                _philosophersState[right(i)] != State.Eating &&
                _philosophersState[left(i)] != State.Eating)
            {
                _philosophersState[i] = State.Eating;
                _philosopherEvents[i].Set();
            }
        }

        private void PutForks(int i)
        {
            _mutex.WaitOne();
            _philosophersState[i] = State.Thinking;
            TryGetForks(right(i));
            TryGetForks(left(i));
            _mutex.Set();
        }

First of all philosopher tries to take both fork. If it is not possible, it waits for the signal from its left and right. Whenever it gets the signal, philosopher again tries to acquire both forks and same process repeats.

void checkForConflict(int i)
        {
            if (_philosophersState[left(i)] == State.Eating)
                Console.WriteLine("Conflict between " + left(i) + " and " + i);
            if (_philosophersState[right(i)] == State.Eating)
                Console.WriteLine("Conflict between " + i + " and " + right(i));
        }

Above code checks for the conflict and displays conflict message whenever two philosophers try to eat using same resource. Our program mustn’t print the conflict messages.

Conclusion
Dining philosopher is a classic deadlock problem of operating system. Every deadlock can be avoided by negating any of the four essential conditions of deadlock.

I have used AutoResetEvent as mutex and for signalling purpose. However, we can use others also.