1.) Consider the traffic deadlock depicted in Figure 7.10. a. Show that the four

Question

1.) Consider the traffic deadlock depicted in Figure 7.10.

a. Show that the four necessary conditions for deadlock hold in this example.

b. State a simple rule for avoiding deadlocks in this system.

2.) Consider a system consisting of four resources of the same type that are shared by three processes, each of which needs at most two resources. Show that the system is deadlock free.

In pseudo code:

3.) A single-lane bridge connects the two Vermont villages of North Tunbridge and South Tunbridge. Farmers in the two villages use this bridge to deliver their produce to the neighboring town. The bridge can become deadlocked if a northbound and a southbound farmer get on the bridge at the same time. (Vermont farmers are stubborn and are unable to back up.) Using semaphores and/or mutex locks, design an algorithm in pseudocode that prevents deadlock. Initially, do not be concerned about starvation (the situation in which northbound farmers prevent southbound farmers from using the bridge, or vice versa).

OOD COD TOD CIO.. ... D D ID TD Figure 7.10 Traffic deadlock for Exercise 7.11 .

Explanation / Answer

1)

a)

1. Mutual Exclusion Condition

The resources involved are non-shareable.

Explanation: At least one resource (thread) must be held in a non-shareable mode, that is, only one process at a time claims exclusive control of the resource. If another process requests that resource, the requesting process must be delayed until the resource has been released.

2. Hold and Wait Condition

Requesting process hold already, resources while waiting for requested resources.

Explanation: There must exist a process that is holding a resource already allocated to it while waiting for additional resource that are currently being held by other processes.

3. No-Preemptive Conditon

Resources already alloicated to a process cannot be preempted.

Explanation: Resources cannot be removed from the processes are used to completion or released voluntarily by the process holding it.

4. Circular Wait Condition

The processes in the system form a circular list or chain where each process in the list is waiting for a resource held by the next process in the list.

Applying the above to the traffic problem we get:

Consider each section of the street as a resource.

The simple rule to avoid traffic deadlock is that a vehicle should only enter an intersection if it is assured that it will not have to stop inside the intersection.

It is not possible to have a deadlock involving only one single process. The deadlock involves a circular “hold-and-wait” condition between two or more processes, so “one” process cannot hold a resource, yet be waiting for another resource that it is holding. In addition, deadlock is not possible between two threads in a process, because it is the process that holds resources, not the thread that is, each thread has access to the resources held by the process.

  

Dealing with Deadlock Problem

In general, there are four strategies of dealing with deadlock problem:

1. The Ostrich Approach

Just ignore the deadlock problem altogether.

2. Deadlock Detection and Recovery

Detect deadlock and, when it occurs, take steps to recover.

3. Deadlock Avoidance

Avoid deadlock by careful resource scheduling.

4. Deadlock Prevention

Prevent deadlock by resource scheduling so as to negate at least one of the four conditions.

Now we consider each strategy in order of decreasing severity.

Deadlock Prevention

Havender in his pioneering work showed that since all four of the conditions are necessary for deadlock to occur, it follows that deadlock might be prevented by denying any one of the conditions.

1

Card reader

2

Printer

3

Plotter

4

Tape drive

5

Card punch

Now the rule is this: processes can request resources whenever they want to, but all requests must be made in numerical order. A process may request first printer and then a tape drive (order: 2, 4), but it may not request first a plotter and then a printer (order: 3, 2). The problem with this strategy is that it may be impossible to find an ordering that satisfies everyone.

Deadlock Detection

Deadlock detection is the process of actually determining that a deadlock exists and identifying the processes and resources involved in the deadlock.
The basic idea is to check allocation against resource availability for all possible allocation sequences to determine if the system is in deadlocked state a. Of course, the deadlock detection algorithm is only half of this strategy. Once a deadlock is detected, there needs to be a way to recover several alternatives exists:

These methods are expensive in the sense that each iteration calls the detection algorithm until the system proves to be deadlock free. The complexity of algorithm is O(N2) where N is the number of proceeds. Another potential problem is starvation; same process killed repeatedly.

There is also bankers algorithm to avoid deadlock altogether

2)

Yes, this system is deadlock-free.

Proof by contradiction. Suppose the system is deadlocked. This implies that each process is

holding one resource and is waiting for one more. Since there are three processes and four

resources, one process must be able to obtain two resources. This process requires no more

resources and, therefore it will return its resources when done.

3)

Using exactly one semaphore, an algorithm that prevents deadlock.

Code:

semaphore ok_to_cross = 1;

void enter_bridge() {

P(ok_to_cross);

}

void exit_bridge() {

V(ok_ to_cross);

}

Solution using Monitor:

/*the correct-direction enter function must be called before getting on

the bridge. The corresponding exit function must be called when the

thread is ready to leave the bridge.*/

monitor bridge {

int num_waiting_north = 0;

int num_waiting_south = 0;

int>

condition ok_to_cross;

int prev = 0;

void enter_bridge_north() {

num_waiting_north++;

while (on_bridge ||(prev == 0 && num_waiting_south > 0))

ok_to_cross.wait();

on_bridge=1;

num_waiting_north--;

prev = 0;

}

void exit_bridge_north() {

on_bridge = 0;

ok_to_cross.broadcast();

}

void enter_bridge_south() {

num_waiting_south++;

while (on_bridge ||(prev == 1 && num_waiting_north > 0))

ok_to_cross.wait();

on_bridge=1;

num_waiting_south--;

prev = 1;

}

void exit_bridge_south() {

on_bridge = 0;

ok_to_cross.broadcast();

}

}

Solution 2 using monitors:

Monitor Bridge {

int nWaiting=0, sWaiting=0, sOnBridge=0, nOnBridge=0;

condition north_turn, south_turn;

enterNorth() {

if (sWaiting>0 || sOnBridge>0)

{

nWaiting++;

wait(north_turn);

while (sOnBridge>0)

wait(north_turn);

nWaiting--;

}

nOnBridge++;

if (sWaiting==0)

signal(north_turn);

}

exitNorth() {

nOnBridge--;

if (nOnBridge ==0)

signal(south_turn);

}

enterSouth() {

if (nWaiting>0 || nOnBridge>0)

{

sWaiting++;

wait(south_turn);

while (nOnBridge>0)

wait(south_turn);

sWaiting--;

}

sOnBridge++;

if (nWaiting==0)

signal(south_turn);

}

exitSouth() {

sOnBridge- -;

if(sOnBridge == 0)

signal(north_turn);

}

}

1

Card reader

2

Printer

3

Plotter

4

Tape drive

5

Card punch