Operating System | Deadlock | Deadlock -Conditions,Prevention,Recovery ,Avoidance,|Algorithm-Banker,RAG,

Deadlock

DEADLOCK

When a process is in the need of some resource, physical or logical, it requests the kernel of operating system. The kernel, being the resource manager, allocates the resources to the processes. If there is a delay in the allocation of the resource to the process, it results in the idling of process. The deadlock is a situation in which some processes in the system faces indefinite delays in resource allocation.
The simplest example of deadlock is where process 1 has been allocated nonshareable resources A, say, a tap drive, and process 2 has be allocated nonsharable resource B, say, a printer. Now, if it turns out that process 1 needs resource B (printer) to proceed and process 2 needs resource A (the tape drive) to proceed and these are the only two processes in the system, each is blocked the other and all useful work in the system stops. This situation ifs termed deadlock. The system is in deadlock state because each process holds a resource .

INR 19,900

DEADLOCK CONDITIONS:-
1. Mutual Exclusion
2. Hold and Wait Condition
3. No-Preemptive Condition
4. Circular Wait Condition

1. Mutual Exclusion Condition - The resources involved are non-shareable. Explanation: At least one resource (thread) must be held in a non-shareable mode, that is, only one process at a time claims exclusive control of the resource. If another process requests that resource, the requesting process must be delayed until the resource has been released.
2. Hold and Wait Condition  -Requesting process hold already, resources while waiting for requested resources.
Explanation: There must exist a process that is holding a resource already allocated to it while waiting for additional resource that are currently being held by other processes.
3. No-Preemptive Condition Resources already allocated to a process cannot be preempted. Explanation: Resources cannot be removed from the processes are used to completion or released voluntarily by the process holding it.
4. Circular Wait Condition The processes in the system form a circular list or chain where each process in the list is waiting for a resource held by the next process in the list.

Resource-Allocation Graph
The deadlock conditions can be modeled using a directed graph called a resource allocation graph (RAG). A resource allocation graph is a directed graph. It consists of 2 kinds of nodes: Boxes — Boxes represent resources, and Instances of the resource are represented as dots within the box i.e. how many units of that resource exist in the system.
Circles — Circles represent threads / processes. They may be a user process or a system process. An edge can exist only between a process node and a resource node. There are 2 kinds of (directed) edges:
Request edge: It represents resource request. It starts from process and terminates to a resource. It indicates the process has requested the resource, and is waiting to acquire it.
Assignment edge: It represents resource allocation. It starts from resource instance and terminates to process. It indicates the process is holding the resource instance. When a request is made, a request edge is added. When request is fulfilled, the request edge is transformed into an assignment edge. When process releases the resource, the assignment edge is deleted.
There are following Approaches to deal with the problem of Deadlock.
Ostrich Approach — sticks your head in the sand and ignores the problem. This approach can be quite useful if you believe that they are rarest chances of deadlock occurrence. In that situation it is not a justifiable proposition to invest a lot in identifying deadlocks and tackling with it. Rather a better option is ignore it.
Deadlock Prevention: This approach prevents deadlock from occurring by eliminating one of the four deadlock conditions.
Deadlock detection algorithms: This approach detects when deadlock has occurred.
Deadlock Recovery Algorithms: After detecting the deadlock, it breaks the deadlock.
Deadlock Avoidance Algorithms: This approach considers resources currently available, resources allocated to each thread, and possible future requests, and only fulfill requests that will not lead to deadlock .

INR29000

Deadlock Prevention is based on designing resource allocation policies, which make deadlocks impossible. Use of the deadlock prevention approach avoids the over- head of deadlock detection and resolution. However, it incurs two kinds of costs - overhead of using the resource allocation policy, and cost of resource idling due to the policy.
Four conditions must hold for a resource deadlock to arise in a system:

1. Non-shareable resources
2.Hold-and-wait by processes
3. No preemption of resources
4.Circular waits
Ensuring that one of these conditions cannot be satisfied prevents deadlocks. We first discuss how each of these conditions can be prevented and then discuss a couple of resource allocation policies based on the prevention approach, it follows that deadlock might be prevented by denying any one of the conditions.
Elimination of “Mutual Exclusion” Condition-
The mutual exclusion condition must hold for non-sharable resources. That is, several processes cannot simultaneously share a single resource. This condition is difficult to eliminate because some resources, such as the tap drive and printer, are inherently non-shareable. Note that shareable resources like readonly-file do not require mutually exclusive access and thus cannot be involved in deadlock.
Elimination of “Hold and Wait” Condition
There are two possibilities for elimination -The first alternative is that a process request be granted all of the resources it needs at once, prior to execution.
The second alternative is to disallow a process from requesting resources whenever it has previously allocated resources. This strategy requires that all of the resources a process will need must be requested at once. The system must grant resources on “all or none” basis. If the complete set of resources needed by a process is not currently available, then the process must wait until the complete set is available. While the process waits, however, it may not hold any resources. Thus the “wait for” condition is denied and deadlocks simply cannot occur. This strategy can lead to serious waste of resources.
Elimination of “Non-Preemption” Condition
The non preemption condition can be alleviated by forcing a process waiting for a resource that cannot immediately be allocated to relinquish all of its currently held resources, so that other processes may use them to finish. Suppose a system does allow processes to hold resources while requesting additional resources. Consider what happens when a request cannot be satisfied. A process holds resources a second process may need in order to proceed while second process may hold the resources needed by the first process. This is a deadlock. This strategy requires that when a process that is holding some resources is denied a request for additional resources. The process must release its held resources and, if necessary, request them again together with additional resources. Implementation of this strategy denies the “no-preemptive” condition effectively. The main drawback of this approach is high cost. When a process releases resources the process may lose all its work to that point. One serious consequence of this strategy is the possibility of indefinite postponement (starvation). A process might be held off indefinitely as it repeatedly requests and releases the same resources.

I Phone 13INR 79,900

Elimination of “Circular Wait” Condition- Presence of a cycle in resource allocation graph indicates the “circular wait” condition. The last condition, the circular wait, can be denied by imposing a total ordering on all of the resource types and than forcing, all processes to request the resources in order (increasing or decreasing). This strategy impose a total ordering of all resources types, and to require that each process requests resources in a numerical order (increasing or decreasing) of enumeration. With this rule, the resource allocation graph can never have a cycle. For example, provide a global numbering of all the resources .
Deadlock Avoidance
This approach to the deadlock problem anticipates deadlock before it actually occurs. This approach employs an algorithm to access the possibility that deadlock could occur and acting accordingly. This method differs from deadlock prevention, which guarantees that deadlock cannot occur by denying one of the necessary conditions of deadlock. If the necessary conditions for a deadlock are in place, it is still possible to avoid deadlock by being careful when resources are allocated. Perhaps the most famous deadlock avoidance algorithm, due to Dijkstra [1965], is the Banker’s algorithm.
Deadlock Avoidance Using Banker’s algorithm.
Advantages:
1.There is no need to preempt resources and rollback state (as in deadlock detection & recovery) .
2. It is less restrictive than deadlock prevention .
Disadvantages:
1. In this case maximum resource requirement for each process must be stated in advance.
2. Processes being considered must be independent (i.e., unconstrained by synchronization requirements) .
3. There must be a fixed number of resources (i.e., can’t add resources, resources can’t break) and processes (i.e., can’t add or delete processes) .
4. Huge overhead — Operating system must use the algorithm every time a resource is requested. So a huge overhead is involved.

INR162,700

Deadlock Detection
Deadlock detection is the process of actually determining that a deadlock exists and identifying the processes and resources involved in the deadlock. The basic idea is to check allocation against resource availability for all possible allocation sequences to determine if the system is in deadlocked state a. Of course, the deadlock detection algorithm is only half of this strategy. Once a deadlock is detected, there needs to be a way to recover several alternatives exists:
• Temporarily prevent resources from deadlocked processes.
• Back off a process to some check point allowing preemption of a needed resource and restarting the process at the checkpoint later.
• Successively kill processes until the system is deadlock free. These methods are expensive in the sense that each iteration calls the detection algorithm until the system proves to be deadlock free. The complexity of algorithm is O(N2) where N is the number of proceeds. Another potential problem is starvation; same process killed repeatedly.

Deadlock Recovery
It considers resources currently available, resources allocated to each thread, and possible future requests, and only fulfill requests that will not lead to deadlock .Deadlock avoidance needs too much a priori information and not very dynamic (can’t add processes or resources), and involves huge overhead .

Mixed Approaches to Deadlock Handling
The deadlock handling approaches differ in terms of theirv usage implications. Hence it is not possible to use a single deadlock handling approach to govern the allocation of all resources. The following mixed approach is found useful:

1. System control block: Control blocks like JCB, PCB etc. can be acquired in a specific order. Hence resource ranking can be used here. If a simpler strategy is desired, all control blocks for a job or process can be allocated together at its initiation.
2. I/O devices files: Avoidance is the only practical strategy for these resources. However, in order to eliminate the overheads of avoidance, new devices are added as and when needed. This is done using the concept of spooling. If a system has only one printer, many printers are created by using some disk area to store a file to be printed. Actual printing takes place when a printer becomes available.

3. Main memory: No deadlock handling is explicitly necessary. The memory allocated to a program is simply preempted by swapping out the program whenever the memory is needed for another program.

INR3200