Deadlock Avoidance
Deadlock Avoidance
Deadlock-prevention algorithms, as discussed in Section 7.4, prevent deadlocks by restraining how requests can be made. The restraints ensure that at least one of the necessary conditions for deadlock cannot occur and, hence, that deadlocks cannot hold. Possible side effects of preventing deadlocks by this method, however, are low device utilization and reduced system throughput. An alternative method for avoiding deadlocks is to require additional information about how resources are to be requested. For example, in a system with one tape drive and one printer, the system might need to know that process P will request first the tape drive and then the printer before releasing both resources, whereas process Q will request first the printer and then the tape drive. With this knowledge of the complete sequence of requests and releases for each process, the system can decide for each request whether or not the process should wait in order to avoid a possible future deadlock.
Each request requires that in making this decision the system consider the resources currently available, the resources currently allocated to each process, and the future requests and releases of each process. The various algorithms that use this approach differ in the amount and type of information required. The simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need. Given this a priori, information, it is possible to construct an algorithm that ensures that the system will never enter a deadlocked state. Such an algorithm defines the deadlock-avoidance approach. A deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that a circularwait condition can never exist. The resource-allocation state is defined by the number of available and allocated resources and the maximum demands of the processes. In the following sections, we explore two deadlock-avoidance algorithms.
Safe State
A state is safe if the system can allocate resources to each process (up to its maximum) in some order and still avoid a deadlock. More formally, a system is in a safe state only if there exists a safe sequence. A sequence of processes pis a safe sequence for the current allocation state if, for each Pi, the resource requests that P, can still make can be satisfied by the currently available resources plus the resources held by all Pi, with / < /. In this situation, if the resources that Pi needs are not immediately available, then P, can wait until all Pj have finished. When they have finished, P; can obtain all of its needed resources, complete its designated task, return its allocated resources, and terminate. When P, terminates, P,+l can obtain its needed resources, and so on. If no such sequence exists, then the system state is said to be unsafe.
A safe state is not a deadlocked state. Conversely, a deadlocked state is an unsafe state. Not all unsafe states are deadlocks, however (Figure 7.5). An unsafe state may lead to a deadlock. As long as the state is safe, the operating system can avoid unsafe (and deadlocked) states. In an unsafe state, the operating system cannot prevent processes from requesting resources such that a deadlock occurs: The behavior of the processes controls unsafe states. To illustrate, we consider a system with 12 magnetic tape drives and three processes: PLl/ P\, and P2. Process PQ requires 10 tape drives, process Pi may need as many as 4 tape drives, and process P? may need up to 9 tape drives. Suppose that, at time to, process PQ is holding 5 tape drives, process P\ is holding 2 tape drives, and process P2 is holding 2 tape drives. (Thus, there are 3 free tape drives.)
At time fo, the system is in a safe state. The sequence < Pi, Po, ?2> satisfies the safety condition. Process Pj can immediately be allocated all its tape drives and then return them (the system will then have 5 available tape drives); then process PL) can get all its tape drives and return them (the system will then have 10 available tape drives); and finally process P^ can get all its tape drives and return them (the system will then have all 12 tape drives available).
A system can go from a safe state to an unsafe state. Suppose that, at time t\, process Pz requests and is allocated one more tape drive. The system is no longer in a safe state. At this point, only process P, can be allocated all its tape drives. When it returns them, the system will have only 4 available tape drives. Since process Pp, is allocated 5 tape drives but has a maximum of 10, it may request 5 more tape drives. Since they are unavailable, process Po must wait. Similarly, process P? may request an additional 6 tape drives and have to wait, resulting in a deadlock. Our mistake was in granting the request from process Pi for one more tape drive. If we had made P2 wait until either of the other processes had finished and released its resources, then we could have avoided the deadlock. Given the concept of a safe state, we can define avoidance algorithms that ensure that the system will never deadlock. The idea is simply to ensure that the system will always remain in a safe state. Initially, the system is in a safe state. Whenever a process requests a resource that is currently available, the system must decide whether the resource can be allocated immediately or whether the process must wait.
The request is granted only if the allocation leaves the system in a safe state. In this scheme, if a process requests a resource that is currently available, it may still have to wait. Thus, resource utilization may be lower than it would otherwise be.
Resource-Allocation-Graph Algorithm
If we have a resource-allocation system with only one instance of each resource type, a variant of the resource-allocation graph defined in Section 7.2.2 can be used for deadlock avoidance. In addition to the request and assignment edges already described, we introduce a new type of edge, called a claim edge. A claim edge P; —> Rj indicates that process P, may request resource R, at some time in the future. This edge resembles a request edge in direction but is represented in the graph by a dashed line. When process P.- requests resource Rj, the claim edge P, —> Rj is converted to a request edge. Similarly, when a resource Rj is released by Pj, the assignment edge Rj -» P,- is reconverted to a claim edge P; —> Rj. We note that the resources must be claimed a priori in the system.
That is, before process p starts executing, all its claim edges must already appear in the resource-allocation graph. We can relax this condition by allowing a claim edge P, —> R- to be added to the graph only if all the edges associated with process P,- are claim edges. Suppose that process P, requests resource Rj. The request can be granted only if converting the request edge P, —» Rj to an assignment edge Rj —> P; does not result in the formation of a cycle in the resource-allocation graph.
Note that we check for safety by using a cycle-detection algorithm. An algorithm for detecting a cycle in this graph requires an order of n 2 operations, where n is the number of processes in the system. If no cycle exists, then the allocation of the resource will leave the system in a safe state. If a cycle is found, then the allocation will put the system in an unsafe state. Therefore, process P: will have to wait for its requests to be satisfied. To illustrate this algorithm, we consider the resource-allocation graph of Figure 7.6. Suppose that Pi requests R?. Although Ri is currently free, we cannot allocate it to p>, since this action will create a cycle in the graph (Figure 7.7). A cycle indicates that the system is in an unsafe state. If Pi requests R2, and Po requests R\, then a deadlock will occur.
Banker's Algorithm
The resource-allocation-graph algorithm is not applicable to a resourceallocation system with multiple instances of each resource type. The deadlockavoidance algorithm that we describe next is applicable to such a system but is less efficient than the resource-allocation graph scheme. This algorithm is commonly known as the banker's algorithm. The name was chosen because the algorithm could be used in a banking system to ensure that the bank never allocated its available cash in such a way that it could no longer satisfy the needs of all its customers. When, a new process enters the system, it must declare the maximum number of instances of each resource type that it may need. This number may not exceed the total number of resources in the system. When a user requests a set of resources, the system must determine whether the allocation of these resources will leave the system in a safe state. If it will, the resources are allocated; otherwise, the process must wait until some other process releases enough resources. Several data structures must be maintained to implement the banker's algorithm.
These data structures encode the state of the resource-allocation system. Let n be the number of processes in the system and m be the number of resource types. We need the following data structures:
• Available. A vector of length m indicates the number of available resources of each type. If Availab!c[f] equals k, there are k instances of resource type Ri available.
• Max. An n x m matrix defines the maximum demand of each process. If M(7.t[;][/] equals k, then process P\ may request at most k instances of resource type /?/.
• Allocation. An n x in matrix defines the number of resources of each type currently allocated to each process. If Allocation[i][j] equals k, then process Pi is currently allocated k instances of resource type /?,. • Need. An n x m matrix indicates the remaining resource need of each process. If Need[i][j] equals k, then process P,- may need k more instances of resource type R- to complete its task. Note that Need[/][/] equals Max[i][j] - Allocntion[i][j]. These data structures vary over time in both size and value. To simplify the presentation of the banker's algorithm, we next establish some notation. Let X and Y be vectors of length n. We say that X < Y if and only if X[i] < Y[/] for all / = 1, 2, ..., n. For example, if x"= (1,7,3,2) and Y = (0,3,2,1), then Y < X. Y < X if Y < X and Y + X. We can treat each row in the matrices Allocation and Need as vectors and refer to them as Allocation; and Need,. The vector Allocation, specifies the resources currently allocated to process P,; the vector Needi specifies the additional resources that process P, may still request to complete its task.
Safety Algorithm
We can now present the algorithm for finding out whether or not a system is in a safe state. This algorithm can be described, as follows: 1. Let Work and Finish be vectors of length in and n, respectively. Initialize Work = Availabl e an d Fiiush\i] - false fo r / - 0,1 , ..., n-l . 2. Find an / such that both a. Finish[i] ==false b. Need, < Work If no such / exists, go to step 4. 3. Work = Work + Allocation, Finish[i] = true Go to step 2. 4. If Finisli[i] -- true for all. /, then the system is in a safe state. This algorithm may require an order of m x it operations to determine whether a state is safe.
Resource-Request Algorithm
We now describe the algorithm which determines if requests can be safely granted. Let Request• be the request vector for process P,. If Request,; [ /'] —— k, then process P, wants k instances of resource type R;. When a request for resources is made by process P,, the following actions are taken: 1. If Request, < Need:, go to step 2. Otherwise, raise an error condition, since the process has exceeded its maximum claim. 2. If Request{ < Available, go to step 3. Otherwise, Ps must wait, since the resources are not available. 3. Have the system pretend to have allocated the requested resources to process P- by modifying the state as follows: Available = Available - Request;; Allocation-, = Allocation; + Request;; Need; = Necdj - Request-; If the resulting resource-allocation state is safe, the transaction is completed, and process P; is allocated its resources. However, if the new state is unsafe, then P, must wait for Request;, and the old resource-allocation state is restored.
An Illustrative Example
Finally, to illustrate the use of the banker's algorithm, consider a system with five processes PQ through P4 and three resource types A, B, and C. Resource type A has 10 instances, resource type B has 5 instances, and resource type C has 7 instances. Suppose that, at time To, the following snapshot of the system has been taken: We claim that the system is currently in a safe state.
Indeed, the sequence p3satisfies the safety criteria. Suppose now that process P] requests one additional instance of resource type A and two instances of resource type C, so Request] = (1,0,2). To decide whether this request can be immediately granted, we first check that Request < Available—that is, that (1/0/2) < (3,3,2), which is true. We then pretend that this request has been fulfilled, and we arrive at the following new state:
We must determine whether this new system state is safe.
To do so, we execute our safety algorithm and find that the sequence satisfies the safety requirement. Hence, we can immediately grant the request of process P\. You should be able to see, however, that when the system is in this state, a request for (3,3,0) by P4 cannot be granted, since the resources are not available. Furthermore, a request for (0,2,0) by Po cannot be granted, even though the resources are available, since the resulting state is unsafe. We leave it as a programming exercise to implement the banker's algorithm
Frequently Asked Questions
Recommended Posts:
- Operating System Concepts ( Multi tasking, multi programming, multi-user, Multi-threading )
- Different Types of Operating Systems
- Batch Operating Systems
- Time sharing operating systems
- Distributed Operating Systems
- Network Operating System
- Real Time operating System
- Various Operating system services
- Architectures of Operating System
- Monolithic architecture - operating system
- Layered Architecture of Operating System
- Microkernel Architecture of operating system
- Hybrid Architecture of Operating System
- System Programs and Calls
- Process Management - Process concept