CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 1 of 7 · 1 min read

Why this page comes first

In this module you will

  • Identify the critical section in a piece of code and explain why it needs protection.
  • State the three requirements of a solution: mutual exclusion, progress and bounded waiting.
  • Show with a trace why a lock variable, strict alternation and two flags each fail.
  • Trace Peterson's algorithm and check it against the three requirements.
  • Explain why Peterson's algorithm breaks on a real processor without ordering guarantees, with measured evidence.

Level 2, page 4 showed that two threads incrementing one counter lose updates, and fixed it with a mutex, without explaining how a mutex can work. This level explains it from the ground up. This page states the problem exactly and tests the first solutions, so that every later tool (atomic instructions, mutexes, condition variables, semaphores) can be judged against the same three requirements. The main sources are "Operating System Concepts" (OSC), chapters 6 and 7, "Operating Systems: Three Easy Pieces" (OSTEP), chapters 26 and 28, and "Modern Operating Systems" (MOS), chapter 2. All programs were compiled with gcc -O2 -Wall -Wextra -pthread and run on a two-processor Linux machine.

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: The worked traces use small numbers chosen so they can be followed by hand.

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