Quiz Bab 7

• Deadlock


  A state when every process in the set of processes is waiting for an event that can be caused only by another process in the set
• System Model


  1. System consists of resources

  2. Resource types R1, R2, ..., Rm

  3. Each resource type Ri has Wi instances

  4. Each process utilizes a resource in the following order: request, use, release
• Resources


  • Can be physical (e.g. printers, disk drives) or logical (e.g. a record in a database, semaphores, monitors)
  • Partitioned into several types, R1, R2, ..., Rm, each consisting of some number of identical instances
• A process may utilize a resource in only the following order: request, use, release
• If the request cannot be granted immediately, then the requesting process must wait until it can acquire the resource
• Necessary conditions for deadlock

  • Mutual exclusion
  • Hold and wait
  • No preemption
  • Circular wait
• Resource-Allocation Graph (RAG)


  A set of vertices V and a set of edges E<|>V is partitioned into two types: P (set of all processes) and R (set of all resource types)<|>Request edge: directed edge Pi -> Rj<|>Assignment edge: directed edge Rj -> Pi
• If the RAG contains no cycles, then there is no deadlock
• If the RAG contains a cycle, then deadlock may exist if there is only one instance per resource type, or there is a possibility of deadlock if there are several instances per resource type
• Methods for handling deadlocks

  • Ensure the system will never enter a deadlock state (deadlock prevention, deadlock avoidance)
  • Allow the system to enter a deadlock state and then recover
  • Ignore the problem and pretend that deadlocks never occur in the system
• Deadlock Prevention


  1. Ensure that at least one of the necessary conditions for deadlocks does not hold

  2. Hold and Wait: require process to request and be allocated all its resources before it begins execution, or allow process to request resources only when the process has none allocated to it

  3. Circular Wait: impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration
• Deadlock prevention methods can lead to low resource utilization and starvation
• Deadlock avoidance is another method to handle deadlocks
• Deadlock detection and recovery is another method to handle deadlocks
• Ignoring the deadlock problem and pretending that deadlocks never occur is used by most operating systems, including UNIX