The Problem

Five philosophers are staying round a table. At the front of every philosopher there is a spaghetti dish and one philosopher needs two sticks to eat. Between two dishes there is only one stick. When a philosopher feels hungry, he/she eats with two sticks taking from left and right side of the dish. If sticks are in use, he/she has to wait. How should a philosopher use the sticks and what he/she should do?


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]);                // take the first stick

            signal(chopstick[(i+1) % 5]);   // take the second stick

            …

            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]  Tanenbaum, Andrew S., Modern Operating Systems, Second Edition, Prentice Hall, Chapter 2, page 125-127, 2002.