METHODS OF HANDLING DEADLOCK PDF

Preview

Summary

METHODS OF HANDLING DEADLOCK-Operating Systems...

Description

Lecture #23 METHODS OF HANDLING DEADLOCK In general, there are four strategies of dealing with deadlock problem: 1. Deadlock Prevention: Prevent deadlock by res ource scheduling so as to negate at least one of the four conditions. 2. Deadlock Avoidance: Avoid deadlock by careful resourc e scheduling. 3. Deadlock Detection and Recovery: Detect deadlock and when it occurs, take steps to recover. 4. Just ignore the deadlock problem altogether and pretend that deadlocks never occur in the system.

Deadlock Prevention A deadlock may be prevented by denying any one of the conditions. a) Elimination of “Mutual Exclusion” Condition: The mutual exclusion condition must hold for nonsharable resources. That is, several processes cannot simultaneously share a single resource. This condition is difficult to eliminate because some resources, such as the Hard disc drive and printer, are inherentl y nonshareable. Note that shareable resources like read-only-file do not require mutually exclusive access and thus cannot be involved in deadlock. b) Elimination of “Hold and Wait” Condition: There are two possibilities for elimination of the second condition. 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 resourc es a process will need must be requested at once. The system must grant resourc es 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 availabl e. While the process waits, however, it may not hold any resources. Thus the “wait for” condition is denied and deadlocks cannot occur. This strategy can lead to serious waste of resources. c) Elimination of “No-preem ption” Condition: The non-preem ption c ondition can be alleviated by forcing a process waiting for a resource that cannot imm ediately be allocated to relinquish all of its currently held resources, so that other processes may use them to finish. 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. Implem entation of this strategy denies the “no-preemptive” condition effectively. d) Elimination of “Circular Wait” Condition: The fourth and final condition for deadlocks is the circular-wait condition. One way to ensure that this condition never holds is to impose a total ordering of all resource types and to require that each process requests resources in an increasing order of enumeration. To illustrate, we let R = { R1, R2, ... , Rm} be the set of resource types. We assign to each resource type a unique integer number, which allows us to compare two resources and to determine whether one precedes another in our ordering. Formally, we define a one-to-one function F: RN, where N is the set of natural numbers. For example, if the set of resource types R includes tape drives, disk drives, and printers, then the function F might be defined as follows:

F (tape drive) = 1 F (disk drive) = 5 F (printer) = 12 We can now consider the following protocol to prevent deadlocks: Each process can request resources only in an increasing order of enumeration. That is, a process can initially request any number of instances of a resource type --say, Ri, After that, the process can request instances of resource type Rj if and only if F(Rj) > F(Ri). For example, using the function defined previously, a process that wants to use the tape drive and printer at the same time must first request the tape drive and then request the printer. Alternatively, we can require that a process requesting an instance of resource type Rj must have released any resources R; such that F(Ri) > F(Rj). It must also be noted that if several instances of the same resource type are needed, a single request for all of them must be issued. If these two protocols are used, then the circular-wait condition cannot hold. We can demonstrate this fact by assuming that a circular wait exists (proof by contradiction). Let the set of processes involved in the circular wait be { P0 , P1, ... , Pn }, where Pi is waiting for a resource Ri, which is held by process Pi+1· (Modulo arithmetic is used on the indexes, so that Pn is waiting for a resource Rn held by P0 .) Then, since process Pi+1 is holding resource Ri while requesting resource Ri+1, we must have F(Ri) < F(Ri+1) for all i. But this condition means that F(Ro) < F(R1) < ... < F(Rn ) < F (Ro). By transitivity, F(Ro) < F(Ro), which is impossible. Therefore, there can be no circular wait.

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. If the necessary conditions for a deadlock are in place, it is still possible to avoid deadlock by being careful when res ources are allocated. It employs the most famous deadlock avoidance algorithm that is the B anker’s algorithm. A deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that a circular wait conditi on can never exist. The resource-allocation state is defined by the number of available and allocated resources, and the maximum demands of the processes. Safe and Unsafe States A sys tem is said to be in a Safe State, if there is a safe execution s equence. An execution sequence is an ordering for process execution such that each process runs until it terminates or block ed and all request for resources are imm ediately granted if the resource is available. A system is said to be in an Unsafe State, if there is no safe exec ution sequence. An unsafe state may not be deadlock ed, but there is at least one sequence of requests from processes that would make the system deadlock ed.

(Relation between Safe, Unsafe and Deadlock ed States) Resource-Allocation Graph Algorithm The deadlock avoidance algorithm us es a variant of the resource-allocation graph to avoid deadlocked state. It introduces a new type of edge, call ed a claim edge. A claim edge Pi Rj indicates that process Pi may request resource Rj at some time in the future. This edge resembles a request edge in direction, but is represented by a dashed line. W hen process Pi requests resource Rj, the claim edge PiRj is converted to a request edge. Similarly, when a resource Rj is released by Pi, the assignment edge Rj Pi is reconverted to a claim edge PiRj. Suppose that process Pi requests resourc e Rj. The request can be granted only if converting the request edge Pi Rj to an assignment edge Rj Pi that does not result in the formation of a cycle in the resource-allocation graph. An algorithm for detecting a cycle in this graph is called cycle detection algorithm. If no cycle exists, then the allocation of the res ource will leave the system in a safe state. If a cycle is found, then the allocation will put the sys tem in an unsafe state. Therefore, process Pi will have to wait for its requests to be satisfied. To illustrate this algorithm, we consider the resource-allocation graph of Figure 23.1. Suppose that P2 requests R2 . Although R2 is currently free, we cannot allocate it to P2, since this action will create a cycle in the graph (Figure 23.2). A cycle, as mentioned, indicates that the system is in an unsafe state. If P1 requests R2, and P2 requests R1, then a deadlock will occur.

23.1

23.2...