CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 1 of 7 · 1 min read

Why this page comes fourth

In this module you will

  • Trace priority scheduling, preemptive and non-preemptive.
  • Explain starvation and show how aging removes it.
  • Describe priority inversion and the usual cure.
  • State the rules of a multilevel feedback queue and trace one.
  • Explain why such a scheduler needs a periodic boost.

Pages 2 and 3 gave two ideas that pull in opposite directions: finish short jobs first, and give everyone a turn. This page combines them. A priority says who is more important, and the multilevel feedback queue learns from each process's past behaviour which ones are short, without asking anyone. It is the design behind the schedulers of several real systems, and the clearest example of a scheduler that adapts. The sources are "Operating Systems: Three Easy Pieces" (OSTEP), chapter 8, "Operating System Concepts" (OSC), chapter 5, and "Modern Operating Systems" (MOS), chapter 2.

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.