CSE Roadmap

Core tier · about 4 hours · 7 parts

Part 1 of 7 · 1 min read

Why this page comes second

In this module you will

  • Trace first come first served (FCFS) and compute its waiting times.
  • Explain the convoy effect with a numeric example.
  • Trace shortest job first (SJF) and its preemptive form, shortest remaining time first (SRTF).
  • Predict the next CPU burst with an exponential average.
  • Explain starvation and why SJF cannot be used exactly in practice.

Page 1 defined the three times and used first come first served without naming it. This page names it, shows its weakness, and then reorders the same four processes to get a better result. Both policies are simple enough to trace by hand, and the traces are the model for the policies on the next pages. The sources are "Operating Systems: Three Easy Pieces" (OSTEP), chapter 7, and "Operating System Concepts" (OSC), chapter 5. The traces were also produced by a short program in C, shown in section 2, and every figure here agrees with it.

About this example About this example

Real: The C programs, commands and outputs on this page were compiled with gcc -Wall -Wextra -pthread and run on a Linux test machine (2 processors, kernel 6.18, glibc 2.39).

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.