Deadlocks

This paper talks about deadlock in the operating system from definition to how to prevent, avoid and detect it.

1. Deadlock definition

Let me start this paper with the introduction of a model in which deadlock occurs. In this model, resources are CPU, Memory location, files, I/O devices,...They are also resource types. Resource instance is one resource of a resouce type. Processes are things which request some resource type and be fulfilled with any instance of requested type. A process uses an instance of a resource by this following sequence: Request -> Use -> Release.

A deadlock is a situation in which two or more competing processes are each waiting for the other to finish, and thus neither ever does. In this above model, deadlock occurs if and only if having all 4 conditions below: Mutual Exclusion which is that some resources are used exclusively; Hold and Wait: Some process holds a resource and waits for others; No Preemption: Resource released only voluntarily; and Circular Wait (Cycle in graph): P0 waits for P1 waits for ... waits for P0.

Figure 1 below is the resource allocation graph in which P1, P2, P3 are processes. R1, R2, R3, R4 are resource types. R1 is using by P2 and requested by P1. R1 is single instance request type while R2 is multi instances request type.

Using concept of resource allocation graph, we can see that, in general case, no cycle means no deadlock and cycle means possible deadlock. In special case: One type - One instance, cycle means deadlock.

For example, in this Figure 2: One type - one instace case below, Process P1 is holding resource R2 and requesting resource R1 while Process P3 is holding resource R1 and requesting R2. If none of above procecesses release resouces, they have to wait for each others forever and it leads to deadlock.

But in the general case in Figure 3 below, no deadlock occurs even if having cycle:

The reason is that R1 and R2 are multi instance resource types and then for example, Process P1 can wait for an instance of R1 not only from P3 but also from P2. So that, when P2 releases R1, P1 have enough resources and can terminate. Similarly, P3 can wait for instance resource from P4 or P1 when it finishes.

Because when deadlock occurs, a process can not terminate, it is a quite big problem. But how to treat it. There are some approaches: Approach 1: When Deadlock occurs, we detect deadlock and recover from deadlock. It is not bad solution but waiting for something bad occurs is not very smart way. So that, we have Approach 2: Prevent / Avoid deadlock. Prevent deadlock is to remove at least one condition for deadlocks and Avoid deadlock is to avoid “unsafe” situations. Because I prefer this approach, I will maily introduce details in the next parts. Approach 1 is stated in the small last part of this paper. Frankly, not only I prefer the second approach so that it is much more stated by many authors By the way, we also have Approach 3 which is to tgnore the problem... and pray ))))))

2. Deadlock prevention

The idea of this approach is to avoid any of the four necessary conditions. With Mutual Exclusion condition, it is simple that if we have sharable resources, the problem is solved. No deadlock when no process has to wait. Frankly, not only operating system resouces, I wish that all resources in the world are shareable freely and we will have no wars . OK, let return to our topic. With Hold and Wait condition, in order to avoid this, all things we have to do is to ask all requests to make initially (before execution). If we can do that, no process can keep forever (and then wait forever) for a resource. With No preemption condition, easily, the solution is to make preemption: temporarily interrupt a process being carried out by operating system, without requiring its cooperation, and with the intention of resuming the task at a later time. Force to a process to release resources for other process to finish and then it is served. But I worry that how to fair treat with all processes . With Circular wait condition, we should make total ordering on resources and request increasingly.

3. Deadlock avoidance

The idea of this approach are to request additional information about requests and keep track of resource-allocation state to check that the current state of a allocation is safe or not and then allow requests only if safe. But what is safe state and Unsafe sate? Safe is a sate in which there exists some allocation sequence that leads to termination. And Unsafe is a state in which every allocation sequence leads to deadlock. Figure 4 below is the image of safe vs unsafe.

The above definition seems so abstract. So that, let me explain more clearly by example in this Figure 5 and 6 below:

In these figures, we have 3 process P0. P1, P2 need 10, 4, 9 resouces to finish but they are holding 5, 2, 2 resource correspondingly. And our operating system has 3 available resources.

If the system allocate the resource in the way of the fist figure: Firstly, allocate 2 resources for P1 to help it have enough resource (4) to finish. After its termination, the system has 5 resources (3 free from begining and 2 has just been released from P1. Now, it can allocate all 5 resources to P0 and finish this process and have 10 resources. Lastly, it allocates 7 resources for P2 and then all process can terminate.

But if by any reasons, the system is not smart enough to allocate by the second way: Allocate 1 resource for P2. It cannot help P2 to finish but loose 1 resource (wastly and receive bad result after that). With 2 free resouces, by the smartest way, it can help P1 finish and that's all things it can do. Even after process P1 release 2 more resources, it can not fulfill any other processes. And it leads to deadlock. We say that by the fool allocation way (Allocate 1 resource for P2), it leads the system to unsafe state.

3.1. Allocation-Graph Algorithm

This deadlock avoidance algorithm is used for single instace case only.

Initially:

• Process “claims” resources
• Claim edge

Runtime:

• Resource requested (request edge)
• Resource assigned (assignment edge)

Unsafe when:

• Cycle created

In this above case, if the system assignes both R1 and R2 for 1 process (for example P1), P1 can terminate and after that release resources for P2 to terminate. Howerver, if it assignes each resource for each process (seems fairly but is fool way), the cycle will occurs and it means it has deadlock.

3.2. Banker’s Algorithm

This algorithm is used for Several resource types; several instances case. And in initial, processes announce max need for each type. It has two parts: Safety Algorithm which detectsif current system state is safe or not and Resource-Request Algorithm which authorizes (or not) resource requests.

• System: m resource types; n processes

• Data Structures

  • Available: vector size m
    • Available[j] = number of available instances of resource type j
  • Max: nxm matrix
    • Max[i,j] = max. demands of Pi for resource type j
  • Allocation: nxm matrix
    • Allocation[i,j] = number of instance of type j held by Pi
  • Need: nxm matrix
    • Need[i,j] = Max[i,j] - Allocation[i,j]: Number of resouce instances type j needs to fulfill Pi

3.2.1 Safety Algorithm

3.2.2 Resource-Request Algorithm

• Request made by Process Pi

  • Requesti[j] = # instances requested of type j

• Steps

  1. If not Requesti ≤Need[i] => error (request more than max.)

  2. If not Requesti ≤Available => Pi must wait

  3. Try state as follows:

     Available’ := Available – Requesti

     Allocation’[i] := Allocation[i] + Requesti Need’[i] := Need[i] – Requesti

  4. Safety algorithm with State (Available’, Allocation’, Need’)

     safe => OK to give resources

     unsafe => Pi must wait

4. Deadlock detection

4.1. Wait-for graph

This method is only used for single instance resource types. We just change the resource allocation graph to wait - for graph. If the cycle occurs, it means deadlock.

4.2. Detection algorithm for mulite Instance resource type

• Algorithm (similar to Banker’s safety)
• Variables
  • Define Work := Available
  • Define Finish[i] := (Allocation[i] == 0)
• Steps
  • While exists i: Finish[i]==false && Requesti ≤Work
    • Work := Work + Allocation[i]
    • Finish[i] := true
  • ∀Pj , (Finish[j] == false) => Pj is deadlocked.

Note that we assume that processes will not ask for more resources. If they do, then deadlock is detected later.

5. Recovery from Deadlock

We can recover from deadlock by terminating Process in two ways:

• Abort all deadlocked processes
• Abort one process at a time or make Resource Preemption.

The issues of the later way is how to select victim (process, resource), Rollback (e.g., restart) and Avoid starvation.