22.11.2005 |
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:
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.
|