CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 1 of 7 · 1 min read

Why this page comes fifth

In this module you will

  • State the two operations of a semaphore and the invariant that governs them.
  • Use a semaphore as a lock, as a counter of available resources and as a signal for ordering.
  • Explain the difference between a binary semaphore and a mutex.
  • Build a semaphore from a mutex and a condition variable.
  • Use the POSIX calls sem_init, sem_wait, sem_post, sem_trywait and sem_timedwait.

Page 3 gave the mutex for exclusion, and page 4 gave condition variables for waiting. Dijkstra proposed a single tool in 1965 that does both jobs: the semaphore. It is older than both, it is still used in operating systems, and it is the most direct way to count things: free buffer slots, available connections, items in a queue. Page 6 uses it for the producer-consumer problem. The sources are "Operating System Concepts" (OSC), chapter 6, "Operating Systems: Three Easy Pieces" (OSTEP), chapter 31, "Modern Operating Systems" (MOS), chapter 2, and "The Linux Programming Interface" (TLPI), chapter 53. 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.