Skip to main content

Source: Operating Systems: Three Easy Pieces (OSTEP) — Chapter 31, Arpaci-Dusseau & Arpaci-Dusseau

Semaphores

Dijkstra introduced the semaphore as one primitive for synchronization [D68b,D72] — usable as both a lock and a condition-like ordering tool.

Crux: how to use semaphores? Binary vs general? Build them from locks/CVs (and the reverse)?

Definition​

POSIX: sem_init, sem_wait (historically P / down), sem_post (V / up).

wait:  value--;  if value < 0 → sleep
post:  value++;  if waiters → wake one

Assume these steps are atomic (implemented with locks underneath). When negative, Dijkstra’s view: magnitude ≈ number waiting (Linux “Zemaphores” often never go below 0).

Binary semaphore = lock​

Init to 1. wait before CS, post after. Second waiter drives value to −1 and sleeps until the holder posts.

Ordering (join)​

Init to 0. Parent wait, child post. Works whether parent waits first (sleeps at −1) or child posts first (parent sees 1 and returns).

Producer / consumer​

Semaphores empty=MAX, full=0. Producer: wait(empty); put; post(full). Consumer: wait(full); get; post(empty).

Race: concurrent put/get on indices need a mutex.

Deadlock: wait(mutex) then wait(full) while holding mutex — producer cannot enter to post(full).

Fix: wait on empty/full outside; hold mutex only around put/get (Fig 31.12).

Quiz

Rank the sequence

1 / 1

Order a producer's steps in the fixed (deadlock-free) bounded-buffer semaphore solution.

OrderDrag the handle to rearrange — top should be first.

  1. 1put the item
  2. 2Lock mutex
  3. 3wait(empty)
  4. 4Unlock mutex
  5. 5post(full)

Drag items into the correct order (or use ↑↓), then check.

Reader-writer locks​

Allow many concurrent readers or one writer [CHP71]. First reader takes writelock; last reader releases it. Writers only take writelock.

Useful pattern — but can starve writers, and fancy R/W often loses to a simple lock (Hill’s Law: simple/dumb can be fastest).

Dining philosophers​

Five philosophers, five forks (semaphores=1). Need left+right to eat.

Broken: everyone wait(left) then wait(right) → circular wait / deadlock.

Fix: break the cycle (e.g. philosopher 4 acquires right then left) [D71].

Quiz

Rank the sequence

1 / 1

Order the events that produce deadlock when every dining philosopher acquires forks left-then-right.

OrderDrag the handle to rearrange — top should be first.

  1. 1No philosopher can acquire a right fork; all block forever
  2. 2Every philosopher holds their left fork
  3. 3Each philosopher then calls wait(right), which is already held by their neighbor
  4. 4Each philosopher calls wait(left) simultaneously

Drag items into the correct order (or use ↑↓), then check.

Implementing semaphores​

Zemaphore: mutex + CV + value; wait while value<=0; post increments and signals (Fig 31.16). Building CVs out of semaphores is surprisingly hard [B04].

Be careful with generalization

Semaphores generalize locks+CVs — but Lampson: “Don’t generalize; generalizations are generally wrong” [L83].

Interactive​

Try: binary/join · prod/cons deadlock vs fix · reader-writer · dining philosophers.

Check your understanding​

Quiz

Semaphores

1 / 6

To use a semaphore as a mutex, initialize it to…

Pick an answer to see if you are right.

Coding challenges​

Homework lab: semaphore puzzles​

Use the OSTEP semaphore homework (and Downey’s Little Book for more).

Lab

Homework: threads-sema

0/5 started

Loading lab…

Summary​

UseInitPattern
Lock1wait / CS / post
Join / signal event0waiter wait; signaler post
Bounded bufferempty=MAX, full=0, mutex=1resource waits outside mutex
R/Wwritelock=1first/last reader gate writers
Philosophersforks=1break circular acquire order

Previous: Condition Variables

Next: Common Concurrency Problems — atomicity, order, deadlock.

Further Reading​