"Excuse Me, It's My Turn"
How does the scheduler actually take the CPU away from a running process? This is the question of preemption.
Early operating systems used cooperative multitasking: the OS had to wait for a program to voluntarily call a yield() function or make a system call. If a program entered an infinite loop, the entire machine froze. This was the model used by early versions of Windows (3.x) and classic Mac OS.
Modern Linux uses preemptive multitasking. The kernel programs a hardware timer (the scheduler tick, historically at 250Hz or 1000Hz — meaning every 4ms or 1ms) to fire a timer interrupt. When the interrupt fires:
- The CPU pauses the currently running process.
- Control transfers to the kernel's interrupt handler.
- The scheduler runs, evaluates
vruntimevalues, and decides whether to switch. - If a switch is warranted, the context switch occurs. Otherwise, the current process resumes.
Kernel Preemption
Linux also supports kernel preemption (enabled by default since 2.6): the scheduler can preempt a process even while it is executing kernel code (a system call), not just user-space code. This dramatically improves responsiveness for interactive workloads. The PREEMPT_RT patch (now partially merged into mainline) takes this further, making nearly all kernel code preemptible to support hard real-time workloads.
Voluntary Preemption
Between full preemption and no preemption is voluntary preemption (CONFIG_PREEMPT_VOLUNTARY), where the kernel inserts explicit preemption points in long kernel code paths. This is a middle ground used in some server-optimized kernel builds where the overhead of full preemption is undesirable.