Unlike batch architectures that maximize total computational throughput, desktop operating systems, mobile devices, and multi-tenant web servers operate under user scrutiny. In interactive environments, the primary metric is Response Time (Tresponse)—the delay between a user action (keystroke, tap, network packet arrival) and the visible system response.
Round-Robin is the oldest, simplest, and most reliable preemptive scheduling algorithm designed for time-sharing systems:
The choice of time quantum length q fundamentally controls the balance between raw throughput and interactive responsiveness:
While Round-Robin provides exceptional fairness and guarantees an upper bound on response time (with n processes and quantum q, no process waits longer than (n − 1) × q time units before its next slice), its average turnaround time is often substantially worse than Shortest Job First.
If three processes with burst lengths of 10 ms run under RR with q = 1 ms, all three complete nearly simultaneously around T = 28, 29, and 30 ms (average turnaround ≈ 29 ms). Under SJF, they complete at 10, 20, and 30 ms (average turnaround = 20 ms). Round-Robin deliberately sacrifices average turnaround time to ensure immediate response times for all tasks.
In production systems, processes are not created equal. A critical window manager rendering 120 FPS display frames must preempt a background virus scanner. Priority scheduling assigns each task a priority integer, and the scheduler dispatches the highest-priority runnable process first.
Strict priority scheduling introduces a lethal synchronization vulnerability known as Priority Inversion:
Solution (Priority Inheritance Protocol, PIP): When task H blocks waiting for a lock held by L, the kernel temporarily boosts task L's priority to match H. Task L runs with high priority, completes its critical section rapidly, releases the lock, drops back to its base priority, and allows H to run immediately.
To prevent low-priority background processes from starving indefinitely when a stream of high-priority interactive tasks exists, schedulers implement dynamic aging. The effective priority is calculated as:
Peffective = Pbase + k × TwaitAs a task waits in the Ready queue, its priority climbs steadily. Eventually, its effective priority surpasses active interactive tasks, guaranteeing that every process receives CPU time.
Corbato's Multi-Level Feedback Queue (MLFQ) is the foundational discipline of modern general-purpose schedulers. Its objective is to solve the fundamental scheduling dilemma: how can a scheduler optimize turnaround time (like SJF) and minimize response time (like RR) without any prior knowledge of job lengths?
MLFQ learns from the past behavior of a process to predict its future behavior, establishing a hierarchy of distinct priority queues (e.g., Q0 at top priority down to Q2 at bottom priority).
Process A enters top queue Q0. The scheduler optimistically assumes the task is short and interactive, granting it immediate CPU access.
Placing unknown jobs at the top queue minimizes response time for interactive tasks while requiring zero prior declarations.
Every scheduler examined so far (FCFS, SJF, SRTN, Round-Robin, and MLFQ) operates on a priority or latency premise: they evaluate process queue states to answer the immediate operational question: "Which specific process should run next to optimize turnaround time or user responsiveness?"
Proportional-Share scheduling (also called Fair-Share scheduling) abandons this framing entirely. Instead of optimizing for completion deadlines or interface responsiveness, it treats CPU execution bandwidth as an economic resource. Its foundational question is:
"How can the operating system guarantee that over time, Process A receives exactly 75% of the processor's silicon capacity, while Process B receives exactly 25%?"
Pioneered by Carl Waldspurger and William Weihl, Lottery Scheduling uses probabilistic randomness to achieve proportional resource division:
[0, Total_Tickets − 1].A common misconception is that the kernel maintains a massive array containing millions of ticket numbers. In real operating systems, ticket tracking requires minimal memory: the scheduler maintains a linked list of runnable tasks, where each task's PCB simply stores its single integer ticket allocation.
/* Kernel Lottery Selection Algorithm: O(N) Traversal */
int total_tickets = 100;
int winning_ticket = random_int(0, total_tickets - 1); /* e.g., draws 82 */
int counter = 0;
struct task_struct *curr = ready_list_head;
while (curr != NULL) {
counter += curr->tickets;
if (counter > winning_ticket) {
/* Found the task owning the winning range! */
switch_to(curr);
break;
}
curr = curr->next;
}counter = 0 + 75 = 75. Is 75 > 82? False. Advance to next task.counter = 75 + 25 = 100. Is 100 > 82? True! Process B wins the draw and executes.The fundamental flaw of lottery scheduling is short-term variance (jitter).
While the Law of Large Numbers guarantees that a 75/25 ticket split will converge to an exact 3:1 ratio over millions of cycles, randomness does not guarantee fairness over short time windows. Just as flipping a fair coin can produce four heads in a row, Process B (the 25% task) might randomly win five consecutive draws.
If Process A is rendering a video stream or handling real-time audio playback, losing several lottery draws in a row introduces noticeable stutter and dropped audio frames.
To preserve the exact proportional guarantees of lottery scheduling while completely eliminating random variance, Waldspurger designed Stride Scheduling.
Think of Stride Scheduling as a race where runners take strides of different lengths:
K = 10,000.
Stridei = K / TicketsiStrideA = 10,000 / 75 ≈ 133.
StrideB = 10,000 / 25 = 400.
pass value):
Every process tracks its progress using a pass counter (initialized to 0).
pass value. After that process executes for one quantum, its pass counter advances by its stride:
passi += Stridei| Tick | Pass Counters Prior to Dispatch | Task Selected (MIN pass) | Pass Counter Update |
|---|---|---|---|
| 0 | Pass(A) = 0, Pass(B) = 0 | Process A (Tie-break) | Pass(A) = 0 + 133 = 133 |
| 1 | Pass(A) = 133, Pass(B) = 0 | Process B | Pass(B) = 0 + 400 = 400 |
| 2 | Pass(A) = 133, Pass(B) = 400 | Process A | Pass(A) = 133 + 133 = 266 |
| 3 | Pass(A) = 266, Pass(B) = 400 | Process A | Pass(A) = 266 + 133 = 399 |
| 4 | Pass(A) = 399, Pass(B) = 400 | Process A | Pass(A) = 399 + 133 = 532 |
| 5 | Pass(A) = 532, Pass(B) = 400 | Process B | Pass(B) = 400 + 400 = 800 |
Notice the resulting execution order: A, B, A, A, A, B. Over these 6 intervals, Process A executes 4 times and Process B executes 2 times. As time proceeds, the ratio converges precisely to 3:1 (75% vs. 25%) with zero randomness, zero jitter, and deterministic predictability.
Why do operating systems courses teach Stride and Lottery scheduling if general-purpose desktop operating systems do not roll dice?
Because Stride Scheduling is the direct conceptual ancestor of modern cloud virtualization and container resource management:
vruntime): In Linux CFS, each thread's odometer is called its vruntime. A thread with a standard nice level of 0 accumulates vruntime in lockstep with physical wall-clock time.nice), its weight is large, so its vruntime accumulates very slowly (equivalent to a tiny Stride). If a thread has low priority, its vruntime advances rapidly.vruntime. The scheduler pulls the leftmost node in O(log N) time—always choosing the task that has received the least virtual execution time.docker run --cpu-shares 1024 vs. --cpu-shares 512), the container runtime writes these values directly into the kernel's CFS cgroup weights, using the exact proportional-share mathematics first established by lottery and stride scheduling.