CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 1 of 7 · 1 min read

Why this page comes second

In this module you will

  • Define an atomic operation and name the three common ones: fetch-and-add, test-and-set and compare-and-swap.
  • Build a spinlock from test-and-set and show that it gives mutual exclusion.
  • Write a lock-free counter with a compare-and-swap loop.
  • Explain what busy waiting costs and when it is acceptable.
  • Interpret measured timings of atomic add, spinlocks and a mutex on two, four and eight threads.

Page 1 ended with a problem: software-only locks such as Peterson's algorithm need ordering guarantees that ordinary reads and writes do not give, and they work only for two threads. The remedy is a small set of special instructions in the processor that read and change memory in one indivisible step. Every lock in an operating system, including the mutex of the next page, is built from them. The sources are "Operating Systems: Three Easy Pieces" (OSTEP), chapter 28, "Operating System Concepts" (OSC), chapter 6, and "The Linux Programming Interface" (TLPI), chapter 30. The timings come from a two-processor Linux machine, with each test repeated five times.

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.