Deadlock

A deadlock situation on a resource can arise if and only if all of the following conditions occur simultaneously in a system: Mutual exclusion: At least one resource must be held in a non-shareable mode. Otherwise, the processes would not be prevented from using the resource when necessary.

If another process requests that resource (non – shareable resource), the requesting process must be delayed until the resource has been released.

A system is in a safe state if the system can allocate resources to each process in some order and still avoid a deadlock.

The following condition is required for a deadlock to be possible:
a) mutual exclusion
b) a process may hold allocated resources while awaiting the assignment of other resources
c) no resource can be forcibly removed from a process holding it

The circular wait condition can be prevented by defining a linear ordering of resource types.

Banker’s algorithm is the deadlock avoidance algorithm.

The drawback of banker’s algorithm:
a) in advance processes rarely know how much resource they will need
b) the number of processes changes as time progresses
c) resource once available can disappear

For an effective operating system, every time a resource request is made at fixed time intervals to check for deadlock.

A problem encountered in multitasking when a process is perpetually denied necessary resources is called starvation.

The resource allocation graph is a visual (mathematical) way to determine the deadlock occurrence.

To avoid deadlock there must be a fixed number of resources to allocate.

Deadlock Prevention

Deadlock prevention is a set of methods to ensure that at least one of the necessary conditions cannot hold.

The number of resources requested by a process must not exceed the total number of resources available in the system.

The request and release of resources are system calls.

Multithreaded programs are more prone to deadlocks.

For a deadlock to arise, the following conditions must hold simultaneously:
a) Mutual exclusion
b) No preemption
c) Hold and wait

Mutual exclusion to prevail in the system at least one resource must be held in a non sharable mode.

For a Hold and wait condition to prevail a process must be holding at least one resource and waiting to acquire additional resources that are being held by other processes.

For non sharable resources like a printer, mutual exclusion must exist.

For sharable resources, mutual exclusion is not required.

Deadlock Avoidance

Each request requires that the system consider the resources currently available to decide whether the current request can be satisfied or must wait to avoid a future possible deadlock.

Given a priori information about the maximum number of resources of each type that maybe requested for each process, it is possible to construct an algorithm that ensures that the system will never enter a deadlock state.

A deadlock avoidance algorithm dynamically examines the resource allocation state to ensure that a circular wait condition can never exist.

A state is safe, if the system can allocate resources to each process in some order and still avoid a deadlock.

A system is in a safe state only if there exists a safe sequence.

All unsafe states are not deadlocks.

A system has 12 magnetic tape drives and 3 processes : P0, P1, and P2. Process P0 requires 10 tape drives, P1 requires 4 and P2 requires 9 tape drives.

Process    
P0            
P1                             
P2                             
 
Maximum needs (process-wise: P0 through P2 top to bottom)    
10             
4   
9
 
Currently allocated (process-wise)
5
2
2

Answer: Safe sequence is P1, P0, P2

If no cycle exists in the resource allocation graph then the system will be in a safe state.

The resource allocation graph is not applicable to a resource allocation system with multiple instances of each resource type.

The Banker’s algorithm is less efficient than the resource allocation graph algorithm.

The data structures available in the Banker’s algorithm are Available, Need, Allocation.

A system with 5 processes P0 through P4 and three resource types A, B, C have A with 10 instances, B with 5 instances, and C with 7 instances. At time t0, the following snapshot has been taken:

Process
P0               
P1               
P2           
P3           
P4       
 
Allocation (process-wise : P0 through P4 top TO bottom) 
A   B   C
0   1   0
2   0   0
3   0   2
2   1   1
0   0   2
 
MAX (process-wise: P0 through P4 top TO bottom)
A   B   C
7   5   3
3   2   2
9   0   2
2   2   2
4   3   3
 
Available
A   B   C
3   3   2

The sequence <P1, P3, P4, P2, P0> leads the system to a safe state.

Deadlock Detection

The wait-for graph is a deadlock detection algorithm that is applicable when all resources have a single instance.

An edge from process Pi to Pj in a wait for graph indicates that Pi is waiting for Pj to release a resource that Pi needs.

If the wait for graph contains a cycle then a deadlock exists.

If deadlocks occur frequently, the detection algorithm must be invoked frequently.

Considerable overhead in computation time is the disadvantage of invoking the detection algorithm for every request.

A deadlock eventually cripples system throughput and will cause the CPU utilization to drop.

A computer system has 6 tape drives, with ‘n’ processes competing for them. Each process may need 3 tape drives. The maximum value of ‘n’ for which the system is guaranteed to be deadlock free is 2.

A system has 3 processes sharing 4 resources. If each process needs a maximum of 2 units then, deadlock can never occur.

‘m’ processes share ‘n’ resources of the same type. The maximum need of each process doesn’t exceed ‘n’ and the sum of all their maximum needs is always less than m+n. In this setup, deadlock can never occur.

Deadlock Recovery

A deadlock can be broken by abort one or more processes to break the circular wait.

The two ways of aborting processes and eliminating deadlocks are Abort one process at a time until the deadlock cycle is eliminated.

Those processes should be aborted on occurrence of a deadlock, the termination of incurs minimum cost.

If we preempt a resource from a process, the process cannot continue with its normal execution and it must be rolled back.

To roll back the process to a safe state, the system needs to keep more information about the states of processes.

If the resources are always preempted from the same process starvation can occur.

What is the solution to starvation?
    the number of rollbacks must be included in the cost factor.