Operating Systems

Answer the follwoing problems on Synchronization:

1.The first known correct software solution to the critical-section problem for two processes was the developed by Dekker. The two processes, P₀ and P₁, share the following variables:

boolean flag[2]; /* initially false */

int turn;

The structure of process P_i (i = = 0 or 1) is shown in Figure 6.25 on page 231 of your text; the other process P_j (j = = 1 or 0). Prove that the algorithm satisfies all three requirements for the critical-section problem.

2. For the following solution to the critical section problem provide an explanation as to why they fail.

Solution 1:

j = 1- i;

proc (int i) {

while (TRUE) {

compute;

while (turn != i);

critical _section;

turn = j;

}

}

shared int turn;

turn = 1;

proc (0);

proc (1);

3.What is the meaning of the term busy waiting? What other kinds of waiting are there in an operating system? Can busy waiting be avoided altogether? Explain your answer.

4. Explain why implementing synchronization primitives by disabling interrupts is not appropriate in a single-processor system if the synchronization primitives are to be used in user-level programs.

5.Does Petersons solution to the mutual exclusion problem work when process scheduling is preemptive? How about when it is non-preemptive?

6. 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. Using semaphores, write code fragments to define synchronization for the customers and the barber.