Operating Systems
BCSC 0004
Deadlocks
1
Deadlock
In a multiprogramming system, a number of process compete for limited number of
resources and if a resource is not available at that instance then process enters into
waiting states.
If a process unable to change its waiting state indefinitely because the resources
required by it are held by another waiting process then system is said to be in
deadlock.
R2
P1 P2
R1
System Model
Every process will request for the resources.
If entertained then, process will use the resources.
Process must release the resource after use.
Necessary Condition of Deadlock
• Mutual exclusion: At least one resource type in the system which can be used in
non- shareable mode i.e mutual exclusion (one at a time/ one by one) e. g. CPU time,
printer.
• Hold and wait: A process is currently holding at least one resource and requesting
additional resources which are being held by other processes.
• No-preemption: A resource can not be preempted from a process by any other
process resource can be released only voluntarily by the process holding it.
Necessary Condition of Deadlock
• Circular wait: Each process must be waiting for a resource which is being held
by another process, which in turn is waiting for the first process to release the
resources.
P1 P2 P3
Deadlock handling Methods
Prevention: Means design such a system which violate at least one of four
necessary conditions of deadlock and ensure independence from deadlock.
Avoidance: system maintains a set of data using which it takes a decision weather
to entertain a new request or not, to be in safe state.
Detection and recovery: Here we wait until deadlock occurs and once we detect it
then recover from it.
Ignorance: we ignore the problem as if it does not exist.
Deadlock Prevention
This guarantees that there is no deadlock.
Prevention method cannot violate the mutual exclusion condition.
Violate Hold and wait
Conservative approach: Process is allowed to start execution if and only if it has acquired
all the resources. (Less efficient, not implementable, easy, deadlock independence)
Do not hold: Process will acquire only desired resources, but before making any fresh
request it must release all the resources that it currently hold. (Efficient, implementable)
Wait timeouts: we place a maximum time upto which a process can wait. After which
process must release all the holding resources & exit.
Deadlock Prevention
• Violate No- Preemption
Forcefully preemption: we allow a process to forcefully preempt the resources holding
by other process.
This method may be used by high priority process or system process.
The process which are in waiting state must be selected as a victim instead of process
in the running state.
Deadlock Prevention
• Violate circular wait
Circular wait can be eliminated by first giving a natural number of every resource
F : N R
Allow every process to either only in the increasing or decreasing order of the
resource number.
If a process require a lesser number (in any of increasing order), then it must first
release all the resources larger than required number.
Deadlock Avoidance
A deadlock avoidance algorithm dynamically examines the resource allocation state.
The resource allocation state is defined by the number of available and allocated
resources and the maximum demands of the processes before allowing that request first.
We check, if there exist “ some sequence in which we can satisfies demand of every
process without going into deadlock, if yes the sequence is called safe sequence” and
request can be allowed. Otherwise there is a possibility of going into deadlock.
Banker’s Algorithm
The banker’s algorithm is
a resource allocation and
deadlock avoidance
algorithm that tests for
safety.
The algorithm for finding
out whether or not a
system is in a safe state.
Resource-Request Algorithm
Considering a system with five processes P0 through P4 and three resources of type A, B, C. Resource
type A has 10 instances, B has 5 instances and type C has 7 instances. Suppose at time t0 following
snapshot of the system has been taken:
Is the system in a safe state? If Yes, then what is the safe sequence?
Applying the Safety algorithm on the given system,
What will happen if process P1 requests one additional instance of resource type A
and two instances of resource type C?
Hence the new system state is safe, so we can immediately grant the request for process P1
If a request (3 , 3, 0) by process P4 arrives in the state defined by
above can it be granted immediately?
• If a request (0 , 2, 0) by process P0 arrives then check weather it is granted
or not? If granted then the new state of the system?
Process Allocation Need Available
P0 0 3 0 7 2 3 2 1 0
P1 3 0 2 0 2 0
P2 3 0 2 8 0 0
P3 2 1 1 0 1 1
P4 0 0 2 4 3 1
All five processes are in waiting state as none is able to satisfy the condition
Needi < Available
Deadlock detection and recovery
Here we do not check safety and where any process request for some resources then
these resources are allocated immediately, if available.
Here there is a possibility of deadlock, which must be detected using different
approach.
Active approach: here we simply invoke the algorithm at defined intervals for
example once per hour or whenever CPU utilization drop below 40%.
Lazy approach: whenever CPU utilization drops below 40 % or some unusual
performance is there, we go for detection.
Deadlock recovery
Optimistic approach Pessimistic approach
Pre-empt some resources from Process termination
processes and give these resources to Abort all deadlock process (Costly)
other processes until the deadlock cycle Abort one process at a time and decide
is broken. next to abort after deadlock detection.
Handles the three problems Some factor based on these process will
Selecting a victim process be terminated:
Rollback Priority of the process
Starvation How long the process has completed
How much longer a process will
compute before completion
How many and what type of resources
process has used
How many resources the process needs
to complete its execution.
