Dinning Philosophers Problem

The Problem

            Five philosophers are staying round a table. At the front of every philosopher there a spaghetti dish and one philosopher needs two sticks to eat. Between two dishes there is one stick. When a philosopher feels hungry, he/she uses two sticks to eat from left and right side of the dish. If sticks are in use, he/she has to wait. Is there a way to do exactly the desired thing?

Solution 1

            Three philosophers must wait until other two philosophers are full. First solution to this problem is as follows:

do

{

            wait(chopstick[i])

            wait(chopstick[(i+1) % 5])

            …

            eat

            …

            signal(chopstick[i]);

            signal(chopstick[(i+1) % 5]);

            …

            think

            …

} while (1);

Solution 2

            Above solution have some problems. There are two “wait” and “signal” functions running consecutively. These functions are not atomic so some other process may enter between two functions and may cause deadlock. Below there is a solution:

#define N                     5

#define LEFT                (i + N - 1) % N

#define RIGHT              (i + 1) % N

#define THINKING         0

#define HUNGRY           1

#define EATING            2

typedef int semaphore;

int state[N];

semaphore        mutex = 1;

semaphore        s[N];

void philosopher(int i)

{

            while (TRUE)

            {

                        think();

                        take_chopsticks(i);

                        eat();

                        put_chopsticks(i);

            }

}

int  take_chopsticks(int i)

{

            wait(&mutex);

            state[i] = HUNGRY;

            test(i);

            signal(%mutex);

            wait(%s[i]);

}

int  put_chopsticks(int i)

{

            wait(&mutex);

            state[i] = THINKING;

            test(LEFT);

            test(RIGHT);

            signal(%mutex);

}

void test(i)

{

            if ( (state[i]==HUNGRY) && (state[LEFT]==EATING) &&  (state[RIGHT]==EATING) )

            {

                        state[i] = EATING;

                        signal(%s[i]);

            }

}

References

[1]        [1]      Tanenbaum, Andrew S., Modern Operating Systems, Second Edition, Prentice Hall, Chapter 2, page 125-127, 2002.