Operating Systems
Homework
#4
Due:
2007/5/22
1.
The first known correct software solution to the
critical-section problem for two processes was developed by Dekker. The two processes, P0 and P1, share
the following variables:
boolean
flag [2]; /* in
int turn;
The
structure of process Pi (i ==
0 or 1) and Pj (j ==
1 or 0) are shown in the following figure. Prove that the algorithm
satisfies all three requirements for the critical-section problem.
do {
flag [i] =
true;
while
(flag [j]) {
if (turn
== j) {
flag [i] =
false;
while
(turn == j)
; // do
nothing
flag [i] =
true;
}
}
// critical
section
turn = j;
flag [i] =
false;
// remainder
section
} while (true);
2.
Explain why spinlocks are not appropriate for single-processor systems
yet are
often used in multiprocessor
systems.
3.
The
Sleeping-Barber Problem. A barbershop consists of a waiting room with n chairs and a barber
room with one barber chair. If there are no customers to be served, the barber
goes to sleep. If a customer enters the barbershop and all chairs are occupied,
then the customer leaves the shop. If the barber is busy but chairs are
available, then the customer sits in one of the free chairs. If the barber is
asleep, the customer wakes up the barber. Write a program to coordinate the
barber and the customers.
4. Write a
bounded-buffer monitor in which the buffers (portions) are embedded within the
monitor itself.