Chapter 06

Operating Systems:
Internals and Design Principles, 6/E

William Stallings
Chapter 6
Concurrency: Deadlock and
Starvation
Dave Bremer
Otago Polytechnic, N.Z.
©2008, Prentice Hall
Roadmap
• Principals of Deadlock
– Deadlock prevention
– Deadlock Avoidance
– Deadlock detection
– An Integrated deadlock strategy
• Dining Philosophers Problem
• Concurrency Mechanisms in UNIX, Linux,
Solaris and Windows
Deadlock
• A set of processes is deadlocked when
each process in the set is blocked awaiting
an event that can only be triggered by
another blocked process in the set
– Typically involves processes competing for
the same set of resources
• No efficient solution
Potential Deadlock
I need I need
quad C quad B and
and B C
I need
I need quad A and
quad D B
and A
Actual Deadlock
HALT until HALT until

D is free C is free
HALT until
HALT until B is free
A is free
Two Processes P and Q
• Lets look at this with
two processes P and Q
• Each needing
exclusive access to a
resource A and B for a
period of time
Joint Progress
Diagram of Deadlock
Alternative logic
• Suppose that P does
not need both
resources at the same
time so that the two
processes have this
form
Diagram of
alternative logic
Resource Categories
Two general categories of resources:
• Reusable
– can be safely used by only one process at a
time and is not depleted by that use.
• Consumable
– one that can be created (produced) and
destroyed (consumed).
Reusable Resources
• Such as:
– Processors, I/O channels, main and
secondary memory, devices, and data
structures such as files, databases, and
semaphores
• Deadlock occurs if each process holds
one resource and requests the other
Example of
Reuse Deadlock
• Consider two processes that compete for
exclusive access to a disk file D and a
tape drive T.
• Deadlock occurs if each process holds
one resource and requests the other.
Reusable Resources
Example
Example 2:
Memory Request
• Space is available for allocation of
200Kbytes, and the following sequence of
events occur
P1 P2
... ...
Request 80 Kbytes; Request 70 Kbytes;
... ...
Request 60 Kbytes; Request 80 Kbytes;
• Deadlock occurs if both processes

progress to their second request
Consumable Resources
• Such as Interrupts, signals, messages,
and information in I/O buffers
• Deadlock may occur if a Receive message
is blocking
• May take a rare combination of events to
cause deadlock
Example of Deadlock
• Consider a pair of processes, in which
each process attempts to receive a
message from the other process and then
send a message to the other process
Resource Allocation
Graphs
• Directed graph that depicts a state of the
system of resources and processes
Conditions for
possible Deadlock
• Mutual exclusion
– Only one process may use a resource at a
time
• Hold-and-wait
– A process may hold allocated resources while
awaiting assignment of others
• No pre-emption
– No resource can be forcibly removed form a
process holding it
Actual Deadlock
Requires …
All previous 3 conditions plus:
• Circular wait
– A closed chain of processes exists, such that
each process holds at least one resource
needed by the next process in the chain
Resource Allocation
Graphs of deadlock
Resource Allocation
Graphs
Dealing with Deadlock
• Three general approaches exist for
dealing with deadlock.
– Prevent deadlock
– Avoid deadlock
– Detect Deadlock
Roadmap
• Principals of Deadlock
– Deadlock prevention
– Deadlock Avoidance
– Deadlock detection
– An Integrated deadlock strategy
• Dining Philosophers Problem
• Concurrency Mechanisms in UNIX, Linux,
Solaris and Windows
Deadlock Prevention
Strategy
• Design a system in such a way that the
possibility of deadlock is excluded.
• Two main methods
– Indirect – prevent all three of the necessary
conditions occurring at once
– Direct – prevent circular waits
Deadlock Prevention
Conditions 1 & 2
• Mutual Exclusion
– Must be supported by the OS
• Hold and Wait

– Require a process request all of its required
resources at one time
Deadlock Prevention
Conditions 3 & 4
• No Preemption
– Process must release resource and request
again
– OS may preempt a process to require it
releases its resources
• Circular Wait
– Define a linear ordering of resource types

Chapter 06

Uploaded by

Copyright:

Available Formats

Chapter 06

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

Chapter 06

Uploaded by

Copyright:

Available Formats

Operating Systems:

Internals and Design Principles, 6/E

HALT until HALT until

• Deadlock occurs if both processes

• Hold and Wait

You might also like