Tuesday, July 6, 2010

The Banker's Algorithm for avoiding deadlocks

The Banker's Algorithm for avoiding deadlocks is about as effective as banker's hours are in the software development industry. Read it for academic interest.

Thursday, July 1, 2010

Deadlocks

I am back after quite a while. Time-slicing works well for processors but not for the human brain. It is better to do a few things well by spending enough time on each of them than to do a hundred things without making much progress in any.

Anyway, I am studying deadlocks right now. The formal definition (unlike most formal definitions!) is quite easy to comprehend: 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.

But all of the conditions below should hold for a deadlock to occur:

  1. Mutual exclusion: Each resource is either currently assigned to exactly one process or is available.
  2. Hold and wait: Processes currently holding resources that were granted earlier can request new resources
  3. No preemption: Resources already granted cannot be forcibly taken away from a process. (The process has to explicitly release them.)
  4. Circular wait: There must be a circular chain of two or more processes, each of which is waiting for a resource held by the next member of the chain.

The 'directed graph' technique is used to model these conditions. All approaches that attempt to prevent deadlocks try and eliminate one or more of the above conditions.