Topic 05: Preemptive Multitasking, Context Switching & Custom Blocking Mutex

Overview: How the kernel runs multiple concurrent tasks using timer interrupts, switches between isolated stacks in pure assembly, and blocks contending tasks without wasting CPU cycles in spinloops.


1. High-Level Summary

Component Source Link What It Does Why It Is Needed
Process Control Block (PCB) src/process.rs:89 Tracks task ID, state, saved registers, and stack Holds everything the kernel needs to suspend and resume an independent task.
Initial Stack Setup src/process.rs:99 Pre-builds a fake hardware interrupt frame Allows the CPU to start a brand-new task using the exact same return mechanism (iretq) used for resuming existing tasks.
Naked Context Switch src/interrupts.rs:104 Saves/restores all 15 registers and swaps RSP Switches execution between tasks in pure assembly with zero compiler interference.
Round-Robin Scheduler src/process.rs:264 Rotates tasks between Ready, Blocked, and Terminated queues Ensures fair CPU sharing on every hardware timer tick.
Blocking Mutex src/sync.rs:54 Puts waiting tasks to sleep and wakes them on release Prevents threads from burning CPU time in spinloops when waiting for shared resources.

2. Spoken Interview Answer (Simple & Direct)

"Preemptive multitasking allows multiple tasks to share a single CPU core without relying on individual programs to voluntarily give up control.

In RustOS, each task is represented by a Process Control Block (PCB). It stores a unique Task ID, execution state (Ready, Running, Blocked, or Terminated), saved registers, and an isolated 8 KiB private stack. When a new task is spawned, I pre-build a fake interrupt frame on its stack: setting the instruction pointer to the task function, flags to enable interrupts, and pushing 15 zeros for general-purpose registers. This allows the CPU to start a brand-new task using the exact same interrupt-return instruction (iretq) that resumes paused tasks.

Preemption is driven by the 8253 timer interrupt. In interrupts.rs, I wrote a naked assembly handler. When the timer ticks, the CPU hardware saves the current task's instruction pointer and flags. Our assembly code then pushes all 15 general-purpose registers onto the task's stack, and calls our Rust scheduler function, timer_schedule.

The scheduler moves the interrupted task to the back of the ready queue, picks the next task, and returns that next task's stack pointer. In assembly, switching tasks is as simple as updating the CPU stack pointer register (RSP) to point to the new task's stack. The assembly routine then pops the new task's 15 registers, sends an End-of-Interrupt signal to the PIC, and executes iretq. The CPU immediately resumes the new task right where it left off.

On top of this, I built a custom blocking Mutex. Unlike a spinlock that spins in a tight loop and starves other threads on a single core, our mutex checks the lock atomically. If it's already locked, the task enqueues its Task ID into a wait list, marks itself as Blocked, and yields immediately. When the lock guard goes out of scope, it automatically pops the next waiting task and wakes it up so the scheduler can run it again."


3. Architecture & Mechanics

3.1 Process Control Block (PCB) & Stack Isolation

Every task runs with its own private 8 KiB stack allocated on the kernel heap. The task's complete metadata is stored in src/process.rs:89 (ProcessControlBlock):

3.2 Faking the Initial Stack Frame

When a task is created for the first time in src/process.rs:99, it hasn't actually been interrupted yet. To make the scheduler treat it just like any other interrupted task, we construct a synthetic interrupt frame on its stack:

Top of Stack (High Address)
+------------------------------------+
| SS     = 0                         |  <-- Stack Segment
| RSP    = Top of Stack              |  <-- Stack Pointer
| RFLAGS = 0x202 (Interrupts Enable) |  <-- CPU Flags
| CS     = Kernel Code Selector      |  <-- Code Segment
| RIP    = Task Entry Function       |  <-- Where the task begins execution
+------------------------------------+
| 15 General Purpose Registers       |  <-- Pushed as 0 (RAX, RBX, RCX, ..., R15)
+------------------------------------+
RSP points here (Lowest Address)

When the CPU executes iretq on this stack, it pops these values and jumps straight into the task's entry point with interrupts enabled, completely unaware that the task was never running before.

3.3 The Context Switch Cycle (4 Steps)

The entire context switch happens inside our naked interrupt handler in src/interrupts.rs:104 and the scheduler in src/process.rs:264:

Timer Interrupt Fires
        │
        ▼
1. CPU saves RIP, CS, RFLAGS, RSP, SS onto Task A's stack
        │
        ▼
2. Naked Assembly pushes all 15 general-purpose registers (RAX..R15)
        │
        ▼
3. Call Rust scheduler: timer_schedule(Task A RSP)
   - Save Task A RSP in its PCB
   - Move Task A to ready queue
   - Pop Task B from ready queue
   - Return Task B RSP
        │
        ▼
4. Naked Assembly updates RSP = Task B RSP
   - Pop 15 registers of Task B
   - Send EOI (0x20) to 8259 PIC
   - iretq restores Task B's RIP and flags
        │
        ▼
Task B is now running!

3.4 Why Naked Assembly (#[unsafe(naked)])?

Normally, Rust and C compilers automatically insert "prologue" and "epilogue" code into functions to set up and tear down stack frames (such as push rbp; mov rbp, rsp). In an interrupt handler that performs a context switch, compiler-generated code would corrupt the stack offsets before we could save the registers.

By marking the handler with #[unsafe(naked)], we instruct the compiler to emit only our raw assembly instructions. This gives us exact, byte-level control over the stack pointer and register layouts.

3.5 Custom Blocking Mutex

In a single-core preemptive operating system, using a basic spinlock for long operations is inefficient and dangerous: if Task A holds the spinlock and Task B runs, Task B will spin in a loop burning its entire timer timeslice doing nothing.

Our custom sync::Mutex<T> solves this:

  1. When a task calls lock(), it attempts to acquire the lock atomically.
  2. If the lock is free, it acquires it immediately and returns a guard.
  3. If the lock is held, the task does not spin. It adds its TaskId to the mutex's internal wait_list, changes its state to Blocked, and triggers a software interrupt to yield the CPU immediately.
  4. When the holding task finishes and its MutexGuard drops, it releases the lock, removes the first task from the wait list, and wakes it up by moving it back to the ready queue.

4. Real Edge Cases & Debugging

The 16-Byte Stack Alignment Rule

The x86_64 architecture requires that the stack pointer (RSP) be aligned to a 16-byte boundary before calling any function. If a function uses SSE/AVX vector instructions (which the Rust compiler often emits for fast string or memory operations) and the stack is misaligned, the CPU immediately throws a General Protection Fault (#GP).

To ensure this never happens, KernelStack::new aligns the stack top downwards to a multiple of 16. Because our initial interrupt frame consists of 20 64-bit entries ($20 \times 8 = 160$ bytes, which is a multiple of 16), the stack pointer remains 16-byte aligned when the task begins running.


5. Verification & Test Traces

When RustOS boots in QEMU, multiple tasks run concurrently alongside the interactive shell:

Welcome to RustOS, from The Rusty Crew!!
Multitasking Scheduler starting...
Exiting task starting, about to exit...
Counter task incremented data to: 1
Clock task added 10, data now: 11
Counter task incremented data to: 12
/ >> 

This live trace demonstrates that:


6. Common Interview Questions

Q1: Why must the timer interrupt handler be declared with #[unsafe(naked)]?

Answer: "Normal functions generated by compilers include automatic setup code (prologues and epilogues) that push base pointers and allocate stack frames. For a context switch, we need total byte-for-byte control over the stack pointer so that RSP matches our register structure exactly. Naked assembly prevents the compiler from adding any extra instructions, allowing us to manually push registers, switch RSP, and pop registers safely."

Q2: What is the difference between cooperative and preemptive multitasking?

Answer: "In cooperative multitasking, a task runs until it chooses to yield the CPU voluntarily. If a task enters an infinite loop, the entire operating system freezes. In preemptive multitasking, a hardware timer interrupt periodically interrupts whatever task is currently running, saves its state, and gives another task a turn. Preemption guarantees fair scheduling and prevents any single task from hanging the system."

Q3: You mentioned Mutex/Semaphore synchronization in your resume. Where did you use the semaphore in your project?

Answer: "I implemented a counting semaphore as part of the kernel synchronization layer, but I did not actually use it in the final task implementation. The shared-data synchronization I used in my tasks was done using the mutex."