Context Switching: The Heart of Multitasking

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

/**
 * Simplified timer interrupt handler (Linux style)
 * 
 * This handler is invoked HZ times per second (typically 100-1000).
 * It handles timekeeping, process accounting, and preemption.
 */
void timer_interrupt_handler(struct pt_regs *regs)
{
    /* Update system time */
    jiffies++;  /* Global kernel tick counter */
    update_wall_time();
    
    /* Get current task */
    struct task_struct *current = get_current();
    
    /* Account CPU time to the current process */
    account_process_tick(current, user_mode(regs));
    
    /* Decrement time slice for the current process */
    if (current->time_slice > 0) {
        current->time_slice--;
    }
    
    /* Check if preemption is needed */
    if (current->time_slice == 0) {
        /* Time quantum exhausted - mark for reschedule */
        set_tsk_need_resched(current);
    }
    
    /* Also check for higher priority processes */
    if (higher_priority_task_runnable()) {
        set_tsk_need_resched(current);
    }
    
    /* Process timers (scheduled delayed work) */
    run_local_timers();
    
    /* Profile tick for performance monitoring */
    profile_tick(CPU_PROFILING);
}
 
/**
 * The actual context switch happens later, when returning
 * from the interrupt handler. The kernel checks the 
 * TIF_NEED_RESCHED flag and calls schedule() if set.
 */
void return_from_interrupt(struct pt_regs *regs)
{
    if (user_mode(regs)) {
        /* Returning to user space - check for pending work */
        if (test_thread_flag(TIF_NEED_RESCHED)) {
            schedule();  /* This performs the actual context switch */
        }
    }
}

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

/**
 * Example: How a blocking read() causes a context switch
 * 
 * This demonstrates the voluntary context switch pathway.
 */
#include <unistd.h>
#include <stdio.h>
#include <fcntl.h>
 
int main() {
    int fd = open("/dev/tty", O_RDONLY);
    char buffer[256];
    
    /*
     * This read() call may block:
     * 
     * 1. User calls read() - enters kernel via syscall
     * 2. Kernel checks: is there data in the tty input buffer?
     * 3. If NO data available:
     *    a. Set current process state to TASK_INTERRUPTIBLE
     *    b. Add process to tty wait queue
     *    c. Call schedule() to switch to another process
     *    d. (Current process now sleeps)
     * 4. Later, when data arrives:
     *    a. tty driver interrupt handler runs
     *    b. Data is placed in buffer
     *    c. Waiting process is woken (moved to Ready state)
     * 5. Eventually scheduler picks this process again
     * 6. read() copies data to user buffer and returns
     */
    ssize_t bytes = read(fd, buffer, sizeof(buffer));
    
    printf("Read %zd bytes
", bytes);
    close(fd);
    return 0;
}

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

/**
 * Example: How a device interrupt wakes a sleeping process
 * 
 * This is a simplified version of how network drivers wake
 * processes waiting on socket receive operations.
 */
 
/* Wait queue for processes waiting on this device */
DECLARE_WAIT_QUEUE_HEAD(device_wait_queue);
volatile int data_ready = 0;
 
/**
 * Device interrupt handler (Top Half)
 * Called when hardware asserts interrupt
 */
irqreturn_t device_interrupt_handler(int irq, void *dev_id)
{
    /* Acknowledge interrupt to hardware */
    write_register(DEVICE_ACK, 1);
    
    /* Read data from device into kernel buffer */
    int bytes = read_from_device(kernel_buffer, BUFFER_SIZE);
    
    if (bytes > 0) {
        /* Mark data as ready */
        data_ready = 1;
        
        /*
         * Wake up any processes sleeping on this wait queue.
         * 
         * wake_up_interruptible() does the following:
         * 1. Traverse the wait queue
         * 2. For each waiting task:
         *    a. Change state from TASK_INTERRUPTIBLE to TASK_RUNNING
         *    b. Add task to the run queue
         *    c. If task has higher priority than current, set TIF_NEED_RESCHED
         */
        wake_up_interruptible(&device_wait_queue);
    }
    
    return IRQ_HANDLED;
}
 
/**
 * User-facing read function (called from read() syscall handler)
 */
ssize_t device_read(struct file *filp, char __user *buf, 
                    size_t count, loff_t *ppos)
{
    /*
     * wait_event_interruptible() does the following:
     * 1. Check condition (data_ready)
     * 2. If false:
     *    a. Add current task to wait queue
     *    b. Set state to TASK_INTERRUPTIBLE
     *    c. Call schedule() -> CONTEXT SWITCH OUT
     *    d. (Later, when woken, continues from here)
     *    e. Remove self from wait queue
     *    f. Check condition again (loop back if still false)
     * 3. If true: proceed without blocking
     */
    if (wait_event_interruptible(device_wait_queue, data_ready)) {
        return -ERESTARTSYS;  /* Interrupted by signal */
    }
    
    /* Copy data to userspace */
    if (copy_to_user(buf, kernel_buffer, count)) {
        return -EFAULT;
    }
    
    data_ready = 0;
    return count;
}

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

/**
 * Simplified priority preemption check (Linux CFS style)
 * 
 * This logic runs when a new task becomes runnable.
 */
 
/**
 * Called when a task is woken up or becomes runnable
 */
void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags)
{
    struct task_struct *current_task = rq->curr;
    
    /*
     * Real-time tasks always preempt normal tasks.
     * This ensures RT tasks get immediate CPU access.
     */
    if (rt_task(p) && !rt_task(current_task)) {
        resched_curr(rq);  /* Mark current for preemption */
        return;
    }
    
    /*
     * For CFS (Completely Fair Scheduler):
     * Compare virtual runtimes. A task with less virtual runtime
     * has had "less than its fair share" and should preempt.
     */
    if (cfs_task(p) && cfs_task(current_task)) {
        if (p->vruntime + wakeup_preempt_threshold < current_task->vruntime) {
            /* New task is "more deserving" - preempt current */
            resched_curr(rq);
        }
    }
    
    /*
     * Note: resched_curr() sets TIF_NEED_RESCHED flag.
     * The actual context switch happens later, at a safe point.
     */
}
 
/**
 * resched_curr() - Mark the current task for rescheduling
 */
void resched_curr(struct rq *rq)
{
    struct task_struct *curr = rq->curr;
    
    /* Set the need-resched flag in the task's thread_info */
    set_tsk_need_resched(curr);
    
    /* On SMP systems, send an IPI if task is on another CPU */
    if (rq != this_rq()) {
        smp_send_reschedule(cpu_of(rq));
    }
}

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

/**
 * Example: Signal interrupting a blocking system call
 * 
 * This demonstrates how signals trigger context switches
 * and interrupt blocking operations.
 */
#include <signal.h>
#include <stdio.h>
#include <unistd.h>
#include <errno.h>
 
volatile sig_atomic_t got_signal = 0;
 
void signal_handler(int signo) {
    got_signal = 1;
    /* Handler runs in the context of the process that 
     * was interrupted - after it was woken and scheduled */
}
 
int main() {
    /* Set up signal handler for SIGUSR1 */
    struct sigaction sa = {
        .sa_handler = signal_handler,
        .sa_flags = 0  /* No SA_RESTART - syscall returns EINTR */
    };
    sigaction(SIGUSR1, &sa, NULL);
    
    printf("PID: %d - sleeping...
", getpid());
    
    /*
     * sleep() puts the process in TASK_INTERRUPTIBLE state.
     * 
     * If SIGUSR1 is sent to this process:
     * 1. Kernel checks signal pending mask
     * 2. Process is moved from Waiting to Ready (context switch IN)
     * 3. sleep() detects signal pending
     * 4. Before returning to userspace, kernel invokes signal handler
     * 5. sleep() returns early with remaining time (or EINTR if nanosleep)
     */
    unsigned int remaining = sleep(3600);  /* Request 1 hour sleep */
    
    if (got_signal) {
        printf("Woken by signal! Slept for %u seconds
", 
               3600 - remaining);
    }
    
    return 0;
}
 
/*
 * To test: In another terminal, run:
 *   kill -SIGUSR1 <pid>
 * 
 * The sleeping process will wake immediately:
 * - Context switch from whatever was running to this process
 * - Signal handler executes
 * - sleep() returns early
 */

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

/**
 * Example: Using sched_yield() for spin-wait optimization
 * 
 * This pattern is used when you must poll but want to be 
 * courteous to other processes. Modern locks (like futex)
 * are typically preferred.
 */
#include <sched.h>
#include <stdatomic.h>
 
atomic_int shared_flag = 0;
 
void wait_for_flag(void) {
    int spin_count = 0;
    
    while (atomic_load(&shared_flag) == 0) {
        spin_count++;
        
        /*
         * After spinning a few times, yield to let other 
         * processes run. This prevents this process from
         * consuming 100% CPU while waiting.
         * 
         * sched_yield() causes:
         * 1. Immediate transition from Running to Ready
         * 2. Scheduler selects next process
         * 3. Context switch to that process
         * 4. This process re-enters the run queue
         * 
         * Note: No guarantee about WHICH process runs next
         * or WHEN this process will be scheduled again.
         */
        if (spin_count > 100) {
            sched_yield();
            spin_count = 0;
        }
        
        /* Optional: CPU relax instruction for hyperthreading */
        __asm__ __volatile__("pause");
    }
}
 
void set_flag(void) {
    atomic_store(&shared_flag, 1);
}
 
/*
 * Better alternative: Use proper synchronization primitives
 * 
 * pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
 * pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
 * 
 * void wait_for_flag_better(void) {
 *     pthread_mutex_lock(&mutex);
 *     while (shared_flag == 0) {
 *         pthread_cond_wait(&cond, &mutex);  // Proper blocking
 *     }
 *     pthread_mutex_unlock(&mutex);
 * }
 */