Operating Systems
When Nobody Could Move
Why sometimes the safest system comes to a complete stop.
Operating SystemsSynchronizationMutexesDeadlocksProcess Management
2. The Deadlock
You just observed synchronization prevent progress.
A Deadlock is a state where two or more processes are unable to execute because each is waiting for a resource held by another.
3. Coffman Conditions
A Deadlock can only occur if all four Coffman Conditions are met simultaneously:
1. Mutual Exclusion
Only one process can hold a resource at a time. Other processes requesting it must wait.
2. Hold and Wait
A process holding allocated resources can request additional resources without releasing its current keys.
3. No Preemption
Resources cannot be forcibly confiscated from a process; they must be released voluntarily.
4. Circular Wait
Process A waits for a resource held by B, which waits for a resource held by C, which waits for a resource held by A.
4. Mitigation Strategies
Engineers resolve or bypass Deadlocks using three general approaches:
4.1 Prevention
Prevention strategies eliminate one of the four Coffman conditions to make deadlocks mathematically impossible.
One common Prevention strategy is to eliminate Circular Wait. By enforcing a strict lock acquisition order, the system guarantees that a circular dependency can never form.
4.1.1 EdgeCase: Lock Ordering
Watch how Lock Ordering prevents deadlocks. By requiring all processes to acquire Mutex A before Mutex B, Process 2 is suspended immediately at the first step, allowing Process 1 to complete and unlock the hardware.
4.2 Avoidance
Instead of preventing deadlocks by restricting behaviour, can the Operating System simply predict whether granting a resource request would eventually become dangerous? This naturally introduces the Banker's Algorithm.
Imagine a banker lending money. A banker never gives away all available money simply because someone asks. Instead, the banker first asks:
"If I approve this request, will everyone still be able to finish?"
If the answer is yes, approve the request. If the answer is no, make the process wait. This is exactly the philosophy behind resource Avoidance.
4.2.1 EdgeCase: Banker's Algorithm
Watch how the OS dynamically checks resource safety. When a process requests resources, the OS pauses and simulates the future path. If a safe sequence exists, it grants the request (Green Path). If it leads to a dead-end, it makes the process wait (Red Path).
4.3 Detection & Recovery
Some operating systems choose to allow deadlocks to occur and run periodic checks to identify wait-loops. Recovery happens only after a deadlock has already occurred, using practical techniques such as:
* Terminating a waiting process
* Rolling back work
* Reclaiming resources
* Restarting the subsystem
* Allowing a hardware watchdog timer to reset the system in embedded products
Current Exploration
When Nobody Could Move
