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 theputdown()
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.
The call to signal()
has no effect during pickup as it signals the current thread, which by definition cannot be in the waiting state.