Computer Science Chapter 7: Deadlocks

Chapter 7: Deadlocks

• Deadlocks occur when sets of concurrent processes are prevented from completing their tasks.
• Deadlocks arise when four conditions hold simultaneously:
  • Mutual exclusion: Only one process can use a resource at a time.
  • Hold and wait: A process holding at least one resource is waiting to acquire additional resources held by other processes.
  • No preemption: A resource can only be released voluntarily, after the process holding it has completed its task.
  • Circular wait: A set of waiting processes exists where each process is waiting for a resource held by the next process in the set, and the last process is waiting for a resource held by the first process.
• System model:
  • System consists of resources (CPU cycles, memory space, I/O devices).
  • Each resource type has a number of instances.
  • Each process utilizes resources via request and release.

Chapter Objectives

• Describe deadlocks and methods for preventing or avoiding them.
• Deadlock Prevention: Methods to ensure that the system will never enter a deadlock state.
  • Mutual Exclusion: Not required for sharable resources.
  • Hold and wait: Guarantee that a process requests all its resources before beginning execution; or the process requests resources only when it has none allocated.
  • No preemption: If a process holding some resources requests another resource that cannot be immediately allocated, then all resources currently held are released. Preempted resources are added to the list of resources the process is waiting for.
  • Circular wait: Impose a total ordering on resource types and require that each process requests them in increasing order of enumeration.

Deadlock Avoidance

• Requires prior information about the maximum resource needs of each process.
• Resource allocation state is defined by: Available resources, allocated resources, and maximum demands of processes.
• System in safe state if there exists a sequence of all processes such that system can allocate requested resources to each process in the sequence.

Safe State

• If a process requests an available resource, the system must decide if immediate allocation leaves the system in a safe state.
• System is in a safe state if there exists a sequence of all processes where the resources that a process can still request can be satisfied using available and held resources.
  • If resources are not immediately available, the process can wait.
  • When a process is finished can obtain resources.
  • Return allocated resources and terminate.

Basic Facts

• If a system is in a safe state, there are no deadlocks.
• If a system is in an unsafe state, there is a possibility of a deadlock.
• Avoidance ensures a system never enters an unsafe state.

Resource-Allocation Graph Scheme

• Claim edge: process may request a resource.
• Claim edge converts to request edge when a process requests a resource.
• Request edge converts to an assignment edge when the resource is allocated to the process.
• When a resource is released, the assignment edge reconverts to a claim edge.
• Resources must be claimed a priori in the system.

Banker's Algorithm

• Handles multiple instances of resource types.
• Each process must claim its maximum resource use a priori.
• When a process requests a resource, it may have to wait.
• When a process gets all its resources, it must return them in a finite amount of time.

Data Structures for Banker's Algorithm

• Available: Vector of length m (number of available resources of each type)
• Max: n x m matrix (Maximum resources each process may need)
• Allocation: n x m matrix (Resources currently allocated to each process)
• Need: n x m matrix (Resources each process needs to complete)(Max - Allocation)

Resource-Request Algorithm for Process Pi

• If Request ≤ Need, and Request ≤ Available, grant the request.
• If either condition fails, the process must wait.

Deadlock Detection

• Allow the system to enter a deadlock state.
• Detection algorithm.
• Recovery scheme.

Single Instance of each Resource Type

• Maintain wait-for graph (Nodes are processes).
• Periodically invoke an algorithm that searches for a cycle in the graph.
• If a cycle exists, a deadlock.
• Algorithm to detect cycles in a graph takes O(n²) operations (n = number of processes).

Several Instances of a Resource Type

• Available: Vector of length m
• Allocation: n x m matrix
• Request: n x m matrix

Detection Algorithm (Steps)

• Initialize Work and Finish vectors
• Set Work = Available, and Finish[i] = true for all i
• Find an index i such that Finish[i] = false and Request ≤ Work
• Work = Work + Allocationi, and Finish[i] = true.
• If all Finish[i] = true, then there are no deadlocks, else there is deadlock.
• Algorithm requires O(m x n²) operations.

Recovery from Deadlock

• Abort all deadlocked processes.
• Abort one process at a time until the deadlock cycle is eliminated.
• Consider priority of process, computation time, resources used, resources needed, if interactive or batch.

Recovery from Deadlock: Resource Preemption

• Selecting a victim (minimize cost)
• Rollback (return to safe state, restart process)
• Starvation (same process repeatedly selected as victim).

Explore the concept of deadlocks in concurrent processes through this quiz. Learn about the four conditions that lead to deadlocks, their impact on system resources, and methods to prevent or avoid them. Test your understanding of key concepts and enhance your knowledge of resource management.