Operating System (CS - 308)
Chapter 7 - New Vocabulary
New Vocabulary
Dead lock - Definition                 Dead lock avoidance
Necessary Conditions                 Dead lock detection
Dead lock characterization         Methods for handling deadlocks
Dead lock Prevention                  Resource allocation graph
Deadlock - Definition
A set of processes is in a dealock state when every process in the set is waiting for an event that can only caused by another process in the set.

In a deadlock, processes never finish execution and system resources are tied up.

Necessary Conditions
There are 4 necessary conditions those happen the same time to have a deadlock
- Mutual Exclusion
- Hold and wait
- No preemption
- Circular wait

Back to Menu

Deadloch characterization
Deadlocks occur if and only if the following 4 conditions hold simultaneously in a system.
1. Mutual Exclusion:
- A resouce can be used only by one process a time (not simultaneous sharable).
2. Hold and wait
- A process that is holding at least one resorce is waiting to acquire additional resoources that currently being hold by another process.
3. No preemption
- Resources cannot be preempted - can only be voluntarily after the process has completed its task.
4. Circular wait
- There must be a circular chain of two or more processes, each of which is waiting for a resource held by the next member of the chain.
Back to Menu
Deadlock prevention
Prevent the deadlock by ensuring that at least one of the 4 necessary conditions cannot hold:
a. Mutual exlusion:
- Sharable resource donot require mutually exclusive access; cannot be involved in a deadlock.

- Problem:  Some of resources are not sharable.

b. Hold and wait:
- Allocate all resources request simultaneously or allocate none of them.

- Problem:

1) Dificult to know many resources a process needs
2) Resource utilization may be very low
3) Starvation is possible
c.  No preemption:
- A resource held by a blocked processes may be taken away.

- Problem: Some processes may cause problems if their resources are taken away.

d. Circular wait:
- Eliminate circular wait, impose a total ordering of all resources and no processes request a resource lower than what it is holding.

- Problem: Not practical

Back to Menu
Deadlock avoidance
Requires that the operating system be given in advance additional information concerning which resources a process will request and use during its lifetime.  With this additional knowledge, we can decide for each request whether or not the process should wait.  Each request requires that the system consider the resources currently available, the resources currently allocated to each process, and the future requests and releases of each process, to decide whether the current request can be satisfied or must be delayed.

Back to Menu

Deadlock detection
- Use the resource allocation graph.
- Every time a resource is requested, check the resource graph to see if any cycle exists
- If a cycle is detected, suspend the process to break the cycle
- high overhead

Back to Menu

Methods for handling deadlock
Method 1:    Ignore the deadlock problem
1. The overhead to deal with deadlock is very high
2. deadlocks occur very rarely

- prtend there is no deadlock problem.
- reboot the system when it happens
- acceptable from MBA point of view

Method 2:
Detection and recovery (see deadlock detection)
Method 3:
See deadlock prevention
Method 4:
See deadlock advoidance
Back to Menu
Resorce allocation graph
- It is a directed graph
- is used to detect a deadlock

- Nodes:

Circular node - represents a process
Square - represents a resource
- Edges:
-  The edge which has direction from square node to circular node is assignment edge

In the above picture, resource R is held by the process A.
- The edge which has direction from circular node to square node is request edge

In this picture, the process B is waiting for the resource S
A sample of Resource Allocation Graph is the figure in deadlock definition.

Back to Menu

Any commends or questions

Email to: dtnguyen@neiu.edu

Chapter 7 - New Vocabulary Page
Created by Doan Nguyen
Last Update March 26, 1999