semaphores

Semaphores are a class of synchronization primitives used to coordinate access to shared resources in concurrent programming. They encapsulate a non-negative integer counter and provide two atomic operations, commonly known as wait (P) and signal (V). A wait decrements the counter if it is positive; if it is zero, the calling thread blocks until another thread signals. A signal increments the counter and may wake a waiting thread. Implementations ensure atomicity and establish memory ordering guarantees.

Semaphores come in two primary forms: counting semaphores, which track a resource pool with a configurable count, and binary semaphores, whose counter is restricted to zero or one. A binary semaphore is often used as a mutex, though the latter typically carries ownership semantics, ensuring the thread that locked the resource is the one to unlock it. Semaphores differ from condition variables in that they encapsulate both resource counting and synchronization in a single primitive.

Semaphores are provided by operating systems and run-time libraries, and may be implemented using atomic instructions and waiting queues. They can be used to implement resource pools, limit concurrency, and coordinate producer-consumer patterns or phased barriers. When used incorrectly, they can lead to deadlocks, priority inversion, or starvation; careful design and, when possible, higher-level constructs can mitigate these risks.

Historically, the term semaphore traces to signaling systems used to convey information, such as flag signaling. In computing, Edsger W. Dijkstra introduced the semaphore concept in the late 1960s as a formal synchronization primitive for cooperating sequential processes.