Process Synchronisation & Deadlocks

The Critical Section Problem

Analogy: Two people try to update the same bank balance at the same time. Both read ₹100, both add ₹50, both write ₹150. But the correct answer is ₹200! This is a race condition.

A critical section is a piece of code that accesses shared resources (variables, files, hardware). At most ONE process should execute it at a time.

Three requirements for a correct solution:

1. Mutual Exclusion: Only ONE process in critical section at any time
2. Progress: If no one is in the CS and some want to enter, someone must get in
             (cannot keep stalling forever — must make progress)
3. Bounded Waiting: If process A is waiting to enter, there's a LIMIT to how many
                    times others can enter before A gets its turn

---

Semaphores — The Traffic Light for Processes

Analogy: A parking lot with N spaces. When you enter (wait), count goes down. When you leave (signal), count goes up. If count = 0, you wait outside.

Semaphore S = an integer variable
Operations (both ATOMIC — indivisible):

wait(S):    while S <= 0; do nothing  ← busy wait (spin)
            S--;

signal(S):  S++;

Binary semaphore (mutex): S starts at 1. Used for mutual exclusion. Counting semaphore: S starts at N. Tracks N available resources.

Protecting a Critical Section with Semaphore

Semaphore mutex = 1;  // 1 = free, 0 = locked

Process i:
  wait(mutex);        // acquire lock
  // ── critical section ──
  signal(mutex);      // release lock

Classic Problem: Producer-Consumer

Buffer size = N
Semaphores:
  mutex = 1     (mutual exclusion on buffer)
  full  = 0     (count of full slots)
  empty = N     (count of empty slots)

Producer:                    Consumer:
  wait(empty);               wait(full);
  wait(mutex);               wait(mutex);
  add item to buffer         remove item from buffer
  signal(mutex);             signal(mutex);
  signal(full);              signal(empty);

KEY ORDER: always wait(empty/full) BEFORE wait(mutex)
Reversed order causes DEADLOCK!

---

Deadlock — The Four Horsemen

Analogy: Four cars at a 4-way intersection, each blocking the next. Nobody can move forward.

Deadlock requires ALL FOUR conditions to hold simultaneously:

1. Mutual Exclusion:
   Resources cannot be shared — only ONE process uses a resource at a time.

2. Hold and Wait:
   A process holds at least one resource AND is waiting to acquire more.

3. No Preemption:
   Resources cannot be forcibly taken — only the holding process can release them.

4. Circular Wait:
   A cycle: P1 waits for P2, P2 waits for P3, P3 waits for P1.

Break ANY ONE condition → deadlock impossible!

---

Resource Allocation Graph (RAG)

Nodes:  Circles = Processes  ○   Squares = Resources  □
Edges:  P → R = "process requesting resource"  (request edge)
        R → P = "resource assigned to process"  (assignment edge)

Single-instance resources:
  CYCLE in RAG ⟺ DEADLOCK

Multi-instance resources:
  Cycle is NECESSARY but NOT SUFFICIENT for deadlock
  Need Banker's algorithm to confirm

Example RAG with deadlock:

P1 ──request──→ R1 ──assigned──→ P2
↑                                  |
└──────assigned── R2 ←─request─────┘

P1 holds R2, wants R1.
P2 holds R1, wants R2.
DEADLOCK (cycle: P1→R1→P2→R2→P1)

---

Banker's Algorithm — Deadlock Avoidance

Analogy: A bank gives loans but always keeps enough cash to satisfy the WORST CASE needs of all customers who could ask for their full remaining credit.

Key matrices:
Max[i][j]        = max resource j that process i may ever need
Allocation[i][j] = resource j currently allocated to process i
Need[i][j]       = Max[i][j] - Allocation[i][j]  ← still needed
Available[j]     = total resource j - sum of Allocation[*][j]

Safety Algorithm:

Work = Available (copy)
Finish[i] = false for all processes

Repeat:
  Find i such that: Finish[i] = false AND Need[i] <= Work
  If found: Work = Work + Allocation[i]; Finish[i] = true
  If not found: break

If all Finish[i] = true → SAFE STATE (safe sequence found)
Otherwise → UNSAFE STATE

Worked Example:

3 processes, 1 resource type:
Max = [7, 3, 9], Allocation = [3, 2, 2], Available = 3
Need = [4, 1, 7]

Step 1: Need[P1]=1 ≤ Available=3 → run P1, Work = 3+2 = 5, Finish[P1]=true
Step 2: Need[P0]=4 ≤ Work=5 → run P0, Work = 5+3 = 8, Finish[P0]=true
Step 3: Need[P2]=7 ≤ Work=8 → run P2, Finish[P2]=true

Safe sequence: P1, P0, P2 ✓ SAFE STATE

---

Deadlock Prevention vs Avoidance vs Detection

Prevention:  Eliminate one of the 4 conditions at design time
             (e.g., request ALL resources at once = no hold-and-wait)
             Pros: simple; Cons: low resource utilisation

Avoidance:   Check safety before granting every request (Banker's)
             Pros: better utilisation; Cons: must know Max in advance

Detection:   Allow deadlock to occur, then detect and recover
             Pros: maximum utilisation; Cons: recovery overhead

---

Quick Check

Q1. Which single condition, if eliminated, is the most practical way to prevent deadlock in most systems? Answer: Circular wait — impose a total ordering of resources; processes must request in order. This is practical and widely used.

Q2. Semaphore mutex=1, full=0. Process executes: wait(mutex) then wait(full). Producer has item but cannot signal because consumer holds mutex. Deadlock? Answer: Yes — classic deadlock from wrong semaphore order. Must wait(full) before wait(mutex) in consumer.

Q3. RAG has a cycle with single-instance resources. Is deadlock certain? Answer: Yes — with single-instance resources, cycle ⟺ deadlock.