Deadlock Computer Science Engineering (CSE) Notes | EduRev

Mock Test Series - Computer Science Engg. (CSE) GATE 2020

Computer Science Engineering (CSE) : Deadlock Computer Science Engineering (CSE) Notes | EduRev

The document Deadlock Computer Science Engineering (CSE) Notes | EduRev is a part of the Computer Science Engineering (CSE) Course Mock Test Series - Computer Science Engg. (CSE) GATE 2020.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

Process Management | Deadlock Introduction

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 Computer Science Engineering (CSE) Notes | EduRev

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.

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.

Deadlock Prevention And Avoidance

Deadlock Characteristics

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

Mutual Exclusion.
Hold and Wait.
No preemption.
Circular wait.

Deadlock Prevention

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

Eliminate Mutual Exclusion 

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

Eliminate Hold and wait

1. Allocate all required resources to the process before 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 remained blocked till it has completed its execution.

2. Process will make new request for resources after releasing the current set of resources. This solution may lead to starvation.

Deadlock Computer Science Engineering (CSE) Notes | EduRev

Eliminate No Preemption

Preempt resources from process when resources required by other high priority process.

Eliminate Circular Wait

Each resource will be assigned with a numerical number. A process can request for the resources only in increasing 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 check for safe state, if after granting request system remains in the safe state it allows the request and if their is no safe state it don’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.

Request will only be granted under below condition.
1. If request made by process is less than equal to max need to that process.

2. If request made by process is less than equal to freely availbale 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

Deadlock Detection And Recovery

In the previous post, we have discussed Deadlock Prevention and Avidance. 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.

Deadlock Computer Science Engineering (CSE) Notes | EduRev

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 cycle is necessary but not sufficient condition for deadlock detection, in this case system may or may not be in deadlock varies according to different situations.

Deadlock Recovery

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 deadlock.
Killing process one by one. After killing each 
process check for deadlock again keep repeating 
process till system recover from deadlock.

2. Resource Preemption
Resources are preempted from the processes involved in deadlock, preempted resources are allocated to other processes, so that their is a possibility of recovering the system from deadlock. In this case system go into starvation.

Operating System | Banker’s Algorithm

The banker’s algorithm is a resource allocation and deadlock avoidance algorithm that tests for safety by simulating the allocation for predetermined maximum possible amounts of all resources, then makes an “s-state” check to test for possible activities, before deciding whether allocation should be allowed to continue.

Following Data structures are used to implement the Banker’s Algorithm:

Let ‘n’ be the number of processes in the system and ‘m’ be the number of resources types.

Available : 

  • It is a 1-d array of size ‘m’ indicating the number of available resources of each type.
  • Available[ j ] = k means there are ‘k’ instances of resource type Rj

Max :

  • It is a 2-d array of size ‘n*m’ that defines the maximum demand of each process in a system.
  • Max[ i, j ] = k means process Pi may request at most ‘k’ instances of resource type Rj.

Allocation :

  • It is a 2-d array of size ‘n*m’ that defines the number of resources of each type currently allocated to each process.
  • Allocation[ i, j ] = k means process Pi is currently allocated ‘k’ instances of resource type Rj

Need :

  •  It is a 2-d array of size ‘n*m’ that indicates the remaining resource need of each process.
  • Need [ i,  j ] = k means process Pi currently allocated ‘k’ instances of resource type Rj
  • Need [ i,  j ] = Max [ i,  j ] – Allocation [ i,  j ]

Allocationi specifies the resources currently allocated to process Pi and Needi specifies the additional resources that process Pi may still request to complete its task.

Banker’s algorithm consist of Safety algorithm and Resource request algorithm

Safety Algorithm

Deadlock Computer Science Engineering (CSE) Notes | EduRev  

Resource-Request Algorithm

Let Requesti be the request array for process Pi. Request[j] = k means process Pi wants k instances of resource type Rj. When a request for resources is made by process Pi, the following actions are taken:

Deadlock Computer Science Engineering (CSE) Notes | EduRev

Example:

Considering a system with five processes P0 through P4 and three resources types A, B, C. Resource type A has 10 instances, B has 5 instances and type C has 7 instances. Suppose at time t0 following snapshot of the system has been taken:

Deadlock Computer Science Engineering (CSE) Notes | EduRev

Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

Dynamic Test

Content Category

Related Searches

Free

,

ppt

,

practice quizzes

,

Objective type Questions

,

Deadlock Computer Science Engineering (CSE) Notes | EduRev

,

Viva Questions

,

pdf

,

Semester Notes

,

Deadlock Computer Science Engineering (CSE) Notes | EduRev

,

Deadlock Computer Science Engineering (CSE) Notes | EduRev

,

study material

,

Extra Questions

,

Important questions

,

Summary

,

video lectures

,

Previous Year Questions with Solutions

,

past year papers

,

mock tests for examination

,

Sample Paper

,

MCQs

,

Exam

,

shortcuts and tricks

;