24308 CSC 080A - 0 - Operating Systems -- Deadlocks

24308 CSC 080A - 0 - Operating Systems

Spring 2005
Monday, 2:30 pm - 3:50 pm, Kramer Science Center KSC 102A
Herbert J. Bernstein (yaya@dowling.edu)

Deadlocks

This web page is http://www.bernstein-plus-sons.com/.dowling/CSC3080S05/CSC3080_Deadlocks.html
Copyright © 2002 Herbert J. Bernstein and other parties. All rights reserved.

Deadlocks

Topics

Basic Issues in Deadlocks

Process 1 waiting for resource held by process 2 which is waiting for resource held by process 1
Especially serious when there is only one CPU being shared
Always request multiple resources in the same order
Provide a mechanism to ensure release of resources held by blocked processes
See http://java.sun.com/docs/books/tutorial/essential/threads/deadlock.html

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 can 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 6 March 2002.
yaya@dowling.edu

24308 CSC 080A - 0 - Operating Systems

Spring 2005 Monday, 2:30 pm - 3:50 pm, Kramer Science Center KSC 102A Herbert J. Bernstein (yaya@dowling.edu)

Deadlocks

Deadlocks

Topics

Basic Issues in Deadlocks

Detailed Understanding of Deadlocks

Spring 2005
Monday, 2:30 pm - 3:50 pm, Kramer Science Center KSC 102A
Herbert J. Bernstein (yaya@dowling.edu)