***************************
Chapter 7: Deadlocks
***************************

System Model
=============

- **System Resources**
  
  - Resources include CPU cycles, memory, files, and I/O devices.  
  - Each resource type may have several instances.  
  - Processes must *request*, *use*, and *release* resources.

- **Resource Allocation Graph (RAG)**
  
  - Vertices:
  
    - **P** = Process  
    - **R** = Resource
  
  - Edges:
  
    - **Request edge (P → R)** : Process *P* requests resource *R*.  
    - **Assignment edge (R → P)** : Resource *R* is allocated to process *P*.
  
  - **Cycle:**
  
    - One instance per resource type → Cycle means deadlock.  
    - Multiple instances → Cycle may lead to deadlock.

------------------------------------------------------------

Deadlock Characterization
==========================

A **deadlock** occurs when processes are waiting indefinitely for resources held by one another.

**Necessary Conditions (Coffman Conditions):**

1. **Mutual Exclusion** – At least one resource must be held in a non-sharable mode.  
2. **Hold and Wait** – A process holds at least one resource and waits for others.  
3. **No Preemption** – Resources cannot be forcibly taken away.  
4. **Circular Wait** – Circular chain of processes, each waiting for a resource held by the next.

All four conditions must hold simultaneously for a deadlock to occur.

------------------------------------------------------------

Methods for Handling Deadlocks
===============================

1. **Deadlock Prevention** – Ensure that at least one necessary condition cannot hold.  
2. **Deadlock Avoidance** – Dynamically ensure system never enters an unsafe state.  
3. **Deadlock Detection and Recovery** – Detect and recover after a deadlock occurs.  
4. **Ignore the Problem** – Often used in practice if deadlocks are rare.

------------------------------------------------------------

Deadlock Prevention
====================

- **Mutual Exclusion:**  
  Make resources sharable whenever possible.

- **Hold and Wait:**  
  Require processes to request all resources at once or release held ones before requesting new.

- **No Preemption:**  
  Allow preemption when a process must wait.

- **Circular Wait:**  
  Impose a total ordering of all resource types; processes request resources in increasing order only.

------------------------------------------------------------

Deadlock Avoidance
===================

- **Safe State:**  
  There exists at least one sequence of process execution that allows all to complete.

- **Unsafe State:**  
  May lead to a deadlock.

- **Banker’s Algorithm:**  
  - Works with multiple resource instances.  
  - Checks if granting a request keeps the system in a safe state before approval.

------------------------------------------------------------

Deadlock Detection
===================

- **Single Instance per Resource Type:**  
  - Use a *Wait-for Graph* (edges from process to process).  
  - Cycle in the graph ⇒ Deadlock.

- **Multiple Instances per Resource Type:**  
  - Use an algorithm similar to the Banker’s algorithm.  
  - Periodically check for deadlocks.

------------------------------------------------------------

Recovery from Deadlock
=======================

- **Process Termination:**  
  - Abort all deadlocked processes.  
  - Or abort one at a time until the cycle is broken.  
  - Selection criteria: process priority, time used, or number of resources held.

- **Resource Preemption:**  
  - Select a victim and take its resources.  
  - Rollback process state as needed.  
  - Avoid starvation by tracking preemption counts.

------------------------------------------------------------

Summary
========

- Deadlocks arise from competition for limited resources.  
- Four necessary conditions must all exist simultaneously.  
- Systems can *prevent*, *avoid*, *detect and recover*, or *ignore* deadlocks.