University of Helsinki
Department of Computer Science
Concurrent Systems, Autumn 2005 / Exercises 3
22.11.2005
Suomeksi

Area to be studied: Andrews: 4.1-4.2 Semaphores: Basic Problems and Techniques, 4.4 Readers and Writers, 4.5 Resource allocation and scheduling. see also Stallings 5.4 Semaphores.

The goal is to get familiar with semaphore usage in mutual exclusion and synchronization. Also the order in which the processes are scheduled must be considered.


1- TERMS
What is meant by the folowing terms:

  1. barrier synchronization,
  2. split binary semaphore,
  3. baton passing?

2 - PRODUCERS - BUFFERS - CONSUMERS
a) Show that the semaphore-based solution to the general producer-consumer problem (Andrew, Fig. 4.5) works properly and fulfills the requirements for both mutual exclusion and synchronization (what must be checked?). Figure out how the system behaves if i) several producers, ii) several consumers are active in the time period between the operations P(empty) and P(mutexD) of a producer.

b) To solve the mutual exclusion problem the algorithm uses two semaphores (mutexD, mutexF). Assume that these are replaced with a single semaphore (mutex). How would this change affect the behavior of the system?

c) Assume that the order of the operations P(empty) and P(mutexD) is changed. How would this affect the behavior of the system? What about changing the order of V(mutexD) and V(full)? Now assume that mutexD and mutexF are replaced by using semaphore mutex, and the order of operations P(mutex) and P(full) is changed. How would this affect?

3 - SYNCHRONIZATION
Design the producers and consumers algorithm using binary semaphores, that is using such kind of semaphore operations P() and V(), where the semaphore value could only be 0 and 1.

Hint: Now the semaphore can not be used for counting units in the buffer, so you need a counter that tells you the number of units in the buffer. Set the binary semaphores to correspond the two interesting state changes in the system: "empty buffer" -> "buffer no more empty" and "full buffer" -> "buffer no more empty".

4 - A BEAR, HONEY POT AND BEES
Friendly bees are feeding a trapped bear by collecting honey for it. The life of the trapped bear is just eating and sleeping. The bees carry honey to a pot, one portion each bee each time until the pot is full. The size of the pot is H portions. When the pot is full, the bee that brought the last portion wakes up the bear. The bear starts eating and the bees wait until the bear has eaten all the honey and the pot is empty again. Then the bear starts sleeping and bees start collecting honey again.

   process bee[i=1 to N] {
       while (true) {
          collect_honey();
          store_in_the_pot();  # store a portion of honey in the pot
       }
   }

   process bear {
      while (true) {
          sleep();              # wait until the pot is full
          empty_the_pot();      # eat honey until the pot is empty
      }
   }
Write routines store_in_the_pot(), empty_the_pot() and sleep() using semaphores and P and V operations. Show that your solution functions correctly (that is explain with words). What does 'correct' mean here?

5 - SOMETIMES THERE IS ROOM FOR FOUR
A student residential home has only one bathroom, which is used both by boys and girls. In a time it can be used only either by boys or by girls. The code for Boy processes is given below:

  01: process Poika[i=1 to M]
  02: {
  03:    while (true) {
  04:       P(mutex);
  05:       count++;
  06:       if (count == 1) P(proceed);
  07:       V(mutex);
  08:
  09:       use_the_bathroom();
  10:
  11:       P(mutex);
  12:       count--;
  13:       if (count == 0) V(proceed);
  14:       V(mutex);
  15:    }
  16: }
a) Write the corresponding code for Girl processes. Give declarations for the variables used in the solution and explain their usage (For what are they used? Why are they necessary?).

b) Suppose that while the bathroom is reserved for girls, three boys arrive. Explain how the solution prohibits the Boy processes from entering the line 9: use_the_bathroom().

c) Change the solution so that there can be no more than 4 boys or 4 girls in the bathroom in a time. Explain why your solution is working correctly.

6 - sleep() and wakeup()
An operating system provides two synchronization primitives for the application programs: sleep() and wakeup(). A call of sleep() always blocks the calling process. A call of wakeup() awakens every process that is blocked at the time wakeup is called (the blocked processes have called the sleep() operation). Both operations are atomic. There are two different approaches for the implementation of the routines:
a) the wakeup() routine awakens all the sleeping processe
b) the wakeup() routine awakens the first sleeping process, and after having started each process awakens the next sleeping process (baton passing).

  01: int sleepers = 0;
  02: sem mutex = 1;
  03: sem alarm = 0;
  04:
  05: procedure sleep()
  06: {
  07:   P(mutex);
  08:   sleepers++;
  09:   V(mutex);
  10:   P(alarm);
  11: }
  12:
  13: procedure wakeup()
  14: {
  15:    P(mutex);
  16:    while (sleepers > 0) { 
  17:      V(alarm);
  18:      sleepers--;
  19:    }
  20:    V(mutex);
  21: }

Unfortunately the given solution is not working correctly. Explain why not!

Write a correct solution based on baton passing technique.

I would be a good cook, but I still have a chicken to skin.

Liisa Marttinen