Deadlocks
In a multi programming environment
several processes may compete for finite number of resources.
In normal operation a process
must request a resource before using it, and release it when it is done, in the
following sequence:
- Request
- If the request cannot be immediately granted, then the process must wait
until the resource(s) it needs become available. For example the system
calls open( ), malloc( ), new( ), and request( ).
- Use
- The process uses the resource, e.g. prints to the printer or reads from
the file.
- Release
- The process relinquishes the resource. so that it becomes available for
other processes. For example, close( ), free( ), delete( ),
and release( ).
A set of processes is deadlocked
when every process in the set is waiting for a resource that is currently
allocated to another process in the set ( and which can only be released when
that other waiting process makes progress. )
Deadlock Characterization
1. Necessary
Conditions
There are four conditions that
are necessary for a deadlock:
- Mutual Exclusion - At
least one resource must be held in a non-sharable mode; If any other
process requests this resource, then that process must wait for the resource
to be released. (Only one process at a time can use the resource)
- Hold and Wait - A process must be
simultaneously holding at least one resource and waiting for at least one
resource that is currently being held by some other process.
- No preemption - Once a process is
holding a resource ( i.e. once its request has been granted ), then that
resource cannot be taken away from that process until the process
voluntarily releases it.
- Circular Wait - A set of processes {
P0, P1, P2, . . ., PN } must exist such that every P[ i ] is waiting for
P[ ( i + 1 ) % ( N + 1 ) ]. (Hold and wait)
2. Resource
Allocation Graph
Deadlocks can be understood more
clearly through the use of Resource-Allocation Graphs, having the
following properties
- A
set of resource categories, { R1, R2, R3, . . ., RN }, which appear as
square nodes on the graph. Dots inside the resource nodes indicate
specific instances of the resource.
- A
set of processes, { P1, P2, P3, . . ., PN }
- Request Edges - A set of
directed arcs from Pi to Rj, indicating that process Pi has requested Rj,
and is currently waiting for that resource to become available.
- Assignment Edges - A set of
directed arcs from Rj to Pi indicating that resource Rj has been allocated
to process Pi, and that Pi is currently holding resource Rj.
- If
a resource-allocation graph contains no cycles, then the system is not
deadlocked.
- If
a resource-allocation graph does contain cycles AND each
resource category contains only a single instance, then a deadlock exists.
- If
a resource category contains more than one instance, then the presence of
a cycle in the resource-allocation graph indicates the possibility of
a deadlock, but does not guarantee one.
Methods for
Handling Deadlocks
Generally there are three ways to
handle Deadlocks:
- Deadlock prevention or avoidance - Do not
allow the system to get into a deadlocked state.
- Deadlock detection and recovery - Abort a
process or preempt some resources when deadlocks are detected.
- Ignore the problem all together - This is the approach that both Windows and UNIX take. Pretends that deadlocks never occur.
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 processes.
No comments:
Post a Comment