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

2 - SYNCHRONIZATION

Design the producers and consumers algorithm using binary semaphores, IEe. using such kind ofsemaphorer operations P() and V(),wheree 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".

3 - 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
      }
   }

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

5 - MEMORY MANAGEMENT, SCHEDULING

We have used memory management as an example of resource management (see lecture slides Memory Management 4, slides 12 and 13). We are considering the situation where a process can reserve several pages in one request.

a) Explain the purpose and tasks of the semaphores (mutex, RQ[*].sem) used in the solution given (click here to see the solution). Show that 1) the routines obey the rules for mutual exclusion (safety properties, liveness properties) and the processes avoid starvation (that is if there are resources each process gets its share) and 2) that customers are served using FCFS order.

Explain specially what happens when the timeslice given for a process fills up in the routine GET just after V(mutex) and another process gets the processor and calls GET. Explain also what happens if the operation V(RQ[i]sem) in REL causes an immediate process switch.

b) Write the code for "request can not be satisfied", "take nbr of units for this process", "return units into pagepool" and for the handling of the request queue (i.e. show the usage of the "index pointers". Assume that the table for the implementation is big enough (QZISE items)).

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