19-07-2011, 04:07 PM
[attachment=14662]
Deadlock
A deadlock is a situation wherein two or more competing actions are waiting for the other to finish, and thus neither ever does.
Example : “When two trains approach each other at a crossing, both shall come to a full stop and neither shall start up again until the other has gone.”
Deadlock Examples
A deadlock refers to a specific condition when two or more processes are waiting for each other to release a resource, or more than two processes are waiting for resources in a circular chain.
Example 1
System has 2 tape drives.
There are two processes P1 and P2 .Each hold one tape drive and each needs another one. Process holding a resource cannot release a resource until it finishes execution. In this case both processes are in deadlock.
Deadlock examples
Example 2 of a deadlock which may occur in database products is the following. Client applications using the database may require exclusive access to a table, and in order to gain exclusive access they ask for a lock. If one client application holds a lock on a table and attempts to obtain the lock on a second table that is already held by a second client application, this may lead to deadlock if the second application then attempts to obtain the lock that is held by the first application.
Necessary conditions for Deadlock
Deadlock occurs only if all the four conditions hold simultaneously.
1 Mutual exclusion condition: a resource that cannot be used by more than one process at a time .At least one process that is used in non-shared mode.
2 Hold and Wait Condition : processes already holding resources may request new resources
3 No preemption condition: No resource can be forcibly removed from a process holding it, resources can be released only by the explicit action of the process
4 Circular wait: there exists a set {P0, P1, …, Pn} 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 Pn is waiting for a resource that is held by P0.
Deadlock Characterization
Mutual exclusion: only one process at a time can use a resource ie a resource cannot be shared by 2 or more processes at any time.
Hold and wait: a process is holding at least one resource and 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 Po.
System Model
Resource types R1, R2, . . ., Rm can be physical(CPU cycles, memory space, I/O devices,printer,tape drive) or logical (files,semaphores and monitors)
Each resource type Ri has Wi instances.
Each process utilizes a resource as follows:
1.Request : process request a resource.
2.Use : process operate on resource.
3.Release : after the process is terminated it releases the resources
Resource allocation graph
This directed graph is used to describe deadlocks more precisely. This directed graph is called a system resource-allocation graph.
It consists of 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
Resource-Allocation Graph
When a process request an instance of resource , then a request edge is inserted.
When request is fulfilled ,then request edge is simultaneously transformed to assignment edge.
When process no longer needs the resource ,assignment edge is deleted.
If graph contains no cycle, the there is no deadlock.
If it contains cycle, deadlock may exist.
If resource type has several instances ,then cycle does not imply that a deadlock has occurred.
Example of a Resource Allocation Graph
Resource-Allocation Graph (Cont.)
Process is denoted by
Resource Type with 4 instances
Pi requests instance of Rj
Pi is holding an instance of Rj
Resource Allocation Graph With a Deadlock 2
Consider a cycle P1R1P2R3P3R2P1
P2 is waiting for the resource R3,which is held by P3.P3 is waiting for P1 or P2 to release resource R2.
Also P1 is waiting for P2 to release R1.
Every process is waiting .so there is deadlock.
Similarly consider a cycle P2R3P3R2P2.
In this case there is also a deadlock.
Resource Allocation Graph With A Cycle But No Deadlock(P1R1P3R2P1)
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.
Methods for Handling Deadlocks
1 Ensure that the system will never enter a deadlock state (deadlock prevention and avoidance).
2 Allow the system to enter a deadlock state ,detect it and recover.
3 Ignore the problem and pretend that deadlocks never occur in the system; This method is used by most operating systems, including UNIX.
Deadlock Prevention
It is a set of methods that ensure that at least one of the following necessary conditions do not occur.
Mutual Exclusion – This condition is not required for sharable resources but it must hold for non-sharable resources. Deadlocks cannot be prevented by denying mutual exclusion condition because some resources are intrinsically sharable.
Hold and Wait – It must guarantee that whenever a process requests a resource, it does not hold any other resources. There are two protocols for making sure that this condition does not hold:
Each process request and all resources are allocated to it before it begins execution.
A process may request some resources. After using these resources if additional resources are required, it must release all the resources that is allocated to it.
Disadvantages of protocols
1 Low Resource Utilization: Resources remains unutilized for a long time.
2 Starvation: A process that require several resources may have to wait indefinitely.
Deadlock Prevention (Cont.)
No Preemption: The third necessary condition for a deadlock to occur is that there can be no preemption of resources. To ensure that this condition does not hold , following protocols are used:
1 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.
2 A process P1 requests some resources. If resources are available they are allocated to it. If resources are not available OS checks whether they are allocated to some other process asy P2 that is waiting for additional resources. If so we preempt P2 of all the resources and allocate to P1.
Deadlock Avoidance
Requires that the system has some additional a priori information available about the process i.e.
Process must declare in priori ,which resources a process will request and use in its lifetime. Also the order in which it will use the resources .This priori info will help us to avoid deadlock.
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.
Safe State
A state is safe if the system can allocate resources to each process in some order and still avoid a deadlock.
A safe state is not a deadlock state.
Not all unsafe states lead to deadlock.
System is in safe state if there exists a safe sequence of all processes.
Sequence <P1, P2, …, Pn> is safe if for each Pi, the resources that Pi can still request can be satisfied by currently available resources + resources held by all the Pj, with j<i.
If Pi resource needs are not immediately available, then Pi can wait until all Pj have finished.
When all Pj are finished, Pi can obtain needed resources, execute, return allocated resources, and terminate.
When Pi terminates, Pi+1 can obtain its needed resources, and so on.
Basic Facts
If a system is in safe state no deadlocks.
If a system is in unsafe state possibility of deadlock.
Avoidance ensure that a system will never enter an unsafe state.
Safe Sequence: Example
UnSafe Sequence: Example
Resource-Allocation Graph Algorithm with claim edge used in deadlock avoidance algorithm.
Claim edge Pi Rj indicated that process Pi may request resource Rj...It is represented by a dashed line.
Claim process Pi requests Rj Claim edge Pi Rj converts to request edge.
When a resource Rj is released by a process Pi, assignment edge Rj Pi reconverts to a claim edge.
All resources must be claimed a priori in the system to avoid deadlock and unsafe state.
Request edge is converted to assignment edge if there is no cycle. it is checked with cycle-detection algorithm.
If there is cycle process will have to wait for its request to be satisfied.
Resource-Allocation Graph For Deadlock Avoidance
Unsafe State In Resource-Allocation Graph
Banker’s Algorithm
Multiple instances of resources can be there in deadlock avoidance algorithm.
Each new 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.
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
Let Work and Finish be vectors of length m and n, respectively. Initialize:
Work = Available
Finish [i] = false for i - 1,3, …, n.
2. Find and 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.
4. If Finish [i] == true for all i, then the system is in a safe state.
Resource-Request Algorithm for Process Pi
Request = 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
Steps to calculate safe sequence
Need of each process is compared with available. If Need ≤ available, then the resources are allocated to that process and process will release the resources.
If need › available, next process need is taken for comparison.
This procedure is continued for all the processes in the queue to find the safe sequence, if it exists.
Deadlock
A deadlock is a situation wherein two or more competing actions are waiting for the other to finish, and thus neither ever does.
Example : “When two trains approach each other at a crossing, both shall come to a full stop and neither shall start up again until the other has gone.”
Deadlock Examples
A deadlock refers to a specific condition when two or more processes are waiting for each other to release a resource, or more than two processes are waiting for resources in a circular chain.
Example 1
System has 2 tape drives.
There are two processes P1 and P2 .Each hold one tape drive and each needs another one. Process holding a resource cannot release a resource until it finishes execution. In this case both processes are in deadlock.
Deadlock examples
Example 2 of a deadlock which may occur in database products is the following. Client applications using the database may require exclusive access to a table, and in order to gain exclusive access they ask for a lock. If one client application holds a lock on a table and attempts to obtain the lock on a second table that is already held by a second client application, this may lead to deadlock if the second application then attempts to obtain the lock that is held by the first application.
Necessary conditions for Deadlock
Deadlock occurs only if all the four conditions hold simultaneously.
1 Mutual exclusion condition: a resource that cannot be used by more than one process at a time .At least one process that is used in non-shared mode.
2 Hold and Wait Condition : processes already holding resources may request new resources
3 No preemption condition: No resource can be forcibly removed from a process holding it, resources can be released only by the explicit action of the process
4 Circular wait: there exists a set {P0, P1, …, Pn} 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 Pn is waiting for a resource that is held by P0.
Deadlock Characterization
Mutual exclusion: only one process at a time can use a resource ie a resource cannot be shared by 2 or more processes at any time.
Hold and wait: a process is holding at least one resource and 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 Po.
System Model
Resource types R1, R2, . . ., Rm can be physical(CPU cycles, memory space, I/O devices,printer,tape drive) or logical (files,semaphores and monitors)
Each resource type Ri has Wi instances.
Each process utilizes a resource as follows:
1.Request : process request a resource.
2.Use : process operate on resource.
3.Release : after the process is terminated it releases the resources
Resource allocation graph
This directed graph is used to describe deadlocks more precisely. This directed graph is called a system resource-allocation graph.
It consists of 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
Resource-Allocation Graph
When a process request an instance of resource , then a request edge is inserted.
When request is fulfilled ,then request edge is simultaneously transformed to assignment edge.
When process no longer needs the resource ,assignment edge is deleted.
If graph contains no cycle, the there is no deadlock.
If it contains cycle, deadlock may exist.
If resource type has several instances ,then cycle does not imply that a deadlock has occurred.
Example of a Resource Allocation Graph
Resource-Allocation Graph (Cont.)
Process is denoted by
Resource Type with 4 instances
Pi requests instance of Rj
Pi is holding an instance of Rj
Resource Allocation Graph With a Deadlock 2
Consider a cycle P1R1P2R3P3R2P1
P2 is waiting for the resource R3,which is held by P3.P3 is waiting for P1 or P2 to release resource R2.
Also P1 is waiting for P2 to release R1.
Every process is waiting .so there is deadlock.
Similarly consider a cycle P2R3P3R2P2.
In this case there is also a deadlock.
Resource Allocation Graph With A Cycle But No Deadlock(P1R1P3R2P1)
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.
Methods for Handling Deadlocks
1 Ensure that the system will never enter a deadlock state (deadlock prevention and avoidance).
2 Allow the system to enter a deadlock state ,detect it and recover.
3 Ignore the problem and pretend that deadlocks never occur in the system; This method is used by most operating systems, including UNIX.
Deadlock Prevention
It is a set of methods that ensure that at least one of the following necessary conditions do not occur.
Mutual Exclusion – This condition is not required for sharable resources but it must hold for non-sharable resources. Deadlocks cannot be prevented by denying mutual exclusion condition because some resources are intrinsically sharable.
Hold and Wait – It must guarantee that whenever a process requests a resource, it does not hold any other resources. There are two protocols for making sure that this condition does not hold:
Each process request and all resources are allocated to it before it begins execution.
A process may request some resources. After using these resources if additional resources are required, it must release all the resources that is allocated to it.
Disadvantages of protocols
1 Low Resource Utilization: Resources remains unutilized for a long time.
2 Starvation: A process that require several resources may have to wait indefinitely.
Deadlock Prevention (Cont.)
No Preemption: The third necessary condition for a deadlock to occur is that there can be no preemption of resources. To ensure that this condition does not hold , following protocols are used:
1 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.
2 A process P1 requests some resources. If resources are available they are allocated to it. If resources are not available OS checks whether they are allocated to some other process asy P2 that is waiting for additional resources. If so we preempt P2 of all the resources and allocate to P1.
Deadlock Avoidance
Requires that the system has some additional a priori information available about the process i.e.
Process must declare in priori ,which resources a process will request and use in its lifetime. Also the order in which it will use the resources .This priori info will help us to avoid deadlock.
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.
Safe State
A state is safe if the system can allocate resources to each process in some order and still avoid a deadlock.
A safe state is not a deadlock state.
Not all unsafe states lead to deadlock.
System is in safe state if there exists a safe sequence of all processes.
Sequence <P1, P2, …, Pn> is safe if for each Pi, the resources that Pi can still request can be satisfied by currently available resources + resources held by all the Pj, with j<i.
If Pi resource needs are not immediately available, then Pi can wait until all Pj have finished.
When all Pj are finished, Pi can obtain needed resources, execute, return allocated resources, and terminate.
When Pi terminates, Pi+1 can obtain its needed resources, and so on.
Basic Facts
If a system is in safe state no deadlocks.
If a system is in unsafe state possibility of deadlock.
Avoidance ensure that a system will never enter an unsafe state.
Safe Sequence: Example
UnSafe Sequence: Example
Resource-Allocation Graph Algorithm with claim edge used in deadlock avoidance algorithm.
Claim edge Pi Rj indicated that process Pi may request resource Rj...It is represented by a dashed line.
Claim process Pi requests Rj Claim edge Pi Rj converts to request edge.
When a resource Rj is released by a process Pi, assignment edge Rj Pi reconverts to a claim edge.
All resources must be claimed a priori in the system to avoid deadlock and unsafe state.
Request edge is converted to assignment edge if there is no cycle. it is checked with cycle-detection algorithm.
If there is cycle process will have to wait for its request to be satisfied.
Resource-Allocation Graph For Deadlock Avoidance
Unsafe State In Resource-Allocation Graph
Banker’s Algorithm
Multiple instances of resources can be there in deadlock avoidance algorithm.
Each new 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.
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
Let Work and Finish be vectors of length m and n, respectively. Initialize:
Work = Available
Finish [i] = false for i - 1,3, …, n.
2. Find and 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.
4. If Finish [i] == true for all i, then the system is in a safe state.
Resource-Request Algorithm for Process Pi
Request = 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
Steps to calculate safe sequence
Need of each process is compared with available. If Need ≤ available, then the resources are allocated to that process and process will release the resources.
If need › available, next process need is taken for comparison.
This procedure is continued for all the processes in the queue to find the safe sequence, if it exists.