Lecture 7 Deadlocks

Concurrency: Deadlock and Starvation
Learning Objectives
By the end of this session, you should be
able to
 Understand the how processes share resources

What is a deadlock?
 You can't get a job without experience; you can't get experience
without a job. Deadlock
 The cause of deadlocks:
 Each process needing what another process has. This results from
sharing resources such as memory, devices, links
The four conditions for deadlock
 Four conditions have been identified as being necessary for

deadlock to occur (Coffman et al., 1971).
 1 The processes involved share resources which they use under
mutual exclusion, and a request to use a resource has been
refused.
 2 Processes are allowed to hold on to resources they have already
acquired, while requesting other resources (a situation termed ‘hold
while waiting’).
 3 Once a process has acquired a resource, this resource cannot be
taken from it forcibly (that is, there is no pre-emption).
 4 A cycle of processes exists such that each process holds a
resource which its successor in the cycle is waiting for.
Strategies to deal with deadlock
 There are several techniques that can be used to deal with

deadlock:
 Avoidance
 Deadlock avoidance methods use some advance knowledge of the
resource usage of process to predict the future state of the system
for avoiding allocations that can eventually lead to a deadlock.
 Deadlock avoidance algorithms are usually in the following steps:
 The resource is allocated to the process only if it is safe to do so
otherwise the request is deferred.
 It is important to look at the notion of safety in resource allocation
because all the algorithms for deadlock avoidance are based on the
concept of safe and unsafe states.
 A system is said to be in safe state if it is not in a deadlock state
and there exists some ordering of the process in which the requests
 Avoidance
 Any ordering of the process that can guarantee the completion of
all the processes is called safe sequence.
 A system is said to be unsafe if no safe sequence exists for that
state.
 Deadlock avoidance algorithm basically perform resource allocation
is such a manner that ensures the system will always remain in safe
state.
 Prevention
 This approach is based on the idea of designing the system in such
a way that deadlocks become impossible.
 Mutual exclusion, hold-and-wait, no pre-emption and circular-wait
are the four necessary conditions for a deadlock to occur.
 If one of these conditions can never be satisfied then deadlock can
be prevented
 Prevention
 i.Collective requests
 These methods deny the hold and wait condition by ensuring that
whenever a process requests a resource it does not hold any other
resource.
 ii.Ordered Requests
 In this method circular-wait is denied such that each resource type
is assigned a unique global number to impose total ordering of all
resource types.
 iii.Preemption
 A preemptable resource is one whose state can be easily saved and
restored later. Deadlocks can be prevented using resource
allocation policies to deny no-preemption condition
 Deadlock Detection
 If deadlocks are not avoided, then another approach is to detect
when they have occurred and recover somehow.
 When should the deadlock detection be done? Frequently, or
infrequently?
 The answer may depend on how frequently deadlocks are expected
to occur, as well as the possible consequences of not catching them
immediately. ( If deadlocks are not removed immediately when they
occur, then more and more processes can "back up" behind the
deadlock, making the eventual task of unblocking the system more
difficult and possibly damaging to more processes. )
 Recovery From Deadlock

 There are three basic approaches to recovery from deadlock:Inform
the system operator, and allow him/her to take manual
intervention.
 Terminate one or more processes involved in the deadlock
 Preempt resources.

Lecture 7 Deadlocks

Uploaded by

Copyright:

Available Formats

Lecture 7 Deadlocks

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lecture 7 Deadlocks

Uploaded by

Copyright:

Available Formats

Concurrency: Deadlock and Starvation

 Understand the how processes share resources

 Four conditions have been identified as being necessary for

 There are several techniques that can be used to deal with

 Recovery From Deadlock

You might also like