4 – Deadlocks
(1) What is Deadlock?
Deadlock
• A set of processes is deadlocked if each process in the set is waiting for an event that
only another process in the set can cause.
• Suppose process D holds resource T and process C holds resource U.
• Now process D requests resource U and process C requests resource T but none of
process will get this resource because these resources are already hold by other process
so both can be blocked, with neither one be able to proceed, this situation is called
deadlock.
Example:
Figure 4-1 Resource allocation graphs. (a) Holding a resource. (b) Requesting a
resource. (c) Deadlock.
• As shown in figure 4-1, resource T assigned to process D and resource U is assigned to
process C.
• Process D is requesting / waiting for resource U and process C is requesting / waiting for
resource T.
• Processes C and D are in deadlock over resources T and U.
(2) Explain preemptable and non-preemptable resource with example.
• Resources come in two types: preemptable and non-preemptable.
• A preemptable resource is one that can be taken away from the process holding it with
no ill effects.
• Consider, for example, a system with 32 MB of user memory, one printer, and two 32-
1
, 4 – Deadlocks
MB processes such that each process wants to print something.
• Process A requests and gets the printer, then starts to compute the values to print.
• Before it has finished with the computation, it exceeds its time quantum and is
swapped out.
• Process B now runs and tries, unsuccessfully, to acquire the printer.
• Potentially, we now have a deadlock situation, because A has the printer and B has the
memory, and neither can proceed without the resource held by the other.
• Fortunately, it is possible to preempt (take away) the memory from B by swapping it out
and swapping A in. Now A can run, do its printing, and then release the printer. No
deadlock occurs.
• A non-preemptable resource, in contrast, is one that cannot be taken away from its
current owner without causing the computation to fail.
• If a process has begun to burn a CD-ROM, suddenly taking the CD recorder away from it
and giving it to another process will result in a garbled CD, CD recorders are not
preemptable at an arbitrary moment.
• In general, deadlocks involve non-preemptable resources.
(3) List the conditions that lead to deadlock.
Conditions that lead to deadlock
• There are four conditions that must hold for deadlock:
1) Mutual exclusion condition
▪ Each resource is either currently assigned to exactly one process or is
available.
2) Hold and wait condition
▪ Process currently holding resources granted earlier can request more
resources.
3) No preemption condition
▪ Previously granted resources cannot be forcibly taken away from process.
4) Circular wait condition
▪ There must be a circular chain of 2 or more processes. Each process is waiting
for resource that is held by next member of the chain.
• All four of these conditions must be present for a deadlock to occur.
2
(1) What is Deadlock?
Deadlock
• A set of processes is deadlocked if each process in the set is waiting for an event that
only another process in the set can cause.
• Suppose process D holds resource T and process C holds resource U.
• Now process D requests resource U and process C requests resource T but none of
process will get this resource because these resources are already hold by other process
so both can be blocked, with neither one be able to proceed, this situation is called
deadlock.
Example:
Figure 4-1 Resource allocation graphs. (a) Holding a resource. (b) Requesting a
resource. (c) Deadlock.
• As shown in figure 4-1, resource T assigned to process D and resource U is assigned to
process C.
• Process D is requesting / waiting for resource U and process C is requesting / waiting for
resource T.
• Processes C and D are in deadlock over resources T and U.
(2) Explain preemptable and non-preemptable resource with example.
• Resources come in two types: preemptable and non-preemptable.
• A preemptable resource is one that can be taken away from the process holding it with
no ill effects.
• Consider, for example, a system with 32 MB of user memory, one printer, and two 32-
1
, 4 – Deadlocks
MB processes such that each process wants to print something.
• Process A requests and gets the printer, then starts to compute the values to print.
• Before it has finished with the computation, it exceeds its time quantum and is
swapped out.
• Process B now runs and tries, unsuccessfully, to acquire the printer.
• Potentially, we now have a deadlock situation, because A has the printer and B has the
memory, and neither can proceed without the resource held by the other.
• Fortunately, it is possible to preempt (take away) the memory from B by swapping it out
and swapping A in. Now A can run, do its printing, and then release the printer. No
deadlock occurs.
• A non-preemptable resource, in contrast, is one that cannot be taken away from its
current owner without causing the computation to fail.
• If a process has begun to burn a CD-ROM, suddenly taking the CD recorder away from it
and giving it to another process will result in a garbled CD, CD recorders are not
preemptable at an arbitrary moment.
• In general, deadlocks involve non-preemptable resources.
(3) List the conditions that lead to deadlock.
Conditions that lead to deadlock
• There are four conditions that must hold for deadlock:
1) Mutual exclusion condition
▪ Each resource is either currently assigned to exactly one process or is
available.
2) Hold and wait condition
▪ Process currently holding resources granted earlier can request more
resources.
3) No preemption condition
▪ Previously granted resources cannot be forcibly taken away from process.
4) Circular wait condition
▪ There must be a circular chain of 2 or more processes. Each process is waiting
for resource that is held by next member of the chain.
• All four of these conditions must be present for a deadlock to occur.
2
