monitor code…what follows is pseudocode for calling the routines*/ Each philosop
ID: 3582758 • Letter: M
Question
monitor code…what follows is pseudocode for calling the routines*/
Each philosopher i invokes the operations pickup() and putdown() in the following
sequence:
DiningPhilosophers.pickup(i);
EAT
DiningPhilosophers.putdown(i);
Question 3.
a. How many philosophers can eat at the same time, and how does the “test” routine make
this possible?
b. On the other hand, how does the “test” routine preserve the condition of a monitor that
only one process can be active within the monitor at one time? Hint: would “Eating” be
considered to be a state or an activity? What about pickup? What about putdown?
Explanation / Answer
The problem of the dining philosophers (originally proposed by Dijkstra) is of great importance in concurrent programming research.
Problem description: In a monastery, there are five Chinese monks who are dedicated philosophers. Each philosopher would be happy to engage only in thinking were it not occasionally necessary to eat. Thus the life of a philosopher is an endless cycle: repeat think; eat forever.
In the center of the table there is a bow of rices that is endlessly replenished; there are five plates and five chopsticks. A philosopher wishing to eat enters the dining room, takes a seat (which reserved for him), eats and then returns to his cell to think. However, it is hopeless (even for Chinese philosophers) to get any rice by only using one chopstick. Philosophers are too polite to reach across the table and pick up a spare chopstick or to eat with their hands.
Requirement:
• Safety requirement: A philosopher cannot be eating concurrently with his neighbour.
• Liveness requirement: A hungry philosopher will eventually eat assuming that a eating philosopher will be eventually full and go back his cell to think.
Monitor Code that follows the sequence pickup(), eat(), putdown():
The solution avoid deadlock by allowing at most N 1 philosophers sitting at the table.
PROGRAM din_phil; CONST N=5; VAR I: integer; PROCESS TYPE chopstick;
ENTRY pickup; ENTRY putdown;
BEGIN
REPEAT
SELECT
ACCEPT pickup DO NULL;
OR ACCEPT putdown DO NULL;
OR TERMINATE
END
FOREVER
END;
VAR chopsticks: ARRAY[1..N] OF chopstick;
PROCESS chairs;
ENTRY getchair; ENTRY replacechair;
VAR freechairs: integer;
BEGIN
freechairs:=N-1;
REPEAT
SELECT
WHEN freechairs>0 => ACCEPT getchair DO null;
freechairs:=freechairs-1;
OR ACCEPT replacechair DO null; freechairs:=freechairs+1;
OR TERMINATE
END
FOREVER
END;
PROCESS TYPE philosopher(name:integer);
VAR I:integer;
chop1, chop2: integer;
BEGIN
chop1:=name;
IF name =N THEN chop2:=1 ELSE chop2:=name+1;
FOR I:=1 TO 10 DO
BEGIN
sleep(random(5)); (*thinking*)
chairs.getchair;
chopsticks[chop1].pickup;
chopsticks[chop2].pickup;
sleep(random(5));
chopsticks[chop1].putdown;
chopsticks[chop2].putdown;
chairs.replacechair
END
END;
VAR phils: ARRAY[1..N} of philosopher;
BEGIN
COBEGIN
FOR I:=1 TO N DO
BEGIN chopsticks[I}; phils[I](I) END;
chairs
COEND
END.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.