Deadlock Prevention

Deadlock Prevention

Deadlocks can be prevented by preventing by one of the four needed conditions

Mutual Exclusion

Shared resources such as read-only files do not give on to deadlocks.

Unfortunately some resources, such as printers and tape drives, need full retrieve by a single process.

Hold and Wait

To stop this condition processes must be stoped from holding one or more resources while simultaneously waiting for one or more others. There are several possibilities for this:

i) Require that all processes request all resources at once. This can be excessive of system resources if a process needs one resource early in its execution and doesn't need some other resource until much later.

ii) Require that processes giving on resources must free them before requesting new resources, and then retrieve the released resources along with the new ones in a single new request. This can be a problem if a process has partially completed an operation using a resource and then fails to get it retrieved after freeing it.

iii) Either of the methods described above can lead to needs if a process requires one or more popular resources.

No Preemption

Preemption of process resource allocations can stop this condition of deadlocks, when it is possible.

i) One method is that if a process is forced to hold when requesting a new resource, then all other resources previously held by this process are completely released, ( preempted ), forcing this process to recover the old resources beside with the new resources in a single request, similar to the previous discussion.

ii) Another method is that when a resource is requested and not accessible, then the system looks to see what other processes currently have those resources and are themselves blocked waiting for some other resource. If such a process is found, then some of their resources may get prevented and added to the list 

of resources for which the process is delayed.

iii) Either of these methods may be applicable for resources whose states are easily saved and restored, such as registers and memory, but are generally not applicable to other devices such as printers and tape drives.

Circular Wait

i) One way to avoid circular wait is to number all resources, and to require that processes request resources only in  increasing or decreasing  order.

ii) In other words, in order to request resource Rj, a process must first freeing all Ri such that i >= j.

iii) One big challenge in this method is determining the relative ordering of the different resources

Deadlock Avoidance

The general idea behind deadlock avoidance is to prevent deadlocks from ever happening, by preventing at least one of the previously mentioned conditions.This requires more data about each process, AND tends to lead to low device utilization. ( it is a conservativeapproach. )

In some algorithms the scheduler only requires to know the maximum number of each resource that a process might potentially use. In more complex algorithms the organiser can also take advantage of the organise of exactly what resources may be needed in what order.

When a scheduler sees that starting a process or allowing resource requests may lead to future deadlocks, then that process is just not started or the request is not granted.

A resource allocation state is defined by the number of available and allocated resources, and the maximum essential of all processes in the system.

Safe State

i) A state is safe if the system can allocate all resources requested by all processes (up to their stated maximums) without going to a deadlock state.

ii) More formally, a state is safe if there subsists a safe sequence of processes { P0, P1, P2, ..., PN } such that all of the resource requests for Pi can be allowed by the resources currently allocated to Pi and all processes Pj where j < i. ( I.e. if all the processes prior to Pi finish and free up their resources, then Pi will be able to finish also, utilizing the resources that they have freed up. )

iii) If a safe sequence does not subsist, then the system is in an unsafe state, which MAY lead to deadlock. (All safe states are deadlock free, but not all unsafe states lead the way to deadlocks. )

Fig: Safe, unsafe, and deadlocked state spaces.

For example, regards a system with 12 tape drives, assigned as follows. Is this a safe state? What is the safe sequence?

i) What happens to the above table if process P2 requests and is entered one more tape drive?

ii) Key to the safe state method is that when a request is made for resources, the request is allowed only if the resulting allocation state is a safe one.

Resource-Allocation Graph Algorithm

i) If resource categories have only single case of their resources then deadlock states can be detected by cycles in the resource-allocation graphs.

ii) In this case, unsafe states can be recognized and avoided by incrementing the resource-allocation graph with claim edges, noted by dashed lines, which point from a process to a resource that it may request in the future.

iii) In order for this technique to work, all claim edges must be added to the graph for any particular process before that process is allowed to request any resources. ( On the other hand, processes may only make requests for resources for which they have already established claim edges, and claim edges cannot be added to any process that is currently holding resources. )

iv) When a process makes a request, the claim edge Pi->Rj is converted to a request edge. Similarly when a resource is released, the assignment reverse back to a claim edge.

v) This approach works by rejecting requests that would produce cycles in the resource-allocation graph, 

taking claim edges into effect.

Consider for example what happens when process P2 requests resource R2:

Fig: Resource allocation graph for dead lock avoidance

The resulting resource-allocation graph would have a cycle in it, and so the request cannot be granted.

Fig: An Unsafe State in a Resource Allocation Graph

Banker's Algorithm

i) For resource categories that contain more than one instance the resource-allocation graph method does not work, and more complex ( and less efficient ) methods must be chosen.

ii) The Banker's Algorithm gets its name because it is a method that bankers should be use to assure that when they lend out resources they will still be able to satisfy all their clients. ( A banker won't loan out a little money to start building a house unless they are sured that they will later be able to loan out the rest of the money to complete the house. )

iii) When a process starts up, it must state in advance the maximum allocation of resources it may request, up to the amount accessible on the system.

iv) When a request is made, the scheduler determines whether allowing the request would leave the system in a safe state. If not, then the process must wait until the request can be allowed safely.

Data Structures for the Banker’s Algorithm

Let n = no. of processes, and m = no. of resources types. N

Available: Vector of length m. If available [j] = k, there are k occurences of resource type Rj available n

Max: n x m matrix. If Max [i,j] = k, then process Pi may request at most k occurences of resource type Rjn

Allocation: n x m matrix. If Allocation[i,j] = k then Pi is presently allocated k instances of Rjn

Need: n x m matrix. If Need[i,j] = k, then Pi may need k more instances of Rj t finish its task 

Need [i,j] = Max[i,j] – Allocation [i,j] 

Safety Algorithm

1. Let Work and complete be vectors of length m and n, accordingly.

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

2. Find and i such that both: 

(a) Finish [i] = false

(b) Needi <= Work 

If no such i exists, go to step 4 

3. 3. Work = Work + Allocationi

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 = request vector for process Pi . If Requesti [j] = k then process Pi wants k instances of resource type Rj

1. If Requesti <= Needi 

go to step 2. Otherwise, raise error condition, since process has exceeded its maximum claim

2. If Requesti £ 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 follows: 

Available = Available – Request; 

Allocationi = Allocationi + Requesti; 

Needi = Needi – Requesti; 

lIf safe Þ the resources are allocated to Pi

lIf unsafe Þ Pi must wait, and the old resource-allocation state is restored

An Illustrative Example

Consider the following situation:

The system is in a safe state since the sequence < P1, P3, P4, P2, P0> satisfies safety criteria.

Example: P1 Request (1,0,2) Check that Request £ Available (that is, (1,0,2) <= (3,3,2) Þ true

Executing safety algorithm shows that sequence < P1, P3, P4, P0, P2> satisfies safety requirement.

Deadlock

Deadlock Characterisation

Deadlock Prevention

Recovery from deadlock

Deadlock detection