Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 66 ยท Synchronization

Semaphores: Counting, Binary and Signaling

Learn how semaphores work with wait and signal, the difference between counting and binary semaphores, and run a tiny Python kernel that blocks and wakes threads.

Spinlocks and mutexes protect a critical section, but many problems need more. A thread may have to wait until a resource is available, or until another thread has finished a step. In 1965 Edsger Dijkstra introduced a single, general tool for both: the semaphore.

A semaphore is an integer variable that can only be changed through two atomic operations:

  • wait (also P, down, acquire): if the value is greater than zero, decrement it and continue. Otherwise block the caller on the semaphore's queue.
  • signal (also V, up, release, post): if some thread is waiting, wake one of them; otherwise increment the value.
TEXT
wait(S):                        signal(S):
    if S.value > 0:                 if S.queue is not empty:
        S.value -= 1                    wake one thread from S.queue
    else:                           else:
        add caller to S.queue           S.value += 1
        block

(Some textbooks let the value go negative and read it as "number of sleepers". The behaviour is the same.)

A tiny kernel to experiment with

Real threads block inside the operating system. Our simulation needs the same idea, so we build a miniature one. Each thread is a generator. It yields ("P", sem) or ("V", sem) to ask the "kernel" for a semaphore operation, and a plain yield for an ordinary step. The scheduler picks a runnable thread at random, applies the operation, and puts blockers to sleep.

Python A mini kernel with 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 input()), it gets the next line from this box.

With the semaphore initialised to 1, only one thread passes P at a time. All 40 increments are counted. A semaphore used this way is a binary semaphore and behaves like a mutex.

Counting semaphores: a pool of identical resources

If the initial value is N, a counting semaphore lets N threads through at once. Think of a parking lot with N spaces: wait takes a space (or waits at the gate), signal frees one. Use it for connection pools, a fixed number of printers, or limiting concurrent downloads.

Python At most three users 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 input()), it gets the next line from this box.

Seven users compete for three slots; the peak never exceeds 3, and everyone eventually gets in.

Signaling: forcing an order

A semaphore initialised to 0 is a one-shot event. The waiting thread blocks until another thread signals. This enforces "B must run after A" without sharing any data.

Python B waits for A

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 input()), it gets the next line from this box.

Whatever the schedule, "B: using the data" always appears after "A: data ready".

Using semaphores safely

Semaphores are powerful but unforgiving. Typical mistakes:

  • Swapping or forgetting a wait/signal. signal(mutex) before wait(mutex) lets two threads in. Forgetting a signal leaves everyone blocked forever.
  • Wrong initial value. Mutex = 1, "event" = 0, pool = N.
  • Wait inside wait in different orders. Two threads that take semaphores A then B and B then A can deadlock.
  • No ownership. Any thread may signal a semaphore, even one that never waited. That makes semaphores flexible, and bugs hard to trace.

Mutex versus semaphore

Mutex Semaphore
Purpose Mutual exclusion of a critical section Count resources or signal events
Values Locked / unlocked 0, 1, 2, ...
Ownership The thread that locked must unlock Any thread may signal
Typical use Protect a data structure Pools, producer-consumer, ordering

A binary semaphore is close to a mutex, but a mutex's ownership rule enables extras such as priority inheritance (see priority inversion).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A semaphore is initialised to 1 and used around a critical section. What is it acting as?

    With value 1, the first wait succeeds and every other thread blocks until the holder signals.
  2. 2. What initial value makes 'B must wait until A signals' work?

    At 0, B's wait blocks immediately. A's signal then wakes B (or lets it pass if A signalled first).
  3. 3. A semaphore starts at 3 and four threads call wait. What happens to the fourth?

    Three waits use up the value; the fourth finds zero and is put on the queue.
  4. 4. Which statement distinguishes a semaphore from a mutex?

    Ownership is the key difference. Semaphores have no owner, which makes them flexible and easier to misuse.

Summary

  • A semaphore is an integer with atomic wait (decrement or block) and signal (wake or increment).
  • Binary semaphores (start at 1) give mutual exclusion; counting semaphores (start at N) manage N identical resources; a semaphore at 0 signals events and orders threads.
  • Blocking is done by the OS on a wait queue, so waiting threads do not burn CPU.
  • Misplaced waits and signals cause races or deadlocks; semaphores have no owner to catch the mistake.

Next: The Producer-Consumer Problem