• The general idea behind deadlock avoidance is to prevent deadlocks from ever happening, by preventing at least one of the aforementioned conditions.
• This requires more information about each process, AND tends to lead to low device utilization. ( I.e. it is a conservative approach. )
• In some algorithms the scheduler only needs to know the maximum number of each resource that a process might potentially use. In more complex algorithms the scheduler can also take advantage of the schedule of exactly what resources may be needed in what order.
• When a scheduler sees that starting a process or granting resource requests may lead to future deadlocks, then that process is just not started or the request is not granted.
• A resource allocation state is defined by the number of available and allocated resources, and the maximum requirements of all processes in the system.
• This requires more information about each process, AND tends to lead to low device utilization. ( I.e. it is a conservative approach. )
• In some algorithms the scheduler only needs to know the maximum number of each resource that a process might potentially use. In more complex algorithms the scheduler can also take advantage of the schedule of exactly what resources may be needed in what order.
• When a scheduler sees that starting a process or granting resource requests may lead to future deadlocks, then that process is just not started or the request is not granted.
• A resource allocation state is defined by the number of available and allocated resources, and the maximum requirements of all processes in the system.
Safe State
A state is safe if the system can allocate all resources requested by all processes ( up to their stated maximums ) without entering a deadlock state.
More formally, a state is safe if there exists a safe sequence of processes { P0, P1, P2, ..., PN } such that all of the resource requests for Pi can be granted using the resources currently allocated to Pi and all processes Pj where j < i. ( I.e. if all the processes prior to Pi finish and free up their resources, then Pi will be able to finish also, using the resources that they have freed up. )
If a safe sequence does not exist, then the system is in an unsafe state, which MAY lead to deadlock. ( All safe states are deadlock free, but not all unsafe states lead to deadlocks. )
EXAMPLE:
Consider a system with 12 magnetic tape drives and 3 processes p0, p1, p2.
Process p0 requires 10 tape drives
Process p1 requires 4
Process p2 requires 9
At time t0 process p0 is holding 5 tape drives
P1 is holding 2
P2 is holding 2
At time t0, the system is in safe state, because p1 can be allocated with all its tape drives and then returns them after its completion. (Now the system will have 5 available drives).
Then p0 can get all its tape drives and return them. (Now the system will have 10 tape drives).
Finally p2 could get all its tape drives and return them. (Now the system will have all 12 tape drives).
System may go from safe to unsafe state.
Suppose at that time t1, process p2 requests and is allocated 1 more tape drive.
The system is in no longer in a safe state. Because at this point, only process p1 can be allocated all its tape drives. When it returns, the system will have only 4 available tape drives. Since process p0 is allocated 5 tape drives, but has a maximum of 10, it may then request 5 more tape drives.
Since they are unavailable, process p0 must wait. Similarly process p2 may request an additional 6 tape drives and have to wait, resulting in deadlock.
Key to the safe state approach is that when a request is made for resources, the request is granted only if the resulting allocation state is a safe one.
Resource-Allocation Graph Algorithm
If resource categories have only single instances of their resources, then deadlock states can be detected by cycles in the resource-allocation graphs.
In this case, unsafe states can be recognized and avoided by augmenting the resource-allocation graph with claim edges, noted by dashed lines, which point from a process to a resource that it may request in the future.
In order for this technique to work, all claim edges must be added to the graph for any particular process before that process is allowed to request any resources. (Alternatively, processes may only make requests for resources for which they have already established claim edges, and claim edges cannot be added to any process that is currently holding resources. )
When a process makes a request, the claim edge Pi->Rj is converted to a request edge. Similarly when a resource is released, the assignment reverts back to a claim edge.
This approach works by denying requests that would produce cycles in the resource-allocation graph, taking claim edges into effect.
BANKER’S ALGORITHM:
• For resource categories that contain more than one instance the resource-allocation graph method does not work, and more complex ( and less efficient ) methods must be chosen.
• The Banker's Algorithm gets its name because it is a method that bankers could use to assure that when they lend out resources they will still be able to satisfy all their clients. ( A banker won't loan out a little money to start building a house unless they are assured that they will later be able to loan out the rest of the money to finish the house. )
• When a process starts up, it must state in advance the maximum allocation of resources it may request, up to the amount available on the system.
• When a request is made, the scheduler determines whether granting the request would leave the system in a safe state. If not, then the process must wait until the request can be granted safely.
• The banker's algorithm relies on several key data structures: ( where n is the number of processes and m is the number of resource categories. )
1. Available[ m ] indicates how many resources are currently available of each type.
2. Max[ n ][ m ] indicates the maximum demand of each process of each resource.
3. Allocation[ n ][ m ] indicates the number of each resource category allocated to each process.
4. Need[ n ][ m ] indicates the remaining resources needed of each type for each process. ( Note that Need[ i ][ j ] = Max[ i ][ j ] - Allocation[ i ][ j ] for all i, j. )
SAFETY ALGORITHM:
• In order to apply the Banker's algorithm, we first need an algorithm for determining whether or not a particular state is safe.
• This algorithm determines if the current state of a system is safe, according to the following steps:
1. Let Work and Finish be vectors of length m and n respectively.
• Work is a working copy of the available resources, which will be modified during the analysis.
• Finish is a vector of booleans indicating whether a particular process can finish. ( or has finished so far in the analysis. )
• Initialize Work to Available, and Finish to false for all elements.
2. Find an i such that both (A) Finish[ i ] == false, and (B) Need[ i ] < Work. This process has not finished, but could with the given available working set. If no such i exists, go to step 4.
3. Set Work = Work + Allocation[ i ], and set Finish[ i ] to true. This corresponds to process i finishing up and releasing its resources back into the work pool. Then loop back to step 2.
4. If finish[ i ] == true for all i, then the state is a safe state, because a safe sequence has been found.
RESOURCE-REQUEST ALGORITHM:
• Now that we have a tool for determining if a particular state is safe or not, we are now ready to look at the Banker's algorithm itself.
• This algorithm determines if a new request is safe, and grants it only if it is safe to do so.
• When a request is made ( that does not exceed currently available resources ), pretend it has been granted, and then see if the resulting state is a safe one. If so, grant the request, and if not, deny the request, as follows:
1. Let Request[ n ][ m ] indicate the number of resources of each type currently requested by processes. If Request[ i ] > Need[ i ] for any process i, raise an error condition.
2. If Request[ i ] > Available for any process i, then that process must wait for resources to become available. Otherwise the process can continue to step 3.
3. Check to see if the request can be granted safely, by pretending it has been granted and then seeing if the resulting state is safe. If so, grant the request, and if not, then the process must wait until its request can be granted safely. The procedure for granting a request ( or pretending to for testing purposes ) is:
• Available = Available - Request
• Allocation = Allocation + Request
• Need = Need - Request
EXAMPLE:
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.
At time T0 according to the given allocation system remains in safe state.
Allocation max available need
A B C A B C A B C A B C
P0 0 1 0 7 5 3 3 3 2 7 4 3
P1 2 0 0 3 2 2 1 2 2
P2 3 0 2 9 0 2 6 0 0
P3 2 1 1 2 2 2 0 1 1
P4 0 0 2 4 3 3 4 3 1
<P1,P3,P4,P2,P0> Satisfies the safety criteria.
Now if 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 granted first check the availability.availability. Request1<=Available((1,0,2)<=(3,3,2)) which is true.
We then satisfy this request and arrived the new state
Allocation need available
A B C A B C A B C
P0 0 1 0 7 4 3 2 3 0
P1 3 0 2 0 2 0
P2 3 0 2 6 0 0
P3 2 1 1 0 1 1
P4 0 0 2 4 3 1
We have to find whether the system is safe or not at this stage.
By using Safety Algorithm the sequence<P1,P3,P4,P0,P2> satisfies safety algorithm, hence we can grant the request of Process P1.
No comments:
Post a Comment