Deadlock

Deadlock - Occurs when resources needed by one process are held by some other waiting process.

Deadlock not only occurs in OS.

Kansas state legislature in the early 20^th century passed the following legislation:

"When two trains approach each other at a crossing, both shall come to a full stop and neither shall start up again until the other has gone. "

Assume we have the following operating system:

1. Finite number of resources to be distributed among some number of competing processes

2. Resources may be of several types and there may be several instances of each

3. When a process requests a resource any instance of that resource will satisfy the process

4. Processes can

a. request a resource

b. use the resource

c. release the resource

5. A set of processes is in a deadlock state when every process in the set is waiting for an event that can be caused only by another process in the set.

a. Same resource type - three tape drives, three processes request a tape drive then they each request another. Dining philosophers request chopsticks held by another.

b. Different resource type - process A has a printer process B has a file, Each requests the other's resource.

Four Necessary Conditions for Deadlock

1. Mutual exclusion: At least one resource is not sharable, i.e. can only be used by one process at a time

2. Hold and wait: A process holds at least one resource and requests resources held by other processes

3. No preemption: resource cannot be preempted, it must be voluntarily released by the process.

4. Circular wait: Given a set of processes { P1, P2, P3, …Pn} P1 has a resource needed by P2, P2 has a resource needed by P3, …, Pn has a resource needed by P1.

System resource-allocation graph

G = (V,E) where V is a set of vertices and E is a set of edges.

The set of vertices is partitioned into Processes and Resources. A resource-allocation graph is a directed graph where an edge from process P_i to resource R_i indicates that P_i has requested R_i (request edge). An edge from R_i to P_i indicates that R_i has been allocated to P_i (assignment edge).

When drawing the graph, processes are represented by circles and resources by squares. Multiple instances of a resource are represented by a dot in the square.

When a process requests a resource a request edge is drawn. When the resource is allocated, the resource edge becomes an assignment edge. Resource edges points to the resource square, but assignment edges are from the dots within the square.

Resource allocation graph, no deadlock

If the graph contains no cycles, then there is no deadlock

If the graph contains a cycle then a deadlock condition may exist.

Resource allocation graph with deadlock.

Resource allocation graph with cycle and no deadlock.

P4 can release an instance of R2 and P3 will be assigned the resource

How can we handle deadlocks?

1. Try to prevent them from happening

2. After system is deadlocked employ some mechanism to detect the deadlock and then recover from deadlock.

3. Ignore the problem, theoretically rare, and pretend deadlocks never occur (UNIX) Since deadlocks are infrequent this may be cheaper alternative

Deadlock Prevention - Make sure one of the 4 necessary conditions for deadlock doesn't hold.

1. Mutual Exclusion - some resources are sharable. Some cannot be shared or be made sharable. A printer can be used by only one process at a time.

2. Hold and Wait - Whenever a process requests one resource make sure it is not holding another resource.

· method 1 - request all resources before it begins execution,

· method 2 - request resources only when process has none, it may request some resources, use them and then release all resources.

· Downside - method 1 - assume process needs to copy file from tape to disk and then print. It will be holding printer entire time even though it needs it only at the end.

· Downside method 2 - process can request tape and disk, release these and then request printer. Only if file remains on disk!! No guarantee.

· Poor resource utilization, chance of starvation

3. No Preemption-

· method 1 - process holds resources and needs another resource that is not in use. Process must release all resources, then waits on released resources in addition to the needed one

· method 2 - check if resources are available when requested, if so allocate them. If not check if they are allocated to another process that is waiting for resources. If so, preempt the desired resources from the waiting process and allocate them to the requesting process. If the requested resource is not available, then the process waits. It can then be preempted by another process in the same way.

4. Circular Wait

· Place an ordering on the resource types. Processes have to request resources in increasing order of numbering

· Alternately, when a process requests a resource of a lower number, resources of higher number are deallocated.

deadlock prevention can have the side effect of reduced system throughput and low device utilization.

Deadlock Avoidance

Processes declare in advance what its maximum resource usage will be. Use this a priori information about a process' resource needs to make sure a system never enters deadlock. (deadlock avoidance approach) Dynamically makes sure that the circular wait conditions doesn't exist.

Def. A system is in a safe state if it can allocate resources to each process, in some order and avoid deadlock.

A system is a safe system if there exists a safe sequence. A sequence of processes <P₁, P₂, P₃, …, P_n > is a safe sequence for the current allocation state if for each P_i, the resources that P_i can still request can be satisfied by the currently available resources plus the resources held by all the P_j, with j<i.

In this state if a process requests a resource and it isn't currently available, it can wait until the other processes finish and then use the resources. The next process in the sequence can finish in the same manner. If this doesn't happen the state is unsafe. Unsafe states may lead to deadlock.

	Maximum Needs	Current Needs
P0	10	5
P1	4	2
P2	9	2

If system has 12 tape drives we are in a safe state because, < P₁, P₀, P₂> satisfies the safety condition.

If we are in the above state and grant P₂ 1 more tape drive the system is no longer safe.

Resource-Allocation Graph Algorithm

Used only when there is one instance of each resource.

Request edges, assignment edges, new edge called claim edge.

Claim edge from process to resource indicate process may request that resource some time in the future. Represented by a dashed arrow. Direction is the same as a request edge.

When process requests resource, claim edge becomes request edge. When process releases a resource, assignment edge becomes claim edge.

If a process requests a resource, the request can be granted only if converting the request edge to an assignment edge does not result in a cycle in the graph.

Safe, but if P2 were to request R2 then we would not be in a safe state

Banker's Algorithm

Used for multiple resource instances.

1. Processes must declare maximum instances of each resource that it will need. Number can't exceed the total number of resources in the system

2. Process will be allocated resources only if this results in a safe state. Otherwise process waits until some other process releases resources.

Given two vectors (arrays), X and Y of length n, X <= Y iff X[i] <= Y[i] for all i = 1,2,…,n. i.e. if X = (1,7,3,2) and Y = (0,3,2,1) then Y <=X.

int available [j] //each array position indicates the number of instances of

// resource R_j

int max [n][m] // Rows represent processes, columns resources, value is

//maximum number of resource R_j needed by process P_i

int allocation [n][m] //number of resources of each type allocated to each

//process

int need [n][m] //remaining resource needs of each process.

Safety Algorithm:

<step 1>

int work[m]

int finish [n]

work = available;

for (i = 0; i < n; i++) finish [i] = false;

<step 2 >

Find i such that both

finish [i] = false

need_i <= work //let need_i be the need vector for process P_i

if i doesn't exist goto step 4.

<step 3>

Work = work + allocation

finish[i] = true

go to step 2

<step 4>

If finish[i] = true for all i then the system is in a safe state.

requires order m x n² operations to decide whether a state is safe

Resource Request Algorithm

Step 1

if request_i < need_i goto step 2, else error request is above maxium

step 2

if request_i < available go to step 3, else process waits

step 3

System pretends to allocate resource

available = available - request

allocation = allocation + request

need = need - request

If this results in a safe state, then resource is allocated, else it is not.

	Allocation	Max	Available
	A B C	A B C	A B C
0	0 1 0	7 5 3	3 3 2
1	2 0 0	3 2 2
2	3 0 2	9 0 2
3	2 1 1	2 2 2
4	0 0 2	4 3 3

	Need (Max - Allocation)
	A B C
0	7 4 3
1	1 2 2
2	6 0 0
3	0 1 1
4	4 3 1

System is safe. (P1, P3, P4, P2, P0 ) is a safe sequence.

What happens if P1 requests one of A, two of type C (1 0 2)

We now have the following state:

	Allocation	Max	Available
	A B C	A B C	A B C
0	0 1 0	7 5 3	2 3 0
1	3 0 2	0 2 0
2	3 0 2	9 0 2
3	2 1 1	2 2 2
4	0 0 2	4 3 3

This is safe since <P1, P3, P4, P0, P2> is a safe sequence

P4 requests 3 3 0?

P0 requests 0 2 0?

Deadlock Detection

In absence of deadlock prevention and avoidance, we need deadlock detection.

Consists of two things: algorithm to detect deadlock, algorithm to recover from deadlock.

detection - recovery includes the overhead incurred by recovery from deadlock and algorithms.

Wait-for graph - Used for single resource instances. - Obtained from resource-allocation graph by removing resource nodes and deleting appropriate edges.

int available [m] //each array position indicates the number of instances of

// resource R_j

int request [n][m] // indicates current request of each process

int allocation [n][m] //number of resources of each type allocated to each

//process

<step 1>

int work[m]

int finish [n]

work = available;

for (i = 0; i < n; i++) if allocation_i != 0 finish [i] = false else finish[i] = true

<step 2 >

Find i such that both

finish [i] = false

request_i <= work //let request_i be the request vector for process P_i

if i doesn't exist goto step 4.

<step 3>

work = work + allocation

finish[i] = true

go to step 2

<step 4>

If finish[i] = false for all i then the process P_i is in deadlock.

	Allocation	Request	Available
	A B C	A B C	A B C
0	0 1 0	0 0 0	0 0 0
1	2 0 0	2 0 2
2	3 0 3	0 0 0
3	2 1 1	1 0 0
4	0 0 2	0 0 2

Not deadlocked p0, p2, p3, p1, p4 is a safe sequence

	Allocation	Request	Available
	A B C	A B C	A B C
0	0 1 0	0 0 0	0 0 0
1	2 0 0	2 0 2
2	3 0 3	0 0 1
3	2 1 1	1 0 0
4	0 0 2	0 0 2

P2 makes additional request for 1 more item.

Now deadlocked.

Overhead in running detection algorithms. Run each time a request is made?? Run as often as deadlock is to occur. (Once per hour, or when CPU utilization drops below 40%.

Recover from deadlock.

Tell operator, he decides who shall live and who shall die!

Abort all deadlocked processes - cost is high. All work done by processes is lost.

Abort one at a time until deadlock no longer exists - need to run deadlock detection algorithm after each process is aborted - high overhead this way.

Resource Preemption –Choose a blocked resource

–Preempt it (releasing its resources)

–Run the detection algorithm

–Iterate if until the state is not a deadlock state

Problem: Starvation – same process may always be picked as victim, include number of rollback in cost factor.