Dijkstra’s Semaphores and the Problem of Coordinating Concurrent Programs
Edsger Dijkstra's semaphore abstraction gave concurrent programs explicit P and V operations for mutual exclusion, resource counting and process coordination.
Concurrency turned sequencing into a coordination problem
Early programs were usually reasoned about as one sequence of operations. Multiprogramming changed that assumption. Several sequential processes could make progress during overlapping intervals, which meant that a correct local action could become globally wrong if another process touched the same state at the wrong moment. Edsger W. Dijkstra’s work at Eindhoven treated synchronization as a programming problem that needed explicit abstractions rather than timing folklore.[1][5]
The challenge was not simply to make a processor busy. A system had to protect critical sections, put processes to sleep when resources were unavailable, and wake them without depending on accidental instruction timing. Those requirements helped move concurrency from hardware scheduling into the vocabulary of programming.
Dijkstra introduced P and V as synchronization primitives
In his retrospective account, Dijkstra placed his introduction of the P- and V-operations on semaphores around May 1961. By 1965, his lecture notes on cooperating sequential processes gave the idea a systematic treatment.[1][2]
A semaphore was a special shared variable that processes could access only through controlled operations. The abstraction was deliberately small: programs did not inspect and modify the synchronization state with ordinary reads and writes; they used P and V so the synchronization action itself had defined semantics.
The names came before modern lock terminology
Dijkstra’s notation did not begin with today’s words such as acquire and release. The P/V vocabulary came from his Dutch-language working context and became part of the historical identity of semaphores. Later systems often changed the names to wait/signal or down/up while preserving the basic coordination idea.[2]
Binary semaphores made mutual exclusion explicit
For mutual exclusion, a semaphore can be restricted to two effective states. A process performs P before entering a protected region and V after leaving it. If another process has already taken the resource, the would-be entrant must wait rather than execute the critical section concurrently.[2]
This was a major conceptual improvement over ad hoc status flags. A plain flag can still be raced upon if testing and changing it are not coordinated. The semaphore packages the synchronization discipline around an operation whose meaning is defined for concurrent use.
Counting semaphores generalized the idea from locks to resources
Dijkstra’s later recollection explains that the earliest semaphore was binary, reflecting an empty-or-full output register, and that Carel Scholten suggested generalizing the value to a natural number. That extension allowed the abstraction to represent a pool or buffer with more than one available unit.[4]
A counting semaphore can therefore model capacity as well as exclusion. Producers and consumers can coordinate around a bounded buffer, while a resource manager can represent several interchangeable devices with one count.
Synchronization became independent of one device
The generalization mattered because it separated the coordination method from the physical story that inspired it. A semaphore no longer meant one particular output register; it became a reusable software abstraction for many forms of process cooperation.
Cooperating Sequential Processes turned the abstraction into a teaching system
Dijkstra’s 1965 notes developed semaphores alongside mutual exclusion, bounded buffers, status variables, and conversations among processes. The text is historically valuable because it shows the abstraction embedded in a broader theory of cooperating sequential processes rather than presented as an isolated trick.[2]
The notes also reveal Dijkstra’s emphasis on proving that concurrent programs behaved correctly. Synchronization was not only an efficiency mechanism. It was part of making the possible interleavings understandable enough to reason about.
The THE system showed concurrency abstractions inside an operating system
Dijkstra’s THE multiprogramming system organized operating-system activities as sequential processes arranged in hierarchical layers. His published description emphasized that the layered structure helped verify the logical soundness of the design and implementation.[3]
Semaphores were part of the practical environment in which this approach developed. The historical significance is the combination: concurrency primitives, process structure, and layered abstraction were being treated as connected software-engineering problems.
Abstraction reduced dependence on accidental timing
A layered system could state what a lower level guaranteed without requiring every higher level to understand the timing details underneath it. Synchronization primitives served a similar purpose at the process boundary: they gave programs a vocabulary for coordination that was stronger than assumptions about which instruction happened first.
Semaphores solved one class of problems and exposed others
Semaphores are powerful enough to encode mutual exclusion, producer-consumer coordination, and many scheduling protocols, but they also permit mistakes. A missing V can block progress; inconsistent acquisition order can deadlock; an incorrect initial value can invalidate the intended protocol.
Later concurrency abstractions such as monitors, message passing, transactional systems, and structured task models can be read partly as attempts to make common synchronization disciplines easier to express. Their existence does not diminish the semaphore; it shows how foundational the problem was.
Low-level power creates proof obligations
Semaphores expose enough control that programmers must maintain global invariants across multiple paths. This is why they remain useful in operating systems and runtimes while higher-level application code often prefers abstractions that package synchronization with the state being protected.
Why Dijkstra’s semaphores remain a concurrency milestone
Dijkstra did not invent concurrency, mutual exclusion, or interrupt-driven systems. His contribution was to give cooperating processes a compact synchronization abstraction and to place it inside a disciplined way of reasoning about multiprogramming. His own retrospective writings, lecture notes, and the THE-system paper document that development directly.[1][2][3]
Modern mutexes, condition mechanisms, resource counters, and runtime schedulers use different interfaces, but the central problem remains recognizable: concurrent activities need explicit rules for when they may proceed. Semaphores made that rule programmable.
Works Cited
- 01
- 02
- 03
- 04
- 05MacTutor — Biography of Edsger W. Dijkstra mathshistory.st-andrews.ac.uk
CodeHistory is a living archive. Citations document the evidence used for this edition; later evidence may refine the account.
Submit a research lead