Operating Systems

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.

7.How does the signal ( ) operation associated with monitors differ from the corresponding operation defined for semaphores?

8.A file is to be shared among different processes, each of which has a unique number. The file can be accessed simultaneously by several processes, subject to the following constraint: The sum of all unique numbers associated with all the processes currently accessing the file must be less than n. Write a monitor to coordinate access to the file.

9. The following is a monitor implementation of the Bounded_Buffer Problem. Fill in the blanks with the proper synchronization functions, using MAX_ITEMS, 0, full.wait(), full.wakeup( ), empty.wait( ) and empty.wakeup ( )

monitor bounded_buffer {

private:

 int items [MAX_ITEMS};

 int numItems = 0;

 condition_variable full, empty;

public:

 void produce (int data) {

 while (numItems == MAX_ITEMS) 2._____________;

 items[numItems++] = data; 

 3._________________;

 }

 int consume ( ) {

 int retData; // data consumed from buffer

 while (numItems == 4._____) 5.____________

 retData = items[--numItems];

 6._______________;

 return retData;

 }

10. Servers can be designed to limit the number of open connections. For example, a server may wish to have only N socket connections at any point in time. As soon as N connections are made, the server will not accept another incoming connection until an existing connection is released. Explain how semaphores can be used by a server to limit the number of concurrent connections.