Friday, July 3, 2015

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.
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
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 Pis 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. 
    Read full article from Avoiding Deadlock: Bankers Algorithm

    Labels

    Review (572) System Design (334) System Design - Review (198) Java (189) Coding (75) Interview-System Design (65) Interview (63) Book Notes (59) Coding - Review (59) to-do (45) Linux (43) Knowledge (39) Interview-Java (35) Knowledge - Review (32) Database (31) Design Patterns (31) Big Data (29) Product Architecture (28) MultiThread (27) Soft Skills (27) Concurrency (26) Cracking Code Interview (26) Miscs (25) Distributed (24) OOD Design (24) Google (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Interview Q&A (20) System Design - Practice (20) Tips (19) Algorithm (17) Company - Facebook (17) Security (17) How to Ace Interview (16) Brain Teaser (14) Linux - Shell (14) Redis (14) Testing (14) Tools (14) Code Quality (13) Search (13) Spark (13) Spring (13) Company - LinkedIn (12) How to (12) Interview-Database (12) Interview-Operating System (12) Solr (12) Architecture Principles (11) Resource (10) Amazon (9) Cache (9) Git (9) Interview - MultiThread (9) Scalability (9) Trouble Shooting (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cassandra (8) Company - Uber (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Design (7) Interview Corner (7) JVM (7) Java Basics (7) Kafka (7) Mac (7) Machine Learning (7) NoSQL (7) C++ (6) Chrome (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) CareerCup (5) Code Review (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Python (5)

    Popular Posts