Deadlocks

🔒 Deadlocks: When Everyone Gets Stuck!

The Story of Four Friends and One Narrow Bridge

Imagine four friends walking on four different paths. All paths meet at a tiny bridge that only fits one person. Each friend reaches the bridge at the same time. Nobody wants to go back. Everyone waits for someone else to move first.

Nobody moves. Ever.

That’s a deadlock!

🎯 What is a Deadlock?

A deadlock happens when two or more processes are stuck waiting for each other. None of them can continue because each one needs something the other is holding.

Simple Example: Two Kids, Two Toys

Kid A has: Red ball
Kid A wants: Blue car

Kid B has: Blue car
Kid B wants: Red ball

Neither will share first.
Both wait forever!

In computers: Programs (called processes) need resources like memory, files, or printers. When they get stuck waiting for each other’s resources, that’s a deadlock.

🧩 The Four Deadly Conditions

For a deadlock to happen, ALL FOUR conditions must be true at the same time. Think of them as four puzzle pieces that create trouble together.

1. Mutual Exclusion 🔐

“Only ONE person can use this at a time!”

graph TD
    A["Printer"] --> B["Only Process A<br>can use it now"]
    B --> C["Process B must wait"]

Example: Only one person can use the bathroom at a time. Others must wait outside.

2. Hold and Wait ✋

“I’m keeping what I have while waiting for more!”

graph TD
    A["Process A"] --> B["Holds: File 1"]
    A --> C["Wants: File 2"]
    D[Won't let go of<br>File 1 while waiting]

Example: A child holds one toy tight while reaching for another toy someone else has.

3. No Preemption 🚫

“You can’t take it from me!”

No one can forcefully take away what a process is holding. The process must give it up willingly.

Example: You can’t snatch a book from someone’s hands. You must wait until they put it down.

4. Circular Wait 🔄

“We’re all waiting in a circle!”

graph TD
    A["Process A"] -->|waits for| B["Process B"]
    B -->|waits for| C["Process C"]
    C -->|waits for| A

Example:

• Alex waits for Ben’s pencil
• Ben waits for Charlie’s eraser
• Charlie waits for Alex’s ruler

Everyone waits in a circle. Forever!

🛡️ Deadlock Prevention: Stop It Before It Starts!

The smartest way to handle deadlocks? Don’t let them happen at all!

We do this by breaking at least ONE of the four conditions.

Breaking Mutual Exclusion

Make resources sharable when possible.

Some things can be shared! Like a read-only file. Many programs can read the same file together.

Before: Only 1 can use the printer
After:  Print requests go to a queue
        Everyone submits, printer handles one by one

Breaking Hold and Wait

Get everything you need at once, OR hold nothing!

graph TD
    A["Process starts"] --> B{Request ALL<br>resources at once}
    B -->|Gets all| C["Run happily!"]
    B -->|Can't get all| D["Wait with nothing"]
    D --> B

Example: Before starting your homework, gather ALL supplies: pencil, paper, eraser, calculator. Don’t start until you have everything!

Breaking No Preemption

Allow taking back resources if needed.

If Process A is waiting for something, take away what A is holding and give it to others.

Example: If you’ve been on the swing too long and others are waiting, a teacher can ask you to give it up.

Breaking Circular Wait

Create a strict ordering!

Number all resources. Processes must request them in order.

Resources numbered:
1 = Keyboard
2 = Mouse
3 = Printer

Rule: Must request in order 1→2→3
Can't ask for 1 if you already have 3!

graph TD
    A["Request Resource 1"] --> B["Then Resource 2"]
    B --> C["Then Resource 3"]
    C --> D["No circles possible!"]

🎯 Deadlock Avoidance: Being Careful Every Step

Prevention says “never allow the conditions.” Avoidance says “be smart about each decision.”

The Banker’s Algorithm 🏦

Imagine a banker with limited money. Before giving a loan, they check: “If I give this loan, can I still help all other customers later?”

graph TD
    A["Process requests&lt;br&gt;resource"] --> B{Is it SAFE<br>to give?}
    B -->|Yes, safe| C["Grant request"]
    B -->|No, unsafe| D["Make process wait"]
    C --> E["Check safety&lt;br&gt;again later"]

Safe State vs Unsafe State

Safe State: There’s at least one way for ALL processes to finish.

Unsafe State: We might get stuck. No guaranteed way out.

Simple Example

Available cookies: 10

Child A needs: 8 total (has 3)
Child B needs: 6 total (has 2)
Child C needs: 5 total (has 2)

Available now: 10 - 3 - 2 - 2 = 3 cookies

Can we help everyone finish?
✓ Give 3 to C (needs 3 more) → C finishes, returns 5
✓ Now have 5, give 4 to B → B finishes, returns 6
✓ Now have 6, give 5 to A → A finishes!

This is a SAFE sequence: C → B → A

🔍 Deadlock Detection: Finding the Problem

Sometimes we let deadlocks happen, then find and fix them.

Resource Allocation Graph

We draw a picture showing who has what and who wants what.

graph LR
    P1["Process 1"] -->|wants| R1["Resource A"]
    R1 -->|held by| P2["Process 2"]
    P2 -->|wants| R2["Resource B"]
    R2 -->|held by| P1

Circle found! Deadlock detected!

Detection Rules

How Often to Check?

• Every request? Safe but slow
• Periodically? Good balance
• When CPU is idle? Efficient but risky

🔧 Deadlock Recovery: Breaking Free!

Once we find a deadlock, we must break it. Here’s how:

Option 1: Terminate Processes 💀

graph TD
    A["Deadlock found!"] --> B{Kill which process?}
    B --> C["Kill ALL deadlocked<br>processes"]
    B --> D["Kill ONE at a time<br>until fixed"]

Choosing who to terminate:

• Process that did least work
• Process with lowest priority
• Process that will be easiest to restart

Option 2: Resource Preemption 🔄

Take resources away from some processes and give to others.

Before:
Process A has: Printer
Process B has: Scanner
Both want what the other has.

After preemption:
Take scanner from B, give to A
A finishes, releases both
B can now continue!

Challenge: The victim process might need to restart from the beginning!

Option 3: Rollback ⏪

Send a process back in time (to a saved checkpoint) and let it try again.

graph TD
    A["Process reaches<br>deadlock"] --> B["Rollback to<br>saved checkpoint"]
    B --> C["Try different<br>path"]
    C --> D["Success!"]

📊 Comparing Our Approaches

🎬 Real-Life Deadlock: The Dining Philosophers

Five philosophers sit around a table. Between each pair is ONE chopstick (5 total). To eat, you need TWO chopsticks.

graph TD
    P1["Philosopher 1"] --> C1["Chopstick 1"]
    P2["Philosopher 2"] --> C2["Chopstick 2"]
    P3["Philosopher 3"] --> C3["Chopstick 3"]
    P4["Philosopher 4"] --> C4["Chopstick 4"]
    P5["Philosopher 5"] --> C5["Chopstick 5"]

The Problem: If ALL philosophers pick up the chopstick on their LEFT at the same time, everyone has ONE chopstick and waits for the RIGHT one.

Deadlock! Everyone starves.

Solutions:

1. Only 4 philosophers sit at once (prevent circular wait)
2. Pick up BOTH chopsticks at once or NONE (prevent hold and wait)
3. Odd philosophers pick left first, even pick right first (break symmetry)

🌟 Key Takeaways

1. Deadlock = Processes stuck waiting for each other forever

2. Four conditions MUST all exist:

   • Mutual Exclusion
   • Hold and Wait
   • No Preemption
   • Circular Wait

3. Prevention = Break at least one condition before running

4. Avoidance = Make careful decisions (like a smart banker)

5. Detection = Find deadlocks using graphs, then recover

6. Recovery = Terminate, preempt resources, or rollback

💡 Remember This!

“A deadlock is like four cars at a four-way stop, each waiting for the other to go first. Nobody moves. Traffic stops. The solution? Someone must go first, or everyone backs up!”

You now understand deadlocks! You can spot them, prevent them, avoid them, detect them, and recover from them.

You’re unstoppable! 🚀