From Timer Tick to Task Switch: A Preemptive x86-64 Kernel Scheduler

A kernel becomes much more interesting when two tasks can make progress without explicitly taking turns. That is the job of preemption: a timer interrupts the running task, the kernel saves its execution state, and the scheduler chooses what should run next.

The scheduling policy can be simple. The mechanism cannot be vague. A reliable first implementation needs a precise agreement between the interrupt stub, the C scheduler, and every task's kernel stack.

This article builds that agreement for a small x86-64 kernel using:

• one CPU;
• kernel threads running at privilege level 0;
• a periodic timer interrupt;
• a round-robin run queue;
• one kernel stack per task;
• no floating-point or vector instructions in kernel code.

Those limits are deliberate. They expose the essential context-switch path without mixing in address-space changes, user-mode transitions, or multiprocessor synchronization. Each of those features can be added once the basic invariant is solid.

The invariant that makes switching possible

At any instant, a task is in one of two forms:

1. It is running, so its register state is live in the CPU.
2. It is suspended, so its complete resumable state begins at task->saved_rsp on its kernel stack.

For this design, saved_rsp points to a stack image that the interrupt exit code can consume directly. Restoring a task therefore means changing rsp, popping general-purpose registers, and executing iretq.

                  high addresses
              +-------------------+
              | thread stack data |
              +-------------------+
              | RFLAGS            |  pushed by CPU
              | CS                |  pushed by CPU
              | RIP               |  pushed by CPU
              | RAX               |  pushed by stub
              | RBX               |
              | ...               |
saved_rsp --> | R15               |
              +-------------------+
                  low addresses

The scheduler does not copy this frame into a task structure. It records the stack pointer. This keeps the interrupt path small and makes an old task and a newly created task look identical to the restore code.

What the processor saves—and what it does not

When an interrupt gate fires while the CPU is already in privilege level 0, x86-64 pushes three values:

• the interrupted instruction pointer (RIP);
• the code-segment selector (CS);
• the flags register (RFLAGS).

It does not automatically save the general-purpose registers. It also does not push the old RSP and SS unless the interrupt crosses privilege levels. Our timer stub must save every general-purpose register that an interrupted C function could have been using.

Use an interrupt gate rather than a trap gate for the timer so the processor clears the interrupt-enable flag on entry. That prevents another maskable timer interrupt from nesting inside the switch path before the kernel is ready for it.

Exceptions are a separate concern. Some exceptions push an error code and others do not, so shared exception stubs usually normalize their frames. The timer interrupt has no error code; do not silently reuse this exact layout for faults.

Define the stack frame in C

The C structure must match the assembly push order byte for byte. If the stub pushes rax first and r15 last, the final stack pointer points at r15:

#include <stdint.h>

struct interrupt_frame {
    uint64_t r15;
    uint64_t r14;
    uint64_t r13;
    uint64_t r12;
    uint64_t r11;
    uint64_t r10;
    uint64_t r9;
    uint64_t r8;
    uint64_t rbp;
    uint64_t rdi;
    uint64_t rsi;
    uint64_t rdx;
    uint64_t rcx;
    uint64_t rbx;
    uint64_t rax;
    uint64_t rip;
    uint64_t cs;
    uint64_t rflags;
};

_Static_assert(sizeof(struct interrupt_frame) == 18 * 8,
               "interrupt frame layout changed");

Field order is part of the architecture-facing interface. Treat changes to this structure like changes to an on-disk format: update both sides and verify the offsets.

Save on one stack and restore from another

The timer entry stub saves registers, passes the resulting stack pointer to C, and receives the stack pointer that should be restored. NASM syntax makes the core mechanism compact:

bits 64

global timer_interrupt_entry
extern schedule_from_tick

timer_interrupt_entry:
    cld

    push rax
    push rbx
    push rcx
    push rdx
    push rsi
    push rdi
    push rbp
    push r8
    push r9
    push r10
    push r11
    push r12
    push r13
    push r14
    push r15

    ; The saved frame begins at the current RSP.
    mov rdi, rsp

    ; An interrupt can arrive at any instruction, so the interrupted
    ; stack alignment is not a safe C ABI assumption. Align downward
    ; for the call. The saved frame itself remains untouched above it.
    and rsp, -16
    call schedule_from_tick

    ; RAX is either the old frame or another task's saved frame.
    mov rsp, rax

    pop r15
    pop r14
    pop r13
    pop r12
    pop r11
    pop r10
    pop r9
    pop r8
    pop rbp
    pop rdi
    pop rsi
    pop rdx
    pop rcx
    pop rbx
    pop rax
    iretq

The unusual line is mov rsp, rax. Everything before it runs on the interrupted task's stack. Everything after it may run on a different task's stack.

The C scheduler returns normally before the stack changes. Its ret still consumes the return address created by call schedule_from_tick. Only then does the assembly replace rsp. This avoids trying to return through a call frame belonging to another task.

Compile all interruptible kernel C code with the red zone disabled. The x86-64 System V ABI normally allows leaf functions to use 128 bytes below rsp without moving the stack pointer, but an interrupt frame would overwrite that area. A typical kernel flag is:

-mno-red-zone

For the first implementation, also prevent the compiler from emitting floating-point or vector instructions in kernel code. Saving only general-purpose registers is correct only while the kernel obeys that restriction.

Represent tasks and the run queue

A minimal task structure needs a saved stack pointer, scheduling state, and links for the run queue:

enum task_state {
    TASK_RUNNING,
    TASK_RUNNABLE,
    TASK_BLOCKED,
    TASK_DEAD
};

struct task {
    uint64_t *saved_rsp;
    void *stack_base;
    enum task_state state;
    unsigned ticks_left;
    unsigned preempt_count;
    bool need_reschedule;
    struct task *next;
    const char *name;
};

static struct task *current_task;
static struct task *idle_task;

A circular list is sufficient for round-robin selection. Starting after the current task, scan until a runnable entry is found. If none exists, return the idle task. The idle task must always be valid and should halt the processor until the next interrupt instead of spinning at full speed.

static struct task *pick_next_runnable(struct task *current)
{
    struct task *candidate = current->next;

    while (candidate != current) {
        if (candidate->state == TASK_RUNNABLE)
            return candidate;
        candidate = candidate->next;
    }

    if (current->state == TASK_RUNNING)
        return current;

    return idle_task;
}

The exact list policy matters less than its invariants. Every live task must appear at most once, blocked tasks must never be selected, and the scheduler must always have a valid fallback.

Turn timer ticks into time slices

Suppose the timer fires 100 times per second and each task receives five ticks. The nominal quantum is 50 milliseconds. Keep timer frequency and quantum length as separate settings; a later timer change should not silently alter scheduling policy.

The tick handler stores the interrupted frame, charges the running task, chooses a successor when the slice expires, acknowledges the interrupt controller, and returns a stack pointer:

#define DEFAULT_QUANTUM_TICKS 5

extern void timer_acknowledge(void);

uint64_t *schedule_from_tick(uint64_t *interrupted_rsp)
{
    struct task *old = current_task;
    old->saved_rsp = interrupted_rsp;

    if (old->ticks_left > 0)
        old->ticks_left--;

    if (old->ticks_left > 0) {
        timer_acknowledge();
        return interrupted_rsp;
    }

    if (old->preempt_count != 0) {
        old->need_reschedule = true;
        timer_acknowledge();
        return interrupted_rsp;
    }

    struct task *next = pick_next_runnable(old);

    if (next != old) {
        old->state = TASK_RUNNABLE;
        next->state = TASK_RUNNING;
        current_task = next;
    }

    current_task->ticks_left = DEFAULT_QUANTUM_TICKS;
    current_task->need_reschedule = false;

    timer_acknowledge();
    return current_task->saved_rsp;
}

The timer acknowledgement belongs on every return path. For a legacy interrupt controller this may be an end-of-interrupt command; for a local APIC it is an EOI write. Hide that difference behind one timer-controller interface.

Do not allocate memory, print to a slow console, or wait for another subsystem inside this path. Interrupts are disabled and the scheduler owns delicate state. Keep the critical section short and make diagnostics write to a bounded in-memory trace buffer.

Construct the first frame for a new thread

An existing task acquires a restorable frame by being interrupted. A new task has never run, so the kernel must build that frame by hand.

Place an empty interrupt_frame at the top of the allocated kernel stack. Set its instruction pointer to a bootstrap function, its code segment to the kernel code selector, and its flags to a valid initial value. Two preserved registers can carry the entry function and argument into the bootstrap code.

#include <stddef.h>
#include <string.h>

#define KERNEL_CS 0x08

typedef void (*thread_entry_t)(void *argument);

extern void thread_bootstrap(void);

static void prepare_new_thread(struct task *task,
                               void *stack_base,
                               size_t stack_size,
                               thread_entry_t entry,
                               void *argument)
{
    uintptr_t top = (uintptr_t)stack_base + stack_size;
    top &= ~(uintptr_t)0x0f;

    struct interrupt_frame *frame =
        (struct interrupt_frame *)(top - sizeof(*frame));

    memset(frame, 0, sizeof(*frame));
    frame->r12 = (uintptr_t)entry;
    frame->r13 = (uintptr_t)argument;
    frame->rip = (uintptr_t)thread_bootstrap;
    frame->cs = KERNEL_CS;
    frame->rflags = 0x202; /* reserved bit set, interrupts enabled */

    task->saved_rsp = (uint64_t *)frame;
    task->stack_base = stack_base;
    task->state = TASK_RUNNABLE;
    task->ticks_left = DEFAULT_QUANTUM_TICKS;
    task->preempt_count = 0;
    task->need_reschedule = false;
}

The bootstrap function converts those saved registers into a normal C call. A thread must never return into uninitialized stack data, so its exit path is explicit:

global thread_bootstrap
extern thread_exit

thread_bootstrap:
    mov rdi, r13        ; first C argument
    call r12            ; thread entry function

    mov rdi, rax        ; optional exit status
    call thread_exit

.unexpected_return:
    cli
    hlt
    jmp .unexpected_return

When this task is selected for the first time, the ordinary restore path pops its manufactured registers and iretq jumps to thread_bootstrap. No special "first run" branch is required in the scheduler.

Preemption creates critical sections

The timer can arrive between any two instructions executed with interrupts enabled. That includes code modifying a linked list, allocator metadata, or the run queue itself.

On a single CPU, a useful first rule is:

• interrupt handlers protect their own shared state with interrupt masking;
• thread code disables preemption while holding scheduler-visible kernel locks;
• no code blocks or yields while preemption is disabled.

Per-task nesting avoids accidentally re-enabling preemption too early:

void preempt_disable(void)
{
    current_task->preempt_count++;
}

void preempt_enable(void)
{
    if (current_task->preempt_count == 0)
        panic("unbalanced preempt_enable");

    current_task->preempt_count--;

    if (current_task->preempt_count == 0 &&
        current_task->need_reschedule) {
        request_reschedule_interrupt();
    }
}

Do not invoke the timer handler as an ordinary C function. A reschedule request must enter through a defined interrupt or yield stub that produces the same saved-frame shape expected by the restore path.

Disabling preemption is not a complete multiprocessor lock. It only prevents the current CPU from switching tasks. Once a second CPU exists, shared structures need real synchronization and carefully defined lock ordering.

Blocking and waking tasks

Round-robin preemption handles CPU sharing, but an operating system also needs tasks to sleep while waiting for data.

The blocking sequence is conceptually:

1. Disable interrupts or acquire the wait-queue lock.
2. Verify that the awaited condition is still false.
3. Link the current task into the wait queue.
4. Mark it TASK_BLOCKED.
5. Enter the reschedule stub.

The condition must be checked while protected by the same synchronization that controls the wait queue. Otherwise, a wake-up can occur between the check and the state change, leaving the task asleep forever.

Waking reverses the ownership:

1. Remove a task from the wait queue.
2. Mark it TASK_RUNNABLE.
3. Place it on the run queue if it is not already there.
4. Request rescheduling if it should run promptly.

For a first kernel, use one run-queue lock and simple FIFO wait queues. Optimize only after the state transitions are observable and correct.

Test the mechanism in layers

A broken context switch often crashes far from the original mistake. Build confidence through small milestones.

1. Validate the timer without switching

Increment a counter, acknowledge the controller, and return to the interrupted code. Confirm that the rate is stable and that there is no interrupt storm.

2. Restore the same frame

Run the full assembly save path but make schedule_from_tick always return interrupted_rsp. If registers or the stack layout are wrong, this isolates the bug from run-queue logic.

3. Start one manufactured thread

Create a new task frame and switch to it once. Have the thread update a memory counter rather than print continuously. Confirm its stack bounds and bootstrap argument.

4. Preempt two CPU-bound threads

Use two threads that never yield. Each should increment a separate counter. If both counters advance, timer preemption is doing real work.

5. Stress every register

Run test code that keeps distinct patterns in registers across many ticks and verifies them after each resumption. This catches missing pushes, incorrect pop order, and structure-offset mistakes.

6. Add stack canaries and guard pages

Place a known value near the bottom of each stack and check it on every switch. Once paging permits it, leave an unmapped guard page below the stack so overflow becomes an immediate page fault instead of silent corruption.

An in-memory switch trace is extremely useful. Record the old task ID, new task ID, saved stack pointers, tick count, and reason for the switch. Keep the buffer fixed-size so tracing cannot allocate memory in interrupt context.

Common failure modes

The kernel crashes only with optimization enabled

Check stack alignment, the red-zone setting, and whether the compiler emitted vector instructions. Debug builds can hide ABI mistakes by producing different stack layouts.

A task restarts instead of resuming

Its saved_rsp probably points at the wrong location, or the scheduler overwrote it with the top of the stack. It must point at the first register consumed by the pop sequence.

The first thread runs, then returns into garbage

The bootstrap called the entry function directly without a defined exit path. Always route a returned thread into thread_exit.

Timer interrupts stop after the first switch

Verify that every path acknowledges the interrupt controller and that the restored RFLAGS has the interrupt-enable bit set when appropriate.

The run queue corrupts itself intermittently

The timer may be preempting code that edits scheduling structures, or a task may be inserted twice. Add state assertions at every transition and protect queue mutations consistently.

Printing makes the scheduler appear broken

Console output is often serialized, slow, or unsafe in interrupt context. Test progress with counters and inspect them from a separate diagnostic path.

What changes for user processes and multiple CPUs

User-mode scheduling extends the same stack-switch principle, but the saved state grows. An interrupt crossing from privilege level 3 to level 0 also saves the old user RSP and SS. Each process may require a different page-table root, and the CPU's privilege-transition stack must point at the current task's kernel stack. System-call entry and signal delivery add more frame formats that should be normalized deliberately.

Floating-point, SIMD, debug, and model-specific state also need an ownership policy. A kernel can save them eagerly on every switch or use a carefully designed lazy scheme, but ignoring them is not valid once user programs can modify them.

On multiple CPUs, replace global scheduler variables with per-CPU state. Each CPU needs its own current task, idle task, timer source, and usually its own run queue. Task migration then requires synchronized ownership, and waking a task on another CPU may require an inter-processor interrupt. Page-table changes introduce translation invalidation across cores as well.

These additions are substantial, but they do not change the central invariant: a non-running task must have one complete, well-defined state that the architecture-specific restore path can consume.

Keep the mechanism boring

A first scheduler does not need priorities, fairness trees, deadline classes, or load balancing. It needs a trustworthy transition from one saved stack to another.

The durable design rules are simple:

• define one exact saved-frame layout;
• make new tasks look like interrupted tasks;
• keep scheduling state transitions explicit;
• protect critical sections from preemption;
• acknowledge every timer interrupt;
• keep the switch path allocation-free and observable;
• add user mode and multiple CPUs only after the single-CPU invariants survive stress.

Once those rules hold, round-robin policy is almost the least interesting part. The real achievement is a context-switch mechanism you can reason about instruction by instruction—and trust as the rest of the kernel grows around it.

Written by Daniel McCarthyBest selling author in kernel development fields, I build C compilers and kernel modules frequently. I love teaching and helping the OSDEV community