Operating System - Deadlock

Deadlock Characterization

 

Deadlock can arise if four conditions hold simultaneously

 

1. Mutual Exclusion : Only one process at a time can use a resource

 

2. Hold and Wait : A process holding at least on resource is waiting to acquire additional resources held by other processes

 

3. No Preemption : A resource can be released only voluntarily by the process holding it, after that process has completed its task

 

4. Circular Wait : There exists a set of circular waiting(P0 waiting P1 resource, P1 waiting P0 resource.)

 

If a system is safe state => No Deadlocks

If a system is in unsafe state => Possibility of Deadlock

 

Ensure system will never enter Deadlock =  Deadlock Prevention, Deadlock Avoidance

 

Deadlock Prevention

 

Invalidate one of the four necessary conditions for Deadlock

 

1. Mutual Exclusion : Not required for sharable resources. Must hold for non-sharable resources

 

2. Hold and Wait : Must aurantee that whenever a process requests a resource, it does not hold any other resources (Low resource utilization => Starvation possible)

 

3. No Preemption : If process that is holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are released

 

4. Circular Wait : Impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration

 

Deadlock Avoidance

 

Deadlock Prevention reduces resource utilization and system performance => Use Deadlock Avoidance

 

Requires that the system has some additional a priori information available

Simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need

 

Single instance of a resource type => Resource-Allogaction Graph

Multiple instance of a resource type => Banker's Algorithm

 

Safe State

 

System is in safe state if there exists a sequence <P1, P2, ..., Pn> of all the processes in the systems such that for each Pi, the resources that Pi can still request can be satisfied by currently available resources + resources held by all the Pj, with j<i

 

Resource Allocation Graph

 

Claim edge Pi -> Rj indicated that process Pi may request resource Rj

Claim edge converts to request edge when a process requests resource

Request edge converted to an assignment edge when the resource is allocated to the process

When a resource is released by a process, assignment edge reconverts to a claim edge

Resources must be claimed a priori in the system

 

Banker's Algorithm

 

Each process must a priori claim maximum use

When a process requests a request it may have to wait

When a process gets all its resources it must return them in a finite amount of time

 

Information : Available, Max, Allocation, Need (n = number of processes, m = number of resources types)

 

Available : The number of available resources (Vector of length m)

 

Max : The number of resources that can be allocated to the maximum (n * m matrix)

 

Allocation : The number of resources already allocated (n * m matrix)

 

Need : Max-Allocation (n * m matrix)

 

1. Let Work and Finish be vectors of length m and n, respectively.

Initialize : Work = Available, Finish[i] = false for i = 0, 1, ..., n-1

 

2. Find an i such that both: Finish[i] = false, Need i <= Work

If no such i exists, go to step 4

 

3. Work = Work + Allocation i, Finish[i] = true

go to step 2

 

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

 

Resource-Request Algorithm for process Pi : 

Request i = Request vector for process Pi

If Request i[j] = k then process Pi wants k instances of resource type Rj

 

1. If Request i <= Need i, go to step 2. Otherwise, raise error condition, since process has exceeded its maximum claim

 

2. If Request i <= Available, go to step 3

Otherwise, Pi must wait, since resources are not available

 

3. Pretend to allocate requested resources to Pi by modifying the state as follow : Available = Available - Request i, Allocation i = Allocation i + Request i, Need i = Need i - Request i

 

If safe => The resources are allocated to Pi

If unsafe => Pi must wait, and the old resource-allocation state is restored

 

Deadlock Detection

 

Single instance of each resource type : 

Maintain wait-for graph

Periodically invoke an algorithms that searches for a cycle in the graph, if there is a cycle, there exists a deadlock

 

Available : The number of available resources of each type (A vector of length m)

 

Allocation : The number of resources of each type currently allocated to each process (An n * m matrix)

 

Request : The current request of each process (An n * m matrix)

 

(Do not use Max because it's for detection, not for prevention)

 

1. Let Work and Finish be vectors of length m and n respectively

Initialize : Work = Available, For i = 1, 2, .., n. If Allocation != 0, then Finish[i] = false. otherwise, Finish[i] = true

 

2. Find an index i such that both : Finish[i] == false, Request i <= Work

If no such i exists, go to step 4

 

3. Work = Work + Allocation i, Finish[i] = true

go to step 2

 

4. If Finish[i] == false, for some 1<= i <= n, then the system is in deadlock state. Moreover, if Finish[i] == false, then Pi is deadlocked

 

Algorithm requires an order of O(m * n^2) operations