CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 1 of 7 · 1 min read

Why this page comes fifth

In this module you will

  • Explain proportional-share scheduling and where it differs from the earlier policies.
  • Compute the expected shares in lottery scheduling and trace stride scheduling.
  • Explain virtual runtime and how nice values become weights.
  • Check the effect of nice on a real Linux machine.
  • Describe in outline how the Linux scheduler picks the next task (EEVDF).

Pages 2 to 4 aimed at short turnaround or quick response. A different aim is fairness in the sense of a promised share: a user paid for 25 per cent of the machine and must get it. This idea, proportional share, is the base of the Linux scheduler that runs the machine this page was tested on. The sources are "Operating Systems: Three Easy Pieces" (OSTEP), chapter 9, "Operating System Concepts" (OSC), chapter 5, "The Linux Programming Interface" (TLPI), chapter 35, and the Linux kernel documentation of the EEVDF scheduler. The measurements come from a two-processor Linux machine with kernel 6.18.

About this example About this example

Real: The facts, definitions and algorithms on this page come from the books named in the text. No program on this page was timed.

Scripted: Numbers marked "made up to show the idea" were chosen for the examples.

Not real: The page simplifies real systems. Actual kernels add more cases, limits and tuning than a short page can show.