osdev-process-scheduling

name	osdev-process-scheduling
description	Process management, context switching, and CPU scheduling for OS kernels. Task structures, ring transitions, SYSCALL/SYSRET, scheduler algorithms. Use when implementing multitasking, context switches, or schedulers.
origin	MCC

Process Scheduling and Multitasking

Complete reference for implementing multitasking in OS kernels: task control blocks, software context switching, system call mechanisms, ring transitions, and scheduler algorithms.

When to Use

• Implementing a task/process/thread structure for the first time
• Writing context switch code in assembly
• Setting up SYSCALL/SYSRET or INT 0x80 for system calls
• Transitioning from ring 0 to ring 3 to run user-mode code
• Choosing and implementing a scheduler algorithm
• Debugging triple faults or corruption during context switches

Task Structure

Every running thread needs a control block that stores its execution state when it is not running. The scheduler selects a task, the context switch loads its state, and the CPU resumes where it left off.

What a Task Control Block Contains

struct task {
    /* Identity */
    uint32_t pid;
    uint32_t tid;           /* thread ID within the process */
    char     name[32];

    /* CPU state (saved/restored on context switch) */
    uint64_t rsp;           /* kernel stack pointer (saved during switch) */
    uint64_t cr3;           /* page table root -- defines address space */

    /* Kernel stack */
    void    *kernel_stack;      /* base of this task's kernel stack */
    size_t   kernel_stack_size; /* typically 4KB-16KB */

    /* Scheduling */
    enum task_state state;  /* RUNNING, READY, BLOCKED, ZOMBIE */
    int      priority;
    uint64_t time_slice;    /* ticks remaining in current quantum */
    uint64_t total_runtime; /* for accounting and dynamic priority */

    /* Process linkage */
    struct task *parent;
    struct list_head children;
    struct list_head siblings;

    /* Scheduling queue link */
    struct list_head run_queue;

    /* FPU/SSE state (lazily saved) */
    uint8_t  fpu_state[512] __attribute__((aligned(16)));
    int      fpu_used;      /* has this task used FPU since last switch? */
};

Why Separate Kernel and User Stacks

Each task has two stacks: a user-mode stack (in user address space) and a kernel-mode stack (in kernel space).

Why this matters: When an interrupt or system call fires in user mode, the CPU needs a safe, trusted stack to push the saved state onto. If it used the user stack, a malicious program could set RSP to an invalid address and crash the kernel. The CPU loads RSP0 from the TSS (Task State Segment) on ring transitions, so each task must have its kernel stack address stored in the TSS before it runs.

Context Switching

A context switch saves the current task's CPU state and loads the next task's saved state. Because function calls and returns already save/restore RIP via the stack, a context switch mainly needs to swap the stack pointer -- when you return from the switch function on a different stack, you resume in the other task.

What Must Be Saved

On x86-64, the C calling convention already preserves some registers across function calls. A context switch implemented as a C-callable function only needs to save the callee-saved registers:

Register	Purpose
RBX, RBP, R12-R15	Callee-saved (C ABI) -- must be preserved
RSP	Stack pointer -- the core of the switch
CR3	Page table base -- only if switching address spaces
FS/GS base	Thread-local storage (if used)

Caller-saved registers (RAX, RCX, RDX, RSI, RDI, R8-R11) are already saved by the C compiler before calling the switch function.

Annotated x86-64 Context Switch

; void switch_to(struct task *prev, struct task *next)
; prev in RDI, next in RSI (System V ABI)
;
; Called as a normal function. When it returns, we are running
; on next's kernel stack, resuming wherever next last called switch_to.
global switch_to
switch_to:
    ; Save callee-saved registers on prev's kernel stack
    push rbp
    push rbx
    push r12
    push r13
    push r14
    push r15

    ; Save prev's stack pointer into prev->rsp
    mov [rdi + TASK_RSP_OFFSET], rsp

    ; Load next's stack pointer
    mov rsp, [rsi + TASK_RSP_OFFSET]

    ; Switch address space if CR3 differs
    mov rax, [rsi + TASK_CR3_OFFSET]
    mov rcx, cr3
    cmp rax, rcx
    je .no_cr3_switch
    mov cr3, rax           ; flushes TLB (non-global entries)
.no_cr3_switch:

    ; Update TSS.RSP0 so interrupts in user mode land on next's kernel stack
    mov rax, [rsi + TASK_KSTACK_TOP]
    mov [tss + TSS_RSP0_OFFSET], rax

    ; Restore callee-saved registers from next's kernel stack
    pop r15
    pop r14
    pop r13
    pop r12
    pop rbx
    pop rbp

    ; RET pops the return address from next's stack.
    ; We resume in whatever function next was in when it called switch_to.
    ret

Why this works: When a task was previously switched away from, it was inside switch_to, having pushed its callee-saved regs and a return address. Loading its RSP puts us at exactly that point. Popping the registers and executing RET resumes it seamlessly.

FPU/SSE State (Lazy Switching)

Saving and restoring 512+ bytes of FPU/SSE state on every context switch is expensive. Instead, use lazy switching:

1. On each context switch, set CR0.TS (Task Switched) bit
2. When a task executes an FPU/SSE instruction, the CPU raises a #NM (Device Not Available) exception
3. In the #NM handler: save the previous task's FPU state, load the current task's FPU state, clear CR0.TS
4. If a task never uses FPU, its state is never saved/restored

See references/context-switch-x86.md for 32-bit context switch code and detailed stack frame layouts.

System Call Mechanisms

System calls allow user-mode code to request kernel services. The CPU must transition from ring 3 to ring 0 safely.

INT 0x80 (Legacy, 32-bit)

The traditional approach: user code puts the syscall number in EAX, arguments in EBX, ECX, EDX, ESI, EDI, EBP, then executes int 0x80. The CPU pushes SS, ESP, EFLAGS, CS, EIP onto the kernel stack (loaded from TSS) and jumps to the IDT entry for vector 0x80.

Cost: ~100+ cycles for the interrupt mechanism alone (privilege check, stack switch, IDT lookup, pipeline flush).

SYSCALL/SYSRET (Fast, 64-bit)

Modern x86-64 uses the SYSCALL instruction, which avoids the IDT entirely. It is faster because it does minimal state saving and does not load a new stack.

What SYSCALL does (hardware):

1. RCX = RIP (return address saved in register, not on stack)
2. R11 = RFLAGS (flags saved in register)
3. RFLAGS &= ~FMASK (mask out specified flags, typically IF and DF)
4. RIP = LSTAR (kernel entry point loaded from MSR)
5. CS = STAR[47:32] (kernel code segment from MSR)
6. SS = STAR[47:32] + 8 (kernel data segment)

What SYSCALL does NOT do: It does not switch RSP. The kernel stack is NOT loaded. You are still on the user stack when the kernel entry point executes. This is the critical difference from INT -- you must load the kernel stack yourself.

Setting Up SYSCALL on x86-64

#define MSR_STAR   0xC0000081
#define MSR_LSTAR  0xC0000082
#define MSR_FMASK  0xC0000084

void syscall_init(void) {
    /* STAR: bits 47:32 = kernel CS, bits 63:48 = user CS (base for SYSRET) */
    /* Kernel CS = 0x08, Kernel DS = 0x10 (CS+8) */
    /* User CS = 0x1B (0x18|3), User DS = 0x23 (0x20|3) */
    /* SYSRET loads CS from STAR[63:48]+16 and SS from STAR[63:48]+8 */
    uint64_t star = ((uint64_t)0x0013 << 48) | ((uint64_t)0x0008 << 32);
    wrmsr(MSR_STAR, star);

    /* LSTAR: kernel entry point for SYSCALL */
    wrmsr(MSR_LSTAR, (uint64_t)syscall_entry);

    /* FMASK: clear IF (bit 9) and DF (bit 10) on SYSCALL */
    wrmsr(MSR_FMASK, (1 << 9) | (1 << 10));

    /* Enable SYSCALL/SYSRET by setting SCE in EFER */
    uint64_t efer = rdmsr(0xC0000080);
    wrmsr(0xC0000080, efer | 1);
}

SYSCALL Entry Assembly

; Entry point: user RSP still loaded, RCX=return RIP, R11=return RFLAGS
global syscall_entry
syscall_entry:
    ; CRITICAL: we are on the user stack here. Cannot push anything safely.

    ; Swap to kernel stack using swapgs to access per-CPU data
    swapgs                          ; GS base now points to per-CPU struct
    mov [gs:PCPU_USER_RSP], rsp     ; save user RSP in per-CPU area
    mov rsp, [gs:PCPU_KERNEL_RSP]   ; load kernel RSP from per-CPU area

    ; Now on kernel stack. Build a trap frame.
    push qword [gs:PCPU_USER_RSP]   ; user RSP
    push r11                         ; user RFLAGS (saved by SYSCALL in R11)
    push rcx                         ; user RIP (saved by SYSCALL in RCX)

    ; Save callee-saved registers and syscall args
    push rbp
    push rbx
    push r12
    push r13
    push r14
    push r15

    ; RAX = syscall number, RDI/RSI/RDX/R10/R8/R9 = arguments
    ; (Note: R10 replaces RCX because SYSCALL clobbers RCX)
    mov rcx, r10                     ; Restore 4th arg to RCX for C calling convention
    mov rdi, rsp                     ; pass pointer to saved regs to C handler
    call syscall_dispatch            ; C function handles the syscall

    ; Restore registers
    pop r15
    pop r14
    pop r13
    pop r12
    pop rbx
    pop rbp

    pop rcx                          ; user RIP -> RCX for SYSRET
    pop r11                          ; user RFLAGS -> R11 for SYSRET
    pop rsp                          ; user RSP

    swapgs                           ; restore user GS base
    sysretq                          ; return to user mode

See references/syscall-mechanisms.md for INT 0x80, SYSENTER/SYSEXIT, ARM SVC, and a comparison table.

Ring Transitions

Ring 3 to Ring 0 (User to Kernel)

Triggered by interrupt, exception, or SYSCALL:

• Via interrupt/exception: CPU reads the IDT entry, loads CS:RIP from it, loads RSP0 from TSS, pushes (SS, RSP, RFLAGS, CS, RIP) onto the new kernel stack, optionally pushes error code
• Via SYSCALL: CPU sets RIP from LSTAR, saves return address in RCX and flags in R11. No stack switch -- kernel code must do it manually

The TSS must have the current task's kernel stack address in RSP0 before user code runs. Update it on every context switch.

Ring 0 to Ring 3 (Kernel to User)

To enter user mode (first process launch or return from syscall/interrupt), build an interrupt return frame on the kernel stack and execute IRETQ:

; Prepare to jump to user mode
enter_usermode:
    ; Build the iret frame (pushed in reverse order of how IRET pops)
    push qword 0x23        ; SS (user data segment, RPL=3)
    push qword user_rsp    ; RSP (user stack pointer)
    push qword 0x202       ; RFLAGS (IF=1, reserved bit 1=1)
    push qword 0x1B        ; CS (user code segment, RPL=3)
    push qword user_rip    ; RIP (entry point)
    iretq                  ; pops all five and switches to ring 3

Why IRETQ: It is the only instruction that atomically loads CS (which sets the privilege level), RIP, RFLAGS, SS, and RSP. SYSRETQ is faster but has constraints (cannot change IOPL, must go to user mode specifically).

Scheduler Algorithms

The scheduler decides which ready task runs next. It is invoked on every timer tick (preemptive) or when a task yields/blocks.

Algorithm Comparison

Algorithm	Complexity	Fairness	Priority Support	Best For
Round Robin	O(1)	Equal time for all	None	Simple kernels, learning
Priority Queue	O(1) with bitmask	Weighted by priority	Static	Real-time, embedded
Multilevel Feedback Queue	O(1)	Adaptive	Dynamic	General-purpose OS
O(1) Scheduler	O(1)	Fair with nice values	Dynamic	Linux 2.6-era production
CFS (Completely Fair Scheduler)	O(log n)	Proportionally fair	Weight-based	Linux mainline

Round Robin

All tasks share a single queue. Each gets a fixed time quantum (typically 20-50ms). On timer tick, decrement the running task's quantum. When it hits zero, move it to the back of the queue and switch to the front.

void schedule(void) {
    struct task *current = get_current_task();
    struct task *next;

    current->time_slice--;
    if (current->time_slice > 0 && current->state == RUNNING)
        return;  /* still has time left */

    /* Move current to back of run queue */
    if (current->state == RUNNING) {
        current->state = READY;
        current->time_slice = DEFAULT_QUANTUM;
        list_move_tail(&current->run_queue, &ready_queue);
    }

    /* Pick the next ready task */
    next = list_first_entry(&ready_queue, struct task, run_queue);
    next->state = RUNNING;

    if (next != current)
        switch_to(current, next);
}

Priority Queue with Bitmask

Maintain N priority levels, each with its own run queue. A bitmask tracks which levels have runnable tasks. Finding the highest-priority non-empty queue is O(1) with __builtin_clz (count leading zeros).

#define NUM_PRIORITIES 32

struct {
    struct list_head queues[NUM_PRIORITIES];
    uint32_t bitmap;  /* bit i set if queues[i] is non-empty */
} scheduler;

struct task *pick_next(void) {
    if (scheduler.bitmap == 0)
        return idle_task;

    int highest = 31 - __builtin_clz(scheduler.bitmap);
    struct task *next = list_first_entry(&scheduler.queues[highest],
                                          struct task, run_queue);
    list_del(&next->run_queue);
    if (list_empty(&scheduler.queues[highest]))
        scheduler.bitmap &= ~(1U << highest);

    return next;
}

Multilevel Feedback Queue (MLFQ)

Combines priority scheduling with dynamic adjustment:

1. New tasks start at the highest priority
2. If a task uses its entire quantum (CPU-bound), demote it one level
3. If a task blocks before its quantum expires (I/O-bound), keep it at current level or promote it
4. Periodically boost all tasks to the highest level to prevent starvation

Why MLFQ: It automatically separates interactive tasks (I/O-bound, stay at high priority) from batch tasks (CPU-bound, sink to low priority) without the administrator assigning static priorities.

O(1) Scheduler Concept

Two arrays of priority queues: active and expired. Tasks are always dequeued from active. When a task exhausts its timeslice, it is moved to expired with a recalculated priority. When active is empty, swap the pointers.

This gives O(1) scheduling decisions regardless of the number of tasks, because finding the highest-priority queue uses a bitmask scan and dequeueing is a list pop.

Common Pitfalls

1. Forgetting to update TSS.RSP0. Every context switch must write the next task's kernel stack top into the TSS. Without this, the next interrupt in user mode pushes state onto the wrong stack, corrupting another task.

2. SYSCALL does not load kernel RSP. Unlike INT, SYSCALL leaves the user stack loaded. Pushing anything before switching to the kernel stack writes to user memory. Use swapgs + per-CPU storage to load the kernel stack.

3. Not saving/restoring CR3. If tasks share the same address space (kernel threads), this is fine. If they have different page tables, forgetting CR3 means the new task runs with the old task's mappings.

4. Stack overflow in kernel stack. Kernel stacks are small (4-16KB). Deep call chains or large local variables can overflow into adjacent memory. Use guard pages (unmapped page below the stack) to catch this as a page fault instead of silent corruption.

5. Interrupts during context switch. If a timer interrupt fires while you are in the middle of switch_to, the interrupt handler may try to schedule again, corrupting the half-saved state. Disable interrupts during the critical section of the context switch.

6. SYSRET with non-canonical RCX. On Intel CPUs, SYSRETQ checks RCX for canonical-ness in ring 0 but the General Protection Fault fires in ring 3. If RCX contains a non-canonical address, the #GP occurs with user-mode CS but kernel-mode RSP -- a privilege escalation. Validate RCX before SYSRETQ or use IRETQ for untrusted return addresses.

7. Priority inversion. A high-priority task waits on a lock held by a low-priority task, while a medium-priority task runs indefinitely. Solutions: priority inheritance (temporarily boost the lock holder) or priority ceiling.

Related Skills

• osdev-paging -- virtual memory and page tables (CR3, address space setup)
• osdev-memory-management -- physical frame allocator, kernel heap for task struct allocation
• osdev-interrupts -- IDT setup, timer interrupt for preemptive scheduling
• osdev-toolchain -- cross-compiler setup, linker scripts, QEMU debugging