Banker Algorithm in operating system.pptx

This is to present the banker algorithm concept in OS

1. Operating System Deadlock avoidance & Banker’s Algorithm

2. Deadlock Avoidance Simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need. Resource-allocation state is defined by the number of available and allocated resources, and the maximum demands of the processes. The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition. Requires that the system has some additional a priori information available.

3. Safe State When a process requests an available resource, system must decide if immediate allocation leaves the system in a safe state . System is in safe state if there exists a safe sequence of all processes. Sequence < P 1 , P 2 , …, P n > is safe if for each P i , the resources that Pi can still request can be satisfied by currently available resources + resources held by all the P j , with j<I . If P i resource needs are not immediately available, then P i can wait until all P j have finished . When P j is finished, P i can obtain needed resources, execute, return allocated resources, and terminate. When P i terminates, P i +1 can obtain its needed resources, and so on.

4. Basic Facts If a system is in safe state  no deadlocks. If a system is in unsafe state  possibility of deadlock. Avoidance  ensure that a system will never enter an unsafe state.

5. Safe, Unsafe , Deadlock State

6. Banker’s Algorithm The banker’s algorithm is a resource allocation and deadlock avoidance algorithm In this each process’s maximum recourses need must be known in advance It tests for safe state by simulating the allocation for predetermined maximum possible amounts of all resources, before deciding whether allocation should be allowed to continue.

7. Banker’s Algorithm Data Structure Let  ‘n’  be the number of processes in the system and  ‘m’  be the number of resources types. Available:   It is a 1-d array of size  ‘m’  indicating the number of available resources of each type. Available[ j ] = k means there are  ‘k’  instances of resource type  R j

8. Banker’s Algorithm Data Structure Max: It is a 2-d array of size ‘ n*m’  that defines the maximum demand of each process in a system. Max[ i , j ] = k means process  P i  may request at most  ‘k’  instances of resource type  R j .

9. Banker’s Algorithm Data Structure Allocation : It is a 2-d array of size  ‘n*m’  that defines the number of resources of each type currently allocated to each process. Allocation[ i,j ] = k means process  P i  is currently allocated  ‘k’  instances of resource type  R j

10. Banker’s Algorithm Data Structure Need : It is a 2-d array of size  ‘n*m’  that indicates the remaining resource need of each process. Need [ i,j ] = k means process  P i  currently need  ‘k’  instances of resource type  R j for its execution. Need [ i,j ] = Max [ i,j ] – Allocation [ i,j ] Allocation i  specifies the resources currently allocated to process P i  and Need i  specifies the additional resources that process P i  may still request to complete its task.

11. Detection Algorithm Is System in Safe State? 1 ) Let Work and Finish be vectors of length ‘m’ and ‘n’ respectively. Initialize: Work = Available Finish[ i ] = false; for i =1, 2, 3, 4….n 2) Find an i such that both a ) Finish[ i ] = false b) Need i  <= Work if no such i exists goto step (4) 3) Work = Work + Allocation[ i ] Finish[ i ] = true goto step (2 ) 4) if Finish [ i ] = true for all i then the system is in a safe state

12. Recourse Request Algorithm Let Request i  be the request array for process P i . Request i   [j] = k means process P i  wants k instances of resource type R j . When a request for resources is made by process P i , the following actions are taken : 1 ) If Request i  <= Need i Goto step (2) ; otherwise, raise an error condition, since the process has exceeded its maximum claim. 2) If Request i  <= Available Goto step (3); otherwise, P i  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: Available = Available – Request i Allocation i  = Allocation i  + Request i Need i  = Need i – Request i

13. Example 2

14. Example - = Calculating Need Max [ i , j] – Allocation [ i , j] = Need [ i , j] 3 2

15. Calculating Safe State

16. Thanks