0
$\begingroup$
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;
  }
 }

The code is invoked as follows:

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

This code is taken straight from Abraham Silberschatz, Operating Systems, 9th edition. In the book, they say that the above code is a solution to the dining philosophers problem that doesn't allow deadlocks, and also guarantees mutual exclusion, i.e. two adjacent diners cannot both be eating at the same time.

But it doesn't seem true. Let's say diner 1 and 2 are next to each other, and diner 1 calls pickup(1). Inside pickup(1), Diner 1 sets his state to HUNGRY, then calls test(1). Inside test(1), DINER 1 finds that he is hungry and that his neighbors are not EATING, and therefore enters the IF statement block. At this point, let's suppose that before he is able to set his state to EATING, diner 2 runs pickup(2) and similarly also enters the IF statement in the test(2) call. Then both diners will be in a situation where they both set their state to EATING, violating mutual exclusion. What's the deal here?

$\endgroup$

1 Answer 1

1
$\begingroup$

So apparently my confusion has to do with not realizing what a monitor really is. "The monitor construct ensures that only one process at a time is active within the monitor" This means that in my example, once process 1 runs the pickup() call in the monitor, process 2 cannot begin its own pickup() call until process 1 has finished executing pickup() (or waits on a signal within that call).

$\endgroup$
1
  • 1
    $\begingroup$ So the "monitor" actually has a lock hidden somewhere. And importantly, it has one lock only, and it takes two locks to create a deadlock. $\endgroup$
    – gnasher729
    Commented Jan 5, 2023 at 12:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.