8.9.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 - READING PROGRAM CODE

a) In the slide 1-50 and also in the course book on page 25 is shown the code for workers. Explain in detail what the worker processes do to fullfill their task.

b) The worker processes are communicating with a coordinator process. Write the code for this coordinator.

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) Is it posssible to implement LOCK and UNLOCK operations just by disabling interrupts.

c) 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?

d) 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!