Necessary Conditions for Deadlock
No Preemption
Read aloud is unavailable in this browser.
The Third Pillar of Deadlock
Consider a thought experiment: if the operating system could forcibly take resources from processes at any time, would deadlock be possible? Two processes waiting for each other's resources could simply have those resources preempted and reallocated—deadlock dissolved. Yet this rarely happens for most resource types. The no preemption condition—processes cannot be forcibly deprived of resources they hold—is the third necessary condition for deadlock.
No preemption means that once a process acquires a resource, that resource belongs to the process until the process voluntarily releases it. The operating system, scheduler, or other processes cannot commandeer the resource. This protection is often essential for correctness, but it also means that waiting processes must wait indefinitely until voluntary release occurs—which may never happen if the holder is itself waiting.
By the end of this page, you will thoroughly understand no preemption as a deadlock condition: its formal definition, the deep reasons why preemption is problematic for many resources, the contrast with preemptible resources like CPU time, and how introducing preemption can serve as a deadlock prevention strategy when feasible.
The No Preemption Condition Defined
Formal Definition:
Resources cannot be preempted; a resource can only be released voluntarily by the process holding it, after that process has completed its task.
Let's dissect this definition:
1. Preemption — The forcible taking of a resource from a process against its will. The process has no say in when or whether the resource is taken.
2. Voluntary Release — The exclusive mechanism for resource deallocation. The holding process decides when to release, not the system or other processes.
3. Task Completion Linkage — Resources are held until the process completes whatever task required them. Partial completion followed by forced release is not permitted.
Coffman et al. stated this condition as: "Resources already allocated cannot be forcibly removed from the processes holding them." This emphasizes that the system lacks the power to reclaim resources—only the holding process can perform the release.
Mathematical Formalization:
Define state transition function for resource allocation:
release(R, Pᵢ, t) → R becomes free at time t
The no-preemption condition states:
∀R, Pᵢ, t: release(R, Pᵢ, t) ⟹ Pᵢ initiated release(R) at time t
That is, every release event is caused by the holding process itself. There is no system-initiated release.
Contrast with Preemptive Systems:
In a preemptive model:
preempt(R, Pᵢ, t) → R taken from Pᵢ at time t, without Pᵢ's consent
If preemption were possible for all resources, the system could break any deadlock by preempting resources from one process in the cycle and granting them to another. No preemption disables this escape valve.
Why Resources Cannot Be Preempted
Unlike process scheduling where CPU preemption is routine, most resources cannot be safely preempted. Understanding why reveals fundamental constraints that make the no-preemption condition necessary for correctness.
- •State Corruption — Many resources have internal state that would be corrupted by mid-operation preemption. A printer mid-page, a disk mid-write, a transaction mid-commit—preemption would leave the resource in an inconsistent, potentially unrecoverable state.
- •Atomicity Violation — Operations requiring exclusive access often need atomicity. Preempting a lock mid-critical-section violates the atomicity guarantee, exposing partial state changes to other processes.
- •No Save/Restore Mechanism — Unlike CPU state (registers, program counter), many resource states cannot be saved and restored. You cannot 'snapshot' a partially printed page and resume it later.
- •Physical Irreversibility — Some resources have physical state changes that cannot be undone. A tape drive that has written bytes cannot un-write them; a robot arm that has moved cannot un-move.
- •Semantic Incompleteness — Preemption would leave work incomplete. A partial file write, an incomplete network message, or a mid-transaction database leave the system in semantically meaningless states.
| Resource | If Preempted Mid-Operation | Result |
|---|---|---|
| Mutex lock | Other process enters critical section concurrently | Data race, corruption, undefined behavior |
| Printer | Print job interrupted mid-page | Garbled output, paper waste, potential jam |
| Write lock on file | File left with partial writes | Data corruption, invalid file format |
| Database transaction | Partial commit | Violated ACID properties, inconsistent data |
| Network socket mid-send | Incomplete message transmitted | Protocol violation, connection reset |
| GPU compute context | Kernel execution interrupted | Undefined results, GPU state corrupted |
These consequences are unacceptable. Systems enforce no-preemption not by choice, but by necessity. The alternative—resource corruption and state inconsistency—is far worse than the deadlock risk introduced by non-preemptible resources.
Preemptible vs. Non-Preemptible Resources
Not all resources are non-preemptible. Understanding which resources can be safely preempted is crucial for system design and deadlock prevention strategies.
- •CPU time — Scheduler can interrupt and resume processes at any time; state fully saveable in PCB
- •Memory (with virtual memory) — Pages can be swapped out, process resumes when paged back in
- •Registers — Saved on context switch, restored transparently
- •CPU cache — Can be flushed; process continues with cache misses
- •I/O bandwidth — Can re-prioritize without corruption
- •Mutex/semaphore — Preemption violates mutual exclusion guarantee
- •Printer mid-job — Cannot meaningfully interrupt and resume
- •Database locks — State changes must complete atomically
- •File write locks — Partial writes corrupt data
- •Device driver during I/O — Hardware may be in inconsistent state
What Makes a Resource Preemptible?
A resource can be preempted if and only if:
-
State is Saveable — The complete state of the resource's use by the process can be captured and stored.
-
State is Restorable — The saved state can be restored later, allowing the process to continue exactly where it left off.
-
Preemption is Invisible — From the preempted process's perspective, preemption never happened—execution resumes seamlessly.
CPU and memory satisfy these criteria: process state is saved in the PCB, memory state in swap space, and resumption is transparent. A mutex lock does not satisfy these criteria: taking the lock away invalidates the mutual exclusion guarantee that the process depends on. The process would need to re-acquire the lock on resumption, potentially reintroducing the original deadlock.
CPU preemption is the gold standard for preemptible resources. The entire process state is saved (registers, PC, stack pointer, flags), and restoration is perfect. If all resources worked like CPUs—with complete state capture and transparent restoration—no-preemption would not be a deadlock concern. The challenge is that most resources lack this property.
The Irreversibility Problem
At the heart of the no-preemption condition lies a fundamental problem: many resource operations are irreversible. Once performed, they cannot be undone, making preemption semantically meaningless or actively harmful.
Classes of Irreversibility:
1. Physical Irreversibility:
Physical actions in the real world cannot be reversed:
- Ink printed on paper
- Holes punched in tape
- Signals transmitted over wire
- Robot arm movements
- Chemical processes (etching, deposition)
Preemption here doesn't just pause the operation—it leaves physical artifacts that cannot be cleaned up.
2. Logical Irreversibility:
Some operations create persistent logical state that cannot be safely rolled back:
- Deleted file (without journaling/snapshot)
- Committed transaction (in many systems)
- Sent network packet (received by remote)
- Published event (consumed by subscribers)
- Incremented counter (observed by others)
Even if we could 'undo' these, other processes may have already observed and acted on the state, creating cascading inconsistencies.
123456789101112131415161718192021222324252627282930313233
// Example: File write - irreversible once partially complete void process_a() { int fd = open("critical_data.bin", O_WRONLY); flock(fd, LOCK_EX); // Acquire exclusive lock // Begin multi-block write operation write(fd, header, sizeof(header)); // Block 1: ✓ Written write(fd, data_part1, sizeof(part1)); // Block 2: ✓ Written // === IF PREEMPTION HAPPENED HERE === // The file now has: // - Valid header // - First part of data // - Missing second part of data // - Missing checksum/footer // // THIS FILE IS NOW CORRUPT // Preemption left the file in an invalid intermediate state write(fd, data_part2, sizeof(part2)); // Block 3: Not written write(fd, checksum, sizeof(checksum)); // Block 4: Not written flock(fd, LOCK_UN); // Release lock close(fd);} // The critical insight: we cannot simply "undo" the partial write// 1. We don't know what the original contents were// 2. Other processes might read the corrupt intermediate state// 3. If this was a journal or log, "undoing" creates gaps// // Non-preemptibility is ESSENTIAL for such operationsSome systems support 'compensating actions'—new operations that logically undo previous ones. But compensating actions are not preemption: they are new forward operations that require their own resources and can themselves deadlock. They also reveal the intermediate state to the system, which may violate isolation guarantees.
No Preemption in Practice
Understanding how no-preemption manifests in real systems illuminates the practical constraints system designers face.
Kernel Locks:
Operating system kernels protect critical data structures with locks:
spin_lock(&inode->i_lock); // Acquire inode lock
// Manipulate inode metadata
inode->i_size = new_size;
inode->i_mtime = current_time;
inode->i_blocks = calculate_blocks(new_size);
spin_unlock(&inode->i_lock); // Release inode lock
If the kernel could preempt the process holding i_lock and give the lock to another process, the inode would be in an inconsistent state:
i_sizeupdatedi_mtimeupdatedi_blocksNOT YET updated (inconsistent with i_size!)
The second process would operate on corrupt metadata. Non-preemptible locks are essential for kernel integrity.
Database Systems:
Databases implement row and page locks that cannot be preempted:
-- Transaction T1
BEGIN;
SELECT * FROM accounts WHERE id = 1 FOR UPDATE;
-- T1 now holds X-lock on row 1
-- This lock CANNOT be preempted by the DBMS
-- T1's transaction integrity depends on this guarantee
UPDATE accounts SET balance = balance - 100 WHERE id = 1;
-- ... more work ...
COMMIT; -- Lock released on commit
Database locks are non-preemptible because:
- The transaction's ACID guarantees depend on lock protection
- Partial transaction state is meaningless and harmful
- Preemption would violate isolation level guarantees
- Rollback is the only safe way to release transaction locks early
Device Drivers:
Device drivers hold hardware state that cannot be preempted:
// DMA transfer in progress
void dma_write_handler(struct device *dev) {
// Hardware operation: DMA engine is actively copying data
// from memory to device.
//
// We CANNOT preempt this operation because:
// 1. The DMA engine is using physical addresses
// 2. If we free the memory buffer, DMA writes to freed memory
// 3. Hardware has no concept of "pause and resume"
// 4. Device might enter error state if protocol violated
wait_for_dma_complete(); // Must wait for hardware
release_buffer(); // Only safe after DMA done
}
Hardware often cannot be "preempted" in any meaningful sense—it operates on its own timeline, and software must coordinate with it, not dictate to it.
Preemption as Deadlock Prevention
Since no-preemption is a necessary condition for deadlock, introducing preemption where feasible can prevent deadlocks. However, this requires careful consideration of which resources can be safely preempted.
- •Voluntary Preemption Protocol — If a process holding resources requests a resource that cannot be immediately granted, all its currently held resources are preempted (released), the process is added to waiting queues for all resources, and it restarts when all are available.
- •Victim Selection — When deadlock is detected, select a victim process to preempt. The victim's resources are forcibly released (with appropriate rollback), breaking the cycle.
- •Timeout-Based Preemption — If a process waits too long for a resource, preempt its held resources and restart. This converts potential deadlock into retry-with-backoff behavior.
- •Priority-Based Preemption — Higher priority processes can preempt resources from lower priority processes. Lower priority processes are rolled back and restart.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647
#include <pthread.h>#include <stdbool.h> // Protocol: If we can't get a resource, release all and retrybool try_acquire_with_preemption( int process_id, resource_t *held_resources, int held_count, resource_t *wanted) { // Try to acquire the wanted resource without blocking if (try_lock(wanted)) { return true; // Got it! No preemption needed } // Cannot acquire wanted resource - must preempt ourselves printf("Process %d: Cannot acquire resource, preempting self", process_id); // Release ALL currently held resources for (int i = 0; i < held_count; i++) { release(held_resources[i]); printf("Process %d: Released resource %d", process_id, held_resources[i].id); } // Save state for restart (application-specific) save_checkpoint(process_id); // Re-request ALL resources (including newly wanted one) // This will block until all are available wait_for_all_resources(process_id, held_resources, held_count, wanted); // Restore state and continue restore_checkpoint(process_id); return true; // Eventually succeeded} // This protocol PREVENTS deadlock by ensuring:// 1. No process ever blocks while holding resources// 2. Resources are only held by running processes// 3. Wait cycles cannot form (all waiters release first)//// Tradeoff: Wasted work, potential livelock if unluckyDatabase transaction abort is a form of controlled preemption. When deadlock is detected, the DBMS aborts one transaction, releasing all its locks and rolling back its changes. This preempts the transaction's resource holdings while maintaining data consistency through the rollback mechanism.
Rollback Mechanisms: Enabling Safe Preemption
Safe preemption requires rollback—the ability to undo the effects of partial execution and restore a consistent state. Understanding rollback mechanisms reveals when and how preemption becomes feasible.
Database Transaction Rollback:
Original State: Account A = $1000, Account B = $500
Transaction:
1. BEGIN
2. Read A: $1000
3. Write A: $900 (debit $100) -- logged in undo log
4. [PREEMPTION/ABORT HERE]
Rollback Process:
1. Examine undo log: "A was $1000, changed to $900"
2. Restore A: A = $1000
3. Release all locks
4. Transaction state = ABORTED
Final State: Account A = $1000, Account B = $500 (unchanged)
Databases make preemption safe through write-ahead logging (WAL):
- Before any modification, log the original value
- If preempted/aborted, use log to restore original values
- Only after commit do changes become permanent
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273
import pickleimport os class Checkpointer: """ Enables preemption by saving and restoring process state. For preemption to be safe, we must be able to: 1. Save ALL relevant state before releasing resources 2. Restore that state when resources are re-acquired 3. Continue execution exactly where we left off """ def __init__(self, process_id): self.process_id = process_id self.checkpoint_file = f"/tmp/checkpoint_{process_id}.pkl" def save_checkpoint(self, state: dict) -> None: """ Save process state before preemption. State must include everything needed to resume: - Local variables - Data structure contents - Progress indicators - Partial results """ checkpoint = { 'state': state, 'resources_held': self.get_current_resources(), 'execution_point': self.get_execution_point(), 'timestamp': time.time() } with open(self.checkpoint_file, 'wb') as f: pickle.dump(checkpoint, f) print(f"Process {self.process_id}: Checkpoint saved") def restore_checkpoint(self) -> dict: """ Restore process state after re-acquiring resources. Returns the saved state so process can continue. """ if not os.path.exists(self.checkpoint_file): raise RuntimeError("No checkpoint to restore") with open(self.checkpoint_file, 'rb') as f: checkpoint = pickle.load(f) # Clean up checkpoint file os.remove(self.checkpoint_file) print(f"Process {self.process_id}: Checkpoint restored") return checkpoint['state'] def preempt_and_release(self, current_state: dict) -> None: """ Voluntarily preempt: save state and release all resources. """ self.save_checkpoint(current_state) # Release all held resources for resource in self.get_current_resources(): release_resource(resource) print(f"Process {self.process_id}: Released {resource}") # Key insight: This works for COMPUTATIONAL state# It does NOT work for:# - Partial I/O operations# - Hardware interactions# - Irreversible side effects# # Preemption is possible only when state is fully capturableRollback has limits: external side effects (network sends, hardware commands, user notifications) cannot be truly rolled back. At best, compensating actions can be performed. This is why true preemption is limited to computational resources with saveable state, not I/O or hardware resources.
KEEP LEARNING
There’s more to understand.
You’re reading the introduction. Create a free account to read the complete lesson, save notes and keep track of your progress.