15.11.2005

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
   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;

2. DOES THE EXECUTION TERMINATE?
   Consider the following program:

     
       co  <await (x > 0)   x = x - 1;>   /*S1*/
       //  <await (x < 0)   x = x + 2;>   /*S2*/
       //  <await (x == 0)  x = x + 5;>   /*S3*/  
       oc
   

   For what initial values of x does the program terminate? What are the corresponding final values? Explain your answer.

3. PROCESS SYNCRONIZATION
   Processes can be syncronized using semaphores to perform in certain order. Show how the following processes can be forced to execute their write commands in such order that that together they output the following sentence:Ihminen, joka ei tee virheitä, ei tavallisesti tee muutakaan.

       P1                                P2                           P3
      .....                            ......                       .......
   write("tee virheitä, ");         write("joka ei ");          write("Ihminen, ");  
      .....                         write("ei tavallisesti ");       ..... 
   write("tee muutakaan.");            .......   
     .......  
   

4. A KEY TO REALITY IS IN THE LOCK
   1. 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.
   2. Is it posssible to implement LOCK and UNLOCK operations just by disabling interrupts.
   3. 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?
   4. 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?

5. SEMAPHORES IN OUR LIVES??
   1. 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.
   2. 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.

6. 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: }

   Explain for what the semaphores car_avail, car_taken, car_filled and passenger_released are used and how they synchronize passenger and car processes. Does this solution work correctly? Allways? Sometimes? Explain!

   The key to learning is in the curiosity.