Lecture-6
Deadlock
Presented By –
Kazi Johir Raihan Suny
Lecturer, CSE, IUBAT
Content of this Lecture
• Concept about Deadlock
• System Model
• Deadlock Characterization
• Resource-Allocation Graph
• Methods for Handling Deadlocks
• Deadlock Prevention
• Deadlock Avoidance
• Deadlock Detection
• Recovery from Deadlock
2
The Deadlock Problem
In an operating system, a deadlock occurs when a process or thread enters
a waiting state because a requested system resource is held by another
waiting process, which in turn is waiting for another resource held by
another waiting process.
Example:
• System has 2 tape drives.
• P1 and P2 each hold one tape drive and each needs another one.
3
Bridge Crossing Example
• Traffic only in one direction.
• Each section of a bridge can be viewed as a resource.
• If a deadlock occurs, it can be resolved if one car backs up.
• Several cars may have to be backed up if a deadlock occurs.
4
System Model
❖ Resource types R1, R2, . . ., Rm
CPU cycles, memory space, I/O devices
❖ Each resource type Ri has Wi instances.
❖ Each process utilizes a resource as follows:
• request
• use
• release
5
Deadlock Characterization
Deadlock can arise if four conditions hold simultaneously:
• Mutual exclusion: only one process at a time can use a resource.
• Hold and wait: a process holding at least one resource is waiting to acquire
additional resources held by other processes.
• No preemption: a resource can be released only voluntarily by the process holding
it, after that process has completed its task.
• Circular wait: there exists a set {P0, P1, …, P0} of waiting processes such that P0 is
waiting for a resource that is held by P1, P1 is waiting for a resource that is held by
P2, …, Pn–1 is waiting for a resource that is held by Pn, and P0 is waiting for a
resource that is held by P0.
6
Circular wait
7
Resource-Allocation Graph
A set of vertices V and a set of edges E.
•V is partitioned into two types:
• P = {P1, P2, …, Pn}, the set consisting of all the processes in the
system.
• R = {R1, R2, …, Rm}, the set consisting of all resource types in the
system.
• request edge – directed edge P1 → Rj
• assignment edge – directed edge Rj → Pi
8
Resource-Allocation Graph
• Process
• Resource Type with 4 instances
• Pi requests instance of Rj
Rj
P
i
• Pi is holding an instance of Rj
P
i
Rj
9
Example of a Resource Allocation Graph
10
Example of a Resource Allocation Graph
Resource Allocation Graph With A Deadlock Resource Allocation Graph With A Cycle But No
Deadlock
Basic Facts:
If graph contains no cycles ⇒ no deadlock.
If graph contains a cycle ⇒
• if only one instance per resource type, then deadlock.
• if several instances per resource type, possibility of deadlock.
11
Resource Allocation Graph Exercise
Exercise 1: Can you explain this resource allocation graph ? Exercise 2: Any problem with resource allocation graph ?
Exercise 3: Is there a deadlock in resource allocation graph? Exercise 4: The resource allocation graph has a cycle.
Is this a deadlock? Why?
12
Resource Allocation Graph Exercise
Exercise 6: Exercise 7:
• Consider the following information: • Consider the following information:
P = {P1,P2,P3,P4} P = {P1,P2,P3}
R = {R1,R2,R3} R = {R1,R2,R3}
E = {R1 --> P1, P1 --> R2, R2 --> P2, E = {R1 --> P1, P1 --> R2, R2 --> P2, P2 --> R3, R3
P2 --> R3, R3 --> P3, P3 --> R1, R1 --> P4} --> P3, P3 --> R1}
- resource type R1 has two instances - resource type R1 has one instance
- resource type R2 has one instance - resource type R2 has one instance
- resource type R3 has one instance - resource type R3 has one instance
Draw a resource allocation graph and explain Draw a resource allocation graph and explain the
the possibility for a deadlock. possibility for a deadlock.
13
Deadlock Prevention
Restrain the ways request can be made:
• Mutual Exclusion –
Not required for sharable resources; must hold for non-sharablere sources.
• Hold and Wait –
Must guarantee that whenever a process requests a resource, it does not hold any other
resources.
• Require process to request and be allocated all its resources before it begins
execution, or allow process to request resources only when the process has none.
• Low resource utilization.
14
Deadlock Prevention
No Preemption –
• If a process that is holding some resources requests another resource that cannot be
immediately allocated to it, then all resources currently being held are released.
• Preempted resources are added to the list of resources for which the process is
waiting.
• Process will be restarted only when it can regain its old resources, as well as the
new ones that it is requesting.
• Circular Wait –
Impose a total ordering of all resource types, and require that each process
requests resources in an increasing order of enumeration.
15
Deadlock Avoidance
Requires that the system has some additional a priori information
available.
• Simplest and most useful model requires that each process declare the maximum
number of resources of each type that it may need.
• The deadlock-avoidance algorithm dynamically examines the resource-allocation state
to ensure that there can never be a circular-wait condition.
• Resource-allocation state is defined by the number of available and allocated resources,
and the maximum demands of the processes.
16
Deadlock Detection
❖ Allow system to enter deadlock state
❖ Detection algorithm
❖ Recovery scheme
17
Banker’s Algorithm
❖ Multiple instances.
❖ Each process must a priori claim maximum use.
❖ When a process requests a resource it may have to wait.
❖ When a process gets all its resources it must return them in a finite amount of time.
18
Data Structures for the Banker’s Algorithm
Let n = number of processes, and m = number of resources types.
• Available: Vector of length m. If available [j] = k, there are k instances of resource
type Rj available
• Max: n x m matrix. If Max [i,j] = k, then process Pi may request at most k
instances of resource type Rj
• Allocation: n x m matrix. If Allocation[i,j] = k then Pi is currently allocated k
instances of Rj
• Need: n x m matrix. If Need[i,j] = k, then Pi may need k more instances of Rj to
complete its task
Need [i,j] = Max[i,j] – Allocation [i,j]
Safety Algorithm
[Link] Work and Finish be vectors of length m and n, respectively. Initialize:
Work = Available
Finish [i] = false for i = 0, 1, …, n- 1
[Link] an i such that both:
(a) Finish [i] = false
(b) Needi ≤ Work
If no such i exists, go to step 4
3. Work = Work + Allocationi
Finish[i] = true
go to step 2
[Link] Finish [i] == true for all i, then the system is in a safe state
Resource-Request Algorithm for Process Pi
Requesti = 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 – Requesti;
Allocationi = Allocationi + Requesti;
Needi = Needi – Requesti;
● If safe ⇒ the resources are allocated to Pi
● If unsafe ⇒ Pi must wait, and the old resource-allocation state is restored
Banker’s Algorithm
22
Banker’s Algorithm
• If available >= Need
flag = T
else
flag = F
• When a process will be finished
than it will release its allocated
resources. And these released
resources will add with
available resources (work).
• In the last step work will be
equal to resources given in the
question.
23
Bankers Algorithm Exercise_1
24
Exercise
1. Define deadlock with an example.
2. Discuss about deadlock characterization.
3. Consider the following information:
P = {P1,P2,P3} R = {R1,R2,R3}
E = {R1 --> P1, P1 --> R2, R2 --> P2, P2 --> R3, R3 --> P3, P3 --> R1}
- resource type R1 has one instance, resource type R2 has one instance, resource
type R3 has one instance
Draw a resource allocation graph and explain the possibility for a deadlock.
4. Discuss about Deadlock Prevention methods.
25
Exercise (cont…)
5.
26
Every end is a
new beginning!!!
27