CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 1 of 7 · 1 min read

Why this page comes seventh

In this module you will

  • Explain the readers-writers problem and use a read-write lock.
  • Show that readers can starve a writer, and the opposite, with measured evidence.
  • State the dining philosophers problem and show why the obvious solution deadlocks.
  • Fix the problem in two ways: lock ordering and limiting the number at the table.
  • Choose between a mutex and a read-write lock for a given workload.

The producer-consumer pattern of page 6 is one of three classic problems. This page covers the other two. The readers-writers problem asks what to do when most users only read shared data: exclusion for everyone wastes parallelism. The dining philosophers problem asks what happens when threads need several locks at once, the situation that causes deadlocks, which Level 5 studies in full. Both are small enough to run and measure. The sources are "Operating System Concepts" (OSC), chapter 7, "Operating Systems: Three Easy Pieces" (OSTEP), chapters 31 and 32, and "Modern Operating Systems" (MOS), chapter 2. All programs were compiled with gcc -O2 -Wall -Wextra -pthread 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.