|
|
Area to be studied: Andrews: 4 Semaphores,
Stallings 6.1-6.6: Concurrency - Deadlock and Starvation.
In these exercises, semaphores are used for mutual exclusion and synchronization. Also basics of deadlocks are handled.
1 - 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.
2 - 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.]
3 - 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.)
4 - 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.]
5 - BANKERS 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 6 units of A, 4 units of B, and 4 units of C. The
system is in the following state:
prosessi allocated maximum
A B C A B C
P1 2 2 2 2 3 2
P2 4 1 0 5 1 1
P3 0 0 1 2 2 2
The process P2 requests for one additional unit of C. Can it be granted? Give your reasons.
What if it would have been P3 requiring one additional A unit? Obviously the request cannot be granted, but what happens then?
|
|