To illustrate this algorithm, we consider the resource-allocation graph of Figure 7.6. Therefore, process P: will have to wait for its requests to be satisfied. If a cycle is found, then the allocation will put the system in an unsafe state. If no cycle exists, then the allocation of the resource will leave the system in a safe state. 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. Note that we check for safety by using a cycle-detection algorithm. 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. Suppose that process P, requests resource Rj. 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. That is, before process p starts executing, all its claim edges must already appear in the resource-allocation graph. We note that the resources must be claimed a priori in the system. Similarly, when a resource Rj is released by Pj, the assignment edge Rj -» P,- is reconverted to a claim edge P -> Rj. When process P.- requests resource Rj, the claim edge P, -> Rj is converted to a request edge. This edge resembles a request edge in direction but is represented in the graph by a dashed line. A claim edge P -> Rj indicates that process P, may request resource R, at some time in the future. In addition to the request and assignment edges already described, we introduce a new type of edge, called a claim edge. 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. Thus, resource utilization may be lower than it would otherwise be. In this scheme, if a process requests a resource that is currently available, it may still have to wait. The request is granted only if the allocation leaves the system 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. Initially, the system is in a safe state. The idea is simply to ensure that the system will always remain in a safe state. Given the concept of a safe state, we can define avoidance algorithms that ensure that the system will never deadlock. 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. Our mistake was in granting the request from process Pi for one more tape drive. Similarly, process P? may request an additional 6 tape drives and have to wait, resulting in a deadlock. Since they are unavailable, process Po must wait. Since process Pp, is allocated 5 tape drives but has a maximum of 10, it may request 5 more tape drives. When it returns them, the system will have only 4 available tape drives. At this point, only process P, can be allocated all its tape drives. Suppose that, at time t\, process Pz requests and is allocated one more tape drive. 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).Ī system can go from a safe state to an unsafe state. Fundamental Of Computers And Programing In C. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |