Book 13 · Operating SystemsPage 26 of 37

Semaphore

In Turkish: semafor
Pronunciation: SEM-uh-for

Updated September 30, 20263 min read

In short

A semaphore is a synchronization tool that keeps a counter of available permits, letting up to a fixed number of threads use a resource at the same time.

What is a semaphore in programming?

A semaphore is a counter shared between threads or processes, with two atomic operations. Acquiring, also called wait or P, takes a permit and decrements the counter, blocking if no permits are left; releasing, also called signal or V, returns a permit and wakes a waiting thread. The idea was introduced by Edsger Dijkstra in the 1960s and is one of the oldest synchronization tools.

A counting semaphore starts at some number N and lets up to N threads hold a permit at once, for example to allow only five simultaneous downloads or database connections. A binary semaphore has only the values 0 and 1. Unlike a mutex, a semaphore has no owner, so one thread can release a permit that another acquired, which makes semaphores useful for signaling: a producer releases a permit each time it adds an item, and a consumer acquires one before taking an item. Operating systems also offer named semaphores that separate processes can share.

A semaphore works like a parking garage with a sign showing the number of free spaces. Each car that enters takes a space, and when the count reaches zero, new cars wait at the gate until someone leaves. Semaphores are used to limit concurrency, build bounded buffers between producers and consumers, and cap how many requests hit a fragile service at once.

Semaphores are most often confused with mutexes. A binary semaphore looks like a mutex, but because it has no owner it lacks protections such as detecting that the wrong thread released it; use a mutex to guard shared data and a semaphore to limit how many or to signal between threads. Like mutexes, semaphores prevent race conditions only when every access goes through them, and forgotten releases or inconsistent ordering can still cause deadlocks. A semaphore also limits concurrency, how many things run at once, which is different from rate limiting, how many things happen per second.

Key takeaways

A semaphore holds a count of permits that threads acquire and release.
A counting semaphore lets up to N threads use a resource at once.
A semaphore has no owner, so any thread can release a permit.
It is well suited to limiting concurrency and signaling between threads.
Use a mutex, not a semaphore, to protect a single piece of shared data.

Example

Limiting concurrent downloads in Pythonpython

import asyncio

limit = asyncio.Semaphore(3)  # at most 3 downloads at once

async def download(n):
    async with limit:           # take a permit, or wait if none are left
        print(f"start {n}")
        await asyncio.sleep(1)  # pretend to download
        print(f"done {n}")      # the permit is returned here

async def main():
    await asyncio.gather(*(download(i) for i in range(10)))

asyncio.run(main())

Readers ask

What is the difference between a semaphore and a mutex?

A mutex allows one thread at a time and belongs to the thread that locked it. A semaphore allows up to a set number of threads and can be released by any thread, which also makes it useful for signaling.

What is a binary semaphore?

A binary semaphore is a semaphore whose counter can only be 0 or 1. It behaves much like a lock but has no owner, so it is often used for signaling that an event has happened.

What do P and V mean for semaphores?

They are Dijkstra's original names for the two operations, taken from Dutch words. P means acquire or wait, and V means release or signal.

Often compared

Mutex vs SemaphoreA mutex lets one thread at a time use a shared resource and only its owner releases it, while a semaphore is a counter that lets up to N threads in at once.