# Writing an OS Kernel from Scratch – Part 17: Scheduler — Making Multitasking Truly Concurrent!
“Cooperative multitasking relies on programs voluntarily yielding the CPU; once there’s an infinite loop, the system freezes. Today, we introduce timer interrupts and implement a preemptive scheduler, making multitasking truly fair!”
In Part 6, we implemented cooperative multitasking, where processes switch via yield(). But this has a fatal flaw: a user program stuck in an infinite loop makes the entire system unresponsive!
A real operating system must be able to forcibly take the CPU away and fairly distribute time among multiple tasks — this is Preemptive Scheduling.
Today, we will: ✅ Enable timer interrupts (PIT) ✅ Implement a Round-Robin scheduler ✅ Support process priority and sleep queues
Give your OS true concurrency capability!
⏱️ 1. Why Do We Need Preemptive Scheduling?
Pain points of cooperative scheduling:
| Problem | Consequence |
|---|---|
| User program infinite loop | System completely freezes, unresponsive |
| I/O-intensive tasks | Frequent voluntary yielding, low CPU utilization |
| Poor real-time performance | Cannot guarantee critical tasks execute on time |
Advantages of preemptive scheduling:
Fairness: each process gets a fixed time slice (e.g., 10ms)
Responsiveness: even with an infinite loop, the system remains responsive
Controllability: control task execution order through priorities
💡 The scheduler is the “traffic police” of the operating system, deciding who gets to use the CPU and when.
🕰️ 2. Timer Interrupt: The Heartbeat of the Scheduler
x86 PCs use the PIT (Programmable Interval Timer) to generate periodic interrupts.
PIT initialization:
Register timer interrupt handler:
🔑 Each timer interrupt is an opportunity for the scheduler to check if it needs to switch tasks!
🔄 3. Round-Robin Scheduler
1. Process PCB adds scheduling fields
2. Scheduler core: scheduler_tick
3. Task switching: schedule
✅ Time slice exhausted → current process goes to queue → switch to next process
🛌 4. Sleep and Wake: Supporting Blocking Operations
A process may voluntarily sleep due to I/O (e.g., reading from keyboard) and should not use the CPU during this time.
1. Sleep queue
2. Sleep (sleep_on)
3. Wake (wake_up)
4. System call integration: blocking read example
💡 Call wake_up in interrupt handlers (e.g., when serial port receives data)
🧪 5. Test: Preemptive Multitasking
User program 1 (CPU-intensive):
User program 2 (I/O-intensive):
Run results:
Even when cpu_hog is in an infinite loop, the system still responds to keyboard input
Both processes run alternately, each using about 50% CPU
✅ Preemptive scheduling successful!
📊 6. Scheduling Policy Extensions
1. Priority scheduling
2. Dynamic priority: I/O-intensive processes → raise priority (improve responsiveness); CPU-intensive processes → lower priority (avoid hogging CPU)
3. Multi-Level Feedback Queue (MLFQ): multiple priority queues; time slice exhausted → downgrade to lower priority queue; wake from I/O blocking → upgrade to higher priority queue
💡 Linux’s CFS (Completely Fair Scheduler) is a more advanced implementation.
⚠️ 7. Key Cautions
1. Interrupt context vs process context: the scheduler cannot directly call switch_to_task in the interrupt handler. Correct approach: set need_resched, check before returning from interrupt
2. Critical section protection: when accessing the run queue / sleep queue, interrupts need to be disabled to prevent reentrancy
3. Timer interrupt handling must be as fast as possible. Interrupt handling must be efficient; only set flags, do actual work outside the interrupt
💬 Final Thoughts
The scheduler is the most core component of a multitasking operating system. It transforms a single CPU into the illusion of running multiple tasks simultaneously.
🌟 The essence of an OS is resource management; the CPU is the most precious resource of all.
📬 Hands-on challenge: Implement priority scheduling, observe execution time differences at different priority levels. Share your scheduler testing data in the comments!
👇 Next article you’d like to see: Virtual File System (VFS), or process synchronization?
#OS #KernelDevelopment #Scheduler #Preemptive #RoundRobin #PIT #Multitasking #WritingFromScratch
Comments