Understanding the Linux Kernel: The Scheduler
15 hours ago
- #EEVDF Algorithm
- #Task Scheduling
- #Linux Scheduler
- The Linux scheduler manages CPU allocation among tasks, using a multi-class system where tasks are scheduled based on priority and fairness.
- Tasks are represented as `task_struct` in the kernel, with processes and threads being the same underlying object but differing in shared resources like memory.
- Scheduling classes are stacked in priority order: `stop`, `deadline`, `rt`, `fair`, `ext`, and `idle`, with `fair` handling most ordinary workloads.
- A task stops running either by voluntarily blocking (e.g., waiting for I/O) or through preemption triggered by a flag (`TIF_NEED_RESCHED`), which is checked at safe points like returning to user space.
- Preemption is initiated by periodic timer ticks (to enforce time slices) or wakeups (when a higher-priority task becomes runnable), ensuring responsiveness.
- Context switches involve saving/restoring CPU state and incur costs from cold caches and TLB misses, leading the scheduler to minimize unnecessary switches.
- The `fair` class uses the EEVDF algorithm, which selects tasks based on virtual runtime, eligibility (ensuring fairness), and earliest virtual deadline (for low latency).
- Virtual runtime (`vruntime`) weights CPU time by task priority (via `nice` values), so higher-priority tasks accrue it slower and get more CPU share.
- Eligibility prevents tasks ahead of their fair share from running, while deadlines are computed from `vruntime` plus slice divided by weight, favoring shorter bursts for interactive tasks.
- EEVDF picks the eligible task with the earliest deadline using an augmented red-black tree for O(log n) efficiency, and tasks are guaranteed a minimum slice to avoid thrashing.