Preemptive vs Non-Preemptive Scheduling: Complete Guide to CPU Scheduling in Operating Systems

Process Arrival Time | Burst Time | Completion Time | Turnaround Time | Waiting Time
P1      0            | 8          | 8               | 8               | 0
P2      1            | 4          | 12              | 11              | 7
P3      2            | 9          | 21              | 19              | 10
P4      3            | 5          | 26              | 23              | 18

Average Turnaround Time: (8 + 11 + 19 + 23) / 4 = 15.25 ms
Average Waiting Time: (0 + 7 + 10 + 18) / 4 = 8.75 ms

Process Burst Time | Execution Order | Completion Time | Turnaround Time | Waiting Time
P1      6          | 3rd            | 16              | 16              | 10
P2      8          | 4th            | 24              | 24              | 16
P3      7          | 2nd            | 10              | 10              | 3
P4      3          | 1st            | 3               | 3               | 0

Average Turnaround Time: (16 + 24 + 10 + 3) / 4 = 13.25 ms
Average Waiting Time: (10 + 16 + 3 + 0) / 4 = 7.25 ms

// Simplified context switch representation
struct process_context {
    int registers[16];
    int program_counter;
    int stack_pointer;
    int process_id;
    int priority;
    int state;
};

void context_switch(struct process_context *old_process, 
                   struct process_context *new_process) {
    // Save current process state
    save_registers(old_process->registers);
    old_process->program_counter = get_program_counter();
    old_process->stack_pointer = get_stack_pointer();
    
    // Load new process state
    load_registers(new_process->registers);
    set_program_counter(new_process->program_counter);
    set_stack_pointer(new_process->stack_pointer);
    
    // Update process states
    old_process->state = READY;
    new_process->state = RUNNING;
}

Time Quantum: 3 ms

Process | Burst Time | Execution Timeline | Completion Time | Turnaround Time
P1      | 9         | 0-3, 9-12, 15-18  | 18              | 18
P2      | 6         | 3-6, 12-15        | 15              | 15  
P3      | 3         | 6-9               | 9               | 9

Average Turnaround Time: (18 + 15 + 9) / 3 = 14 ms
Context Switches: 5

Process | Arrival Time | Burst Time | Start Time | Completion Time | Turnaround
P1      | 0           | 8          | 0          | 17              | 17
P2      | 1           | 4          | 1          | 5               | 4
P3      | 2           | 9          | 17         | 26              | 24
P4      | 3           | 5          | 5          | 10              | 7

Execution Order: P1(0-1) → P2(1-5) → P4(5-10) → P1(10-17) → P3(17-26)
Average Turnaround Time: (17 + 4 + 24 + 7) / 4 = 13 ms

Workload Mix: 1 CPU-intensive process (100ms) + 4 I/O-intensive processes (5ms each)

Non-Preemptive FCFS:
- CPU process executes first: 0-100ms
- I/O processes wait: 100ms, 105ms, 110ms, 115ms
- Average response time: (0 + 100 + 105 + 110 + 115) / 5 = 86ms

Preemptive Round Robin (Quantum = 10ms):
- All processes get CPU time within first 50ms
- Average response time: (0 + 10 + 20 + 30 + 40) / 5 = 20ms
- 76% improvement in response time

// Typical context switch times on different architectures
Architecture    | Context Switch Time | Memory Access Impact
x86-64         | 2-5 microseconds    | L1 cache pollution
ARM Cortex-A   | 1-3 microseconds    | TLB flush required  
RISC-V         | 1-4 microseconds    | Pipeline stall

// Impact on system with 1000 context switches per second
Total overhead = 1000 × 3μs = 3ms per second = 0.3% CPU utilization

# Example: Scientific computation batch job
#!/bin/bash
# Non-preemptive environment optimal for:
./large_matrix_multiplication input.dat > output.dat
./monte_carlo_simulation 1000000 > results.dat
./data_analysis_pipeline results.dat > final_report.dat

# Example: Web server handling multiple requests
import threading
import time

def handle_request(request_id, processing_time):
    """Simulate request processing with preemptive scheduling"""
    print(f"Request {request_id} started at {time.time():.2f}")
    
    # Simulate processing with potential preemption
    for chunk in range(processing_time):
        time.sleep(0.1)  # Allows OS to preempt if needed
        print(f"Request {request_id} chunk {chunk} completed")
    
    print(f"Request {request_id} finished at {time.time():.2f}")

# Multiple concurrent requests benefit from preemptive scheduling
threads = []
for i in range(5):
    thread = threading.Thread(target=handle_request, args=(i, 10))
    threads.append(thread)
    thread.start()

for thread in threads:
    thread.join()

// Simplified CFS concept
struct task_struct {
    u64 vruntime;           // Virtual runtime
    int nice;               // Process priority
    struct sched_entity se; // Scheduling entity
};

// CFS selection algorithm (simplified)
struct task_struct *pick_next_task_fair(struct rq *rq) {
    struct sched_entity *se = __pick_first_entity(&rq->cfs);
    return task_of(se); // Return task with lowest vruntime
}

Process Classification for Hybrid Scheduling:

CPU-Bound Processes:
- Longer time quantum (non-preemptive behavior)
- Lower context switching frequency
- Examples: Compilers, mathematical computations

I/O-Bound Processes:
- Shorter time quantum (preemptive behavior)
- Higher responsiveness priority
- Examples: Text editors, web browsers

Real-Time Processes:
- Strict deadline-based scheduling
- Preemptive with priority inheritance
- Examples: Audio/video streaming, control systems

// Priority Inheritance Protocol Implementation
void acquire_mutex(mutex_t *mutex, task_t *task) {
    if (mutex->owner && mutex->owner->priority < task->priority) {
        // Temporarily boost mutex owner's priority
        mutex->owner->inherited_priority = task->priority;
        reschedule_task(mutex->owner);
    }
    
    // Standard mutex acquisition
    lock_mutex(mutex, task);
}

void release_mutex(mutex_t *mutex, task_t *task) {
    // Restore original priority
    if (task->inherited_priority > task->base_priority) {
        task->inherited_priority = task->base_priority;
    }
    
    unlock_mutex(mutex);
    schedule(); // Trigger rescheduling
}

# Linux CPU affinity example
# Bind process to specific CPU cores to reduce context switch overhead
taskset -c 0,1 ./cpu_intensive_task
taskset -c 2,3 ./another_cpu_task

# Check current CPU affinity
taskset -p [process_id]

# Set CPU affinity for running process
taskset -cp 0-3 [process_id]

# Monitor context switches per second
sar -w 1 10

# View detailed process scheduling information
cat /proc/[pid]/sched

# Monitor CPU usage by process
top -p [pid] -d 1

# Analyze scheduler latency
perf record -e sched:sched_switch ./your_program
perf report

# Check current scheduling policy
chrt -p [pid]

# Set real-time scheduling policy
chrt -f -p 99 [pid]  # FIFO with priority 99
chrt -r -p 50 [pid]  # Round Robin with priority 50