Operating SystemsDeadlock Prevention

Deadlock Prevention Strategies

LevelAdvanced

Duration90 mins

TopicDeadlock Prevention

3 / 5

Breaking No Preemption

Attacking the No-Preemption Condition

The no-preemption condition states that resources cannot be forcibly taken away from a process—they can only be released voluntarily when the process no longer needs them. This condition is essential for deadlock: if we could simply take resources from waiting processes, we could break any potential deadlock cycle.

Breaking the no-preemption condition means allowing resource preemption: the system can forcibly revoke a resource from one process and give it to another. This is a powerful deadlock prevention mechanism, but it comes with significant constraints on which resources can be preempted safely.

The Key Insight

Preemption is only feasible for resources whose state can be saved and restored. The process losing the resource must not be left in an inconsistent state, and when the resource is returned, the process must be able to continue from where it left off.

Why preemption breaks deadlock:

Consider the classic deadlock scenario:

Process A holds Resource 1, waits for Resource 2
Process B holds Resource 2, waits for Resource 1

With preemption enabled:

System detects potential deadlock (or simply responds to A's waiting)
System preempts Resource 1 from A, saves A's state
B can now acquire Resource 1, proceed, and complete
B releases Resources 1 and 2
A is restored, given both resources, and continues

The deadlock is broken because resources can be taken away, preventing the indefinite wait.

Understanding Resource Preemption

Preemption in the context of resources means forcibly taking a resource away from a process before that process has voluntarily released it. This is analogous to CPU preemption, where the operating system can forcibly suspend a running process to schedule another.

Formal Definition:

A resource R is preemptible if:

The current state of R (and the process's use of R) can be captured
R can be reassigned to another process
The original process can later resume using R with its state restored
No data corruption or inconsistency results from this operation

Not all resources satisfy these conditions. Understanding which resources are preemptible is crucial for applying this prevention strategy.

Resource Preemptibility Classification
Resource Type	Preemptible?	Reason	Preemption Mechanism
CPU	Yes	State fully captured in registers/PCB	Context switch saves all execution state
Memory pages	Yes	Contents can be saved to disk	Page-out to swap, page-in when needed
CPU registers	Yes	Finite, well-defined state	Saved/restored during context switch
Virtual memory address space	Yes	Page table entries, mappings	Process can be swapped out entirely
Printer (mid-job)	No	Paper already has partial output	Cannot 'un-print' what's been printed
Tape drive (mid-write)	No	Tape position, partial writes	Sequential medium, no random access
Mutex/Lock	Dangerous	May leave protected data inconsistent	Would violate critical section guarantees
Database lock	Sometimes	If transaction can be rolled back	Transaction abort and rollback
File (mid-write)	Sometimes	Depends on write semantics	May need to rollback partial writes
Network connection	Partially	TCP state is complex	Connection may timeout, need retransmit

The Critical Distinction

CPU and memory are easily preemptible because their state is well-defined and can be fully captured. Physical devices mid-operation are generally NOT preemptible because the physical world doesn't have an 'undo' button. Synchronization primitives are dangerous to preempt because they protect invariants.

CPU Preemption: The Model Case

The CPU is the classic example of a preemptible resource. Modern operating systems regularly preempt the CPU from running processes, demonstrating that preemption can work smoothly when properly implemented.

Why CPU preemption works:

Complete state capture: All CPU state (registers, program counter, flags, FPU state) can be saved
Well-defined save/restore mechanism: Context switch is a solved problem
No side effects: Taking the CPU away doesn't corrupt data or cause physical changes
Transparent resumption: Process resumes exactly where it was interrupted

cpu_preemption.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// CPU Preemption - How the scheduler implements it
 
typedef struct {
    // General purpose registers
    uint64_t rax, rbx, rcx, rdx;
    uint64_t rsi, rdi, rbp, rsp;
    uint64_t r8, r9, r10, r11, r12, r13, r14, r15;
    
    // Instruction pointer and flags
    uint64_t rip;      // Where execution was interrupted
    uint64_t rflags;   // CPU flags
    
    // Segment registers
    uint16_t cs, ds, es, fs, gs, ss;
    
    // Floating point / SIMD state
    uint8_t fpu_state[512];  // FXSAVE area
    
    // Additional state
    uint64_t cr3;      // Page table base (address space)
} cpu_context_t;
 
typedef struct {
    pid_t pid;
    cpu_context_t context;     // Saved CPU state
    process_state_t state;     // RUNNING, READY, BLOCKED, etc.
    struct process* next;      // For scheduler queues
} process_t;
 
// Timer interrupt handler - triggers preemption
void timer_interrupt_handler(interrupt_frame_t* frame) {
    process_t* current = get_current_process();
    
    // Step 1: Save current process state
    save_cpu_context(&current->context, frame);
    current->state = READY;
    
    // Step 2: Add to ready queue
    scheduler_enqueue(current);
    
    // Step 3: Select next process
    process_t* next = scheduler_dequeue();
    
    // Step 4: Restore next process state
    restore_cpu_context(&next->context, frame);
    next->state = RUNNING;
    set_current_process(next);
    
    // Step 5: Return to next process
    // (interrupt return uses modified frame)
}
 
/*
 * KEY OBSERVATION:
 * 
 * From the process's perspective, it has no idea preemption occurred.
 * The save/restore is transparent and complete.
 * 
 * This is the gold standard for preemptible resources:
 * - Complete state capture
 * - Atomic save/restore
 * - No side effects
 * - Transparent to the preempted entity
 * 
 * For deadlock prevention, we want to achieve this for OTHER resources.
 */

The CPU preemption model informs resource preemption design:

When considering whether a resource can be preempted, we ask:

Can we define the complete 'context' for this resource's use?
Can we atomically save that context?
Can we later restore the context exactly?
Will the process be unaware of the preemption (or at least able to handle it)?

Resources that answer 'yes' to all four questions are candidates for preemption-based deadlock prevention.

Memory Preemption and Swapping

Memory is another resource that can be preempted. The operating system can take physical memory frames away from one process and give them to another. This is the basis of virtual memory and swapping.

How memory preemption works:

Page-out: Contents of a memory page are written to swap space (disk)
Frame reuse: The physical frame is reassigned to another process
Fault handling: When the original process accesses the page, a page fault occurs
Page-in: Contents are read back from swap, process continues

From the process's perspective, memory access appears continuous—the preemption is transparent.

memory_preemption.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
// Memory Preemption via Paging
 
typedef struct {
    uint64_t frame_number;     // Physical frame if present
    bool present;              // Is page in physical memory?
    bool dirty;                // Has page been modified?
    bool referenced;           // Has page been accessed recently?
    uint64_t swap_location;    // Location in swap if not present
} page_table_entry_t;
 
// Memory pressure handler - preempts pages from processes
void memory_pressure_handler() {
    while (free_frames_count() < MINIMUM_FREE_FRAMES) {
        // Select a page to preempt (e.g., using LRU)
        page_table_entry_t* victim = select_victim_page();
        process_t* victim_owner = get_page_owner(victim);
        
        // Step 1: If dirty, write to swap
        if (victim->dirty) {
            victim->swap_location = allocate_swap_slot();
            write_to_swap(victim->frame_number, victim->swap_location);
        }
        
        // Step 2: Mark page as not present
        victim->present = false;
        victim->frame_number = 0;
        
        // Step 3: Invalidate TLB entry
        invalidate_tlb_entry(victim_owner->pid, get_page_address(victim));
        
        // Step 4: Add frame to free list
        add_to_free_list(victim->frame_number);
        
        // The victim process doesn't know its page is gone
        // until it tries to access it (page fault)
    }
}
 
// Page fault handler - restores preempted pages
void page_fault_handler(uint64_t faulting_address) {
    process_t* current = get_current_process();
    page_table_entry_t* pte = get_page_table_entry(current, faulting_address);
    
    if (!pte->present && pte->swap_location != 0) {
        // Page was preempted - restore it
        
        // Step 1: Allocate a new frame
        uint64_t new_frame = allocate_frame();
        if (new_frame == 0) {
            // No free frames - preempt another page first
            memory_pressure_handler();
            new_frame = allocate_frame();
        }
        
        // Step 2: Read from swap
        read_from_swap(pte->swap_location, new_frame);
        free_swap_slot(pte->swap_location);
        
        // Step 3: Update page table
        pte->frame_number = new_frame;
        pte->present = true;
        pte->swap_location = 0;
        
        // Step 4: Process can now continue - it never knew the preemption happened
        return;  // Restart the faulting instruction
    }
    
    // Handle other fault types (e.g., invalid access)
    handle_segfault(current, faulting_address);
}
 
/*
 * DEADLOCK PREVENTION THROUGH MEMORY PREEMPTION:
 * 
 * Scenario: Multiple processes need memory, total demand exceeds physical RAM
 * 
 * Without preemption: Processes block indefinitely waiting for memory
 * 
 * With preemption:
 * - OS preempts pages from waiting processes
 * - Frees memory for processes that can proceed
 * - When preempted processes run, their pages fault and are restored
 * - No deadlock possible - memory is always available (virtually)
 */

Virtual Memory is Preemption

Every system using virtual memory with demand paging is already using resource preemption! The OS regularly takes physical memory from processes and gives it to others. This is why memory deadlock is rare in modern systems—preemption is built into the memory management subsystem.

Preemption Protocols for Deadlock Prevention

Several formal protocols exist for using preemption to prevent deadlock. These protocols define the conditions under which resources are preempted and how processes respond.

Preemption Protocol Variants

•Protocol 1: Preempt on Wait — If a process requests a resource that cannot be immediately allocated, all resources currently held by that process are preempted (added back to the pool). The process restarts when all needed resources are available.
•Protocol 2: Preempt from Wait — If process A needs a resource held by process B, and B is waiting for some other resource, then B's resource is preempted and given to A. B continues waiting for both its original request and the preempted resource.
•Protocol 3: Priority-based Preemption — Higher-priority processes can preempt resources from lower-priority processes. Used in real-time systems to ensure critical tasks can proceed.
•Protocol 4: Timeout-based Preemption — If a process holds a resource for too long without making progress, the resource is preempted. Addresses potential livelock.

preemption_protocol.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
// Protocol 1: Preempt on Wait
// If a process cannot get a resource, all its resources are preempted
 
typedef struct {
    int held[MAX_RESOURCES];           // Resources currently held
    int waiting_for[MAX_RESOURCES];    // Resources we're waiting for
    bool preempted;                    // Have we been preempted?
    void* saved_state;                 // State before preemption
} process_t;
 
result_t request_resource_protocol1(process_t* proc, int resource_id) {
    mutex_lock(&rm.lock);
    
    if (rm.available[resource_id] > 0) {
        // Resource available - allocate normally
        rm.available[resource_id]--;
        proc->held[resource_id]++;
        mutex_unlock(&rm.lock);
        return SUCCESS;
    }
    
    // Resource not available - PREEMPT ALL our held resources
    proc->preempted = true;
    save_process_state(proc);
    
    for (int i = 0; i < MAX_RESOURCES; i++) {
        rm.available[i] += proc->held[i];
        proc->waiting_for[i] += proc->held[i];  // Need these back later
        proc->held[i] = 0;
    }
    
    // Add the new request to our waiting set
    proc->waiting_for[resource_id]++;
    
    // Now wait for ALL resources (held nothing)
    while (!can_allocate_all(proc->waiting_for)) {
        cond_wait(&rm.available_cond, &rm.lock);
    }
    
    // All resources available - allocate them
    for (int i = 0; i < MAX_RESOURCES; i++) {
        rm.available[i] -= proc->waiting_for[i];
        proc->held[i] = proc->waiting_for[i];
        proc->waiting_for[i] = 0;
    }
    
    // Restore state and continue
    restore_process_state(proc);
    proc->preempted = false;
    
    mutex_unlock(&rm.lock);
    return SUCCESS;
}
 
// Protocol 2: Preempt from Waiting Processes
result_t request_resource_protocol2(process_t* requester, int resource_id) {
    mutex_lock(&rm.lock);
    
    if (rm.available[resource_id] > 0) {
        rm.available[resource_id]--;
        requester->held[resource_id]++;
        mutex_unlock(&rm.lock);
        return SUCCESS;
    }
    
    // Resource not available - find who has it
    process_t* holder = find_holder(resource_id);
    
    if (holder != NULL && is_waiting(holder)) {
        // Holder is waiting for something else - PREEMPT from holder
        save_process_state(holder);
        holder->held[resource_id]--;
        holder->waiting_for[resource_id]++;  // Holder now waits for this too
        
        // Give resource to requester
        requester->held[resource_id]++;
        
        mutex_unlock(&rm.lock);
        return SUCCESS;
    }
    
    // Holder is not waiting (actively using resource) - must wait
    while (rm.available[resource_id] == 0) {
        cond_wait(&rm.available_cond, &rm.lock);
    }
    
    rm.available[resource_id]--;
    requester->held[resource_id]++;
    mutex_unlock(&rm.lock);
    return SUCCESS;
}
 
/*
 * COMPARISON:
 * 
 * Protocol 1 (Preempt on Wait):
 *   + Simple to implement
 *   + Guaranteed deadlock-free
 *   - May preempt resources unnecessarily
 *   - Higher overhead (save/restore state frequently)
 *   - Potential for poor resource utilization
 * 
 * Protocol 2 (Preempt from Wait):
 *   + Only preempts when necessary
 *   + Better resource utilization
 *   - More complex implementation
 *   - May cascade (preempted process preempts another)
 *   - Fairness concerns (some processes may starve)
 */

The Challenge of Non-Preemptible Resources

While preemption is effective for CPU, memory, and some logical resources, many resources cannot be safely preempted. Understanding why helps us know when preemption-based prevention is applicable.

Categories of non-preemptible resources:

Why Some Resources Cannot Be Preempted

•Physical devices mid-operation — A printer halfway through a page cannot be preempted without ruining the output. A disk write mid-sector would corrupt data. The physical world has no 'undo'.
•Synchronization primitives — If process A holds a mutex protecting a half-updated data structure, preempting the mutex and giving it to B would expose B to inconsistent data. The mutex exists precisely to prevent this.
•External connections — A network connection has state on the remote end. Preempting an HTTP request mid-response isn't possible—the server has already started sending.
•Hardware state — Some hardware requires setup sequences. Preempting a GPU mid-render or a DMA transfer mid-flight causes undefined behavior.
•Transactional operations — A database transaction that has made partial updates cannot simply be preempted—the partial updates leave the database inconsistent.

Case Study: Why Mutex Preemption is Dangerous

Consider a banking application:

mutex_lock(&account_mutex);
balance = read_balance(account_id);
balance -= withdrawal_amount;
// ** PREEMPTION POINT - mutex taken away **
write_balance(account_id, balance);
mutex_unlock(&account_mutex);

If the mutex is preempted after reading but before writing:

Another process acquires the mutex
That process reads the old balance (our subtraction not yet written)
Both processes think they have the full balance
Result: money appears from nowhere, balance is corrupted

The mutex exists to prevent exactly this scenario. Preempting it defeats its purpose.

Locks Cannot Be Preempted

This is why deadlock prevention via preemption is limited in scope. Locks, semaphores, and similar synchronization primitives protect critical sections precisely because they cannot be preempted. For lock-based deadlocks, we must use other prevention strategies (resource ordering, hold-and-wait prevention) or detection/recovery.

Transaction Rollback as Preemption

In database systems, transaction abort and rollback serves as a form of preemption. When a transaction holds locks and must be terminated (for deadlock resolution or timeout), the database rolls back all changes, releasing the locks. This is preemption of logical resources.

Why database preemption works:

Write-Ahead Logging (WAL): All changes are logged before being applied
Atomicity: Transactions are all-or-nothing; partial changes can be undone
Isolation: Other transactions don't see uncommitted changes (MVCC, locking)
Recovery: Rollback procedure is well-defined and tested

transaction_rollback.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
// Transaction Rollback as Resource Preemption
 
typedef struct {
    transaction_id_t id;
    list_t read_set;         // Objects read by this transaction
    list_t write_set;        // Objects modified by this transaction
    list_t undo_log;         // Log for rollback
    list_t held_locks;       // Locks held by this transaction
    transaction_state_t state;
} transaction_t;
 
// Deadlock detected - select victim and abort
void resolve_deadlock(list_t* deadlocked_transactions) {
    // Select victim (e.g., youngest transaction, smallest, etc.)
    transaction_t* victim = select_deadlock_victim(deadlocked_transactions);
    
    // PREEMPT: abort and rollback the victim
    abort_transaction(victim);
}
 
void abort_transaction(transaction_t* txn) {
    // Step 1: Apply undo log in reverse order
    for (int i = txn->undo_log.count - 1; i >= 0; i--) {
        undo_record_t* record = txn->undo_log.items[i];
        
        switch (record->type) {
            case UNDO_UPDATE:
                // Restore old value
                write_data(record->object_id, record->old_value);
                break;
            case UNDO_INSERT:
                // Delete the inserted record
                delete_data(record->object_id);
                break;
            case UNDO_DELETE:
                // Re-insert the deleted record
                insert_data(record->object_id, record->old_value);
                break;
        }
    }
    
    // Step 2: Release all locks (this is the preemption!)
    for_each(lock, txn->held_locks) {
        release_lock(lock);  // Other transactions can now acquire these
    }
    
    // Step 3: Mark transaction as aborted
    txn->state = ABORTED;
    
    // Step 4: Notify application (may retry)
    notify_transaction_aborted(txn->id);
}
 
// Application handles abort by retrying
void application_logic() {
    int retries = 0;
    while (retries < MAX_RETRIES) {
        transaction_t* txn = begin_transaction();
        
        try {
            // Perform operations...
            transfer_funds(account_a, account_b, amount);
            
            commit_transaction(txn);
            return;  // Success!
            
        } catch (TransactionAbortException) {
            // Transaction was preempted (aborted for deadlock)
            retries++;
            wait_random_backoff();  // Prevent livelock
            // Loop will retry
        }
    }
    
    report_failure("Transaction failed after max retries");
}
 
/*
 * ANALYSIS:
 * 
 * Database abort/rollback IS preemption of locks:
 * 1. Transaction holds locks (resources)
 * 2. Deadlock detected
 * 3. Victim selected
 * 4. Victim's locks forcibly released (preempted)
 * 5. Victim's work undone (state restored)
 * 6. Other transactions proceed
 * 
 * The key is the UNDO LOG - it makes preemption safe by enabling
 * consistent state restoration.
 */

Making Resources Preemptible

The lesson from databases is that resources can be made preemptible by maintaining enough information to restore consistent state after preemption. Write-ahead logging, checkpointing, and undo records are all techniques that enable preemption of resources that would otherwise be non-preemptible.

Practical Considerations and Tradeoffs

Understanding when preemption-based prevention is practical requires careful analysis of costs and benefits.

Preemption Strategy Analysis
Factor	Consideration	Impact on Design
State size	How much state must be saved?	Large state → high preemption cost
Save/restore time	How long does preemption take?	Long time → throughput reduction
Frequency	How often will preemption occur?	Frequent → overhead dominates
Idempotency	Can work be safely redone?	Non-idempotent → complex recovery
Fairness	Who gets preempted?	Always same victim → starvation
Cascading	Does preemption cause more preemption?	Cascading → system instability
Progress guarantee	Will preempted process eventually complete?	No guarantee → starvation possible

When to Use Preemption

•Resource state is small and fast to save
•Preemption is relatively rare (exceptional case)
•Work can be safely redone or is idempotent
•Strong progress guarantees exist
•Resource is fundamentally virtual (CPU, memory)

When to Avoid Preemption

•Resource is a physical device mid-operation
•Resource protects critical section invariants
•State is large, complex, or impossible to save
•Side effects cannot be undone
•Preemption would cascade uncontrollably

Real-World Application:

In practice, preemption-based deadlock prevention is primarily used for:

Operating system scheduling: CPU is the canonical preemptible resource
Virtual memory systems: Pages are preempted transparently
Database deadlock resolution: Transactions are aborted and rolled back
Distributed systems: Requests can time out and retry

For application-level synchronization primitives (mutexes, semaphores), preemption is usually not used. Instead, prevention via resource ordering or detection with recovery is preferred.

Summary: Breaking No Preemption

We've examined how breaking the no-preemption condition can prevent deadlock. Let's consolidate our understanding:

Key Takeaways

•Preemption means forcibly taking resources — If the system can revoke resources from waiting processes, deadlock cycles can be broken.
•Resources must be save/restore capable — Only resources whose state can be fully captured and later restored are candidates for preemption.
•CPU and memory are model preemptible resources — Context switching and paging are mature implementations of resource preemption.
•Physical devices and locks are generally non-preemptible — The physical world has no undo button, and locks protect invariants that preemption would violate.
•Database rollback is a form of preemption — Undo logs make transaction locks preemptible by enabling consistent state restoration.
•Multiple protocols exist — Preempt-on-wait, preempt-from-wait, and priority-based preemption offer different tradeoffs.
•Overhead and feasibility are key concerns — Preemption has costs (state save/restore) and isn't applicable to all resource types.

What's next:

The final prevention strategy attacks the circular wait condition by imposing a total ordering on resources and requiring processes to acquire resources in order. This is often the most practical prevention strategy for application-level synchronization, as it doesn't require preemption or advance knowledge of all resource needs.

Page Complete

You now understand how preemption can prevent deadlock when resources support state save and restore. While powerful for virtual resources like CPU and memory, preemption is limited for physical devices and synchronization primitives, which is why resource ordering remains the most widely applicable prevention strategy.

3 / 5

Loading learning content...

Operating SystemsDeadlock Prevention

Deadlock Prevention Strategies

LevelAdvanced

Duration90 mins

TopicDeadlock Prevention

3 / 5

Breaking No Preemption

Attacking the No-Preemption Condition

The Key Insight

Why preemption breaks deadlock:

Consider the classic deadlock scenario:

Process A holds Resource 1, waits for Resource 2
Process B holds Resource 2, waits for Resource 1

With preemption enabled:

System detects potential deadlock (or simply responds to A's waiting)
System preempts Resource 1 from A, saves A's state
B can now acquire Resource 1, proceed, and complete
B releases Resources 1 and 2
A is restored, given both resources, and continues

The deadlock is broken because resources can be taken away, preventing the indefinite wait.

Understanding Resource Preemption

Formal Definition:

A resource R is preemptible if:

The current state of R (and the process's use of R) can be captured
R can be reassigned to another process
The original process can later resume using R with its state restored
No data corruption or inconsistency results from this operation

Not all resources satisfy these conditions. Understanding which resources are preemptible is crucial for applying this prevention strategy.

Resource Preemptibility Classification
Resource Type	Preemptible?	Reason	Preemption Mechanism
CPU	Yes	State fully captured in registers/PCB	Context switch saves all execution state
Memory pages	Yes	Contents can be saved to disk	Page-out to swap, page-in when needed
CPU registers	Yes	Finite, well-defined state	Saved/restored during context switch
Virtual memory address space	Yes	Page table entries, mappings	Process can be swapped out entirely
Printer (mid-job)	No	Paper already has partial output	Cannot 'un-print' what's been printed
Tape drive (mid-write)	No	Tape position, partial writes	Sequential medium, no random access
Mutex/Lock	Dangerous	May leave protected data inconsistent	Would violate critical section guarantees
Database lock	Sometimes	If transaction can be rolled back	Transaction abort and rollback
File (mid-write)	Sometimes	Depends on write semantics	May need to rollback partial writes
Network connection	Partially	TCP state is complex	Connection may timeout, need retransmit

The Critical Distinction

CPU Preemption: The Model Case

Why CPU preemption works:

Complete state capture: All CPU state (registers, program counter, flags, FPU state) can be saved
Well-defined save/restore mechanism: Context switch is a solved problem
No side effects: Taking the CPU away doesn't corrupt data or cause physical changes
Transparent resumption: Process resumes exactly where it was interrupted

cpu_preemption.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// CPU Preemption - How the scheduler implements it
 
typedef struct {
    // General purpose registers
    uint64_t rax, rbx, rcx, rdx;
    uint64_t rsi, rdi, rbp, rsp;
    uint64_t r8, r9, r10, r11, r12, r13, r14, r15;
    
    // Instruction pointer and flags
    uint64_t rip;      // Where execution was interrupted
    uint64_t rflags;   // CPU flags
    
    // Segment registers
    uint16_t cs, ds, es, fs, gs, ss;
    
    // Floating point / SIMD state
    uint8_t fpu_state[512];  // FXSAVE area
    
    // Additional state
    uint64_t cr3;      // Page table base (address space)
} cpu_context_t;
 
typedef struct {
    pid_t pid;
    cpu_context_t context;     // Saved CPU state
    process_state_t state;     // RUNNING, READY, BLOCKED, etc.
    struct process* next;      // For scheduler queues
} process_t;
 
// Timer interrupt handler - triggers preemption
void timer_interrupt_handler(interrupt_frame_t* frame) {
    process_t* current = get_current_process();
    
    // Step 1: Save current process state
    save_cpu_context(&current->context, frame);
    current->state = READY;
    
    // Step 2: Add to ready queue
    scheduler_enqueue(current);
    
    // Step 3: Select next process
    process_t* next = scheduler_dequeue();
    
    // Step 4: Restore next process state
    restore_cpu_context(&next->context, frame);
    next->state = RUNNING;
    set_current_process(next);
    
    // Step 5: Return to next process
    // (interrupt return uses modified frame)
}
 
/*
 * KEY OBSERVATION:
 * 
 * From the process's perspective, it has no idea preemption occurred.
 * The save/restore is transparent and complete.
 * 
 * This is the gold standard for preemptible resources:
 * - Complete state capture
 * - Atomic save/restore
 * - No side effects
 * - Transparent to the preempted entity
 * 
 * For deadlock prevention, we want to achieve this for OTHER resources.
 */

The CPU preemption model informs resource preemption design:

When considering whether a resource can be preempted, we ask:

Can we define the complete 'context' for this resource's use?
Can we atomically save that context?
Can we later restore the context exactly?
Will the process be unaware of the preemption (or at least able to handle it)?

Resources that answer 'yes' to all four questions are candidates for preemption-based deadlock prevention.

Memory Preemption and Swapping

How memory preemption works:

Page-out: Contents of a memory page are written to swap space (disk)
Frame reuse: The physical frame is reassigned to another process
Fault handling: When the original process accesses the page, a page fault occurs
Page-in: Contents are read back from swap, process continues

From the process's perspective, memory access appears continuous—the preemption is transparent.

memory_preemption.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
// Memory Preemption via Paging
 
typedef struct {
    uint64_t frame_number;     // Physical frame if present
    bool present;              // Is page in physical memory?
    bool dirty;                // Has page been modified?
    bool referenced;           // Has page been accessed recently?
    uint64_t swap_location;    // Location in swap if not present
} page_table_entry_t;
 
// Memory pressure handler - preempts pages from processes
void memory_pressure_handler() {
    while (free_frames_count() < MINIMUM_FREE_FRAMES) {
        // Select a page to preempt (e.g., using LRU)
        page_table_entry_t* victim = select_victim_page();
        process_t* victim_owner = get_page_owner(victim);
        
        // Step 1: If dirty, write to swap
        if (victim->dirty) {
            victim->swap_location = allocate_swap_slot();
            write_to_swap(victim->frame_number, victim->swap_location);
        }
        
        // Step 2: Mark page as not present
        victim->present = false;
        victim->frame_number = 0;
        
        // Step 3: Invalidate TLB entry
        invalidate_tlb_entry(victim_owner->pid, get_page_address(victim));
        
        // Step 4: Add frame to free list
        add_to_free_list(victim->frame_number);
        
        // The victim process doesn't know its page is gone
        // until it tries to access it (page fault)
    }
}
 
// Page fault handler - restores preempted pages
void page_fault_handler(uint64_t faulting_address) {
    process_t* current = get_current_process();
    page_table_entry_t* pte = get_page_table_entry(current, faulting_address);
    
    if (!pte->present && pte->swap_location != 0) {
        // Page was preempted - restore it
        
        // Step 1: Allocate a new frame
        uint64_t new_frame = allocate_frame();
        if (new_frame == 0) {
            // No free frames - preempt another page first
            memory_pressure_handler();
            new_frame = allocate_frame();
        }
        
        // Step 2: Read from swap
        read_from_swap(pte->swap_location, new_frame);
        free_swap_slot(pte->swap_location);
        
        // Step 3: Update page table
        pte->frame_number = new_frame;
        pte->present = true;
        pte->swap_location = 0;
        
        // Step 4: Process can now continue - it never knew the preemption happened
        return;  // Restart the faulting instruction
    }
    
    // Handle other fault types (e.g., invalid access)
    handle_segfault(current, faulting_address);
}
 
/*
 * DEADLOCK PREVENTION THROUGH MEMORY PREEMPTION:
 * 
 * Scenario: Multiple processes need memory, total demand exceeds physical RAM
 * 
 * Without preemption: Processes block indefinitely waiting for memory
 * 
 * With preemption:
 * - OS preempts pages from waiting processes
 * - Frees memory for processes that can proceed
 * - When preempted processes run, their pages fault and are restored
 * - No deadlock possible - memory is always available (virtually)
 */

Virtual Memory is Preemption

Preemption Protocols for Deadlock Prevention

Several formal protocols exist for using preemption to prevent deadlock. These protocols define the conditions under which resources are preempted and how processes respond.

Preemption Protocol Variants

•Protocol 1: Preempt on Wait — If a process requests a resource that cannot be immediately allocated, all resources currently held by that process are preempted (added back to the pool). The process restarts when all needed resources are available.
•Protocol 2: Preempt from Wait — If process A needs a resource held by process B, and B is waiting for some other resource, then B's resource is preempted and given to A. B continues waiting for both its original request and the preempted resource.
•Protocol 3: Priority-based Preemption — Higher-priority processes can preempt resources from lower-priority processes. Used in real-time systems to ensure critical tasks can proceed.
•Protocol 4: Timeout-based Preemption — If a process holds a resource for too long without making progress, the resource is preempted. Addresses potential livelock.

preemption_protocol.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
// Protocol 1: Preempt on Wait
// If a process cannot get a resource, all its resources are preempted
 
typedef struct {
    int held[MAX_RESOURCES];           // Resources currently held
    int waiting_for[MAX_RESOURCES];    // Resources we're waiting for
    bool preempted;                    // Have we been preempted?
    void* saved_state;                 // State before preemption
} process_t;
 
result_t request_resource_protocol1(process_t* proc, int resource_id) {
    mutex_lock(&rm.lock);
    
    if (rm.available[resource_id] > 0) {
        // Resource available - allocate normally
        rm.available[resource_id]--;
        proc->held[resource_id]++;
        mutex_unlock(&rm.lock);
        return SUCCESS;
    }
    
    // Resource not available - PREEMPT ALL our held resources
    proc->preempted = true;
    save_process_state(proc);
    
    for (int i = 0; i < MAX_RESOURCES; i++) {
        rm.available[i] += proc->held[i];
        proc->waiting_for[i] += proc->held[i];  // Need these back later
        proc->held[i] = 0;
    }
    
    // Add the new request to our waiting set
    proc->waiting_for[resource_id]++;
    
    // Now wait for ALL resources (held nothing)
    while (!can_allocate_all(proc->waiting_for)) {
        cond_wait(&rm.available_cond, &rm.lock);
    }
    
    // All resources available - allocate them
    for (int i = 0; i < MAX_RESOURCES; i++) {
        rm.available[i] -= proc->waiting_for[i];
        proc->held[i] = proc->waiting_for[i];
        proc->waiting_for[i] = 0;
    }
    
    // Restore state and continue
    restore_process_state(proc);
    proc->preempted = false;
    
    mutex_unlock(&rm.lock);
    return SUCCESS;
}
 
// Protocol 2: Preempt from Waiting Processes
result_t request_resource_protocol2(process_t* requester, int resource_id) {
    mutex_lock(&rm.lock);
    
    if (rm.available[resource_id] > 0) {
        rm.available[resource_id]--;
        requester->held[resource_id]++;
        mutex_unlock(&rm.lock);
        return SUCCESS;
    }
    
    // Resource not available - find who has it
    process_t* holder = find_holder(resource_id);
    
    if (holder != NULL && is_waiting(holder)) {
        // Holder is waiting for something else - PREEMPT from holder
        save_process_state(holder);
        holder->held[resource_id]--;
        holder->waiting_for[resource_id]++;  // Holder now waits for this too
        
        // Give resource to requester
        requester->held[resource_id]++;
        
        mutex_unlock(&rm.lock);
        return SUCCESS;
    }
    
    // Holder is not waiting (actively using resource) - must wait
    while (rm.available[resource_id] == 0) {
        cond_wait(&rm.available_cond, &rm.lock);
    }
    
    rm.available[resource_id]--;
    requester->held[resource_id]++;
    mutex_unlock(&rm.lock);
    return SUCCESS;
}
 
/*
 * COMPARISON:
 * 
 * Protocol 1 (Preempt on Wait):
 *   + Simple to implement
 *   + Guaranteed deadlock-free
 *   - May preempt resources unnecessarily
 *   - Higher overhead (save/restore state frequently)
 *   - Potential for poor resource utilization
 * 
 * Protocol 2 (Preempt from Wait):
 *   + Only preempts when necessary
 *   + Better resource utilization
 *   - More complex implementation
 *   - May cascade (preempted process preempts another)
 *   - Fairness concerns (some processes may starve)
 */

The Challenge of Non-Preemptible Resources

Categories of non-preemptible resources:

Why Some Resources Cannot Be Preempted

•Physical devices mid-operation — A printer halfway through a page cannot be preempted without ruining the output. A disk write mid-sector would corrupt data. The physical world has no 'undo'.
•Synchronization primitives — If process A holds a mutex protecting a half-updated data structure, preempting the mutex and giving it to B would expose B to inconsistent data. The mutex exists precisely to prevent this.
•External connections — A network connection has state on the remote end. Preempting an HTTP request mid-response isn't possible—the server has already started sending.
•Hardware state — Some hardware requires setup sequences. Preempting a GPU mid-render or a DMA transfer mid-flight causes undefined behavior.
•Transactional operations — A database transaction that has made partial updates cannot simply be preempted—the partial updates leave the database inconsistent.

Case Study: Why Mutex Preemption is Dangerous

Consider a banking application:

mutex_lock(&account_mutex);
balance = read_balance(account_id);
balance -= withdrawal_amount;
// ** PREEMPTION POINT - mutex taken away **
write_balance(account_id, balance);
mutex_unlock(&account_mutex);

If the mutex is preempted after reading but before writing:

Another process acquires the mutex
That process reads the old balance (our subtraction not yet written)
Both processes think they have the full balance
Result: money appears from nowhere, balance is corrupted

The mutex exists to prevent exactly this scenario. Preempting it defeats its purpose.

Locks Cannot Be Preempted

Transaction Rollback as Preemption

Why database preemption works:

Write-Ahead Logging (WAL): All changes are logged before being applied
Atomicity: Transactions are all-or-nothing; partial changes can be undone
Isolation: Other transactions don't see uncommitted changes (MVCC, locking)
Recovery: Rollback procedure is well-defined and tested

transaction_rollback.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
// Transaction Rollback as Resource Preemption
 
typedef struct {
    transaction_id_t id;
    list_t read_set;         // Objects read by this transaction
    list_t write_set;        // Objects modified by this transaction
    list_t undo_log;         // Log for rollback
    list_t held_locks;       // Locks held by this transaction
    transaction_state_t state;
} transaction_t;
 
// Deadlock detected - select victim and abort
void resolve_deadlock(list_t* deadlocked_transactions) {
    // Select victim (e.g., youngest transaction, smallest, etc.)
    transaction_t* victim = select_deadlock_victim(deadlocked_transactions);
    
    // PREEMPT: abort and rollback the victim
    abort_transaction(victim);
}
 
void abort_transaction(transaction_t* txn) {
    // Step 1: Apply undo log in reverse order
    for (int i = txn->undo_log.count - 1; i >= 0; i--) {
        undo_record_t* record = txn->undo_log.items[i];
        
        switch (record->type) {
            case UNDO_UPDATE:
                // Restore old value
                write_data(record->object_id, record->old_value);
                break;
            case UNDO_INSERT:
                // Delete the inserted record
                delete_data(record->object_id);
                break;
            case UNDO_DELETE:
                // Re-insert the deleted record
                insert_data(record->object_id, record->old_value);
                break;
        }
    }
    
    // Step 2: Release all locks (this is the preemption!)
    for_each(lock, txn->held_locks) {
        release_lock(lock);  // Other transactions can now acquire these
    }
    
    // Step 3: Mark transaction as aborted
    txn->state = ABORTED;
    
    // Step 4: Notify application (may retry)
    notify_transaction_aborted(txn->id);
}
 
// Application handles abort by retrying
void application_logic() {
    int retries = 0;
    while (retries < MAX_RETRIES) {
        transaction_t* txn = begin_transaction();
        
        try {
            // Perform operations...
            transfer_funds(account_a, account_b, amount);
            
            commit_transaction(txn);
            return;  // Success!
            
        } catch (TransactionAbortException) {
            // Transaction was preempted (aborted for deadlock)
            retries++;
            wait_random_backoff();  // Prevent livelock
            // Loop will retry
        }
    }
    
    report_failure("Transaction failed after max retries");
}
 
/*
 * ANALYSIS:
 * 
 * Database abort/rollback IS preemption of locks:
 * 1. Transaction holds locks (resources)
 * 2. Deadlock detected
 * 3. Victim selected
 * 4. Victim's locks forcibly released (preempted)
 * 5. Victim's work undone (state restored)
 * 6. Other transactions proceed
 * 
 * The key is the UNDO LOG - it makes preemption safe by enabling
 * consistent state restoration.
 */

Making Resources Preemptible

Practical Considerations and Tradeoffs

Understanding when preemption-based prevention is practical requires careful analysis of costs and benefits.

Preemption Strategy Analysis
Factor	Consideration	Impact on Design
State size	How much state must be saved?	Large state → high preemption cost
Save/restore time	How long does preemption take?	Long time → throughput reduction
Frequency	How often will preemption occur?	Frequent → overhead dominates
Idempotency	Can work be safely redone?	Non-idempotent → complex recovery
Fairness	Who gets preempted?	Always same victim → starvation
Cascading	Does preemption cause more preemption?	Cascading → system instability
Progress guarantee	Will preempted process eventually complete?	No guarantee → starvation possible

When to Use Preemption

•Resource state is small and fast to save
•Preemption is relatively rare (exceptional case)
•Work can be safely redone or is idempotent
•Strong progress guarantees exist
•Resource is fundamentally virtual (CPU, memory)

When to Avoid Preemption

•Resource is a physical device mid-operation
•Resource protects critical section invariants
•State is large, complex, or impossible to save
•Side effects cannot be undone
•Preemption would cascade uncontrollably

Real-World Application:

In practice, preemption-based deadlock prevention is primarily used for:

Operating system scheduling: CPU is the canonical preemptible resource
Virtual memory systems: Pages are preempted transparently
Database deadlock resolution: Transactions are aborted and rolled back
Distributed systems: Requests can time out and retry

For application-level synchronization primitives (mutexes, semaphores), preemption is usually not used. Instead, prevention via resource ordering or detection with recovery is preferred.

Summary: Breaking No Preemption

We've examined how breaking the no-preemption condition can prevent deadlock. Let's consolidate our understanding:

Key Takeaways

•Preemption means forcibly taking resources — If the system can revoke resources from waiting processes, deadlock cycles can be broken.
•Resources must be save/restore capable — Only resources whose state can be fully captured and later restored are candidates for preemption.
•CPU and memory are model preemptible resources — Context switching and paging are mature implementations of resource preemption.
•Physical devices and locks are generally non-preemptible — The physical world has no undo button, and locks protect invariants that preemption would violate.
•Database rollback is a form of preemption — Undo logs make transaction locks preemptible by enabling consistent state restoration.
•Multiple protocols exist — Preempt-on-wait, preempt-from-wait, and priority-based preemption offer different tradeoffs.
•Overhead and feasibility are key concerns — Preemption has costs (state save/restore) and isn't applicable to all resource types.

What's next:

Page Complete

3 / 5