1965

The Semaphore

A semaphore is an integer and two operations, and the integer is the whole of the shared state however many processes there are. Getting there took Dijkstra four wrong answers, and he prints all four before the right one because the sequence is the argument. This page enumerates the entire state space of every one of them and measures four properties over it, so that each rejection is a number rather than a paragraph.

New to mutual exclusion? Start here

Two programs share something: a counter, a file, a printer. Each has a stretch of code that must not run while the other is in its own. That stretch is the critical section, and keeping them apart is the mutual exclusion problem. Race is what happens when nobody does.

The constraint is what they are allowed to use to arrange it. No timing assumptions, because either one may be stopped at any moment for any length of time; no instruction that does more than read or write one shared variable, which Dijkstra postulates rather than argues for. Everything on this page is built out of that.

A semaphore is what Dijkstra added when the arrangement got too clever to check: a single integer, with two operations that are the only way to touch it. One waits until the integer is positive and takes one away; the other puts one back. The integer is the whole of the shared state, however many programs there are.

Two things at once

A program you write reads top to bottom, one step after the last. Once two of them run at the same time, that stops being true of the pair: their steps interleave, in an order nobody chose and nothing wrote down.

The hard part is that the order is not random so much as unconstrained. Any interleaving the hardware permits is one you have to treat as possible, even if no test you ever run happens to produce it: nothing promises that a scheduler will eventually choose it, and nothing promises it will not, on someone else's machine, months later, on the run you were not watching. So the machines in this topic are not about making the right order happen. They are about which orders are possible, which of those are wrong, and what it costs to rule them out.

The machine for this idea on its own is Race, if you would rather press it than read about it.

Machines here that come first: Round Robin, The Interrupt.

Four rejected constructions, one integer, and the count that is the permission

1 Four rejected constructions, and the single measurement each one fails

Two programs, each looping through a critical section it must not be inside at the same time as the other. Only shared variables to talk with, and reading or writing one is indivisible. Dijkstra works through four constructions and rejects every one, in prose, by exhibiting a bad schedule apiece. He counts nothing.

So this counts. Each construction is built as a program of indivisible steps and its whole reachable state graph is walked, and then four properties are measured over that graph, one per rejection. A dash means the construction has no state of that kind at all; a number is how many it has. The four graphs run from 16 states to 32.

Both inside: a reachable state with both processes in their critical sections. Nothing moves: a state whose only successor is itself. Neither enters: a cycle both processes keep taking steps in, from which the critical section is never reached and which can still be left. One stops: hold process 2 in its remainder of cycle, which is the one place Dijkstra requires a halt to have no effect on anybody else, and count the states from which process 1 can no longer reach its critical section.

constructionboth insidenothing movesneither entersone stops
the first solution———3 of 5
the second effort1———
the safe sluice—1——
back off and retry——9—

Each of the four fails one column and passes the other three, and no two fail the same one. This is not four goes at the same mistake. It is a sequence, and each attempt is answering the objection to the one before it.

L1: if c2 = 0 then goto L1;
    c1:= 0;
    critical section 1;
    c1:= 1;
    remainder of cycle 1; goto L1

Process 1 as the paper prints it. Process 2 is its mirror image. 25 reachable states

Rejected for one reason and correct in the other three: both inside. In short, it is both can find the other outside and enter together. 25 reachable states.

2 Dekker's solution, and the two operations that replace it

Dekker’s solution is the first correct one, and Dijkstra says so: “To the Dutch mathematician Th.J.Dekker the credit is due for the first correct solution.” It is a mixture of every effort before it, and the reader who cannot see why it works is told plainly that the ground has been prepared “by means of a carefully selected set of rejected constructions”.

Then section 3.2 stops solving the problem and adds a part. A semaphore is an integer, and two operations are the only things allowed to touch it. V increases it by one, and “this increase is to be regarded as an indivisible operation”. P decreases it by one, “as soon as the resulting value would be non-negative”. That waiting clause is the whole mechanism, and it is only in P.

constructionboth insidenothing movesneither entersone stops
Dekker's solution————
P(free) and V(free)————

Both pass all four, and neither has a state of any of those kinds. The difference between them is not correctness: it is 122 reachable states against 12, and nine steps of entry protocol against one operation.

3 The same three lines with the count raised above one

Nothing above needed the semaphore to be a one. “The semaphores are essentially non-negative integers”, and restricting them to nought and one is what you do when the problem is mutual exclusion, not what they are. Raise the count and the same three lines let that many processes in at once.

states they can reach
32
most ever inside at once
1
states with more inside than the count allows
0

Of the 32 states these 3 processes can reach, 0 have more than 1 inside at once, and the most ever inside is 1. The program did not change. The integer did. With the count at one the critical sections are forced into a total order, so of those 1,680 orderings only 6 survive.

And the program never names another process. These two rows are read off the two solutions the same document prints eleven pages apart: the generalised construction of section 2.2, and P and V.

what it needssection 2.2a semaphore
shared variables91
other processes each one inspects20

4 The choice the definition of P leaves out

One thing the definition refuses to say. When several processes have started a P on the same semaphore and it becomes positive, exactly one of them may complete — and Dijkstra writes that “Which one, again, is left unspecified”. That is not a gap in the paper. It is the reason the mechanism scales: something still picks the winner, but Dijkstra puts that choice “at least outside our control”, so no process has to know which other one is waiting and no program has to do the picking.

ways out of that state
2
branchwhat happensand the other one
branch 1process 1 completes its Pthe other one waits, and nothing says for how long
branch 2process 2 completes its Pthe other one waits, and nothing says for how long

Both processes are waiting inside P and the semaphore has just gone back to one. The graph has 2 ways out of that state and the definition of P prefers neither: it says only that one of the initiated operations is allowed to complete. Nothing here is fair, and nothing in the paper says it is.

These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.

Each claim, whether it held, and the values behind it
claimheldmeasured
each of Dijkstra's four rejected constructions fails exactly one of the four measurementsyesthe first solution: one stops, the other is blocked; the second effort: both inside; the safe sluice: nothing can move; back off and retry: neither ever enters
and no two of them fail the same oneyesone stops, the other is blocked | both inside | nothing can move | neither ever enters
Dekker's solution and P/V both pass all four, over 122 and 12 reachable statesyesthe difference between them is not correctness, it is that one is nine steps of intricacy and the other is three lines
with the semaphore at one, no state of the 2304 reachable with eight processes has two of them insideyesand the count is (N+1) times two to the N at every N from two to eight
with five processes and the semaphore at k, exactly k are inside at once, for every k from one to fouryesthe same three lines; only the integer changed
with the count at one, 6 complete runs survive of the 1,680 three processes could otherwise takeyesN factorial at a count of one, because the only freedom left is which order they go in; and every interleaving there is at a count of N, which for two processes is the 20 Race enumerates
for eight processes the section 2.2 solution needs 19 shared variables and inspects 7 other processes; the semaphore needs 1 and inspects 0yesread off two programs printed in the same document
where both processes are waiting in P and the semaphore returns to one, the graph has exactly 2 successorsyesand nothing in the definition of P prefers either of them, which is why nothing here is fair

What is real here, and what is not

Nothing here runs concurrently, and that is the point

Every number on this page is a count over a finite graph of states, computed in one thread. A demonstration that races when you happen to press a button at the wrong moment teaches that concurrency is bad luck. It is not. Every schedule the model permits is enumerated, and the counts have denominators. Race takes the same stance for the same reason.

1965 is the date of the notes, not of the invention

The operations are older than the document that defines them. Dijkstra's own recollection, written decades later, is that “Around May 1961, in something like EWD31, I introduced the P- and V-operations on semaphores”. Read the hedge: he is not certain which document it was, and EWD31 is not in the archive — the E.W. Dijkstra Archive's index for that range lists twenty-four manuscripts and 31 is not among them. EWD123 “was written in 1965 and served as lecture notes for my course in the fall semester of that year”, which is the date this page carries and the date the definition everybody uses was written down.

The four measurements are ours; the four rejections are his

Dijkstra rejects each construction in prose by exhibiting one bad schedule. He gives no counts anywhere in section 2.1. So the columns here are this page's translation of his four objections into properties of a state graph, and the translation is a choice that could have been made differently. What is not a choice is the result: each attempt fails exactly one column, no two fail the same one, and Dekker's solution and the semaphore fail none.

What separates a livelock from a deadlock here, and how we found out

Two implementations of this census were written, one in Python while researching and one in JavaScript for the page, and they disagreed on exactly one cell: whether the safe sluice's single stuck state counts as a livelock. It meets the part of the definition about movement, since both processes keep taking steps and neither ever enters, and fails the part about escape, since it has no way out at all. Dijkstra separates them himself: the sluice's processes “will wait upon each other until eternity”, while the fourth construction is rejected because it works only with some luck. A cycle that can be left is the one that needs luck, so a component with no exit is not counted here. The disagreement is what made the distinction get written down.

P and V mean two different pairs of Dutch words, both his

The folklore picks one. Dijkstra used both. In EWD35 he writes that P is for Passering and V for Vrijgave, and that “This terminology is taken from the railway environment” — the shared variables were called seinpalen, signal posts, which is where the word semaphore comes from. In EWD51 and EWD74 the same two letters are Prolaag and Verhoog. He renamed them, and a page that calls either one a myth is wrong. The often-repeated gloss that prolaag is short for probeer te verlagen is not in Dijkstra's text at all: it appears in a translator's glossary prepended to the EWD51 transcription, and it is presented here as that and nothing more.

Not the first synchronisation primitive, and this page does not say so

Dekker's solution is 1959 and predates it; interrupt masking and hardware interlocks predate both. What can be said is narrower and is what the page says: this is the primitive Dijkstra defined, and the one every later mechanism gets compared to. The generalisation from the binary case to a counting one he credits in the text to somebody else — “It is the merit of the Dutch physicist and computer designer Drs.C.S.Scholten”.

The critical section is one step, and a real one is not

Each process here does P, then a critical section that takes exactly one step, then V, then a remainder that takes one step. Making the critical section longer multiplies the state count and changes none of the four measurements, because none of them depends on how long a process stays inside. It would change the numbers this page prints, so the numbers are about this program and not about concurrency.

What this page deliberately leaves to its neighbours

Why an unsynchronised increment loses an update is Race, and Dijkstra uses that same lost update to argue that V cannot be written as S := S + 1. Cycles, Coffman's four conditions and the difference between deadlock and starvation are Deadlock. A write that refuses is Compare and Swap. None of that is re-derived here.

Half of EWD123 is not in the archived copy

The transcription is paginated and only the first part is on disk here. It carries sections 1 to 4.3, which is everything this page cites: the four constructions, Dekker's solution, the definitions of P and V, and the generalised problem. The deadly embrace, the banker's algorithm and the private semaphore are in the second part, and this page does not cite them.

Sound: no

Asked and answered, so it does not get re-opened. The measurement here is a count of states, and there is nothing in it with a duration. A tone per transition would be an animation with a soundtrack, not a measurement carried by sound.

Sources

Logical Art builds interactive explanations of difficult machines.

The machines:

A few more, on the studio: Sampling, Reed-Solomon, The System Call, Packet Switching, Signature, Write-Ahead Log, False Sharing, TLS Handshake. Or browse every Bit, every Nibble, or the whole chronology.

A Logical Art machine by RoamingPigs, Inc. Built by Cisco Caceres in Las Vegas, NV.