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];  /* initially false */

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.