See discussions, stats, and author profiles for this publication at: https://www.researchgate.
net/publication/296895088
Deadlocks in Operating System
Data · March 2016
CITATIONS READS
0 6,785
1 author:
Qasim Mohammed Hussein
Al-Kunooze University College
108 PUBLICATIONS 157 CITATIONS
SEE PROFILE
All content following this page was uploaded by Qasim Mohammed Hussein on 06 March 2016.
The user has requested enhancement of the downloaded file.
Deadlock in Operating System
Assistance Prof. Dr.
Qasim Mohammed Hussein
Reference: operating system concepts
Abraham Silberschatz, Peter Baer Galvin, Greg Gagne
System model
• A system consists of a finite number of resources to be
distributed among a number of competing processes
• Resources may be either physical (printer, memory
space, CPU cycle) or logical (files, semaphores).
Process may utilize a resource in the following sequence:
1) Request. If the request cannot be granted
immediately then the requesting process must wait
until it can acquire the resource.
2) Use. The process can operate on the resource .
3) Release. The process releases the resource
System model
Process may utilize a resource in the following
sequence:
1) Request. If the request cannot be granted
immediately then the requesting process must
wait until it can acquire the resource.
2) Use. The process can operate on the resource .
3) Release. The process releases the resource.
Deadlock state
• A set of processes is in a deadlock state when
every process in the set is waiting for an event
that can be caused only by another process in
the set.
• Consider a process that copies data from a
DVD drive to a file on disk, sorts the file, and
then prints the results to a printer. The
process must initially request the DVD drive,
disk file, and printer
Deadlock conditions
• Mutual exclusion. At least one resource must be held in a
non-sharable mode; that is, only one process at a time can use
the resource. If another process requests that resource, the
requesting process must be delayed until the resource has been
released.
• Hold and wait. A process must be holding at least one
resource and waiting to acquire additional resources that are
currently being held by other processes.
• No preemption. Resources cannot be preempted; that is, a
resource can be released only voluntarily by the process
holding it, after that process has completed its task.
• Circular wait. A set { P1 , •••r Pn} of waiting processes must
exist such that Po is waiting for a resource held by PI, PI is
waiting for a resource held by P2 , ... , Pn-1is waiting for a
resource held by Pn , and Pn is waiting for a resource held by
Methods for Handling Deadlocks
We can deal with the deadlock problem in
one of three ways:
1) We can use a protocol to prevent or
avoid deadlocks. ensuring that the
system will never enter a deadlock state.
2) We can allow the system to enter a
deadlock state, detect it, and recover.
3) We can ignore the problem altogether
and pretend that deadlocks never occur
in the system.
Methods for Handling Deadlocks
• To ensure that deadlocks never occur, the
system can use either a deadlock prevention
• or a deadlock-avoidance scheme.
• Deadlock prevention provides a set of
methods for ensuring that at least one of the
necessary conditions cannot hold.
Deadlock prevention
We can prevent the occurrence of a deadlock by
ensuring that at least one of deadlock conditions
cannot hold.
1) The mutual-exclusion condition must hold for
non-sharable resources. Sharable resources
do not require mutually exclusive access and
thus cannot be involved in a deadlock.
• Example, a printer cannot be simultaneously
shared by several processes. Read-only files
are a good example of a sharable resource.
Deadlock prevention
This an be implemented by two protocols:
1) Allocate all resource to process before its execution.
2) Allows a process to request resources only when it
has none.
The main disadvantages of the two protocols are:
1. Low resource utilization: since resources may
be allocated but unused for a long period
2. Starvation is possible.
Deadlock prevention
3. No Preemption: we can use the following
protocol. If a process is holding some resources
and requests another resource that cannot be
immediately allocated to it (the process must
wait), then all resources currently being held are
preempted.
• 4. Circular Wait: By impose a total ordering of
all resource types and to require that each
process requests resources in an increasing
order of enumeration. Such as : tape drive = 1,
F(disk drive) = 5, and F(printer) = 12
Deadlock Avoidance
• Require that the system has additional information
about how resources are to be requested.
• The simplest and most useful model requires that
each process declare the maximum number of
resources of each type that it may need.
• A deadlock-avoidance algorithm dynamically
examines the resource-allocation state to ensure that
a circular wait condition can never exist.
The resource-allocation state is defined by the number
of available and allocated resources and the maximum
demands of the processes
Banker's Algorithm example
Deadlock Detection
If a system does not employ either a deadlock-
prevention or a deadlock avoidance algorithm then a
deadlock situation may occur. So, the system must
provide:
1) An algorithm that examines the state of the system
to determine whether a deadlock has occurred.
2) An algorithm to recover from the deadlock.
Invoking the detection algorithm, we need to answer:
1. How often is a deadlock likely to occur?
2. How many processes will be affected by deadlock
when it happens?
Deadlock Detection
• A detection and recovery will incur a considerable
overhead in computation time that includes:
1) Run time cost of maintaining the necessary
information.
2) Executing the detection algorithm.
3) The potential losses inherent in recovery from a
deadlock.
Deadlock recovery
• When a deadlock exists, two alternatives are
available.
1. One possibility is to inform the operator that
a deadlock has occurred and to let the
operator deal with the deadlock manually.
2. The system recovers from the deadlock
automatically. There are two options for
breaking a deadlock: process termination
and resource preemption
Recovery from deadlock: (A) process termination
In aborting processes to eliminate the deadlock,
there are two ways:
1. Abort all deadlocked processes. will break
the deadlock cycle, but at great expense.
2. Abort one process at a time until the
deadlock cycle is eliminated. This method
incurs considerable overhead, since, after
each process is aborted, a deadlock detection
algorithm must be invoked to determine
whether any processes are still deadlocked.
Recovery from deadlock: (B) Resource Preemption
preempt some resources from processes and give
these resources to other processes until the
deadlock cycle is broken. three issues need to be
addressed:
1) Selecting a victim. Determine which resources
and which processes are to be preempted?
2) Rollback. If we preempt a resource from a
process, what should be done with that process?
3) Starvation. How do we ensure that starvation will
not occur, guarantee that resources will not
always be preempted from the same process?
View publication stats
