Project 10: Simple Kernel with Multitasking
Build a preemptive multitasking kernel from scratch–implementing Task Control Blocks, context switching in assembly, a round-robin scheduler, and timer-based preemption–the core of every operating system.
Quick Reference
| Attribute | Value |
|---|---|
| Difficulty | Master |
| Time Estimate | 4-6 weeks |
| Language | C with x86 Assembly (alt: Rust) |
| Prerequisites | Projects 5-8 (x86 boot, protected mode, IDT, paging) |
| Key Topics | Task Control Blocks, context switching, scheduling, timer preemption |
| Platform | x86 32-bit (QEMU) |
| Tools | GCC cross-compiler, NASM, QEMU, GDB |
1. Learning Objectives
By completing this project, you will:
- Understand process abstraction: Master how operating systems create the illusion of simultaneous execution
- Implement context switching: Write assembly code that saves and restores CPU state between tasks
- Design Task Control Blocks: Create data structures that represent running programs
- Build a scheduler: Implement round-robin and priority-based scheduling algorithms
- Master timer preemption: Use hardware timers to forcibly switch between tasks
- Handle synchronization basics: Understand race conditions between tasks and interrupt handlers
- Debug concurrent systems: Develop techniques for debugging non-deterministic behavior
- Lay the foundation for a real OS: Everything you build here is used in Linux, Windows, and macOS
2. Theoretical Foundation
2.1 Core Concepts
What is Multitasking?
Multitasking creates the illusion that multiple programs run simultaneously on a single CPU. In reality, the CPU rapidly switches between tasks:
┌─────────────────────────────────────────────────────────────────────────────┐
│ THE ILLUSION OF MULTITASKING │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ WHAT THE USER SEES: │
│ ─────────────────── │
│ │
│ Task A: ████████████████████████████████████████████████████████████ │
│ Task B: ████████████████████████████████████████████████████████████ │
│ Task C: ████████████████████████████████████████████████████████████ │
│ │
│ (All tasks appear to run continuously and simultaneously) │
│ │
│ ───────────────────────────────────────────────────────────────────────── │
│ │
│ WHAT ACTUALLY HAPPENS (time-slicing): │
│ ──────────────────────────────────── │
│ │
│ Time: 0 10 20 30 40 50 60 70 80 90 100 ms │
│ ├────┼────┼────┼────┼────┼────┼────┼────┼────┼────┤ │
│ │
│ Task A: ████ ████ ████ ████ │
│ Task B: ████ ████ ████ ████ │
│ Task C: ████ ████ ████ ████ │
│ │
│ CPU: A B C A B C A B C A B │
│ │
│ Each task runs for a "time quantum" (e.g., 10ms) before switching │
│ Context switches happen so fast (~10-20 microseconds) that users │
│ perceive all tasks as running simultaneously │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
Types of Multitasking
┌─────────────────────────────────────────────────────────────────────────────┐
│ COOPERATIVE vs PREEMPTIVE MULTITASKING │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ COOPERATIVE MULTITASKING (yield-based): │
│ ─────────────────────────────────────── │
│ │
│ • Tasks explicitly give up CPU by calling yield() │
│ • If a task doesn't yield, others never run │
│ • Simpler to implement, no race conditions │
│ • Problem: Buggy/malicious task can freeze system │
│ │
│ Code pattern: │
│ while (1) { │
│ do_some_work(); │
│ yield(); // "I'm done for now, let others run" │
│ } │
│ │
│ Used in: Classic Mac OS, Windows 3.x, embedded RTOS (optional) │
│ │
│ ───────────────────────────────────────────────────────────────────────── │
│ │
│ PREEMPTIVE MULTITASKING (timer-based): │
│ ────────────────────────────────────── │
│ │
│ • Hardware timer forces context switches │
│ • Tasks don't need to cooperate │
│ • System remains responsive even with buggy tasks │
│ • More complex: race conditions, interrupt handling │
│ │
│ Mechanism: │
│ 1. Timer fires every N ms (time quantum) │
│ 2. CPU jumps to timer interrupt handler │
│ 3. Handler saves current task state │
│ 4. Scheduler picks next task │
│ 5. Handler restores next task state │
│ 6. Return from interrupt → now running new task! │
│ │
│ Used in: Linux, Windows NT+, macOS, iOS, Android, every modern OS │
│ │
│ ───────────────────────────────────────────────────────────────────────── │
│ │
│ THIS PROJECT: We'll implement BOTH! │
│ - Start with cooperative (simpler) │
│ - Then add preemption (real OS behavior) │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
The Task Control Block (TCB)
The TCB is the kernel’s representation of a task (process/thread):
┌─────────────────────────────────────────────────────────────────────────────┐
│ TASK CONTROL BLOCK (TCB) │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ Every task has a TCB that stores: │
│ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ TCB Structure │ │
│ ├─────────────────────────────────────────────────────────────────────┤ │
│ │ │ │
│ │ IDENTITY │ │
│ │ ├── task_id : uint32_t // Unique identifier │ │
│ │ └── name : char[16] // Human-readable name │ │
│ │ │ │
│ │ STATE │ │
│ │ ├── state : enum // READY, RUNNING, BLOCKED │ │
│ │ ├── priority : uint8_t // For priority scheduling │ │
│ │ └── time_slice : uint32_t // Remaining time quantum │ │
│ │ │ │
│ │ SAVED CONTEXT (when not running) │ │
│ │ ├── esp : uint32_t // Stack pointer │ │
│ │ ├── ebp : uint32_t // Base pointer │ │
│ │ ├── eip : uint32_t // Instruction pointer │ │
│ │ ├── eflags : uint32_t // Flags register │ │
│ │ └── [eax..edi] : uint32_t[8] // General registers │ │
│ │ │ │
│ │ MEMORY │ │
│ │ ├── stack_base : uint32_t* // Bottom of stack │ │
│ │ ├── stack_size : uint32_t // Stack size in bytes │ │
│ │ └── page_directory : uint32_t* // For virtual memory (opt) │ │
│ │ │ │
│ │ SCHEDULING │ │
│ │ ├── next : TCB* // Next in ready queue │ │
│ │ └── prev : TCB* // Previous in ready queue │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
│ IN MEMORY: │
│ │
│ ┌─────────────────┐ ┌─────────────────┐ ┌─────────────────┐ │
│ │ TCB: Task A │────►│ TCB: Task B │────►│ TCB: Task C │──┐ │
│ │ state: RUN │ │ state: READY │ │ state: READY │ │ │
│ │ esp: 0x... │ │ esp: 0x... │ │ esp: 0x... │ │ │
│ └─────────────────┘ └─────────────────┘ └─────────────────┘ │ │
│ ▲ │ │
│ └─────────────────────────────────────────────────────────────┘ │
│ (circular linked list) │
│ │
│ CURRENT TASK POINTER: │
│ current_task → [TCB: Task A] │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
Context Switching - The Heart of Multitasking
Context switching saves one task’s CPU state and restores another’s:
┌─────────────────────────────────────────────────────────────────────────────┐
│ CONTEXT SWITCH ANATOMY │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ STEP 1: SAVE CURRENT TASK'S CONTEXT │
│ ──────────────────────────────────── │
│ │
│ Before switch, Task A is running: │
│ │
│ CPU Registers: Task A's Stack: │
│ ┌─────────────┐ ┌─────────────┐ ← ESP │
│ │ EAX = 0x42 │ │ local_x │ │
│ │ EBX = 0x100 │ │ local_y │ │
│ │ ECX = 0x07 │ │ ret_addr │ │
│ │ ... │ │ ... │ │
│ │ ESP = 0x... │──────────────────│─────────────│ │
│ │ EIP = 0x... │ │ │ │
│ └─────────────┘ └─────────────┘ │
│ │
│ Save registers to Task A's stack: │
│ │
│ push eax ; Save general purpose registers │
│ push ebx │
│ push ecx │
│ push edx │
│ push ebp │
│ push esi │
│ push edi │
│ mov [task_a.esp], esp ; Save stack pointer to TCB │
│ │
│ Task A's Stack (after saving): │
│ ┌─────────────┐ ← New ESP (saved in TCB) │
│ │ EDI │ │
│ │ ESI │ │
│ │ EBP │ │
│ │ EDX │ │
│ │ ECX │ │
│ │ EBX │ │
│ │ EAX │ │
│ │ local_x │ │
│ │ local_y │ │
│ │ ret_addr │ │
│ └─────────────┘ │
│ │
│ ───────────────────────────────────────────────────────────────────────── │
│ │
│ STEP 2: RESTORE NEXT TASK'S CONTEXT │
│ ──────────────────────────────────── │
│ │
│ mov esp, [task_b.esp] ; Load Task B's stack pointer │
│ pop edi ; Restore Task B's registers │
│ pop esi │
│ pop ebp │
│ pop edx │
│ pop ecx │
│ pop ebx │
│ pop eax │
│ ret ; Returns to Task B's saved EIP! │
│ │
│ After restore: │
│ │
│ CPU Registers: Task B's Stack: │
│ ┌─────────────┐ ┌─────────────┐ │
│ │ EAX = 0x99 │ │ local_a │ ← ESP (after pops + ret) │
│ │ EBX = 0x200 │ │ local_b │ │
│ │ ECX = 0x03 │ │ ret_addr │ ← We "return" here! │
│ │ ... │ │ ... │ │
│ │ ESP = 0x... │────────│─────────────│ │
│ │ EIP = ??? │ │ │ │
│ └─────────────┘ └─────────────┘ │
│ │
│ The `ret` instruction pops Task B's saved return address into EIP, │
│ so execution continues from where Task B left off! │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
The x86 Context Switch in Assembly
┌─────────────────────────────────────────────────────────────────────────────┐
│ x86 CONTEXT SWITCH IMPLEMENTATION │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ ; void switch_context(tcb_t *old, tcb_t *new) │
│ ; old = pointer to current task's TCB │
│ ; new = pointer to next task's TCB │
│ │
│ switch_context: │
│ ; Function prologue - standard C calling convention │
│ push ebp │
│ mov ebp, esp │
│ │
│ ; Save callee-saved registers (C calling convention) │
│ push ebx │
│ push esi │
│ push edi │
│ │
│ ; Get pointers from arguments │
│ mov eax, [ebp + 8] ; eax = old (first argument) │
│ mov edx, [ebp + 12] ; edx = new (second argument) │
│ │
│ ; Save current stack pointer to old task's TCB │
│ mov [eax + TCB_ESP], esp │
│ │
│ ; Load new task's stack pointer │
│ mov esp, [edx + TCB_ESP] │
│ │
│ ; Restore callee-saved registers from new stack │
│ pop edi │
│ pop esi │
│ pop ebx │
│ │
│ ; Function epilogue │
│ pop ebp │
│ ret ; Returns to new task's caller! │
│ │
│ ───────────────────────────────────────────────────────────────────────── │
│ │
│ WHY THIS WORKS: │
│ │
│ When Task A calls switch_context(old_tcb, new_tcb): │
│ 1. Return address is pushed (where to continue in Task A) │
│ 2. Registers are saved to Task A's stack │
│ 3. Task A's stack pointer is saved to its TCB │
│ 4. Task B's stack pointer is loaded from its TCB │
│ 5. Registers are restored from Task B's stack │
│ 6. `ret` pops Task B's return address → now running Task B! │
│ │
│ The magic: We change ESP between saving and restoring, so we │
│ restore a DIFFERENT task's context than we saved! │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
Task Creation - Setting Up the Initial Stack
When creating a new task, we must set up its stack to look like it was interrupted:
┌─────────────────────────────────────────────────────────────────────────────┐
│ NEW TASK STACK INITIALIZATION │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ Goal: Make the stack look like the task was previously running and │
│ yielded/was preempted, so switch_context can "restore" it. │
│ │
│ tcb_t* create_task(void (*entry)(void), void* stack_top) { │
│ tcb_t* tcb = allocate_tcb(); │
│ │
│ // Start at top of stack, work downward │
│ uint32_t* sp = (uint32_t*)stack_top; │
│ │
│ // Fake "return address" - the task's entry point │
│ *(--sp) = (uint32_t)entry; │
│ │
│ // Fake saved EBP (can be 0 for new task) │
│ *(--sp) = 0; │
│ │
│ // Fake saved callee-saved registers │
│ *(--sp) = 0; // EBX │
│ *(--sp) = 0; // ESI │
│ *(--sp) = 0; // EDI │
│ │
│ // Save this stack pointer in TCB │
│ tcb->esp = (uint32_t)sp; │
│ │
│ return tcb; │
│ } │
│ │
│ ───────────────────────────────────────────────────────────────────────── │
│ │
│ RESULTING STACK LAYOUT: │
│ │
│ Stack top (high address) │
│ ┌─────────────────────────┐ │
│ │ (unused space) │ │
│ ├─────────────────────────┤ │
│ │ entry (return addr) │ ← ret will pop this into EIP │
│ ├─────────────────────────┤ │
│ │ 0 (saved EBP) │ ← pop ebp gets this │
│ ├─────────────────────────┤ │
│ │ 0 (saved EBX) │ ← pop ebx │
│ ├─────────────────────────┤ │
│ │ 0 (saved ESI) │ ← pop esi │
│ ├─────────────────────────┤ │
│ │ 0 (saved EDI) │ ← pop edi - ESP starts here │
│ ├─────────────────────────┤ ← tcb->esp points here │
│ │ (more space) │ │
│ └─────────────────────────┘ │
│ Stack bottom (low address) │
│ │
│ When switch_context switches TO this task: │
│ 1. ESP is loaded from TCB │
│ 2. Pops restore EDI, ESI, EBX, EBP (all zeros, but that's fine) │
│ 3. ret pops entry point into EIP │
│ 4. CPU jumps to entry() - task starts running! │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
Timer Preemption
The hardware timer forces context switches:
┌─────────────────────────────────────────────────────────────────────────────┐
│ TIMER-BASED PREEMPTION │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ PROGRAMMABLE INTERVAL TIMER (PIT 8254): │
│ ────────────────────────────────────── │
│ │
│ • 1.193182 MHz base frequency │
│ • Divisor sets interrupt frequency │
│ • IRQ 0 (remapped to interrupt 32 after PIC init) │
│ │
│ // Set PIT to fire every 10ms (100 Hz) │
│ // Divisor = 1193182 / 100 = 11932 │
│ #define PIT_FREQ 1193182 │
│ #define TICK_FREQ 100 │
│ #define DIVISOR (PIT_FREQ / TICK_FREQ) │
│ │
│ void init_pit(void) { │
│ outb(0x43, 0x36); // Channel 0, mode 3, lo/hi byte │
│ outb(0x40, DIVISOR & 0xFF); // Low byte │
│ outb(0x40, DIVISOR >> 8); // High byte │
│ } │
│ │
│ ───────────────────────────────────────────────────────────────────────── │
│ │
│ TIMER INTERRUPT HANDLER: │
│ ──────────────────────── │
│ │
│ ; Timer ISR - called by hardware every 10ms │
│ timer_isr: │
│ ; Save ALL registers (interrupt can happen anywhere!) │
│ pusha │
│ push ds │
│ push es │
│ push fs │
│ push gs │
│ │
│ ; Set up kernel segments │
│ mov ax, 0x10 │
│ mov ds, ax │
│ mov es, ax │
│ │
│ ; Save current ESP to current task's TCB │
│ mov eax, [current_task] │
│ mov [eax + TCB_ESP], esp │
│ │
│ ; Call C scheduler │
│ call schedule ; Returns pointer to next task │
│ mov [current_task], eax ; Update current task pointer │
│ │
│ ; Switch stacks │
│ mov esp, [eax + TCB_ESP] │
│ │
│ ; Acknowledge interrupt (send EOI to PIC) │
│ mov al, 0x20 │
│ out 0x20, al │
│ │
│ ; Restore all registers │
│ pop gs │
│ pop fs │
│ pop es │
│ pop ds │
│ popa │
│ │
│ iret ; Return from interrupt → now in new task! │
│ │
│ ───────────────────────────────────────────────────────────────────────── │
│ │
│ THE PREEMPTION FLOW: │
│ │
│ Task A running │
│ │ │
│ ▼ │
│ [10ms passes - TIMER FIRES] │
│ │ │
│ ▼ │
│ CPU pushes EFLAGS, CS, EIP (interrupt frame) │
│ │ │
│ ▼ │
│ timer_isr saves all registers │
│ │ │
│ ▼ │
│ Save ESP to Task A's TCB │
│ │ │
│ ▼ │
│ Scheduler picks Task B │
│ │ │
│ ▼ │
│ Load ESP from Task B's TCB │
│ │ │
│ ▼ │
│ timer_isr restores Task B's registers │
│ │ │
│ ▼ │
│ iret → CPU pops Task B's EIP, CS, EFLAGS │
│ │ │
│ ▼ │
│ Task B is now running! │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
Scheduling Algorithms
┌─────────────────────────────────────────────────────────────────────────────┐
│ SCHEDULING ALGORITHMS │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ 1. ROUND-ROBIN (What we'll implement first) │
│ ─────────────────────────────────────────── │
│ │
│ Simple circular queue: each task gets equal time │
│ │
│ Ready Queue: A → B → C → D → (back to A) │
│ │
│ Execution order: A(10ms) → B(10ms) → C(10ms) → D(10ms) → A(10ms) → ... │
│ │
│ tcb_t* schedule_round_robin(void) { │
│ current_task = current_task->next; │
│ while (current_task->state != READY) { │
│ current_task = current_task->next; │
│ } │
│ return current_task; │
│ } │
│ │
│ Pros: Fair, simple, no starvation │
│ Cons: No priority support, bad for interactive tasks │
│ │
│ ───────────────────────────────────────────────────────────────────────── │
│ │
│ 2. PRIORITY SCHEDULING (Extension) │
│ ─────────────────────────────────── │
│ │
│ Higher priority tasks run first: │
│ │
│ Priority 3 (high): A │
│ Priority 2 (med): B, C │
│ Priority 1 (low): D, E │
│ │
│ Execution: A runs until blocked, then B→C→B→C..., D/E only if others │
│ are blocked │
│ │
│ Problem: Starvation (low priority never runs if high priority busy) │
│ Solution: Priority aging (boost starved tasks), priority donation │
│ │
│ ───────────────────────────────────────────────────────────────────────── │
│ │
│ 3. MULTI-LEVEL FEEDBACK QUEUE (Modern schedulers) │
│ ──────────────────────────────────────────────── │
│ │
│ Queue 0 (interactive): Short quantum, high priority ←─ New tasks start│
│ Queue 1 (mid): Medium quantum │
│ Queue 2 (CPU-bound): Long quantum, low priority ←─ Tasks demoted │
│ │
│ • Tasks that use full quantum get demoted │
│ • Tasks that block early get promoted │
│ • Automatically adapts to task behavior │
│ │
│ Used in: Linux CFS, Windows scheduler │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
2.2 Why This Matters
Understanding Operating Systems:
- Every OS uses these exact concepts
- Linux’s
task_structis a complex TCB - Windows’ thread switching uses similar assembly
Interview Preparation:
- “Explain context switching” - very common question
- Understanding helps with concurrent programming
- Debugging multithreaded bugs requires this knowledge
Real-World Applications:
- RTOS development (FreeRTOS, Zephyr)
- Embedded systems with multiple tasks
- Game engines (task systems)
- Web servers (worker threads)
2.3 Historical Context
The Evolution of Multitasking:
- 1960s: Time-sharing systems (Multics, CTSS)
- 1970s: Unix process model
- 1980s: Cooperative multitasking (Mac OS, Windows 3.x)
- 1990s: Preemptive multitasking becomes standard (Windows NT, Linux)
- 2000s: Multi-core brings true parallelism
- Today: Thousands of threads, async/await, user-space scheduling
2.4 Common Misconceptions
| Misconception | Reality |
|---|---|
| “Context switch is expensive” | ~1-10 microseconds on modern CPUs; not free, but very fast |
| “Cooperative multitasking is obsolete” | Still used in embedded (FreeRTOS), green threads, async |
| “Each task needs its own page table” | Threads share page tables; only processes need separate |
| “The scheduler runs constantly” | Scheduler only runs on timer interrupt or yield |
| “Preemption can happen mid-instruction” | Instructions are atomic; preemption happens between them |
3. Project Specification
3.1 What You Will Build
A minimal but complete multitasking kernel that demonstrates:
- Task Control Blocks with proper state management
- Cooperative scheduling using explicit yield()
- Preemptive scheduling using timer interrupts
- Task lifecycle (create, run, terminate)
- Round-robin scheduler with equal time slices
- Idle task that runs when no other tasks are ready
- Debug output showing context switches
3.2 Functional Requirements
| ID | Requirement |
|---|---|
| FR1 | System supports at least 8 concurrent tasks |
| FR2 | Each task has a separate 4KB stack |
| FR3 | Tasks can yield() cooperatively |
| FR4 | Timer interrupt preempts running task every 10ms |
| FR5 | Scheduler uses round-robin algorithm |
| FR6 | Tasks can terminate and be cleaned up |
| FR7 | Idle task runs when all other tasks blocked/terminated |
| FR8 | Serial output shows task switches and states |
3.3 Non-Functional Requirements
| ID | Requirement |
|---|---|
| NFR1 | Context switch completes in < 1000 cycles |
| NFR2 | Kernel code is interrupt-safe |
| NFR3 | No memory leaks from task creation/destruction |
| NFR4 | System remains stable under rapid task switching |
| NFR5 | Debug output doesn’t significantly impact timing |
3.4 Example Usage / Output
$ make
nasm -f elf32 boot.asm -o boot.o
i686-elf-gcc -c kernel.c -o kernel.o -ffreestanding -Wall
i686-elf-gcc -c task.c -o task.o -ffreestanding -Wall
i686-elf-gcc -c scheduler.c -o scheduler.o -ffreestanding -Wall
nasm -f elf32 switch.asm -o switch.o
i686-elf-ld -T link.ld -o kernel.elf boot.o kernel.o task.o scheduler.o switch.o
$ qemu-system-i386 -kernel kernel.elf -serial stdio
================================================================================
Simple Multitasking Kernel v1.0
================================================================================
[INIT] Creating tasks...
Task 0: Idle (priority 0)
Task 1: Counter_A (priority 1)
Task 2: Counter_B (priority 1)
Task 3: Printer (priority 1)
[INIT] Starting scheduler...
[SCHED] Timer tick! Switching: Idle -> Counter_A
[Task 1] Counter A: 1
[Task 1] Counter A: 2
[Task 1] Counter A: 3
[SCHED] Timer tick! Switching: Counter_A -> Counter_B
[Task 2] Counter B: 1
[Task 2] Counter B: 2
[SCHED] Timer tick! Switching: Counter_B -> Printer
[Task 3] ========================================
[Task 3] Hello from the Printer task!
[Task 3] ========================================
[SCHED] Timer tick! Switching: Printer -> Counter_A
[Task 1] Counter A: 4
[Task 1] Counter A: 5
[Task 1] Yielding early...
[SCHED] Voluntary yield! Switching: Counter_A -> Counter_B
[Task 2] Counter B: 3
...
[Task 2] Counter B terminating.
[SCHED] Task 2 terminated. Switching: Counter_B -> Printer
[STATS] After 100 ticks:
Context switches: 97
Task 0 (Idle): 3 runs
Task 1 (Counter_A): 32 runs
Task 2 (Counter_B): 32 runs (terminated)
Task 3 (Printer): 30 runs
All tasks complete. Halting.
3.5 Real World Outcome
After completing this project, you will have:
- A working kernel that actually runs multiple tasks
- Deep understanding of how all OSes work at their core
- Assembly skills for the most performance-critical OS code
- Foundation for RTOS development
- Interview-ready knowledge of concurrency fundamentals
- Debugging skills for the hardest class of bugs (race conditions)
4. Solution Architecture
4.1 High-Level Design
┌─────────────────────────────────────────────────────────────────────────────┐
│ MULTITASKING KERNEL ARCHITECTURE │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ ┌────────────────────────────────────────────────────────────────────────┐│
│ │ USER TASKS ││
│ │ ┌──────────────┐ ┌──────────────┐ ┌──────────────┐ ││
│ │ │ Task 1 │ │ Task 2 │ │ Task 3 │ ... ││
│ │ │ Counter_A │ │ Counter_B │ │ Printer │ ││
│ │ │ (running) │ │ (ready) │ │ (ready) │ ││
│ │ └──────────────┘ └──────────────┘ └──────────────┘ ││
│ └────────────────────────────────────────────────────────────────────────┘│
│ │ │
│ yield() or timer interrupt │
│ │ │
│ ▼ │
│ ┌────────────────────────────────────────────────────────────────────────┐│
│ │ SCHEDULER ││
│ │ ┌──────────────┐ ┌──────────────┐ ┌──────────────────────────────┐ ││
│ │ │ Ready Queue │ │ Scheduling │ │ Context Switch │ ││
│ │ │ (linked list)│ │ Algorithm │ │ (assembly) │ ││
│ │ │ Task1→2→3 │ │ (round-robin)│ │ save/restore registers │ ││
│ │ └──────────────┘ └──────────────┘ └──────────────────────────────┘ ││
│ └────────────────────────────────────────────────────────────────────────┘│
│ │ │
│ ▼ │
│ ┌────────────────────────────────────────────────────────────────────────┐│
│ │ KERNEL SERVICES ││
│ │ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ ┌─────────────────┐ ││
│ │ │ Task Mgmt │ │ Timer │ │ Memory │ │ Debug │ ││
│ │ │ create/exit │ │ (PIT 10ms) │ │ (stacks) │ │ (serial print) │ ││
│ │ └─────────────┘ └─────────────┘ └─────────────┘ └─────────────────┘ ││
│ └────────────────────────────────────────────────────────────────────────┘│
│ │ │
│ ▼ │
│ ┌────────────────────────────────────────────────────────────────────────┐│
│ │ HARDWARE ABSTRACTION ││
│ │ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ ││
│ │ │ IDT │ │ PIC │ │ Serial │ ││
│ │ │ (interrupts)│ │ (IRQ ctrl) │ │ (debug) │ ││
│ │ └─────────────┘ └─────────────┘ └─────────────┘ ││
│ └────────────────────────────────────────────────────────────────────────┘│
│ │
└─────────────────────────────────────────────────────────────────────────────┘
4.2 Key Components
| Component | File | Responsibility |
|---|---|---|
| Boot/Entry | boot.asm |
GDT, enter protected mode, call kernel |
| Kernel Main | kernel.c |
Initialize subsystems, create tasks, start scheduler |
| Task Manager | task.c |
TCB allocation, task create/destroy |
| Scheduler | scheduler.c |
Ready queue, pick next task, statistics |
| Context Switch | switch.asm |
Save/restore CPU registers |
| Timer | timer.c |
PIT configuration, tick counting |
| IDT | idt.c |
Interrupt setup, ISR wrappers |
| Serial | serial.c |
Debug output |
4.3 Data Structures
// Task states
typedef enum {
TASK_CREATED, // Newly created, not yet run
TASK_READY, // Ready to run
TASK_RUNNING, // Currently executing
TASK_BLOCKED, // Waiting for something
TASK_TERMINATED // Finished execution
} task_state_t;
// Task Control Block
typedef struct tcb {
uint32_t id; // Unique task ID
char name[16]; // Human-readable name
task_state_t state; // Current state
uint8_t priority; // Scheduling priority
// Saved context (stack pointer contains all register state)
uint32_t esp; // Saved stack pointer
// Stack management
uint32_t *stack_base; // Bottom of allocated stack
uint32_t stack_size; // Size in bytes
// Scheduling
struct tcb *next; // Next task in queue
struct tcb *prev; // Previous task in queue
// Statistics
uint32_t run_count; // Times this task has run
uint32_t total_ticks; // Total time slices used
} tcb_t;
// Scheduler state
typedef struct {
tcb_t *current; // Currently running task
tcb_t *idle_task; // Idle task (always ready)
tcb_t *head; // First task in ready queue
uint32_t num_tasks; // Total tasks
uint32_t context_switches; // Switch counter
uint32_t tick_count; // Timer ticks since boot
} scheduler_t;
4.4 Algorithm Overview
Task Creation:
1. Allocate TCB structure
2. Allocate stack memory (4KB)
3. Initialize stack:
- Place entry point as return address
- Push fake saved registers
4. Set ESP in TCB to prepared stack
5. Set state to READY
6. Add to ready queue
Scheduler (Round-Robin):
1. Move current task to end of ready queue
2. Pick task at head of ready queue
3. If all tasks blocked, pick idle task
4. Call switch_context(old, new)
Timer Interrupt:
1. Push all registers to current stack
2. Save ESP to current task's TCB
3. Call scheduler to pick next task
4. Load ESP from new task's TCB
5. Send EOI to PIC
6. Pop all registers from new stack
7. IRET - now running new task
5. Implementation Guide
5.1 Development Environment Setup
# Same as Project 6 (Protected Mode Kernel)
# Cross-compiler for i686-elf target
# Verify tools
i686-elf-gcc --version
nasm --version
qemu-system-i386 --version
# Debug setup
# Terminal 1:
qemu-system-i386 -kernel kernel.elf -serial stdio -s -S
# Terminal 2:
gdb kernel.elf
(gdb) target remote localhost:1234
(gdb) break schedule
(gdb) continue
5.2 Project Structure
multitasking_kernel/
├── Makefile
├── link.ld # Linker script
├── boot.asm # Boot, GDT, enter protected mode
├── kernel.c # Main entry, initialization
├── kernel.h # Kernel-wide definitions
├── task.c # Task creation/destruction
├── task.h # TCB definition
├── scheduler.c # Scheduling algorithm
├── scheduler.h # Scheduler interface
├── switch.asm # Context switch assembly
├── timer.c # PIT setup
├── timer.h
├── idt.c # IDT and ISR setup
├── idt.h
├── isr.asm # ISR stubs in assembly
├── serial.c # Debug output
├── serial.h
└── tasks/ # Example user tasks
├── counter.c
└── printer.c
5.3 The Core Question You’re Answering
“How does an operating system run multiple programs on a single CPU?”
You’ll answer this by:
- Creating data structures to represent each program (TCB)
- Writing assembly to save one program’s state and restore another’s
- Using hardware timers to force programs to share the CPU
- Building a scheduler that decides which program runs next
5.4 Concepts You Must Understand First
| Concept | Self-Assessment Question | Reference |
|---|---|---|
| x86 calling convention | What registers must a called function preserve? | System V ABI |
| Stack layout | What’s on the stack after a function call? | OSTEP Ch. 6 |
| Interrupts | How does the CPU save state when an interrupt fires? | Intel SDM |
| x86 protected mode | What is the difference between Ring 0 and Ring 3? | OSDev Wiki |
| Timer hardware | How does the PIT generate periodic interrupts? | OSDev Wiki |
5.5 Questions to Guide Your Design
TCB Design:
- What’s the minimum state needed to resume a task?
- Where should the TCB be stored (heap, static array)?
- How do you handle task termination?
Context Switch:
- Why are some registers caller-saved and others callee-saved?
- What happens if you don’t save the flags register?
- How is interrupt-triggered switch different from yield()?
Scheduler:
- How do you handle the case when all tasks are blocked?
- What if a task monopolizes the CPU (never yields)?
- How do you prevent race conditions in scheduler data structures?
5.6 Thinking Exercise
Before coding, trace through this scenario by hand:
SCENARIO: Two tasks, 10ms time slice
Time 0: Task A starts running
- A's registers: EAX=1, EBX=2, ESP=0x1000
- A calls function foo()
- Stack now has return address
Time 5ms: Task A still running in foo()
- EAX=5, EBX=2, ESP=0x0FF0 (used some stack)
Time 10ms: Timer interrupt!
1. What is pushed to A's stack by the interrupt?
2. After ISR saves registers, what does A's stack look like?
3. A's ESP saved to TCB. What value?
4. B's ESP loaded. What happens next?
Draw A’s stack at each step. This is exactly what happens in your code.
5.7 Hints in Layers
Hint 1 - Starting Point: Start with cooperative multitasking only. Don’t add timer preemption until yield() works perfectly. Create a simple switch_context that only handles voluntary yields.
Hint 2 - Next Level: The switch_context function signature should be:
void switch_context(tcb_t *old, tcb_t *new);
In assembly, this means:
[ebp+8]= old TCB pointer[ebp+12]= new TCB pointer- Save ESP to
[old + offset_of_esp] - Load ESP from
[new + offset_of_esp]
Hint 3 - Technical Details: Stack setup for a new task:
void setup_task_stack(tcb_t *task, void (*entry)(void)) {
uint32_t *sp = (uint32_t*)(task->stack_base + task->stack_size);
// Decrement and fill stack from top
*(--sp) = (uint32_t)task_exit; // Return address if task returns
*(--sp) = (uint32_t)entry; // Entry point (switch will "ret" to this)
*(--sp) = 0; // EBP
*(--sp) = 0; // EBX
*(--sp) = 0; // ESI
*(--sp) = 0; // EDI
task->esp = (uint32_t)sp;
}
Hint 4 - Debugging: Add debug output everywhere at first:
void timer_isr_handler(void) {
serial_print("[TIMER] Tick! Current: ");
serial_print(current_task->name);
tcb_t *old = current_task;
tcb_t *new = schedule();
if (old != new) {
serial_print(" -> ");
serial_print(new->name);
}
serial_print("\n");
if (old != new) {
switch_context(old, new);
}
pic_send_eoi(0);
}
5.8 The Interview Questions They’ll Ask
- “Explain what happens during a context switch.”
- Expected: Save registers, save SP to TCB, load SP from new TCB, restore registers, return to new task
- “What is a Task Control Block and what does it contain?”
- Expected: ID, state, saved registers/SP, stack info, scheduling data
- “What’s the difference between cooperative and preemptive multitasking?”
- Expected: Cooperative requires yield(), preemptive uses timer interrupt
- “How does the scheduler decide which process runs next?”
- Expected: Round-robin (equal time), priority (higher first), MLFQ (adaptive)
- “What is a race condition and how would you prevent one in your scheduler?”
- Expected: Concurrent access to shared data; disable interrupts or use locks
- “Why do we need an idle task?”
- Expected: CPU must execute something; idle task runs when all others blocked
- “What happens if a process returns from its main function?”
- Expected: Should call exit/terminate; without handling, undefined behavior
5.9 Books That Will Help
| Topic | Book | Chapters |
|---|---|---|
| Process Concept | “Operating Systems: Three Easy Pieces” by Arpaci-Dusseau | Ch. 4-6 |
| Scheduling | “Operating Systems: Three Easy Pieces” | Ch. 7-9 |
| Context Switching | “Operating Systems: Three Easy Pieces” | Ch. 6 |
| x86 Details | “Operating Systems: From 0 to 1” (free online) | Ch. 5-6 |
| Implementation | “The Little Book About OS Development” | Ch. 5-6 |
5.10 Implementation Phases
Phase 1: TCB and Manual Switching (Week 1)
- Define TCB structure
- Create task_create() function
- Write switch_context() assembly
- Manually call switch_context() in main() to test
Phase 2: Cooperative Scheduler (Week 1-2)
- Implement ready queue (linked list)
- Write schedule() function (round-robin)
- Implement yield() that calls scheduler
- Create 2-3 test tasks that yield to each other
Phase 3: Timer Preemption (Week 2-3)
- Set up PIT for 10ms interrupts
- Write timer ISR that saves context
- Integrate scheduler into timer ISR
- Test preemption without yield()
Phase 4: Task Lifecycle (Week 3-4)
- Implement task_exit() / terminate
- Handle task returning from entry function
- Clean up terminated tasks
- Add idle task
Phase 5: Polish (Week 4-6)
- Add debugging output
- Implement statistics (run counts, switches)
- Add priority scheduling (optional)
- Test edge cases (all tasks blocked, etc.)
5.11 Key Implementation Decisions
| Decision | Option A | Option B | Recommendation |
|---|---|---|---|
| TCB storage | Static array | Dynamic alloc | Static (simpler, no malloc needed) |
| Ready queue | Array | Linked list | Linked list (easier add/remove) |
| Stack size | Fixed | Variable | Fixed 4KB (simpler) |
| Timer frequency | 10ms | 1ms | 10ms (less overhead) |
| Interrupt handling | Disable during switch | Lock-free | Disable (much simpler) |
6. Testing Strategy
6.1 Unit Testing
// Test 1: TCB creation
void test_tcb_create(void) {
tcb_t *task = task_create("test", test_func, 4096, 1);
assert(task != NULL);
assert(task->state == TASK_READY);
assert(task->stack_base != NULL);
assert(task->esp != 0);
serial_print("TCB create: PASS\n");
}
// Test 2: Context switch preserves registers
volatile uint32_t test_value = 0;
void task_a(void) {
register uint32_t eax __asm__("eax") = 0xDEADBEEF;
yield();
if (eax != 0xDEADBEEF) {
serial_print("Register corruption!\n");
} else {
serial_print("Registers preserved: PASS\n");
}
test_value = 1;
while(1) yield();
}
6.2 Integration Testing
// Test: Two tasks alternate correctly
void test_alternating(void) {
volatile int counter_a = 0;
volatile int counter_b = 0;
// Create tasks that increment counters
task_create("A", task_counter_a, 4096, 1);
task_create("B", task_counter_b, 4096, 1);
// Run for 100 ticks
while (scheduler.tick_count < 100);
// Both should have run multiple times
assert(counter_a > 10);
assert(counter_b > 10);
serial_print("Alternating test: PASS\n");
}
6.3 Stress Testing
// Create many tasks, ensure stability
void test_many_tasks(void) {
for (int i = 0; i < MAX_TASKS; i++) {
char name[16];
sprintf(name, "task_%d", i);
task_create(name, stress_task, 4096, 1);
}
// Run for 1000 ticks
while (scheduler.tick_count < 1000);
// Check all tasks ran
assert(scheduler.context_switches > 900);
serial_print("Stress test: PASS\n");
}
7. Common Pitfalls & Debugging
7.1 Common Pitfalls
| Symptom | Likely Cause | Fix |
|---|---|---|
| Triple fault on first switch | Stack setup wrong | Check stack initialization, ensure return address is valid |
| Task runs once then hangs | ESP not saved/restored correctly | Verify switch.asm offsets match TCB struct |
| Register values corrupted | Missing push/pop in switch | Save all callee-saved registers |
| Timer never fires | PIT not configured | Check PIT initialization, IRQ0 enabled |
| Scheduler starves tasks | Queue corruption | Verify next/prev pointers after add/remove |
| Crash on task exit | No exit handling | Ensure task_exit() switches to another task |
| Interrupt in switch causes crash | Interrupts not disabled | Disable interrupts during switch_context |
7.2 Debugging Techniques
Serial Debugging:
#define DEBUG_SCHED 1
#if DEBUG_SCHED
#define sched_debug(msg, ...) serial_printf("[SCHED] " msg "\n", ##__VA_ARGS__)
#else
#define sched_debug(msg, ...)
#endif
void schedule(void) {
sched_debug("Entering scheduler, current=%s", current->name);
// ...
sched_debug("Selected next=%s", next->name);
}
GDB with QEMU:
# In switch.asm, set a breakpoint:
(gdb) break switch_context
(gdb) continue
# When hit, examine:
(gdb) info registers
(gdb) x/16x $esp # Show stack
(gdb) print *(tcb_t*)$eax # Show old TCB
(gdb) print *(tcb_t*)$edx # Show new TCB
# Single-step through assembly:
(gdb) si
(gdb) info registers
Stack Visualization:
void dump_stack(tcb_t *task) {
serial_printf("Stack dump for %s (ESP=0x%x):\n", task->name, task->esp);
uint32_t *sp = (uint32_t*)task->esp;
for (int i = 0; i < 16; i++) {
serial_printf(" [ESP+%02d] 0x%08x\n", i*4, sp[i]);
}
}
7.3 The Classic Bugs
Bug 1: Switching to self
// WRONG
void schedule(void) {
current = current->next;
switch_context(old, current); // old == current!
}
// RIGHT
void schedule(void) {
tcb_t *old = current;
current = current->next;
if (old != current) {
switch_context(old, current);
}
}
Bug 2: Forgetting interrupt reentrancy
// WRONG - timer fires during schedule, corrupts state
void timer_handler(void) {
schedule();
pic_eoi();
}
// RIGHT - disable interrupts during scheduling
void timer_handler(void) {
cli(); // Disable interrupts
schedule();
pic_eoi();
sti(); // Re-enable in new task
}
Bug 3: Wrong TCB offset in assembly
; WRONG - assuming esp is at offset 0
mov [eax], esp
; RIGHT - use actual offset
TCB_ESP equ 20 ; Calculate from struct layout!
mov [eax + TCB_ESP], esp
8. Extensions & Challenges
8.1 Beginner Extensions
- Add task priorities: Higher priority runs first
- Implement sleep(): Task blocks for N milliseconds
- Add task names to debug output: Pretty-print scheduler state
- Implement task statistics: Track run time, switch count
8.2 Intermediate Extensions
- Implement blocking/waking: Tasks can wait for events
- Add semaphores: Counting synchronization primitive
- Implement message passing: Tasks communicate via queues
- Variable time slices: Different quanta for different priorities
8.3 Advanced Extensions
- Add user mode: Tasks run in Ring 3, kernel in Ring 0
- Implement processes: Separate address spaces (requires paging)
- Add preemptive priority: Higher priority preempts lower
- Implement SMP: Run on multiple CPU cores
8.4 Expert Challenges
- Port to ARM Cortex-M: Use PendSV for context switch
- Implement CFS-like scheduler: Completely Fair Scheduler
- Add real-time support: Deadline scheduling
- Implement user-space threading: M:N threading model
9. Real-World Connections
9.1 How Linux Does It
Linux’s task_struct: ~600+ fields including:
struct thread_info: Architecture-specific contextpid_t pid, tgid: Process and thread group IDsstruct mm_struct *mm: Address spacestruct sched_entity se: CFS scheduling info
Linux’s context switch:
__switch_to()in arch/x86/kernel/process_64.c- Saves/restores FPU state
- Updates the TSS (Task State Segment)
- Switches page tables for processes
9.2 How Windows Does It
Windows’ ETHREAD/KTHREAD:
- Similar concept to TCB
KTHREADfor kernel threading stateETHREADextends with process information
Windows’ scheduler:
- Multi-level feedback queue
- 32 priority levels
- Real-time priorities 16-31
- Variable time quanta based on priority
9.3 Career Applications
Operating Systems Developer:
- Kernel teams at Microsoft, Apple, Google
- Linux kernel contributors
- RTOS vendors (Wind River, Green Hills)
Embedded Systems:
- Automotive (AUTOSAR)
- Aerospace (DO-178C certified)
- Medical devices
Game Development:
- Custom task systems for game engines
- Fiber-based job systems
- Lock-free task queues
10. Resources
10.1 Essential Reading
| Resource | URL/Location | Usage |
|---|---|---|
| OSTEP (Free Book) | ostep.org | Chapters 4-9 (processes, scheduling) |
| OSDev Wiki | wiki.osdev.org | Context switching, scheduling articles |
| Intel SDM | Intel Developer | Interrupt/exception handling |
| James Molloy Tutorial | jamesmolloy.co.uk | Multitasking chapter |
10.2 Reference Implementations
| Project | URL | Notes |
|---|---|---|
| xv6 | github.com/mit-pdos/xv6-public | MIT teaching OS |
| ToaruOS | github.com/klange/toaruos | Hobby OS with good scheduler |
| MINIX 3 | minix3.org | Tanenbaum’s teaching OS |
| SerenityOS | serenityos.org | Modern hobby OS in C++ |
10.3 Video Resources
- YouTube: “Write Your Own Operating System” - Series covering context switching
- MIT 6.828 Lectures - Operating System Engineering course
- OSTEP Video Lectures - Author’s explanations
11. Self-Assessment Checklist
Before Starting
- I can explain x86 protected mode (Project 6)
- I understand how interrupts work (Project 7)
- I can write simple x86 assembly
- I understand the stack and calling conventions
After Phase 2 (Cooperative)
- I can explain what’s in a TCB
- I understand why we push registers in a specific order
- Two tasks alternate via yield()
- I can trace through switch_context instruction by instruction
After Phase 3 (Preemptive)
- I understand the difference between interrupt and call
- Timer fires every 10ms and triggers switches
- Tasks don’t need to yield() to share CPU
- I can explain EXC_RETURN and IRET
After Completion
- All test cases pass
- System is stable over 10,000 timer ticks
- I can create, run, and terminate tasks
- I can answer all interview questions in section 5.8
- I could implement this on a different architecture
12. Submission / Completion Criteria
Your project is complete when:
- Functionality:
- At least 4 tasks run concurrently
- Cooperative yield() works correctly
- Timer preemption works (tasks don’t need to yield)
- Tasks can terminate cleanly
- Idle task runs when others blocked
- Round-robin scheduling is fair
- Code Quality:
- Clean separation of concerns (task.c, scheduler.c, etc.)
- No warnings with -Wall -Werror
- Assembly is well-commented
- Debug output can be disabled
- Testing:
- Tested with QEMU for extended runs
- Context switch preserves all registers
- No memory corruption or leaks
- Edge cases handled (all tasks blocked, etc.)
- Understanding:
- Can explain every line of switch.asm
- Can modify time slice duration
- Can add a new scheduling algorithm
- Understands interrupt-safety requirements
Summary
This project takes you to the heart of operating systems. You’ll understand:
- Process abstraction - How OSes create the illusion of many programs running
- Context switching - The critical assembly that makes it all work
- Scheduling - How the kernel decides who runs next
- Preemption - Using hardware timers to enforce time-sharing
These concepts are used in every modern OS: Linux, Windows, macOS, iOS, Android. Understanding them deeply will transform how you think about concurrent programming and system design.
Estimated time: 4-6 weeks for complete implementation Difficulty: Master (requires understanding of Projects 5-8) Reward: You’ve built the core of an operating system
Next: P11-filesystem-driver.md - Implement a FAT16 file system driver