|
|
Area to be studied: Andrews: 4 Semaphores,
Stallings 6.1-6.6: Concurrency - Deadlock and Starvation. Andrews 5. Monitors pp. 203-215.
In these exercises, semaphores and monitors are used for mutual exclusion and
synchronization. Also basics of deadlocks are handled.
1 - TUNNEL, ONE-WAY TRAFIC AND "SEMAPHORE LIGHTS"
There is a one-way tunnel through the mountain. Cars coming from the
same direction can drive through the tunnel at the same time, meanwhile
cars heading from opposite direction have to wait until the tunnel is
empty. Before the car can drive into the tunnel, it has to use
operation enter_tunnel(direction) to ask the permission to
proceed. And when the car leaves from tunnel it has to call operation
exit_tunnel(direction). The direction is the driving direction:
from south to north or from north to south. The code for the cars is
process car[1 to N] {
...
enter_tunnel(direction);
drive_in_tunnel();
exit_tunnel(direction);
}
Give the code for the operations enter_tunnel() and exit_tunnel(). The solution must permit multiple cars in tunnel driving in same direction. But it need not to be fair: therefore the waiting times on the tunnel opening may be very long. Show that your solution is working.
[Hint: you need separate counters and semaphores for each direction.]
2 - MERRY-GO-AROUND
Suppose there are N customer processes and one vehicle process (vehicle = merry-go-round, carousel, roller coaster, for example). The customers repeatedly wait to take rides in the vehicle, which can hold C customers in a time (C < N). However, the vehicle is started for a ride only when it is full. After each ride all customers continue with some other activities before returning to maybe get a new ride.
Develop code for the actions of the customer and vehicle processes. (Notice: for the customer, sitting in the vehicle is just waiting.)
3 - DINING PHILOSOFERS
a) The dining philosophers represent a classical problem statement in the litterature. What is the problem this example is expected to illustrate? What are in the real world the philosophers, forks, spaghettis, and possibly available secretaries (who can provide the philosophers with forks)?
There are three conditions which must be present for a deadlock to be possible. How is each of these conditions fullfilled in the dining philosophers problem?
Would it be possible to prevent a deadlock in the dining philosophers problem by changing the rules. (Rethink the above conditions.)
b) Philosophers find out, that only two of them can be eating in a
time. Therefore they throw one fork away, and make an agreement that
one can use any two forks that are available. They employ a waiter and
a dish washer to take care of the forks. When a philosofer gets hungry,
he goes to table and asks waiter for two forks. If there are no forks
available, the philosofer has to wait. When the philosofer has eat, he
returns the forks to the dish washer, who washes them and gives the
forks to the waiter. Here is the code for the philosofers:
process philosopher[i=1 to 5]
{
while (true) {
think();
V(request_forks);
P(start_to_eat);
eat();
V(release_forks);
}
Give the code for the waiter process and for the dish washer process. [Note: When there are two separate events to wait, the easiest way to implement is to have an own process for both.]
4 - BANKER'S ALGORITHM
Use the Banker's algorithm to solve the following resource allocation
problem. The system contains three different types of resources: A, B
and C. There are 9 units of A, 3 units of B, and 6 units of C. The
system is in the following state:
process allocated required maximum demand
A B C A B C A B C
p1 1 0 0 0 0 0 3 2 2
p2 5 1 1 1 0 1 6 1 3
p3 2 1 1 0 0 0 3 1 4
p4 0 0 2 0 0 0 4 2 2
The process p2 requests for one additional unit of A and C. Can it be granted? Give your reasons by showing the different steps of the banker's algorithm. What happens after executing the banker's algorith?
What if it would have been p1 and not p2, requiring one additional A and one additional C unit?
5 - MONITORBATHS
monitor Bathroom {
cond bath_free;
int girls = 0;
int boys = 0;
procedure Enter_Boy (){
if (girls !=0) wait (Bath_free);
boys ++;
}
procedure Enter_girl(){
if (boys!=0) wait(Bath_free);
girls++;
}
procedure Exit_boy(){
boys --;
if (boys==0) signal_all(Bath_free);
}
procedure Exit_girl (){
girls--;
if (girls==0) signal_all(Bath_free);
}
}
2 - THE BEAR AND THE HONEYBEES AND THE 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.
|
|