User Rating:  / 0

PoorBest 

Related Content: CS604 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Operating Systems

Summary

• Deadlock avoidance
• Banker’s algorithms
• Safety algorithm
• Safe Sequence

Deadlock Avoidance

Resource Allocation Graph Algorithm

In addition to the request and assignment edges explained in the previous lectures, we introduce a new type of edge called a claim edge to resource allocation graphs. A claim edge Pi →Rj indicates that process Pi may request resource Rj at some time in the future.
A dashed line is used to represent a claim edge. When Pi requests resource Rj the claim edge is converted to a request edge. In the following resource allocation graph, the edge P2 →R2 is a claim edge.

Suppose that Pi requests resource Rj. The request can be granted only if converting the request edge Pi →Rj into an assignment edge Rj →Pi does not result in the formation of a cycle. 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. The following resource allocation graph shows that the system is in an unsafe state:

Banker’s Algorithm

In this algorithm, when a new process enters the system, it must declare the maximum number of instances of each resource type that it may need, i.e., each process must a priori claim maximum use of various system resources. This number may not exceed the total number of instances of resources in the system, and there can be multiple instances
of resources. When a process 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. We say that a system is in a safe state if all of the processes in
the system can be executed to termination in some order; the order of process termination is called safe sequence. When a process gets all its resources, it must use them and return them in a finite amount of time.
Let n be the number of processes in the system and m be the number of resource types. We need the following data structures in the Banker’s algorithm:

• Available: A vector of length m indicates the number of available instances of resources of each type. Available[j] = = k means that there are k available instances of resource Rj.
• Max: An n x m matrix defines the maximum demand of resources of each process. Max[i,j] = = k means that process Pi may request at most k instances of resource Rj.
• Allocation: An n x m matrix defines the number of instances of resources of each type currently allocated to each process. Allocation[i,j] = = k means that Pi is currently allocated k instances of resource type Rj.
• Need: An n x m matrix indicates the remaining resource need of each process.
  Need[i,j] = = k means that Pi may need k more instances of resource type Rj to complete its task. Note that Need[i,j] = = Max[i,j] - Allocation[i,j].

Safety Algorithm

The algorithm for finding out whether or not a system is in a safe state can be described as follows:

1. Let Work and Finish be vectors of length m and n, respectively. Initialize Work = Available and Finish[i] = false fori = 1, 2, …, n.
2. Find an i such that both
   • Finish[i] = = false
   • Needi <= Work
     If no such i exists go to step 4.
3. Work = Work + Allocationi
   Finish[i] = true
   Go to step 2
4. If Finish[i] = = true for all i, then the system is in a safe mode.

This algorithm may require an order of m x n2 operations to decide whether a state is safe.

Resource Request Algorithm

Let Requesti be the request vector for process Pi. if Requesti [j]=k, then process Pi wants k instances of resource Rj. When a request for resources is made by process Pi the following actions are taken:

1. If Requesti <= Needi go to step 2. Otherwise, raise an error condition since the process has exceeded its maximum claim.
2. If Requesti <= Available, go to step 3. Otherwise Pi must wait, since the resources are not available.
3. Have the system pretend to have allocated the requested resources to process Pi by modifying the state as follows:
   Availabe = Available-Requesti ;
   Allocationi = Allocationi + Requesti ;
   Needi = Needi –Requesti;

Invoke the Safety algorithm. If the resulting resource allocation graph is safe, the transaction is completed. Else, the old resource allocation state is restored and process Pi must wait for Requesti.

An illustrative example

We now show a few examples to illustrate how Banker’s algorithm works. Consider a system with five processes P0 through P4 and three resource types: A, B, C. Resource type A has 10 instances, resource type B has 5 instances and resource type C has 7 instances.
Suppose that at a time T0 the following snapshot of the system has been taken:

The content of the matrix Need is defined to be Max- Allocation and is:

In the following sequence of snapshots, we show execution of the Safety algorithm for the given system state to determine if the system is in a safe state. We progressively construct a safe sequence.

• Safe Sequence: < P1>
• Safe Sequence: < P1, P3>
• Safe Sequence: < P1, P3, P4>
• Safe Sequence: < P1, P3, P4, P0>

The Safety algorithm concludes that the system is in a safe state, with < P0, P1, P2, P3, P4> being a safe sequence.
Suppose now that process P1 requests one additional instance of resource type A and two instances of resource type C so Request 1 = (1, 0, 2). To decide whether this request can be fulfilled immediately, we invoke Banker’s algorithm, which first check that Request1 <= Available, which is true because (1,0,2)<=(3,3,2). It then pretends that this request has been fulfilled, and arrives at the following state:

Banker’s algorithm then executes the Safety algorithm to determine if the resultant system will be in a safe state. Here is the complete working of Banker’s algorithm. If P1 requests (1,0,2), lets evaluate if this request may be granted immediately. Banker’s algorithm takes the following steps.

1. Is Request1 ≤ Need1?
   (1,0,2) ≤ (1,2,2) ⇒ true
2. Is Request1 ≤ Available?
   (1,0,2) ≤ (3,3,2) ⇒ true

It then pretends that request is granted and updates the various data structures accordingly. It then invokes the Safety algorithm to determine if the resultant state is safe.
Here is sequence of steps taken by the Safety algorithm. The algorithm progressively constructs a safe sequence.

Safe Sequence: < P1 >

Safe Sequence: < P1, P3 >

Safe Sequence: < P1, P3 , P4>

Safe Sequence: < P1, P3 , P4, P0>

Hence executing Safety algorithm shows that sequence <P1, P3, P4, P0, P2> satisfies the safety requirement and so P1’s request may be granted immediately. Note that safe sequence is not necessarily a unique sequence. There are several safe sequences for the above example. See lecture slides for more details.
Here is another example. P0 requests (0,2,0). Should this request be granted? In order to answer this question, we again follow Banker’s algorithm as shown in the following sequence of steps.

1. Is Request0 ≤ Need0?
   (0,2,0) ≤ (7,4,3) ⇒ true
2. Is Request1 ≤ Available?
   (0,2,0) ≤ (3,3,2) ⇒ true

The following is the updated system state. We run the Safety algorithm on this state now and show the steps of executing the algorithm.

Safe Sequence: <P3 >

Safe Sequence: <P3, P1 >

Safe Sequence: <P3, P1, P2 >

Safe Sequence: <P3, P1, P2, P0, P4 >

Hence executing the safety algorithm shows that sequence <P3, P1, P2, P0, P4 > satisfies safety requirement. And so P0’s request may be granted immediately.
Suppose P0 requests (0,2,0). Can this request be granted after granting P1’s request of (1,0,2)?

• < Prev
• Next >