mem
Deadlock
In a multiprogramming environment, a situation when permanent blocking of a set of processes that either compete for system resources or of communication with each other happens, we can call this as deadlock situation. This deadlock problem involves conflicting needs for resources
By two or more processes.
Necessary Conditions for Deadlock
A deadlock situation can arise, if the following four conditions hold simultaneously in a system.
Mutual Exclusion
Resources must be allocated to processes at any time in an exclusive manner and not on a shared basis for a deadlock to be possible. If another process requests that resource, the requesting process must be delayed until the resource has been released.
Hold and Wait Condition
Even if a process holds certain resources at any moment, it should be possible for it to request for new ones. It should not give up (release) the already held resources to be able to request for new ones. If it is not true, a deadlock can never take place.
No Preemption Condition
Resources can’t be preempted. A resource can be released only voluntarily by the process holding it, after that process has completed its task.
Circular Wait Condition
There must exist a set = {Po, Pi, P2, …, Pn} of waiting processes such that Po is waiting for a resource that is held by PI, P1
weld. by is waiting for a resource that is
Pr, _ 1 is waiting for a resource that is held by Pr, and Pn is
aiting for a resource that is held by Po.
Resource Allocation Graph
The resource allocation graph consists of a set of vertices V and a Set of edges E.
vertices V is partitioned into two types
- P = {P1, P2,…, Pn}, the set consisting of all the processes in t
- R = {R1, R2,…, Rm}, the set consisting of all resource types in 1f,.
- Directed Edge P; Ri is known as request edge.
- Directed Edge R P; is known as assignment edge.
Resource Instance
- One instance of resource type R1. Two instances of resource type R2.
- One instance of resource type • Three instances of resource type R4.
R
R2
Example of resource allocation graph
–
Process States
- Process P1 is holding an instance of resource type R2 and is waiting for an instance of resource type R1.
- Process R2 is holding an instance of R1 and R2 is waiting for an instance of resource type
- Process P3 is holding an instance of R3.
- Basic facts related to resource allocation graphs are given below
Note If graph consists no cycle it means there is no deadlock in the system
If graph contains cycle
- If only one instance per resource type,
- If several instances per resource type,
Deadlock Handling Strategies
- Deadlock prevention 2. Deadlock avoidance
- Deadlock detection
Deadlock Prevention
Deadlock prevention is a set of methods for ensuring that atleast one of the necessary conditions can’t hold.
Deadlock Avoidance
A deadlock avoidance algorithm dynamically examines the resource allocation state to ensure that a circular wait condition can never exist The resource allocation state is defined by the number of available and allocated resources and the maximum demands of the processes.
Safe State
A state is safe, if the system can allocate resources to each process and still avoid a deadlock.
A system is in safe state, if there exists a safe sequence of all processes. A deadlock state is an unsafe state. Not all unsafe states cause deadlocks.
Banker’s Algorithm
Data structures for Banker’s algorithm available. Vector of length m. If available [j] = k, there are k instances of resource type R1 available.
- Max n x m If max [i, j] = k, then process Pi may request at most k
instances of resource type Rj.
- Allocation n x m If allocation [i, j ] = k, then Pi is currently allocated k instances of Ri
- Need n x m matt-. If need [i, j I = k, then Pi may need k more instances of R to complete its task
Need [i,j]= max [i, j] — allocation [i, j]
.
- safety Algorithm
Setp 1 Let work and finish be vectors of length m and n, respectively. Initialize.
Work = Available
Finish [i]= False (for i=1,2,….n
Step 2 Find i such that both
- Finish [i]. False
- Need ≤ Work
If no such i exists, go to step 4. Step 3 Work = Work + Allocation
Finish [i]= Tree .
Go to step 2.
Step 4 Finish [I] = True (for all i)
Then, the system is in a safe system. Example Banker’s Algorithm
Need = Max – Allocation Thus, we have
As available resources are (3 3 2). The process P1 with need (1 2 be executed.
Available resource = Available + Allocated resource of PI
3 3 2
2 0 0
5 3 2
Now, available resources are (5 3 2).
The next process that can be executed after assigning available
resource is P3. Thus, P3 will execute next.
Now, available resource = Available resource + Resource of P3
5 3 2
2 1 1
7 4 3
Now, available resources are 7 4 3. Next process will be P4.
A B C
7 4 3
0 0 2
7 4 5
Next process that will be executed is Po.
Available resource
7 4 5
0 1 0
7 5 5
Key Points
- The sequence < P, P3, P4 P0 P2 > ensures that the deadlock will never occur.
- If a safe sequence can be found that means the processes can run concurrently and will never cause a deadlock.
- First in first out scheduling based on queuing.
- Shortest seek time scheduling is designed for maximum through put in most scenarios
- RR scheduling involves extensive overhead, especially with a small time unit. Kernel is defined as a program running all times on the computer. It is the part of operating system that loads first. In simple word, kernel provides the
communication between system software and hardware.
Deadlock Detection
Allow system to enter deadlock state and then there is
(i) Detection algorithm (ii) Recovery scheme
Single instance of each resource type
- Maintain wait for graph.
(a) Nodes are processes. (b) P–> Pi, if Pi is waiting for Pi.
- Periodically invoke an algorithm that searches for a cycle in the graph.
- An algorithm to detect a cycle in a graph requires an order of n2 operations, where n is the number of vertices in the graph.
|
Resource allocation graph
Recovery Scheme
- Resource preemption
- Process termination
- Abort all deadlock processes
- Abort one process at a time until the deadlock cycle eliminated