UNIT-2 (CHAPTER-2 DEADLOCKS) OPERATING SYSTEMS

SKYSPIN

UNIT-2 (CHAPTER-2 DEADLOCKS)

Introduction of Deadlock in Operating System

A process in operating systems uses different resources and uses resources in following way.
1) Requests a resource
2) Use the resource
2) Releases the resource


Deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process.
Consider an example when two trains are coming toward each other on same track and there is only one track, none of the trains can move once they are in front of each other. Similar situation occurs in operating systems when there are two or more processes hold some resources and wait for resources held by other(s). For example, in the below diagram, Process 1 is holding Resource 1 and waiting for resource 2 which is acquired by process 2, and process 2 is waiting for resource 1.

Deadlock can arise if following four conditions hold simultaneously (Necessary Conditions)

Mutual Exclusion: One or more than one resource are non-sharable (Only one process can use at a time)
Hold and Wait: A process is holding at least one resource and waiting for resources.
No Preemption: A resource cannot be taken from a process unless the process releases the resource.
Circular Wait: A set of processes are waiting for each other in circular form.

Methods for handling deadlock

There are three ways to handle deadlock
1) Deadlock prevention or avoidance: The idea is to not let the system into deadlock state.
One can zoom into each category individually, Prevention is done by negating one of above mentioned necessary conditions for deadlock.
Avoidance is kind of futuristic in nature. By using strategy of “Avoidance”, we have to make an assumption. We need to ensure that all information about resources which process WILL need are known to us prior to execution of the process. We use Banker’s algorithm (Which is in-turn a gift from Dijkstra) in order to avoid deadlock.
2) Deadlock detection and recovery: Let deadlock occur, then do preemption to handle it once occurred.
3) Ignore the problem all together: If deadlock is very rare, then let it happen and reboot the system. This is the approach that both Windows and UNIX take.

Conditions for Deadlock in Operating System

Deadlock is a situation which involves the interaction of more than one resources and processes with each other.
We can visualise the occurrence of deadlock as a situation where there are two people on a staircase. One is ascending the staircase while the other is descending. The staircase is so narrow that it can only fit one person at a time. As a result, one has to retreat while the others moves on and uses the staircase. Once that person is finished, the other one can use that staircase. But here, none of the people is willing to retreat and waits for the each other to retreat. None of them is able to use the staircase. The people here is the process and the staircase is the resource.
When a process requests for the resource that is been held another process which needs another resource to continue, but is been held by the first process, then it is called a deadlock.

 

There are 4 conditions necessary for the occurrence of a deadlock. They can be understood with the help of the above illustrated example of staircase :

1. Mutual Exclusion:
   When two people meet in the landings, they can’t just walk through because there is space only for one person. This condition to allow only one person (or process) to use the step between them (or the resource) is the first condition necessary for the occurrence of the deadlock.
2. Hold and Wait:
   When the 2 people refuses to retreat and hold their grounds, it is called holding. This is the next necessary condition for the the deadlock.
3. No Preemption:
   For resolving the deadlock one can simply cancel one of the processes for other to continue. But Operating System doesn’t do so. It allocates the resources to the processors for as much time needed until the task is completed. Hence, there is no temporary reallocation of the resources. It is third condition for deadlock.
4. Circular Wait:
   When the two people refuses to retreat and wait for each other to retreat, so that they can complete their task, it is called circular wait. It is the last condition for the deadlock to occur.

Note:
All the 4 conditions are necessary for the deadlock to occur. If any one is prevented or resolved, the deadlock is resolved.

Deadlock Prevention And Avoidance

Deadlock Characteristics

As discussed in the previous post, deadlock has following characteristics.

1. Mutual Exclusion
2. Hold and Wait
3. No preemption
4. Circular wait

Deadlock Prevention

We can prevent Deadlock by eliminating any of the above four conditions.


Eliminate Mutual Exclusion
It is not possible to dis-satisfy the mutual exclusion because some resources, such as the tape drive and printer, are inherently non-shareable.

Eliminate Hold and wait

1. Allocate all required resources to the process before the start of its execution, this way hold and wait condition is eliminated but it will lead to low device utilization. for example, if a process requires printer at a later time and we have allocated printer before the start of its execution printer will remain blocked till it has completed its execution.
2. The process will make a new request for resources after releasing the current set of resources. This solution may lead to starvation.

Eliminate No Preemption
Preempt resources from the process when resources required by other high priority processes.

Eliminate Circular Wait
Each resource will be assigned with a numerical number. A process can request the resources increasing/decreasing. order of numbering.
For Example, if P1 process is allocated R5 resources, now next time if P1 ask for R4, R3 lesser than R5 such request will not be granted, only request for resources more than R5 will be granted.

Deadlock Avoidance

Deadlock avoidance can be done with Banker’s Algorithm.
Banker’s Algorithm
Bankers’s Algorithm is resource allocation and deadlock avoidance algorithm which test all the request made by processes for resources, it checks for the safe state, if after granting request system remains in the safe state it allows the request and if there is no safe state it doesn’t allow the request made by the process.
Inputs to Banker’s Algorithm:

1. Max need of resources by each process.
2. Currently allocated resources by each process.
3. Max free available resources in the system.

The request will only be granted under the below condition:

1. If the request made by the process is less than equal to max need to that process.
2. If the request made by the process is less than equal to the freely available resource in the system.

Example:

Total resources in system:
A B C D
6 5 7 6

Available system resources are:
A B C D
3 1 1 2

Processes (currently allocated resources):
    A B C D
P1  1 2 2 1
P2  1 0 3 3
P3  1 2 1 0

Processes (maximum resources):
    A B C D
P1  3 3 2 2
P2  1 2 3 4
P3  1 3 5 0

Need = maximum resources - currently allocated resources.
Processes (need resources):
    A B C D
P1  2 1 0 1
P2  0 2 0 1
P3  0 1 4 0

Note:Deadlock prevention is more strict that Deadlock Avoidance.

Deadlock Detection And Recovery

In the previous post, we have discussed Deadlock Prevention and Avoidance. In this post, Deadlock Detection and Recovery technique to handle deadlock is discussed.

Deadlock Detection

1. If resources have single instance:
   In this case for Deadlock detection we can run an algorithm to check for cycle in the Resource Allocation Graph. Presence of cycle in the graph is the sufficient condition for deadlock.
   In the above diagram, resource 1 and resource 2 have single instances. There is a cycle R1 → P1 → R2 → P2. So, Deadlock is Confirmed.
   
   
2. If there are multiple instances of resources:
   Detection of the cycle is necessary but not sufficient condition for deadlock detection, in this case, the system may or may not be in deadlock varies according to different situations.

Deadlock Recovery

A traditional operating system such as Windows doesn’t deal with deadlock recovery as it is time and space consuming process. Real-time operating systems use Deadlock recovery.

Recovery method
1. Killing the process: killing all the process involved in the deadlock. Killing process one by one. After killing each process check for deadlock again keep repeating the process till system recover from deadlock.
2. Resource Preemption: Resources are preempted from the processes involved in the deadlock, preempted resources are allocated to other processes so that there is a possibility of recovering the system from deadlock. In this case, the system goes into starvation.

Deadlock Detection Algorithm in Operating System

If a system does not employ either a deadlock prevention or deadlock avoidance algorithm then a deadlock situation may occur. In this case-

• Apply an algorithm to examine state of system to determine whether deadlock has has occurred or not.
• Apply an algorithm to recover from the deadlock. For more refer- Deadlock Recovery

Deadlock Detection Algorithm/ Bankers Algorithm:
The algorithm employs several time varying data structures:

• Available- A vector of length m indicates the number of available resources of each type.
• Allocation- An n*m matrix defines the number of resources of each type currently allocated to a process. Column represents resource and resource represent process.
• Request- An n*m matrix indicates the current request of each process. If request[i][j] equals k then process P_i is requesting k more instances of resource type R_j.

We treat rows in the matrices Allocation and Request as vectors, we refer them as Allocation_i and Request_i.

Steps of Algorithm:

1. Let Work and Finish be vectors of length m and n respectively. Initialize Work= Available. For i=0, 1, …., n-1, if Request_i = 0, then Finish[i] = true; otherwise, Finish[i]= false.
2. Find an index i such that both
   a) Finish[i] == false
   b) 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 i, 0<=i<n, then the system is in a deadlocked state. Moreover, if Finish[i]==false the process P_i is deadlocked.

For example,

1. In this, Work = [0, 0, 0] &
   Finish = [false, false, false, false, false]
2. i=0 is selected as both Finish[0] = false and [0, 0, 0]<=[0, 0, 0].
3. Work =[0, 0, 0]+[0, 1, 0] =>[0, 1, 0] &
   Finish = [true, false, false, false, false].
4. i=2 is selected as both Finish[2] = false and [0, 0, 0]<=[0, 1, 0].
5. Work =[0, 1, 0]+[3, 0, 3] =>[3, 1, 3] &
   Finish = [true, false, true, false, false].
6. i=1 is selected as both Finish[1] = false and [2, 0, 2]<=[3, 1, 3].
7. Work =[3, 1, 3]+[2, 0, 2] =>[5, 1, 5] &
   Finish = [true, true, true, false, false].
8. i=3 is selected as both Finish[3] = false and [1, 0, 0]<=[5, 1, 5].
9. Work =[5, 1, 5]+[2, 1, 1] =>[7, 2, 6] &
   Finish = [true, true, true, true, false].
10. i=4 is selected as both Finish[4] = false and [0, 0, 2]<=[7, 2, 6].
11. Work =[7, 2, 6]+[0, 0, 2] =>[7, 2, 8] &
    Finish = [true, true, true, true, true].
12. Since Finish is a vector of all true it means there is no deadlock in this example.

Recovery from Deadlock in Operating System

Prerequisite – Deadlock Detection And Recovery
When a Deadlock Detection Algorithm determines that a deadlock has occurred in the system, the system must recover from that deadlock. There are two approaches of breaking a Deadlock:

1. Process Termination:

To eliminate the deadlock, we can simply kill one or more processes. For this, we use two methods:
(a). Abort all the Deadlocked Processes:
Aborting all the processes will certainly break the deadlock, but with a great expenses. The deadlocked processes may have computed for a long time and the result of those partial computations must be discarded and there is a probability to recalculate them later.

• (b). Abort one process at a time untill deadlock is eliminated:
  Abort one deadlocked process at a time, untill deadlock cycle is eliminated from the system. Due to this method, there may be considerable overhead, because after aborting each process, we have to run deadlock detection algorithm to check whether any processes are still deadlocked.

2. Resource Preemption:

To eliminate deadlocks using resource preemption, we preepmt some resources from processes and give those resources to other processes. This method will raise three issues –

• (a). Selecting a victim:
  We must determine which resources and which processes are to be preempted and also the order to minimize the cost.
• (b). Rollback:
  We must determine what should be done with the process from which resources are preempted. One simple idea is total rollback. That means abort the process and restart it.
• (c). Starvation:
  In a system, it may happen that same process is always picked as a victim. As a result, that process will never complete its designated task. This situation is called Starvation and must be avoided. One solution is that a process must be picked as a victim only a finite number of times. 

Deadlock, Starvation, and Livelock

Prerequisite – Deadlock and Starvation
Livelock occurs when two or more processes continually repeat the same interaction in response to changes in the other processes without doing any useful work. These processes are not in the waiting state, and they are running concurrently. This is different from a deadlock because in a deadlock all processes are in the waiting state.


 Example:
Imagine a pair of processes using two resources, as shown:

void process_A(void)

{

    enter_reg(& resource_1);

    enter_reg(& resource_2);

    use_both_resources();

    leave_reg(& resource_2);

    leave_reg(& resource_1);

}

void process_B(void)

{

    enter_reg(& resource_1);

    enter_reg(& resource_2);

    use_both_resources();

    leave_reg(& resource_2);

    leave_reg(& resource_1);

}

Each of the two processes needs the two resources and they use the polling primitive enter_reg to try to acquire the locks necessary for them. In case the attempt fails, the process just tries again.
If process A runs first and acquires resource 1 and then process B runs and acquires resource 2, no matter which one runs next, it will make no further progress, but neither of the two processes blocks. What actually happens is that it uses up its CPU quantum over and over again without any progress being made but also without any sort of blocking. Thus this situation is not that of a deadlock( as no process is being blocked) but we have something functionally equivalent to deadlock: LIVELOCK.

 Difference between Deadlock, Starvation, and Livelock:

A livelock is similar to a deadlock, except that the states of the processes involved in the livelock constantly change with regard to one another, none progressing. Livelock is a special case of resource starvation; the general definition only states that a specific process is not progressing.

var l1 = .... // lock object like semaphore or mutex etc

var l2 = .... // lock object like semaphore or mutex etc

      

        // Thread1

        Thread.Start( ()=> {

              

    while (true) {

          

        if (!l1.Lock(1000)) {

            continue;

        }

          

        if (!l2.Lock(1000)) {

            continue;

        }

          

        /// do some work

    });

  

        // Thread2

        Thread.Start( ()=> {

              

        while (true) {

              

            if (!l2.Lock(1000)) {

                continue;

            }

              

            if (!l1.Lock(1000)) {

                continue;

            }

              

            // do some work

        });

 Deadlock:

var p = new object();

lock(p)

{

    lock(p)

    {

        // deadlock. Since p is previously locked

        // we will never reach here...

    }

A deadlock is a state in which each member of a group of actions, is waiting for some other member to release a lock. A livelock on the other hand is almost similar to a deadlock, except that the states of the processes involved in a livelock constantly keep on changing with regard to one another, none progressing. Thus Livelock is a special case of resource starvation, as stated from the general definition, the process is not progressing.

Starvation:

Starvation is a problem which is closely related to both, Livelock and Deadlock. In a dynamic system, requests for resources keep on happening. Thereby, some policy is needed to make a decision about who gets the resource when. This process, being reasonable, may lead to a some processes never getting serviced even though they are not deadlocked.

Queue q = .....

  

          while (q.Count & gt; 0)

{

    var c = q.Dequeue();

    .........

  

        // Some method in different thread accidentally

        // puts c back in queue twice within same time frame

        q.Enqueue(c);

    q.Enqueue(c);

  

    // leading to growth of queue twice then it

    // can consume, thus starving of computing

}

Starvation happens when “greedy” threads make shared resources unavailable for long periods. For instance, suppose an object provides a synchronized method that often takes a long time to return. If one thread invokes this method frequently, other threads that also need frequent synchronized access to the same object will often be blocked.

Difference between Deadlock and Starvation in OS

Deadlock:
Deadlock occurs when each process holds a resource and wait for other resource held by any other process. Necessary conditions for deadlock to occur are Mutual Exclusion, Hold and Wait, No Preemption and Circular Wait. In this no process holding one resource and waiting for another get executed. For example, in the below diagram, Process 1 is holding Resource 1 and waiting for resource 2 which is acquired by process 2, and process 2 is waiting for resource 1. Hence both process 1 and process 2 are in deadlock.



Starvation:
Starvation is the problem that occurs when high priority processes keep executing and low priority processes get blocked for indefinite time. In heavily loaded computer system, a steady stream of higher-priority processes can prevent a low-priority process from ever getting the CPU. In starvation resources are continuously utilized by high priority processes. Problem of starvation can be resolved using Aging. In Aging priority of long waiting processes is gradually increased.

 Difference between Deadlock and Starvation: