1 2 3
Concurrent Programming
Exercise Booklet 6: Monitors
Solutions to selected exercises (♦) are provided at the end of this document. Important: You should first try solving them before looking at the solutions. You will otherwise learn nothing.
Strategy: Signal and continue (E = W < S)
Exercise 1. Implement a monitor Counter that allows safe concurrent increments and decrements.
Exercise 2. Implement a monitor Semaphore that provides the semaphore operations (acquire and release). Does your solution guarantee freedom from starvation?
Exercise 3. Implement the following:
1. A buffer of integer numbers whose size is fixed at creation time.
2. A class producer that adds consecutive natural numbers to a buffer which is given to it at creation time.
3. A consumer class that prints on the screen the values that it obtains from a buffer which is given to it at the time of its creation.
4. A program that creates a buffer of size 2 and activates a consumeer and producer, concurrently.
Exercise 4. (♦) We wish to implement a three-way sequencer using monitors in order to coordinate
N threads. A three-way sequencer provides the following operations first, second, third. The idea is that each of the threads can invoke any of these operations. The sequencer will alternate cyclically the execution of first, then second, and finally third.
Exercise 5. We wish to implement a barrier using monitors in order to coordinate N threads. A barrier
provides a unique operation called synchronize. The idea is that each of the N threads invokes the operation synchronize and its effect is that the thread will block, and cannot continue, until all remaining threads invoke the synchronize operation. For example, if myBarrier is a barrier for coordinating 3 threads, the following use of myBarrier in each thread
thread T1: { print(’a’); myBarrier.synchronize(); print(1); } thread T2: { print(’b’); myBarrier.synchronize(); print(2); } thread T3: { print(’c’); myBarrier.synchronize(); print(3); }
guarantees that the letters will be displayed before the numbers. Supply an implementation for the barrier monitor. You may assume that once all N processes reach the barrier, they will be allowed to continue and so will all subsequent threads that call synchronize.
Exercise 6. Show that the following variation of readers/writers seen in class may deadlock. Recall that the solution in class gives priority to the writers.
CS511 - Concurrent Programming Exercise Booklet 6
monitor RW {
int readers = 0;
int writers = 0;
condition OKtoRead , OKtoWrite;
1
2
3
4
5
6
7
8 9}
public void StartRead () {
while (writers != 0 or not OKtoWrite.empty()) {
OKtoRead.wait();
1
1
2
3
4 5}
1 2 3 4 5 6
Exercise 7. In a smart energy grid connected users can either behave as consumers or producers of energy (though not both at the same time). For example, the following code fragment shows a user that behaves
as a consumer for an hour and then as a producer for two hours:
grid.startConsuming(); sleep(1h); grid.stopConsuming(); grid.startProducing(); sleep(2h); grid.stopProducing();
Address the following scenarios using monitors:
1. Users can always behave as producers, but can only behave as consumers if there is an equal or greater number of producers. Moreover, you must guarantee that a producer cannot stop producing if, in doing so, it leaves some consumer without a supply.
2. Modify your solution so that users cannot behave as producers (i.e. they block) if the grid has more than N producers.
3. Extend the previous solution so that the exit of producers is given priority over the entry of new consumers.
Exercise 8. In a local pizza shop two types of pizzas are produced: small and large. The cook places the
pizzas on a counter so that the clients can help themselves and then pay at the register. Clients may either buy a small pizza or a large pizza. In the case of large pizzas, if there are no large pizzas, they reluctantly accept two small pizzas. Clients are not polite and hence do not wait in a queue (they all compete for the pizzas).
CS511 - Concurrent Programming
Exercise Booklet 6
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
readers = readers + 1;
OKtoRead.signal();
}
public void EndRead { readers = readers -1; if (readers==0) {
OKtoWrite.signal();
} }
public void StartWrite () while (writers != 0 or
{
readers != 0) {
}
OKtoWrite.wait();
}
writers =
writers + 1;
EndWrite () {
writers =
if (OKtoRead.empty()) {
OKtoWrite.signal();
} else {
OKtoRead.signal(); };
} }
public void EndWrite () { writers = writers - 1; OKtoWrite.signal(); OKtoRead.signal();
public void
writers - 1;
The only difference is the EndWrite operation which in the slides reads as follows:
2
CS511 - Concurrent Programming Exercise Booklet 6
1. Provide a solution in which only the pizza shop is modeled.
2. Modify your solution assuming that the counter holds at most N pizzas at any given time.
Exercise 9. The organizing committee of a conference has a conference room for talks. People interested
in attending a talk enter the room and wait until the talk starts. Talks start when the speaker has arrived in the room. Participants are respectful and do not leave the room until the talk has finished. Neither do they enter when the speaker has already begun. The room has capacity for 50 participants, excluding the speaker; when the room is full, new assistants must wait until the next talk starts, after the speakers rest.
Provide a solution using monitors that takes the following scenarios into account:
1. There is only one room and the same talk is given over and over again. The speaker rests 5 minutes between talks. If, at the moment in which the talk starts, the room is empty (disregarding for the speaker), the speaker rests five minutes waiting for the assistants to arrive.
2. The same as above except that three talks take place in the room, one after the other. The speakers must wait until there are at least 40 people in the room.
3
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
monitor TWS{
int state = 1;
condition first , second , third;
CS511 - Concurrent Programming
Exercise Booklet 6
1 Solutions to Selected Exercises
void
}
void
}
void
first () {
while (state != 1)
first.wait(); state = 2;
second.signal();
second () {
while (state != 2)
second.wait(); state = 3;
third.signal();
third () {
while (state != 3)
third.wait(); state = 1;
first.signal();
}
Answer to exercise 4
4