Chapter 22: Schedulers

22.1 What is a Scheduler?

The scheduler is the component of the kernel that decides which process runs next on the CPU. On a single-core system, only one process can run at a time. The scheduler divides CPU time among all processes, giving each one a fair share.

The scheduler runs in two situations:

• Preemptive scheduling: triggered by the timer interrupt (typically every 1-10 ms). The interrupt handler calls the scheduler, which may switch to a different process.
• Voluntary scheduling: a process calls yield() or blocks on I/O, voluntarily giving up the CPU.

22.2 Scheduling Policies

Policy	Description	Complexity
First-In-First-Out	Run each process until it blocks or exits	O(1)
Round Robin	Each process runs for a fixed time slice, then cycles to the next	O(1) enqueue, O(n) pick
Priority-based	Higher-priority processes run before lower-priority ones	O(1) with priority queues
Multi-Level Feedback	Multiple queues with different priorities; processes move between queues	O(1)
O(1) Scheduler	Two priority arrays (active/expired), O(1) selection	O(1)
Completely Fair Scheduler	Red-black tree of processes sorted by virtual runtime	O(log n)

22.3 Round Robin Scheduler

A round-robin scheduler is the simplest practical scheduler. Each process gets a fixed time slice (quantum). When the timer interrupt fires, the kernel switches to the next process in the ready queue.

/* Ready queue (circular linked list of runnable processes) */
struct pcb *ready_queue = NULL;
int process_count = 0;

/* Add a process to the ready queue */
void scheduler_enqueue(struct pcb *pcb) {
    if (!ready_queue) {
        ready_queue = pcb;
        pcb->next_ready = pcb;
    } else {
        pcb->next_ready = ready_queue->next_ready;
        ready_queue->next_ready = pcb;
    }
    process_count++;
}

/* Remove a process from the ready queue */
void scheduler_dequeue(struct pcb *pcb) {
    /* Find predecessor and link around pcb */
    struct pcb *prev = ready_queue;
    while (prev->next_ready != pcb) prev = prev->next_ready;
    prev->next_ready = pcb->next_ready;
    if (pcb == ready_queue) {
        ready_queue = (pcb == pcb->next_ready) ? NULL : pcb->next_ready;
    }
    pcb->next_ready = NULL;
    process_count--;
}

/* Pick the next process to run */
struct pcb *scheduler_pick_next(void) {
    if (!ready_queue) return NULL;
    ready_queue = ready_queue->next_ready;  /* advance to next */
    return ready_queue;
}

22.4 Timer Interrupt and Preemption

The timer interrupt (Chapter 12) is the heartbeat of the scheduler. Every time the system timer fires (e.g., every 1 ms), the interrupt handler calls the scheduler.

/* Timer interrupt handler (called from interrupt dispatcher) */
void timer_tick_handler(void) {
    struct pcb *current = get_current_process();

    /* Check if current process has exhausted its quantum */
    current->ticks_remaining--;
    if (current->ticks_remaining > 0 && !current->need_resched) {
        return;  /* Quantum not exhausted, let it keep running */
    }

    /* Reset quantum */
    current->ticks_remaining = TIME_SLICE_TICKS;
    current->need_resched = 0;

    /* Signal that a reschedule is needed on return from interrupt */
    need_reschedule = 1;
}

/* Return from interrupt: check if we should reschedule */
void irq_return(void) {
    if (need_reschedule) {
        need_reschedule = 0;
        struct pcb *next = scheduler_pick_next();
        if (next && next != get_current_process()) {
            switch_to_process(next);
        }
    }
    /* ERET to the process */
    asm volatile("eret");
}

22.5 Process States

The scheduler tracks four process states:

enum process_state {
    PROCESS_RUNNING,     /* Currently executing on CPU */
    PROCESS_READY,       /* Could run, waiting for CPU */
    PROCESS_BLOCKED,     /* Waiting for I/O or a lock */
    PROCESS_ZOMBIE       /* Exited, waiting for parent to collect exit code */
};

Only READY processes are in the scheduler's ready queue. BLOCKED processes are moved to a wait queue. When the blocking condition resolves (e.g., I/O completes, lock acquired), the process is moved back to READY and re-enqueued.

22.6 Context Switch Flow

The full context switch sequence (building on Chapter 13):

/* Complete context switch with scheduler involvement */
void switch_to_process(struct pcb *next) {
    struct pcb *prev = get_current_process();

    /* Update state */
    prev->state = PROCESS_READY;
    next->state = PROCESS_RUNNING;

    /* Switch page tables */
    switch_page_table(next->page_table);

    /* Switch to next process's stack and restore registers */
    switch_context(&prev->context, &next->context);
}

22.7 Our Implementation

Our kernel uses a multi-level feedback queue with 3 priority levels:

• Priority 0 (highest): interactive processes (short time slice, 2 ms)
• Priority 1: normal processes (default time slice, 10 ms)
• Priority 2 (lowest): batch processes (long time slice, 50 ms)

Each priority level has its own round-robin queue. A process that uses its full time slice without blocking is demoted to a lower priority. A process that blocks frequently (I/O-bound) is promoted to a higher priority. This ensures interactive processes get responsive scheduling while CPU-bound processes don't starve interactive ones.

The scheduler is initialized in scheduler_init(), which sets up the timer interrupt at 1 ms interval and creates the idle process (a process that runs when nothing else is ready). The idle process halts the CPU with WFI to save power.

22.8 Exercises

22.9 Summary

The scheduler determines which process runs next and for how long. Round-robin scheduling is simple and fair, giving each process an equal time slice. The timer interrupt triggers preemptive scheduling, allowing the kernel to switch between processes transparently. Our kernel uses a multi-level feedback queue with priority promotion/demotion to balance responsiveness and throughput. The idle process runs when no other process is ready, using WFI to conserve power.