- The Linux scheduler manages CPU allocation, determining which task runs next on each core, balancing speed and fairness.
- It schedules task_struct objects, representing execution flows, with processes and threads being the same internally but differing in shared resources.
- Linux uses scheduling classes in a priority order: stop, deadline, rt (real-time), fair, ext, and idle, with fair handling most common workloads.
- Tasks stop running by either voluntarily blocking (e.g., waiting for I/O) or being preempted via the TIF_NEED_RESCHED flag, with switches occurring at safe points like returning to user space.
- Preemption is triggered by the periodic timer tick or wakeups, where a newly runnable task may be deemed more deserving than the current one.
- Context switches involve saving/loading CPU state and can incur significant costs due to cache and TLB invalidation, leading the scheduler to minimize unnecessary switches.
- The fair class uses the EEVDF (Earliest Eligible Virtual Deadline First) algorithm, based on virtual runtime, eligibility, and virtual deadlines to ensure fairness and low latency.
- Virtual runtime (vruntime) adjusts real time by task weight (from nice values), with heavier tasks having slower vruntime progression, granting them more CPU share.
- Eligibility ensures tasks only run if they are not ahead of their fair share (based on average vruntime), preventing starvation.
- Tasks receive a virtual deadline from their vruntime plus slice (converted by weight), with the scheduler picking the eligible task with the earliest deadline, favoring shorter slices for better latency.