OS: Deadlocks

Deadlock Definition and Handling

Deadlock: definition 

There exists a cycle of processes such that each process 

cannot proceed until the next process takes some specific 

action. 

Result: all processes in the cycle are stuck! 

There are three practical strategies for dealing with deadlocks

·        Deadlock Prevention

·        Deadlock Avoidance

·        Deadlock Detection and Recovery

Deadlock Prevention

Since four conditions are required to produce a deadlock, one can infer that if one or more of the conditions is negated, then deadlock can be prevented. Thus, the basic idea of deadlock prevention is to deny at least one of the four necessary conditions for deadlock. 

The mutual exclusion condition cannot be disallowed, so it is customary to prevent one or more of the remaining three conditions. 

Deadlock prevention methods tend to be wasteful in terms of machine resources.

• Denying Hold and Wait
• Denying No Preemption
• Denying Circular Wait

Deadlock Avoidance

Deadlock avoidance attempts to predict the possibility of a deadlock dynamically as each resource is made. The basic idea of deadlock avoidance is to grant only those requests for available resources that cannot possibly result in a state of deadlock. This strategy is usually implemented by checking the effect of granting a particular resource request by the resource allocator.  If granting of the resource cannot possibly lead to deadlock, the resource is granted to the requester. Otherwise, the requesting process is suspended until its pending request can be safely granted.

The most famous deadlock avoidance algorithm is Dijikstra’s Banker’s Algorithm.The algorithm is called by this name because it involves a banker who makes loan and receives payments from a given source of capital. The banker will only grant a loan if he can still meet the needs of other customers, based on their projected future loan requirements.

and finally...

Deadlock Detection and Recovery

This technique does not attempt to prevent deadlocks; instead, it lets them occur.The system detects when deadlock happens, and then takes some reactive action to recover .With deadlock detection, requested resources are granted to processes whenever possiblePeriodically, operating system performs an algorithm that allows it to detect the circular wait condition(polling). polling can be made as frequently as resource request, or less frequently, depending on how likely it is for a deadlock to occur.

Checking at each resource request has two advantages: It leads to early detection, and the algorithm is relatively simple because it is based on incremental changes to the state of the systemOn the other hand, such frequent checks consume considerable processor time. Once the deadlock algorithm has successfully detected a deadlock, some strategy is needed for recovery

Three approaches are

• Recovery through Preemption; In some cases, it may be possible to temporarily take a resource away from its current owner and give it to another.
• Recovery through Rollback; If it is known that deadlocks are likely, one can arrange to have processes checkpointed periodically. For example, can undo transactions, thus free locks on database records. This often requires extra software functionality.
• Recovery through Termination; The most trivial way to break a deadlock is to kill one or more processes. One possibility is to kill a process in the cycle. Warning! Irrecoverable losses or erroneous results may occur, even if this is the least advanced process.

The Ostrich Algorithm

• The UNIX approach is just to ignore the problem on the assumption that most users would prefer an occasional deadlock over a rule restricting user access to only one resource at a time.
• Just like an ostrich covering its head under sand and pretending no one is seeing. :)
• The problem is that the prevention price is high, mostly in terms of putting inconvenient restrictions on processes