Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
227 lines (168 sloc) 5.49 KB

Chapter 6: Deadlock Part 2 (Algorithms)

  • Banker's Algorithm:
// conditions
n --> processes
m --> resource types

// vector needed by the algorithm
Available_m: Available[i] = k // number of instances k for resource i

Max_nXm: Max[i, j] = k // maximum requirement of every process inside matrix; every row vector represents the resource requirement of the i_th process

Allocation_nXm: Allocation[i, j] = k //current allocation of resources to processes.

Need_nXm: Need[i, j] = k // the resources that will be required by process. Calculate using difference between Max and Allocation.
  • Actual algorithm (runs every time a process request a resource):
// a request
Pi -> Request_i

// algorithm
// check if the request is less than Need vector
if Request_i <= Need_i   
  then go to step 2
else
  error

// check if a valid request 
if Request_i <= Available
  then go to step 3
else
  wait

// modify Available, Allocation and Need vector by request granted
// the system pretends to have allocated the resources
Available = Available - Request_i
Allocation_i = Allocation_i + Request_i
Need_i = Need_i - Request_i

Check if this new state is safe, i.e., if a safe sequence exists.
  • A safe sequence is the way processes are allocated resources and guarantees that every process completes execution. However, it may not be the same order in which the resources requested resources. Below is the algorithm used to check if a sequence is safe:

  • Safety Algorithm:

// Step 1: initialization
Work = Available
Finish = False

// Step 2
Find an i such that Finish[i] = False and Need[i] <= Work
If no such i, go to step 4

// Step 3:
Work = Work + Allocation_i
Finish = True
go to step 2 

// Step 4: 
If Finish[i] = True for all i
  then system is Safe
  • When a system in Unsafe it may lead to deadlock and it doesn't mean it will always cause a deadlock. When it is safe, it will always avoid a deadlock.

  • An example illustrating the process deadlock avoidance:

// Resources
A = 10 // 10 instances
B = 5
C = 7

// Processes
P0, P1, P2, P3, P4

// The process requests in advance in form of matrix
// Allocation, Max, Available
// Allocation and Max requirements are given; Available = (Resource Instances - Allocated)
// Example
|    |   | Allocation |   |   | Max |   |   | Available |   |
|----|---|------------|---|---|-----|---|---|-----------|---|
|    | 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 |   |           |   |


// Need Matrix (Max - Allocation)
|    |   | Need |   |
|----|---|------|---|
|    | A | B    | C |
| P0 | 7 | 4    | 3 |
| P1 | 1 | 2    | 2 |
| P2 | 6 | 0    | 0 |
| P3 | 0 | 1    | 1 |
| P4 | 4 | 3    | 1 |

// Safety sequence check
Work = 3 3 2
Finish 

// P0 cannot complete Need(P0) is not less than current Work

// Execution of process P1
P1: Finish[1] = True;
Work = 532 // work is calculate by adding allocation to current work

// P2 cannot complete Need(P2) is not less than current Work

// Execution of process P3
P3: Finish[3] = True;
Work = 7 4 3

// Execution of process P4
P4: Finish[4] = True;
Work = 7 4 5

// Execution of process P0
P0: Finish[0] = True;
Work = 7 5 5 

// Execution of process P2
P2: Finish[2] = True;
Work = 10 5 7

// The safe sequence is:
P1, P3, P4, P0, P2
  • Safe sequence can be different depending on the order of how processes are processed.

  • Assuming there is a new future request R1 = [1,0,2] from P1 , which already has Need request of _N(P1) = [1, 2, 2] _, what are the result using the same algorithm from above:

P1: Request = 1 0 2
Pass first two checks of the algorithm then goto next step

Available = 2 3 0

// Modify Allocation for P1 only (Previous Allocation + Request)

|    |   | Allocation |   | 
|----|---|------------|---|
|    | A | B          | C | 
| P0 | 0 | 1          | 0 | 
| P1 | 3 | 0          | 2 | 
| P2 | 3 | 0          | 2 | 
| P3 | 2 | 1          | 1 | 
| P4 | 0 | 0          | 2 | 

// Modify Need for P1 only (Previous Need - Request)
|    |   | Need |   |
|----|---|------|---|
|    | A | B    | C |
| P0 | 7 | 4    | 3 |
| P1 | 0 | 2    | 0 |
| P2 | 6 | 0    | 0 |
| P3 | 0 | 1    | 1 |
| P4 | 4 | 3    | 1 |

// Check if safe

// P0 cannot be executed

// Execute P1 if Need(P1) < Available and calculate Available (Available + Allocation) 
Available: 5 3 2

// Execute P3
Available: 7 4 3

// Execute P4
Available: 7 4 5

// Execute P0
Available: 7 5 5

// Execute P2
Available: 10 5 7

// Safe sequence
P1, P3, P4, P0, P2
  • Exercise: Try P0 with a request of 0 2 0

  • Detection and Recovery Algorithm stucture:

// initializations
Available_m
Allocation_nXm
Request_nXm

// Main Algorithm 
// Step 1
Work_m = Available
Finish[i] = False if Allocation_i != 0 // no requests for resources yet
          = True if Allocation_i = 0

// Step 2
Find and i such that Finish[i] = False and Request_i <= Work
If no such i, then go to Step 4

// Step 3
Work = Work + Allocation_i
Finish = True
then go to step 2

// Step 4
If Finish[i] = False for some i
  then there is a deadlock
  • After this process then the algorithm must choose the Process to terminate so as to recover from deadlock.

  • The time complexity of the Banker's algorith is O(mXn^2). But it can be reduced to O(n^2).