ch07

Chapter 7: Deadlocks

Overview

  • Chapter covers concepts related to deadlocks in operating systems.

  • Key Topics:

    • The Deadlock Problem

    • System Model

    • Deadlock Characterization

    • Methods for Handling Deadlocks

      • Deadlock Prevention

      • Deadlock Avoidance

      • Deadlock Detection

      • Recovery from Deadlock

The Deadlock Problem

  • Definition: A set of blocked processes, each holding a resource and waiting to acquire a resource held by another process within the same set.

  • Most operating systems do not prevent or resolve deadlocks.

  • Examples:

    • System with 2 disk drives, where Process P1 and P2 each hold one and need the other's resource.

    • Semaphore example with two processes waiting on each other leads to deadlock.

System Model

  • Resource types include:

    • CPU cycles

    • Memory space

    • I/O devices

  • Each resource type (R1, R2, ..., Rm) has Wi instances.

  • Processes utilize resources by:

    • Request: via system calls (e.g., open(), allocate()), blocks if unavailable.

    • Use.

    • Release: via system calls (e.g., close(), free()).

Deadlock Characterization

  • Four necessary conditions for deadlock to occur:

    1. Mutual Exclusion: Only one process can use a resource at a time.

    2. Hold and Wait: A process holding at least one resource is waiting to acquire additional resources.

    3. No Preemption: Only the process holding a resource can release it voluntarily.

    4. Circular Wait: A closed loop of processes, each waiting for a resource held by the next in the loop.

Resource-Allocation Graph

  • Components:

    • Processes (P) and Resource types (R).

    • Request edge: directed edge Pi → Rj (process requests a resource).

    • Assignment edge: directed edge Rj → Pi (process holds a resource).

  • Cycle Detection:

    • No cycles → no deadlock.

    • Cycle with one instance per resource type → deadlock.

Methods for Handling Deadlocks

  1. Deadlock Prevention & Avoidance: Ensure the system never enters a deadlock state.

  2. Deadlock Detection & Recovery: Allow deadlocks to occur but have mechanisms to detect and recover from them.

  3. Ignore Deadlocks: Many OSes like UNIX and Windows ignore deadlocks despite performance degradation.

Deadlock Prevention Strategies

  • Mutual Exclusion: Non-sharable (e.g., printers) vs. sharable resources (e.g., read-only files).

  • Hold and Wait: Require processes to request all resources before execution or request resources only when none are held.

  • No Preemption: Release all currently held resources if a process requests an additional resource that cannot be granted.

  • Circular Wait: Impose an ordering of resources, forcing processes to request them in a specified order to avoid cycles.

Deadlock Avoidance

  • Requires prior knowledge of maximum resource needs of processes.

  • Examines the resource-allocation state to ensure no circular-wait condition arises.

  • Safe State: Exists if there is a sequence of processes such that each can complete without deadlock.

Banker's Algorithm

  • Mechanism for deadlock avoidance with multiple instances of resources.

  • Each process must declare the maximum number of resources it may need.

  • The system determines if resource allocation leads to a safe state.

  • If safe, resources are allocated; otherwise, the process waits.

Deadlock Detection Algorithms

  • Single Instance: Use wait-for graphs; nodes are processes, edges represent waiting conditions. Cycle detection identifies deadlocks.

  • Several Instances: Track available, allocation, and request matrices to analyze and detect potential deadlocks.

Recovery from Deadlock

  • Process Termination:

    • Abort all deadlocked processes or one at a time to resolve the deadlock.

  • Resource Preemption:

    • Choosing a victim based on cost considerations, followed by rollback to a safe state.

Example Scenarios

  • Example illustrating the Banker's Algorithm shows how to determine system safety based on current resource allocations and requests.

  • Detection algorithm usage is influenced by the likelihood of deadlocks occurring and performance considerations.

Conclusion

  • Understanding deadlocks is crucial for system stability and resource management in operating systems.


Detailed Notes on Deadlocks

Definition

A deadlock is defined as a set of blocked processes, each holding a resource and waiting to acquire a resource held by another process within the same set. Most operating systems do not prevent or resolve deadlocks, which can severely impede system performance.

Characterization

Four necessary conditions must hold simultaneously for a deadlock to occur:

  1. Mutual Exclusion: Only one process can use a resource at a time.

  2. Hold and Wait: A process holding at least one resource is waiting to acquire additional resources.

  3. No Preemption: Only the process holding a resource can release it voluntarily.

  4. Circular Wait: A closed loop of processes exists, where each process is waiting for a resource held by the next in the loop.

Resource-Allocation Graph (RAG)

Components:

  • Processes (P)

  • Resource types (R)

Edges:

  • Request edge: Directed edge from process Pi to resource Rj (process requests a resource).

  • Assignment edge: Directed edge from resource Rj to process Pi (process holds a resource).

Cycle Detection:

  • No cycles: Indicates no deadlock.

  • Cycle with one instance per resource type: Indicates a deadlock.

Deadlock Prevention

Strategies aimed at ensuring that the system never enters a deadlock state include:

  • Mutual Exclusion: Differentiate between non-sharable resources (e.g., printers) and sharable resources (e.g., read-only files).

  • Hold and Wait: Require processes to request all resources they will need before execution, or only request resources when none are currently held.

  • No Preemption: Automatically release all resources currently held by a process if it requests an additional resource that cannot be granted.

  • Circular Wait: Impose an ordering of resources, compelling processes to request resources in a specified order, thus avoiding cycles.

Deadlock Avoidance

Deadlock avoidance methods require prior knowledge of maximum resource needs of processes and examine the current resource-allocation state to prevent circular-wait conditions from arising.

  • Safe State Check: A state is safe if there is a sequence of processes such that each can complete without leading to a deadlock.

  • Banker's Algorithm: Used for deadlock avoidance with multiple instances of resources, where each process must declare its maximum resource needs. The system examines resource allocation to ensure the allocation does not lead to an unsafe state.

Deadlock Detection

Detection algorithms identify deadlocks after they have occurred:

  1. Single Instance: Use wait-for graphs where nodes are processes, and edges represent waiting conditions. A cycle indicates a deadlock.

  2. Multiple Instances: Track three matrices (available, allocation, and request) to analyze system state and detect potential deadlocks.

Recovery from Deadlock

Two main strategies used for recovery are:

  1. Process Termination: Abort all deadlocked processes or resolve them one at a time to clear the deadlock.

  2. Resource Preemption: Select a victim process based on cost considerations, followed by rollback to a safe state, thereby freeing up resources.

Understanding and managing deadlocks are crucial for maintaining system stability and efficient resource allocation in operating systems.