Wednesday, October 01, 2008



  • Physical resources: printers, type drivers, memory space, CPU cycles...
  • logical resources: files, semaphores, monitors

A deadlock situation can arise if the following 4 conditions hold simultaneously:

  1. Mutual exclusion. At least one resource is held in a nonsharable mode. If another process requests that resource, the requesting process must be delayed until the resource is released. For example, thread1 wants to acquire the mutex lock in the order of (1st mutex, 2nd mutex), while thread2 wants to acquire the mutex in the order (2nd mutex, 1st mutex). Deadlock is possible if thread1 acquires 1st mutex while thread2 acquires 2nd mutex. [prevention:] the mutual-exclusion condition must hold for nonsharable resources. (printer cannot be simultaneously shared by several processes)
  2. Hold and wait. A process holds at least one resource and waiting to acquire additional resources that are currently being held by other processes. [prevention:] Guarantee that, whenever a process requests a resource, it does not hold any other resources. Use different protocols.
  3. No preemption. A resource can be released only voluntarily by the process holding it, after that process has completed it task. [prevention:] if a process is hold some resources and requests another resource that cannot be immediately allocated, then all resources currently being held are preempted(implicitly released)
  4. circle wait. P0 is waiting for resource held by P1, P1 is waiting for a resource held by P2, ..., Pn is waiting for a resource held by P0. [prevention:] use a order of all resource types and to require that each process requests resources in an increasing order. 

Deadlock can be solved with one of following ways:

  • We can use a protocol to prevent or avoid deadlocks, ensuring the system will never enter a deadlock state.
  • All the system to enter a deadlock state, delete it and recover.
  • Ignore the problem totally and pretend the deadlocks never occur.

The last one is used by most systems. It is up to developers to write programs to handle deadlocks.

No comments:

Post a Comment