University of Helsinki
Department of Computer Science

29.11.2004

Area to be studied: Andrews: 5.1-5.2 Monitors, check also the case studies 5.4 and 5.5. [not included in exam], 7.1-7.5 Message Passing.
See also Stallings 5.6 Mesage Passing.

Goals: study the usage of monitors in synchronization. This course assumes that the signal()-operation uses signal-and-continue semantics.

1 - READERS, WRITERS AND MONITOR

Using a monitor, write a solution for the readers/writers problem (see fig. 5.5.) where the writers have a higher priority than the readers (after a writer has arrived no reader is allowed to enter the reading phase). Give also the code for the reader and writer processes.

2 - THE BEAR AND THE HONEYBEES AND MONITOR

Bees feed a trapped bear by collecting honey for it into a pot. The trapped bear just eats and sleeps. Each bee repeatedly gathers one portion of honey and puts it into the pot. The bee who fills the pot awakens the bear. The bear sleeps until the pot is full (H portions), then eats all honey and goes back to sleep. The bees wait untill the pot is empty and again start filling it. Program the filling and empying of the pot with a monitor and write code for the bear and the N bee processes. Explain also in which situation exclusion and synchronization is needed and how that is implemented in your solution.

3 - MEMORY MANAGEMENT AND MONITOR

The problem 5 in exercises 3 considered memory allocation when customers can request as many pages as they like. Write the corresponding routines (using a monitor) for the following cases:

a) memory is allocated immediately when the request can be satisfied although there might be former requests in queue. Give the solution based on the "covering condition" method,

b) as in a) but use "baton passing" method,

c) memory is allocated using the FCFS policy and the solution is based on the "condition passing" method.

4 - SLEEPING BARBER AND MONITOR

Figure 5.10 gives a solution to the sleeping barber problem.

a) 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.

b) 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).

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

5 - 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.

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