Transcript lesson21

The ‘deadlock’ conditions
Reviewing some key points
concerning the potential for
‘deadlock’ in an operating system
What is ‘deadlock’?
• The blocking of a set of processes that are
competing for certain system resources or
that are communicating with one another
• The blocking is permanent unless the OS
takes some extraordinary action, such as
killing one or more processes or forcing
one or more processes to backtrack
– William Stallings (see chapter 6 summary)
Four required conditions
•
•
•
•
Mutual exclusion
Hold and Wait
No Preemption
Circular wait
Mutual Exclusion
• A particular resource may be used by only
one process at a time
• If a process has acquired the right to use a
particular resource, then no other process
may acquire the right to use that resource
until it has been released by its owner
Hold and Wait
• When a process acquires the right to use
a resource, it may attempt to acquire the
right to use another resource, and while
waiting for permission to use the second
resource, it may hold onto its right to use
the first resource
No preemption
• Once a process has been granted the right
to use a particular resource, this right can
not be involuntarily taken away, but will be
held until explicitly released by its owner
Circular wait
• There exists a closed chain of processes
in which each process of the chain holds
some resource that is needed by the next
process in this chain
Dealing with ‘deadlock’
• Three general approaches:
– Prevention
– Detection
– Avoidance
Prevention
• Guarantee that deadlock cannot occur, by
insuring that one or more of the necessary
conditions for deadlock will not be met
Detection
• Needed if the OS always follows a policy
of granting requests for resources
• Periodically the OS needs to check for an
occurrence of a circular wait, and if found,
take some action to break the deadlock
Avoidance
• The OS can analyze each new request for
resources to see if granting it could lead to
a deadlock, and then denying the request
if it could potentially result in a deadlock
• The Banker’s Algorithm is an example of
this approach
Important rule-of-thumb
• You can avoid ‘circular waits’ by following
a fixed order when requesting resources
(in cases where a process needs multiple
resources), and release these resources
(in the reverse order) if they cannot all be
immediately acquired