29.3. -2.4.2004

Area to be studied: Andrews 2.1-2.5 (Atomic actions and Await statements), 3.1-3.2 (Critical section problem, Spin locks), 4.1-4.2 (Semaphores), 6.3 (Implementing semaphores in a kernel). See also Stallings 5.1, 5.3-5.4 (Principles of concurrency, Mutual exclusion: hardware support, Semaphores).

The goal is to get familiar with the basic problem areas in concurrent systems, and the basic methods used for mutual exclusion and synchronisation.

1 - NOTATIONS: CONCURRENT STATEMENTS, ATOMIC ACTIONS

a) Consider the following statements

    S1:  x = x + y;
    S2:  y = x - y;
    S3:  x = x - y;
    S4:  print x,y;

Assume that x is initially 2 and that y is initially 5. For each of the following, what are the possible final values of x and y? Explain!

    1) S1; S2; S3; S4;
    2) co <S1;> // <S2;> // <S3;> oc; S4;
    3) co <await (x>y) S1; S2; > // <S3;> oc; S4;

b) Consider the following program

    int x = 0, y = 10;
    co  while (x != y)  x = x + 1;
    //  while (x != y)  y = y - 1;
    oc

Will the program terminate? Always/sometimes/never? Explain!

2 - CENTRALIZED vs REPLICATED SERVICE

A state-wide ticket-reservation service relies on one single server, which is used by all ticket offices. What types of concurrency-related problems are to be expected?

You can improve the performance of the system through introducing a replicate server (an additional server containing exactly the same data). In which respects does this increase/decrease the performance of the system?

3 - A KEY TO REALITY IS IN THE LOCK

a) If the operating system uses priority scheduling, what kinds of problems can be expected with the usage of the operations LOCK/UNLOCK? Consider both i) one-processor computers and ii) two-processor computers.

b) What parts of the operations P(sem) and V(sem) need to be programmed as critical sections (using lower level mechanisms)? How can the OS programmer implement the critical sections of the P and V operations as atomic, indivisible routines i) one-processor computers and ii) two-processor computers?

c) What are the advantages / disadvantages of programming the critical phases of P(sem) and V(sem) as short as possible instead of wrapping the whole implementation inside the critical section? Is it worth of doing?

4 - SEMAPHORES IN OUR LIVES??

a) A restaurant has a nice terrace, but there is room only for 25 customers at a time. When the terrace is full, the new customers have to wait for the room. The entry is checked in a semaphore bouncer, and a customer has to ask the semaphore, if he is allowed to go to the terrace. When the customer exits the terrace, he has to let the semaphore bouncer to know that he is leaving. Write an algorithm for the customerprocesses. Use semaphores for mutual exclusion.

b) A digger and several lorries are working in a small sandpit. Obviously, the digger is not allowed to start to fill the lorry, if there is now lorry in the pit. New lorries are not allowed to drive down to the pit, if there is already a lorry in the pit. The lorry is not allowed to leave the pit before it is fully loaded. Write the communication parts of the algorithm obeyed by the diggerprocess and by the several lorry processes. Use semaphores for synchronization.

[Don't let the nice word 'semaphore' to bluff. After all, the question is about very simple concept!]

5 - SYNCHRONIZATION IN JURASSIC PARK

Jurassic Park consists of a dinosaur museum and a park for safari riding. There are M passengers and N single-passenger cars. Passengers wander around the museom for a random time, then line up to take a ride in a safari car. When a car is available, it loads the one passenger it can hold and rides around the park for a random amount of time. If the N cars are all out riding around, then a passenger who wants to ride waits. If a car is ready to load but there are no waiting passengers, then the car waits.

The following solution uses semaphores to synchronize the passenger processes and car processes:

   01: sem car_avail = 0, car_taken = 0, car_filled = 0, passenger_released=0;
   02:
   03: process passenger[i=1 to M]
   04: {
   05:  while (true) do {
   06:          ...
   07:          sleep(random(1000*museo_time));
   08:          P(car_avail); V(car_taken); P(car_filled);
   09:          P(passenger_released);
   10:  }
   11: }
   12:
   13: process car[i=1 to N]
   14: {        
   15:  while (true) {
   16:          V(car_avail); P(car_taken); V(car_filled);
   17:          sleep(random(1000*ride_time));
   18:          V(passenger_released);
   19:  }
   20: }

Does this solution work correctly? Allways? Sometimes? Explain!