Avoiding Deadlock: Bankers Algorithm

http://geeksquiz.com/deadlock-prevention/

Deadlock Avoidance

Deadlock avoidance can be done with Banker’s Algorithm.

http://rosettacode.org/wiki/Banker's_algorithm

The Banker's algorithm is a resource allocation and deadlock avoidance algorithm developed by Edsger Dijkstra that tests for safety by simulating the allocation of predetermined maximum possible amounts of all resources, and then makes a "s-state" check to test for possible deadlock conditions for all other pending activities, before deciding whether allocation should be allowed to continue, if their is no safe state it don’t allow the request made by the process.

http://akbar.marlboro.edu/~mahoney/support/alg/alg/node144.html

One reason this algorithm is not widely used in the real world is because to use it the operating system must know the maximum amount of resources that every process is going to need at all times. 

Therefore, for example, a just-executed program must declare up-front that it will be needing no more than, say, 400K of memory. The operating system would then store the limit of 400K and use it in the deadlock avoidance calculations.

Avoiding Deadlock: Bankers Algorithm

The system is said to be in a safe state if there exists a sequence of other valid system states that leads to the successful completion of all processes.

• Processes request only 1 resource at a time.
• Request is granted only it results in a safe state.
• If request results in an unsafe state, the request is denied and the process continues to hold resources it has until such time as it's request can be met.
• All requests will be granted in a finite amount of time.
• Algorithm can be extended for multiple resource types.
• Advantage: Avoids deadlock and it is less restrictive than deadlock prevention.
• Disadvantage: Only works with fixed number of resources and processes.
• Guarantees finite time - not reasonable response time
• Needs advanced knowledge of maximum needs
• Not suitable for multi-access systems
• Unnecessary delays in avoiding unsafe states which may not lead to deadlock

Inputs to Banker’s Algorithm
1. Max need of resources by each process.
2. Currently allocated resources by each process.
3. Max free available resources in the system.

Request will only be granted under below condition.
1. If request made by process is less than equal to max need to that process.

2. If request made by process is less than equal to freely availbale resource in the system.

Coding
http://akbar.marlboro.edu/~mahoney/support/alg/alg/node145.html
http://rosettacode.org/wiki/Banker's_algorithm

Quiz/practices

http://geeksquiz.com/gate-gate-cs-2014-set-1-question-41/
http://geeksquiz.com/gate-gate-cs-2014-set-3-question-41/

A system contains three programs and each requires three tape units for its operation. The minimum number of tape units which the system must have such that deadlocks never arise is _________.
(A) 6
(B) 7
(C) 8
(D) 9
Answer: (B) 

if you use 5 then it may be possible that p1 have 2 p2 have 2 and p3 have 1 resource so all of the three process will wail infinitely ..if 6 resources then it may be possible that all three process have 2 resources each so they will wait infinitely,if 7 resources use then atleast one must have 3 resources so never deadlock can occur.

http://geeksquiz.com/gate-gate-cs-2010-question-46/

A system has n resources R0,…,Rn-1,and k processes P0,….Pk-1.The implementation of the resource request logic of each process Pi is as follows: 

 if (i % 2 == 0) {
      if (i < n) request Ri
      if (i+2 < n) request Ri+2
}
else {
      if (i < n) request Rn-i
      if (i+2 < n) request Rn-i-2
}

In which one of the following situations is a deadlock possible?
(A) n=40, k=26
(B) n=21, k=12
(C) n=20, k=10
(D) n=41, k=19
Answer: (B) 

Option B is answer

No. of resources, n = 21
No. of processes, k = 12

Processes {P0, P1....P11}  make the following Resource requests:
{R0, R20, R2, R18, R4, R16, R6, R14, R8, R12, R10, R10}

For example P0 will request R0 (0%2 is = 0 and 0< n=21). 

Similarly, P10 will request R10.

P11 will request R10 as n - i = 21 - 11 = 10.

As different processes are requesting the same resource, deadlock
may occur. 

todo: http://users.cs.cf.ac.uk/O.F.Rana/os/lectureos12/lectureos12.html

Read full article from Avoiding Deadlock: Bankers Algorithm