Breaking No Preemption

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.
 */

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)
 */

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)
 */

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.
 */