 |
22908 CSC 080A - 0 - Operating Systems
Spring 2012
Herbert J. Bernstein (yaya@dowling.edu)
Deadlocks
|
|
This web page is http://www.bernstein-plus-sons.com/.dowling/CSC3080S12/CSC3080_Deadlocks.html
Copyright © 2002 Herbert
J. Bernstein and other parties. All rights reserved.
Deadlocks
Topics
Basic Issues in Deadlocks
Detailed Understanding of
Deadlocks
- Some resources can be shared
- Some resources must be held and used to completion by one process at a time
- Deadlock occurs when:
- There are some non-sharable resources held by various processes,
- Such that each process is waiting for a non-sharable resource held by another process.
- Since each process is waiting, it will never release the resources needed
by any of the other processes.
- No process will ever awaken
- Typical sequences:
- Request lock on resource
- Use resource
- Release lock on resource
- Conditions for deadlock (Coffman et. al, 1971)
- Non-sharable resources (mutual exclusion - free or owned by a process)
- Process holding resources can request resources (hold and wait)
- Process holding resources cannot be forced to release them (non-preemption)
- There is a closed cycle of processes each of which is waiting for a resource
held by the next member of the cycle (circular wait)
- Graphical models
- Edge from resource to process: resource held by that process
- Edge from process to resource: process is waiting for resource
- Cycles are deadlocks
- Effective for unique resources
- Matrix models
- Define resource vectors (counts of resources taken or needed)
- Total existing resources for the system (vector)
- Currently allocated resources for each process (matrix)
- Currently available resources for the system (vector)
- Currently needed resources for each process (matrix)
- Detect deadlocks
- Scan for processes requesting no more than currently available resources
- Add those resources back into the pool and check off those processes
- Repeat until all processes are satisfied or some are blocked
- Can also be represented graphically
- Solutions
- Avoid the problem
- create a monitor/spooler to share resources
- allocate resources in fixed order (global numbering)
- request all resources up front
- release all resources before requesting a new block of resources
- two-phase locking (try for all resources, release and try again
if any are blocked)
- require pre-declaration of resources to be requested
only schedule jobs for which resources are available
Dijkstra's Banker's algorithm
- never hold a resource indefinitely (release or allow preemption)
- Reboot -- ignore the problem
- Break the cycle by restarting some process in the cycle
- Break the cycle by killing some process
Updated 7 March 2012.
yaya@dowling.edu