University of Helsinki
Department of Computer Science

5.12.2005

Area to be studied: Andrews: 5.2-5.5 Monitors, pp 215-22; 7.1-7.5 Message Passing, pp 295-314, check also the case studies 5.4 and 5.5. [not included in exam],see also Stallings 5.6 Message Passing.

Goals: study the usage of monitors and message passing in synchronization. For monitors this course assumes that the signal()-operation uses signal-and-continue semantics and for message passing we use asyncronous communication with unblocking SEND and blocking RECEIVE.

1 - CORRECTLY WORKING MONITOR?

1. The monitor code given below is not always working correctly. Explain what all problems the code includes. Explain what happens when the doctor and patients get the monitor in the following orders:

   	
          i) patient1, doctor, patient2;   
          ii) patient1, patient2, doctor;   
          iii) doctor, patient1, patient2; 
   

2. Write correct code that also quarantines that the patients can go to the doctor in the order they have arrived.

       monitor Reception {
       cond in;
       cond out;
       cond check;
       boolean reserved  =  false;
          
      procedure Cometoreception( ) {    #  code for a patient 
         if (reserved) wait(in);        #  wait to get in  
         reserved = true;        #  mark  reception room reserved      
         go to the reception room 
         signal(check);    #  tell the doctor 
         examination by the doctor
         wait(out);     #  wait until allowed to leave
         leave the reception room
      }
     
      procedure Examinepatient ( ) {   # code for the doctor
         signal(in); #  call a patient in 
         wait(check); # wait for a patient to arrive o  
         examine a patient
         signal(out);   # allow a patient to leave
         reserved =false; #   mark reception room empty  
         }                                                                                                                         
      }  
      process Patient(  )[i = 1 to n]  {
         while (true)
            do what ever you do
            feel sick
            call  Reception.Cometoreception( );       
         }
      }
   
      process Doctor(  ) {
         while (true)  call Reception.Examinepatient( );
       }
   

2 - SLEEPING BARBER AND MONITOR

Andrews figure 5.10 gives a monitor solution to the sleeping barber problem.

1. Some of the while-loops can be replaced by if-statements. Determine which ones, give the reasons. Why does the given solution use while-statements? Notice that most of the time the execution of a monitor procedure is indivisible.
2. Give a solution which is as simple as possible. Assume the signal-and-continue semantics, and that there are only one barber and one chair (see Fig 5.9).

3. Suppose that the barbershop is extended: there will be several barbers. Make the required updates in the algorithm of Fig 5.10.

3 - BARRIER SYNCHRONIZATION

N processes work together on a long and heavy computation. The computation is - to some extent - fault tolerant. The processes contain several checkpoints, and when the processes reach a checkpoint they write all their state information into a disk file. The checkpointing is fully synchronized: the writing starts when all processes have reached the corresponding checkpoint, and the computation continues when all have finished their writing. The processes communicate using message passing.

What channels are needed for the communication? Write the code needed for this synchronization using channels.

4 - MESSAGE PASSING AT KORVATUNTURI

Almost all the year the flying reindeers that draw the sleigh of Santa Claus in the Christmas Eve spend their time wandering around in Lappland with other reindeers. Nearby Christmas they start gathering to Korvatunturi where Santa Claus has his Christmas present factory. When all the N flying reindeers have arrived, the leader of the team, Rudolf the Rednose, informs Santa. Santa harnesses the reindeers and the sleigh full of presents starts its journey.

When Santa has delivered all the presents to children around the world, they return to Korvatunturi. There Santa thanks the reindeers and unharnesses them to wander free with the other reindeers. Represent Santa Claus and the flying reindeers as processes that communicate using message passing. Draw a diagram showing the communication between Santa and the reindeers. Write code for Santa, Rudolf and other reindeers.

5 - SHARED SAVINGS ACCOUNT

A savings account is shared by several people. Each person may deposit or withdraw funds from the account. The balance of the account must never become negative.Write code for a server that takes care of the account. The clients may ask either for deposition or withdrawal of some amount of money. If there is not enough money on the account, the withdrawal has to wait until there are enouhg funds. The server and clients communicate using message passing.

6- DATABASE SERVER

Consider the readers/writers problem. Design such a solution to the problem where the database used is situated on a separate server and only server processes are allowed to access the database. The readers and writers interact with server using asynchronous message passing.

Show the needed message interfaces (channels) for the readers and writers to use and give the code for the server processes.

Hint: Use the monitor given in Andrews figure 5.5 to implement the mutual exclusion needed (one writer in a time, multiple readers in a time).

7- GIVE FEEDBACK ABOUT THIS COURSE

by filling the feedback form for this course (they still seem to use the old name Concurrent Systems!) but preferable after the exam so you are also able to give comments considering the exam.

If you never doubt, you probably don't know enough.