Sunday 16 June 2013

Banker's Algorithm algorithm

Deadlock Definition
A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause (including itself).

Waiting for an event could be:

  • waiting for access to a critical section
  • waiting for a resource Note that it is usually a non-preemptable (resource). pre-emptable resources can be yanked away and given to another.

It could also be a situation in which two computer programs sharing the same resource are effectively
preventing each other from accessing the resource, resulting in both programs ceasing to function.

Conditions for Deadlock
  • Mutual exclusion: resources cannot be shared.
  • Hold and wait: processes request resources incrementally, and hold on to what they've got.
  • No pre-emption: resources cannot be forcibly taken from processes.
  • Circular wait: circular chain of waiting, in which each process is waiting for a resource held by the next process in the chain.

Strategies for dealing with Deadlock

  • ignore the problem altogether ie. ostrich algorithm it may occur very infrequently, cost of detection/prevention etc may not be worth it.
  • detection and recovery
  • avoidance by careful resource allocation
  • prevention by structurally negating one of the four necessary conditions.

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.

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.





EmoticonEmoticon