OS Scheduling¶
Why preemptive: without preemption, a buggy process loops forever, starving all others. Timer interrupt every ~1ms allows the kernel to preempt any task.
FCFS: arrival order, simple, convoy effect — long jobs block short ones.
Round Robin: time quantum per task, fair, good response time, quantum size trade-off (too small = context switch overhead, too large = FCFS behavior).
Priority: highest priority first, starvation risk, solved by aging.
CFS (Linux default): tracks vruntime per task in a red-black tree. Lowest vruntime runs next. Lower nice = smaller vruntime increments = more CPU time. Preemption at every timer tick if current task has run disproportionately.
Cooperative vs preemptive (Go): Go was cooperative until Go 1.14 (yield only at function calls — a tight loop would never yield). Go 1.14 added asynchronous preemption via SIGURG: Go runtime sends SIGURG to the M's OS thread after 10ms, causing the goroutine to yield at any safe point.
Worked example — the FCFS convoy effect: process A arrives first needing a 100ms CPU burst; processes B and C arrive right after, each needing only 1ms. Under FCFS, B and C — despite being nearly instant — sit in the queue for the full 100ms while A runs to completion, then finish immediately after. Average wait time across the three: (0 + 100 + 101) / 3 ≈ 67ms, almost entirely caused by two 1ms jobs being stuck behind one long one. Under round robin with a 10ms quantum, A runs for 10ms, gets preempted, and B and C each get their full 1ms turn within the next 20ms of wall-clock time — both finish almost immediately instead of waiting 100ms, at the cost of A now taking slightly longer than 100ms wall-clock to finish because it's timesliced with the others.
Worked example — CFS vruntime: two nice 0 tasks A and B are both runnable, vruntime = 0 for each. The scheduler picks A (tie), runs it for 5ms, and A's vruntime becomes 5ms. On the next scheduling decision, B has the lower vruntime (0 < 5), so B runs next — for 5ms, reaching vruntime = 5ms too. The two tasks alternate in lockstep, each accumulating CPU time at the same rate, which is exactly CFS's fairness goal: always run whichever runnable task has received the least CPU time so far, tracked in a red-black tree keyed by vruntime so "find the minimum" is a cheap O(log n) operation rather than a linear scan.