Skip to content
Tutorials Center
My learning

Topics

Lesson 136 of 171 ยท Concurrency

Semaphores, Deadlocks and Classic Concurrency Problems

Learn C++20 counting and binary semaphores, how they differ from mutexes, the four deadlock conditions, the dining philosophers, a bounded buffer and false sharing.

A mutex answers one question: "may I be the only one in here?" Many real problems ask a different one: "is there a free slot?", "has the other thread produced something yet?", "may another connection be opened?". For those, C++20 offers semaphores: a counter of permits that threads take and give back. Semaphores are also the setting for the classic textbook problems of concurrency (deadlock, dining philosophers, the bounded buffer), which are worth knowing because the same shapes appear in real programs.

In this lesson you'll use std::counting_semaphore and std::binary_semaphore, learn how a semaphore differs from a mutex, see the four conditions that together cause a deadlock and how to break one, solve the dining philosophers problem, build a bounded producer-consumer buffer without a condition variable, and meet false sharing, a performance trap that isn't a bug but feels like one. You should know threads and condition variables.

Counting semaphores

std::counting_semaphore<Max> from <semaphore> holds a count of available permits, between 0 and Max. The constructor sets the initial count.

  • acquire() takes one permit. If the count is 0 it blocks until another thread releases one.
  • try_acquire() takes a permit if one is free and returns true/false right away. try_acquire_for and try_acquire_until wait up to a limit.
  • release(n = 1) adds permits and wakes waiting threads.

A classic use is limiting concurrency: at most N threads may be inside a section at the same time.

C++ At most two workers at a time

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Six threads start together, but only two get a permit at a time, so the printed maximum is never above 2 (it is normally exactly 2). Unlike a mutex, nobody "owns" a permit: a thread that did not call acquire() may call release(). The template argument 4 is only an upper bound for the counter, which lets implementations pick faster code.

Binary semaphores and signalling

std::binary_semaphore is std::counting_semaphore<1>: the count is 0 or 1. Because any thread may release it, a binary semaphore works as a signal from one thread to another: start it at 0, let the waiter acquire(), and let the other thread release() when the event happens.

C++ Two threads taking turns

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The output alternates strictly, ping 1, pong 1, ping 2, and so on, whatever the scheduler does. A mutex could not do this, because the thread that locks it must be the thread that unlocks it.

Mutex or semaphore?

std::mutex std::counting_semaphore
Question it answers "Am I alone in this section?" "Is a permit available?"
Ownership The locking thread must unlock Any thread may release()
Count 0 or 1 0 up to Max
Typical use Protect shared data Limit concurrency, signal events, count free slots
RAII guard lock_guard, scoped_lock None in the standard library

Prefer a mutex to protect data: the guards make it hard to forget the unlock, and a mutex can detect misuse in debug builds. Use a semaphore when the thing you protect is a number of things (connections, buffer slots) or when one thread signals another. If you take a permit and an exception is thrown before release(), the permit is lost forever; wrap acquire()/release() in your own small RAII class when that matters.

Deadlock: the four conditions

A deadlock is a state in which threads wait for one another forever and nothing can make progress. Edward Coffman described four conditions that must all hold at once:

  1. Mutual exclusion: a resource can be held by only one thread at a time.
  2. Hold and wait: a thread holds one resource while waiting for another.
  3. No preemption: a resource can't be taken away; the holder has to release it.
  4. Circular wait: there is a cycle of threads, each waiting for a resource the next one holds.

Remove any single condition and deadlock becomes impossible. That gives you the practical cures:

  • Break hold and wait by acquiring everything at once: std::scoped_lock lock{a, b}; locks both mutexes with a deadlock-avoidance algorithm (see Mutexes).
  • Break circular wait with a global lock order: always take the lower-numbered resource first.
  • Break no preemption with try_lock and back-off: if the second resource isn't free, release the first and retry.
  • Break mutual exclusion where you can, for example with read-only sharing or lock-free atomics.

The dining philosophers

Five philosophers sit around a table. Between each pair of neighbours lies one fork, five forks in all. To eat, a philosopher needs the fork on the left and the fork on the right. If every philosopher picks up their left fork at the same moment, each waits forever for the right one: all four conditions hold, and the table is deadlocked.

The program below uses the lock-order cure: every philosopher takes the lower-numbered fork first, so a cycle can't form (the last philosopher takes fork 0 before fork 4, which breaks the circle).

C++ Dining philosophers without deadlock

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Everyone finishes with 50 meals. If you change first and second to always be left and right, the program can hang: a deadlock depends on timing, so it may run fine many times before it freezes. A shorter alternative is std::scoped_lock both{forks[left], forks[right]};, which needs no manual ordering. Another classic solution, using a counting semaphore, lets at most four philosophers sit down at once: with five forks, at least one of those four can always get two.

Deadlock has two relatives worth naming. Livelock is when threads keep reacting to each other and keep changing state without progressing, like two people stepping aside in a corridor in the same direction forever. Starvation is when one thread is never chosen: it isn't blocked forever by a cycle, the others just always win.

The bounded buffer (producer-consumer)

A producer makes items and a consumer uses them, with a buffer of fixed size between them. Two rules have to hold: the producer must wait when the buffer is full, and the consumer must wait when it is empty. Two counting semaphores express that directly: one counts free slots, one counts filled slots. A mutex protects the buffer itself.

C++ A bounded buffer with two semaphores

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The queue never holds more than 3 items, yet the program needs no sleeps and no polling. The consumer prints 36 (1 + 2 + ... + 8). Compare this with the condition-variable queue: the semaphores carry the counts for you, whereas the condition variable version needs a predicate. A semaphore version is shorter for a fixed count of items, but the condition variable version is more flexible, for example when shutting down early.

False sharing

Not every concurrency problem is a logic bug. CPUs move memory in cache lines, usually 64 bytes. If two threads write to two different variables that happen to sit on the same cache line, the line bounces between the cores on every write, and both threads slow down badly even though they never touch each other's data. This is false sharing. The fix is to pad or align the hot variables to separate cache lines with alignas(64):

C++
struct Counters {
    alignas(64) std::atomic<long> a{0};   // each counter on its own cache line
    alignas(64) std::atomic<long> b{0};
};

The standard names the size: std::hardware_destructive_interference_size in <new> (a compile-time estimate of the cache-line size, although some compilers warn that it can differ between builds). The result is always correct either way; only the speed differs, which is why false sharing is found by measuring, not by reading code. Cache and Data-Oriented Design explains cache lines in more detail.

Common mistakes

  • Treating a semaphore like a mutex. It has no owner and no RAII guard: forgetting release() after an exception leaks a permit.
  • Releasing too many permits. Releasing past Max is undefined behavior; keep every release() matched to an acquire().
  • Locking in inconsistent order. Two functions that take the same two mutexes in opposite orders can deadlock. Use one std::scoped_lock or a fixed order.
  • Waiting while holding a lock. Never acquire() a semaphore that another thread can only release after taking your mutex.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which statement about std::counting_semaphore is true?

    A semaphore has no owner. That is why it can signal between threads, unlike a mutex, which must be unlocked by the thread that locked it.
  2. 2. Which of these is NOT one of the four conditions for a deadlock?

    The four conditions are mutual exclusion, hold and wait, no preemption and circular wait. Starvation is a separate problem.
  3. 3. How does always locking the lower-numbered fork first prevent deadlock in the dining philosophers?

    With a global order a thread holding a higher resource never waits for a lower one, so a cycle of waiting threads cannot exist.
  4. 4. In the bounded buffer, what does the semaphore free_slots count?

    The producer acquires a free slot before pushing, and the consumer releases one after popping, so the producer blocks when the buffer is full.
  5. 5. What is false sharing?

    Different variables on one cache line cause the line to bounce between cores. The program is correct but slow; alignas(64) separates the variables.

Summary

  • A std::counting_semaphore is a counter of permits: acquire() waits for one, release() returns it; any thread may release. binary_semaphore is the 0/1 version, good for signalling and turn-taking.
  • Use mutexes to protect data and semaphores to limit counts or signal events.
  • A deadlock needs mutual exclusion, hold and wait, no preemption and circular wait; remove one to cure it, usually with std::scoped_lock or a fixed lock order.
  • The dining philosophers show circular wait; livelock and starvation are close relatives.
  • A bounded buffer uses two semaphores (free slots, filled slots) plus a mutex for the queue.
  • False sharing is a performance trap, fixed with alignas(64).

Next: Atomics and the Memory Model, where you'll share simple values between threads without any lock.