DEADLOCK:
Deadlocks are a set of blocked processes each holding a resource and waiting to acquire a resource held by another process.
HOW TO AVOID DEADLOCKS:
Deadlocks can be avoided by avoiding at least one of the four conditions, because all this four conditions are required simultaneously to cause deadlock.
1.Mutual Exclusion
Resources shared such as read-only files do not lead to deadlocks but resources, such as printers and tape drives, requires exclusive access by a single process.
One or more resources must be held by a process in a non sharable mode.
2.Hold and Wait
In this condition processes must be prevented from holding one or more resources while simultaneously waiting for one or more others.
3.No Preemption
Preemption of process resource allocations can avoid the condition of deadlocks, where ever possible.
There is only voluntary release of resource by the process-nobody else can make a process to give up a resource.
4.Circular Wait
Circular wait can be avoided if we number all resources, and require that processes request resources only in strictly increasing (or decreasing) order.
Process A waits for process B waits for process C……waits for process A.
HANDLING DEADLOCK:
The above points focus on preventing deadlocks. But what to do once a deadlock has occurred. Following three strategies can be used to remove deadlock after its occurrence.
1.Preemption
We can take a resource from one process and give it to other. This will resolve the deadlock situation, but sometimes it does causes problems.
2.Rollback
In situations where deadlock is a real possibility, the system can periodically make a record of the state of each process and when deadlock occurs, roll everything back to the last checkpoint, and restart, but allocating resources differently so that deadlock does not occur.
3.Kill one or more processes
This is the simplest way, but it works.
•There are three ways of handling deadlocks:
1.Deadlock prevention or avoidance - Do not allow the system to get into a deadlocked state.
2.Deadlock detection and recovery - Abort a process or preempt some resources when deadlocks are detected.
3.Ignore the problem all together - If deadlocks only occur once a year or so, it may be better to simply let them happen and reboot as necessary than to incur the constant overhead and system performance penalties associated with deadlock prevention or detection. This is the approach that both Windows and UNIX take.
•In order to avoid deadlocks, the system must have additional information about all processes. In particular, the system must know what resources a process will or may request in the future. ( Ranging from a simple worst-case maximum to a complete resource request and release plan for each process, depending on the particular algorithm. )
•Deadlock detection is fairly straightforward, but deadlock recovery requires either aborting processes or preempting resources, neither of which is an attractive alternative.
•If deadlocks are neither prevented nor detected, then when a deadlock occurs the system will gradually slow down, as more and more processes become stuck waiting for resources currently held by the deadlock and by other waiting
RESOURCE ALLOCATION GRAPH:
Deadlocks can be described more precisely in terms of a directed graph called system resource allocation graph.
G = ( V, E ) The graph contains nodes and edges.
V Nodes consist of processes = { P1, P2, P3, ...} and resource types { R1, R2, ...}
E Edges are ( Pi, Rj ) or ( Ri, Pj )
An arrow from the process to resource indicates the process is requesting the resource.
An arrow from resource to process shows an instance of the resource has been allocated to the process.
Process is a circle, resource type is square; dots represent number of instances of resource in type. Request points to square, assignment come from dot.
•If the graph contains no cycles, then no process is deadlocked.
•If there is a cycle, then:
a) If resource types have multiple instances, then deadlock MAY exist.
b) If each resource type has 1 instance, then deadlock has occurred.
Deadlocks are a set of blocked processes each holding a resource and waiting to acquire a resource held by another process.
HOW TO AVOID DEADLOCKS:
Deadlocks can be avoided by avoiding at least one of the four conditions, because all this four conditions are required simultaneously to cause deadlock.
1.Mutual Exclusion
Resources shared such as read-only files do not lead to deadlocks but resources, such as printers and tape drives, requires exclusive access by a single process.
One or more resources must be held by a process in a non sharable mode.
2.Hold and Wait
In this condition processes must be prevented from holding one or more resources while simultaneously waiting for one or more others.
3.No Preemption
Preemption of process resource allocations can avoid the condition of deadlocks, where ever possible.
There is only voluntary release of resource by the process-nobody else can make a process to give up a resource.
4.Circular Wait
Circular wait can be avoided if we number all resources, and require that processes request resources only in strictly increasing (or decreasing) order.
Process A waits for process B waits for process C……waits for process A.
HANDLING DEADLOCK:
The above points focus on preventing deadlocks. But what to do once a deadlock has occurred. Following three strategies can be used to remove deadlock after its occurrence.
1.Preemption
We can take a resource from one process and give it to other. This will resolve the deadlock situation, but sometimes it does causes problems.
2.Rollback
In situations where deadlock is a real possibility, the system can periodically make a record of the state of each process and when deadlock occurs, roll everything back to the last checkpoint, and restart, but allocating resources differently so that deadlock does not occur.
3.Kill one or more processes
This is the simplest way, but it works.
•There are three ways of handling deadlocks:
1.Deadlock prevention or avoidance - Do not allow the system to get into a deadlocked state.
2.Deadlock detection and recovery - Abort a process or preempt some resources when deadlocks are detected.
3.Ignore the problem all together - If deadlocks only occur once a year or so, it may be better to simply let them happen and reboot as necessary than to incur the constant overhead and system performance penalties associated with deadlock prevention or detection. This is the approach that both Windows and UNIX take.
•In order to avoid deadlocks, the system must have additional information about all processes. In particular, the system must know what resources a process will or may request in the future. ( Ranging from a simple worst-case maximum to a complete resource request and release plan for each process, depending on the particular algorithm. )
•Deadlock detection is fairly straightforward, but deadlock recovery requires either aborting processes or preempting resources, neither of which is an attractive alternative.
•If deadlocks are neither prevented nor detected, then when a deadlock occurs the system will gradually slow down, as more and more processes become stuck waiting for resources currently held by the deadlock and by other waiting
RESOURCE ALLOCATION GRAPH:
Deadlocks can be described more precisely in terms of a directed graph called system resource allocation graph.
G = ( V, E ) The graph contains nodes and edges.
V Nodes consist of processes = { P1, P2, P3, ...} and resource types { R1, R2, ...}
E Edges are ( Pi, Rj ) or ( Ri, Pj )
An arrow from the process to resource indicates the process is requesting the resource.
An arrow from resource to process shows an instance of the resource has been allocated to the process.
Process is a circle, resource type is square; dots represent number of instances of resource in type. Request points to square, assignment come from dot.
•If the graph contains no cycles, then no process is deadlocked.
•If there is a cycle, then:
a) If resource types have multiple instances, then deadlock MAY exist.
b) If each resource type has 1 instance, then deadlock has occurred.
No comments:
Post a Comment