Banker

Banker's Algorithm for Deadlock Avoidance

When a request is made, check to see if after the request is satisfied, there is a (at least one!) sequence of moves that can satisfy all the requests. that is, the new state is safe. If so, satisfy the request, else make the request wait.

How do you find if a state is safe:

For example if given n processes and m resources

Max[n * m]

    Allocated[n * m]

    Still_Needs[n * m]

Available[m]

    Temp[m]

 Done[n]

while () (Temp[j]=Available[j] for all j

   Find an i such that

       a) Done[i] = False

       b) Still_Needs[i,j] <= Temp[j]

   if so { Temp[j] += Allocated[i,j] for all j

       Done[i] = TRUE}

   else if Done[i] = TRUE for all i then state is safe

   else state is unsafe

(Taken from: http://carbon.cudenver.edu/~dkumar/CSC3453/Lec_figures/ch8_class_notes.pdf )

Detection and Recovery process

Is there a deadlock currently?

One resource of each type (1 printer, 1 plotter, 1 terminal etc.)

check if there is a cycle in the resource graph. for each node N in the graph do DFS (depth first search) of the graph with N as the root In the DFS if you come back to a node already traversed, then there is a cycle. }

Multiple resources of each type:

m resources, n processes
Max resources in existence = [E1, E2, E3, .... Em]
Current Allocation = C1-n,1-m
Resources currently Available = [A1, A2, ... Am]
Request matrix = R1-n,1-m
Invariant = Sum(Cij) + Aj = Ej
Define A <= B for 2 vectors, A and B, if Ai <= Bi for all i
Overview of deadlock detection algorithm,

Check R matrix, and find a row i such at Ri < A.
If such a process is found, add Ci to A and remove process i from the system.
Keep doing this till either you have removed all processes, or you cannot remove any other process.
Whatever is remaining is deadlocked.

[ Basic idea, is that there is at least 1 execution which will un-deadlock the system ]

Recovery:

Through pre-emption
Rollback
- keep check-pointing periodically
- when a deadlock is detected, see which resource is needed.
- Take away the resource from the process currently having it.
- Later on, you can restart this process from a check pointed state where it may need to reacquire the resource.
Killing processes
- where possible, kill a process that can be rerun from the beginning without ill-effects

Further information could be searched on the following websites.