concurrencyoperating-systemcomputer-sciencemonitordining-philosopher

Dining-Philosopher's Monitor solution: Does `pickup(i)` need to invoke `self[i].signal()` indirectly?


From Operating System Concepts

5.8.2 Dining-Philosophers Solution Using Monitors

Next, we illustrate monitor concepts by presenting a deadlock-free solution to the dining-philosophers problem. This solution imposes the restriction that a philosopher may pick up her chopsticks only if both of them are available. To code this solution, we need to distinguish among three states in which we may find a philosopher. For this purpose, we introduce the following data structure:

enum {THINKING, HUNGRY, EATING} state[5];

Philosopher i can set the variable state[i] = EATING only if her two neighbors are not eating: (state[(i+4) % 5] != EATING) and (state[(i+1) % 5] != EATING).

We also need to declare

condition self[5];

This allows philosopher i to delay herself when she is hungry but is unable to obtain the chopsticks she needs.

monitor DiningPhilosophers
{

    enum {THINKING, HUNGRY, EATING} state[5];
    condition self[5];
    void pickup(int i) {

        state[i] = HUNGRY;
        test(i);
        if (state[i] != EATING)
            self[i].wait();

    }
    void putdown(int i) {

        state[i] = THINKING;
        test((i + 4) % 5);
        test((i + 1) % 5);

    }
    void test(int i) {

        if ((state[(i + 4) % 5] != EATING) &&
        (state[i] == HUNGRY) &&
        (state[(i + 1) % 5] != EATING)) {
            state[i] = EATING;
            self[i].signal();
        }

    }
    initialization code() {

        for (int i = 0; i < 5; i++)
            state[i] = THINKING;
    }

}

Figure 5.18 A monitor solution to the dining-philosopher problem.

Each philosopher, before starting to eat, must invoke the operation pickup(). This act may result in the suspension of the philosopher process. After the successful completion of the operation, the philosopher may eat. Following this, the philosopher invokes the putdown() operation.

DiningPhilosophers.pickup(i);
...
eat
...
DiningPhilosophers.putdown(i);

pickup(i) calls test(i), which in turns calls self[i].signal() when the condition suffices. Does pickup(i) need to invoke self[i].signal() indirectly?

Thanks.


Solution

  • The call to signal() has no effect during pickup as it signals the current thread, which by definition cannot be in the waiting state.