Deadlocks

Deadlock is a situation in computer systems where two or more processes cannot proceed because each is waiting for a resource that another process holds. Deadlock is a critical problem in concurrent systems, such as operating systems, databases, and distributed systems, and must be addressed to ensure smooth operation.

Key Concepts of Deadlock

1. Deadlock Definition

A deadlock occurs when a set of processes becomes permanently blocked because each process in the set is waiting for a resource held by another process in the set.

2. Resources in Deadlock

  • Preemptible Resources: Can be taken away from a process without affecting it (e.g., CPU, RAM).

  • Non-Preemptible Resources: Cannot be forcibly removed; the process holding the resource must release it voluntarily (e.g., printers, files).

Necessary Conditions for Deadlock

For deadlock to occur, the following four conditions must hold simultaneously:

  1. Mutual Exclusion At least one resource must be in a non-shareable mode, meaning only one process can use it at a time.

  2. Hold and Wait A process holding one or more resources is waiting for additional resources held by other processes.

  3. No Preemption Resources cannot be forcibly taken from a process; they must be released voluntarily by the process holding them.

  4. Circular Wait A set of processes {P1, P2, ..., Pn} exists such that P1 is waiting for a resource held by P2, P2 is waiting for a resource held by P3, ..., and Pn is waiting for a resource held by P1.

Deadlock Representation

  • Resource Allocation Graph (RAG):

    • Vertices: Represent processes and resources.

    • Edges: Represent the relationship between processes and resources.

      • Request edge (from process to resource).

      • Allocation edge (from resource to process).

    A cycle in this graph is a necessary condition for deadlock.

Deadlock Handling Strategies

  1. Deadlock Prevention Modify the system to ensure that at least one of the necessary conditions for deadlock cannot hold:

    • Eliminate Mutual Exclusion: Use sharable resources wherever possible.

    • Avoid Hold and Wait: Require processes to request all required resources at once.

    • Allow Preemption: Permit resources to be forcibly taken from processes.

    • Break Circular Wait: Impose an ordering of resource acquisition.

  2. Deadlock Avoidance Ensure the system never enters a deadlock state by dynamically analyzing resource allocation:

    • Banker’s Algorithm: Simulates resource allocation to determine if granting a resource will leave the system in a safe state.

  3. Deadlock Detection and Recovery Allow deadlock to occur, then detect and resolve it:

    • Detection: Check for cycles in the resource allocation graph.

    • Recovery:

      • Terminate one or more processes in the deadlock cycle.

      • Preempt resources from processes.

  4. Deadlock Ignorance In some systems, deadlock is considered rare and not handled explicitly. For example, most operating systems like Windows and Linux use this approach.

Deadlock Prevention in Depth

Strategies to Break Each Condition:

  1. Breaking Mutual Exclusion

    • Design resources to be shareable wherever possible (e.g., read-only files).

  2. Breaking Hold and Wait

    • Ensure processes request all resources at once.

    • Require processes to release held resources before requesting new ones.

  3. Breaking No Preemption

    • Allow resources to be forcibly taken from processes.

    • Save the state of the process and resume it later.

  4. Breaking Circular Wait

    • Impose a strict order in which processes must request resources.

Deadlock Avoidance: The Banker’s Algorithm

The Banker’s Algorithm ensures that a system remains in a safe state by:

  1. Checking Requests: A process can request resources only if:

    • The request does not exceed the process's declared maximum need.

    • The system has enough available resources.

  2. Simulating Allocation: The algorithm simulates granting the request to verify that the system will remain in a safe state.

Deadlock Detection

  1. Using a Resource Allocation Graph

    • Look for cycles in the graph.

  2. Using Matrices

    • Maintain a matrix of allocated and requested resources.

    • Detect deadlock by checking if processes can finish with available resources.

Deadlock Recovery

  1. Process Termination

    • Abort one or more processes in the deadlock cycle to break the cycle.

  2. Resource Preemption

    • Temporarily take resources from processes.

Differences Between Deadlock and Starvation

Aspect

Deadlock

Starvation

Cause

Circular wait and resource dependency.

Processes with lower priority are ignored.

State

Permanent unless resolved explicitly.

Temporary and depends on scheduling.

Resolution

Requires detection and intervention.

Can be mitigated with fair scheduling.

Examples of Deadlock

  1. Dining Philosophers Problem Philosophers need two chopsticks to eat but only one is available at a time, causing a circular wait.

  2. Traffic Gridlock Cars in a circular intersection block each other because each waits for the other to move.

  3. File Access in Programs One program locks a file while another program locks a second file, and both wait for the other’s file to be unlocked.

Real-World Applications and Questions

1. How do operating systems handle deadlock?

  • They often use a mix of prevention, avoidance, and detection strategies depending on the system requirements.

2. What are practical examples of deadlock in databases?

  • Deadlocks can occur when two transactions lock resources and wait for each other to release them.

3. Why is deadlock prevention preferred over detection in real-time systems?

  • Prevention is more reliable because real-time systems cannot afford delays caused by deadlock recovery.

4. What is the difference between livelock and deadlock?

  • In a livelock, processes keep changing states but cannot make progress.

  • In a deadlock, processes are stuck and make no progress.

PreviousSynchronization

Last updated