bankers algorithm in operating system.pptx

bankers algorithm in operating system.pptx

1. Deadlocks Definition: Deadlock exists among a set of processes if Every process is waiting for an event This event can be caused only by another process in the set Event is the acquire of release of another resource  Kansas 20th century law: “When two trains approach each other at a crossing, both shall come to a full stop and neither shall start up again until the other has gone”

2.  A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set.  Example (hardware resources): System has 2 tape drives. P 1 and P 2 each hold one tape drive and each needs another one.  Example (“software” resource:): semaphores A and B , initialized to 1 P 1 wai t (B) wai t (A) P wait (A); wait (B); sig n al(B); sig n al(A); sig n al(A) sig n al(B)

3. Deadlocks are a set of blocked processes each holding a resource and waiting to acquire a resource held by another process. Deadlock in OS

4.  Necessary conditions for deadlock to exist: Mutual Exclusion At least one resource must be held is in non-sharable mode Hold and wait There exists a process holding a resource, and waiting for another No preemption Resources cannot be preempted Circular wait There exists a set of processes {P 1 , P 2 , … P N }, such that  P 1 is waiting for P 2 , P 2 for P 3 , …. and P N for P 1 All four conditions must hold for deadlock to occur

5. Truck A has to wait for truck B to move Not deadl o cked

6. Gridlock

7.  When a process requests an available resource, system must decide if immediate allocation leaves the system in a safe state.  A system is in a safe state only if there exists a safe sequence < P 1 , P 2 , …, P n > for the current allocation state such that for each P i , the resource requests that P i can still make can be satisfied by currently available resources + resources held by all the P j , with j < i .  That is: 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.

8.  State is safe because OS can definitely avoid deadlock by blocking any new requests until safe order is executed  This avoids circular wait condition Process waits until safe state is guaranteed

9.  Suppose there are 12 tape drives max need current usage could ask for p0 10 5 5 p1 4 2 2 p2 9 2 7 3 drives remain  current state is safe because a safe sequence exists: <p1,p0,p2> p1 can complete with current resources p0 can complete with current+p1 p2 can complete with current +p1+p0  if p2 requests 1 drive, then it must wait to avoid unsafe state.

10.  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 .

11. Avoidance algorithms  Single instance of a resource type. Use a resource-allocation graph  Multip l e ins t an c e s o f a resourc e type . Use the banker’s algorithm

12.  Suppose total bank capital is 1000 MTL  Current cash : 1000- (410+210) = 380 MTL Customer c1 c2 Max. Need 800 600 Present Loan 410 210 Claim 390 390

13.  Definitions  Each process has a LOAN, CLAIM, MAXIMUM NEED LOAN: current number of resources held MAXIMUM NEED: total number resources needed to complete CLAIM: = (MAXIMUM - LOAN)

14.  Establish a LOAN ceiling (MAXIMUM NEED) for each process  MAXIMUM NEED < total number of resources available (ie., capital)  Total loans for a process must be less than or equal to MAXIMUM NEED  Loaned resources must be returned back in finite time

15. Search for a process with a claim that can satisfied using the current number of remaining resources (ie., tentatively grant the claim) If such a process is found then assume that it will return the loaned resources. Update the number of remaining resources Repeat steps 1-3 for all processes and mark them

16.  DO NOT GRANT THE CLAIM if at least one process can not be marked.  Implementation A resource request is only allowed if it results in a SAFE state The system is always maintained in a SAFE state so eventually all requests will be filled

17. Banker’s Algorithm  Banker’s algorithm is a deadlock avoidance algorithm.  Each process must priori claim it’s maximum use: it must declare the maximum number of instances of each resource type that it may need.  The n u m b er m ay n ot exc e ed the t otal n u m ber of resources in the system.  When a process requests a resource it may have to wait.  When a process gets all its resources it must return them in a finite amount of time.

18.  Suppose we know the “worst case” resource needs of processes in advance A bit like knowing the credit limit on your credit cards. (This is why they call it the Banker’s Algorithm)  Observation: Suppose we just give some process ALL the resources it could need… Then it will execute to completion. After which it will give back the resources.  Like a bank: If Visa just hands you all the money your credit lines permit, at the end of the month, you’ll pay your entire bill, right?

19.  So… A process pre-declares its worst-case needs Then it asks for what it “really” needs, a little at a time The algorithm decides when to grant requests  It delays a request unless: It can find a sequence of processes… …. such that it could grant their outstanding need… … so they would terminate… … letting it collect their resources… … and in this way it can execute everything to completion!

20. Data Structures for the Banker’s Algorithm Let n = number of processes, and m = number of resources types .  Available : Vector of length m . If Available [ j ] = k , there are k instances of resource type Rj available.  Max : n x m matrix. If Max [ i,j ] = k , then process Pi may request at most k instances of resource type Rj .  Allocation : n x m matrix. If Allocation [ i,j ] = k then Pi is currently allocated k instances of Rj.  Need : n x m matrix. If Need [ i,j ] = k , then Pi may need k more instances of Rj to complete its task. Need [ i,j] = Max [ i,j ] – Allocation [ i,j ]

21. Safety Algorithm Let Work and Finish be vectors of length m and n , respectively. Initialize: Work = Available Finish [i] = false for i = 0, 1, …, n- 1 . Find an index i such that both: Finish [i] = false (b) Need [i] Work ( i th row of Need is component-wise less then or equal to Work ) If no such i exists, go to step 4. 3. Work = Work + Allocation [i] (component-wise addition of W ork and i th row of All o cati o n ) Finish [i] = true Put Pi to the safety sequence go to step 2. 4.If Finish [i] = true for all i , then the system is in a safe state.

22. If request[i] > need[i] then error (asked for too much) If request[i] > available[i] then wait (can’t supply it now) Resources are available to satisfy the request Let’s assume that we satisfy the request. Then we would have: available = available - request[i] allocation[i] = allocation [i] + request[i] need[i] = need [i] - request [i] Now, check if this would leave us in a safe state: if yes, grant the request, if no, then leave the state as is and cause process to wait.

23. Allocation Max Av a ilab le A B C A B C A B C P0 0 1 0 7 5 3 3 3 2 P1 2 0 0 3 2 2 P2 3 0 2 9 0 2 P3 2 1 1 2 2 2 P4 0 0 2 4 3 3 this is a safe state: safe sequence <P1, P3, P4, P2, P0> Suppose that P1 requests (1,0,2) - add it to P1’s allocation and subtract it from Available

24. Allocation Max Av a ilab le A B C A B C A B C P0 0 1 0 7 5 3 2 3 0 P1 3 0 2 3 2 2 P2 3 0 2 9 0 2 P3 2 1 1 2 2 2 P4 0 0 2 4 3 3 This is still safe: safe seq <P1, P3, P4, P0, P2> In this new state,P4 requests (3,3,0) not enough available resources P0 requests (0,2,0) let’s check resulting state

25. Allocation Max Av a ilab le A B C 2 1 0 A B C P0 0 3 0 P1 3 0 2 P2 3 0 2 P3 2 1 1 P4 0 0 2 A B C 7 5 3 3 2 2 9 0 2 2 2 2 4 3 3 This is unsafe state (why?) So P0’s request will be denied Problems with Banker’s Algorithm?

26.  Single resource  at each request, consider whether granting will lead to an unsafe state - if so, deny is state after the notional grant still safe? are there enough resources to satisfy the demands of some process if so, process is notionally allowed to proceed in due course, it is assumed to finish and return all its resources process closest to its limit is the checked, and the steps repeated if all processes can eventually run to completion, state is safe

27.  Multiple resources  m types of resource, n processes vector comparison : A  B if A i  B i for 0  i  m

28.  Advantages Allows jobs to proceed when a prevention algorithm wouldn't  Problems Requires there to be a fixed number of resources What happens if a resource goes down? Does not allow the process to change its Maximum need while processing

29. processes rarely know in advance how many resources they will need the number of processes changes as time progresses resources once available can disappear the algorithm assumes processes will return their resources within a reasonable time processes may only get their resources after an arbitrarily long delay practical use is therefore rare!

30. THAN K Y OU