concurrent.quest

Spread II

The Process
Table

— on threads, locks, and the nocturnal ballet of the scheduler

In the year nineteen hundred and sixty-five, Professor Dijkstra lit a cigarette in the computing hall at Eindhoven and wrote, upon a sheet of onion-skin paper, two lowercase letters: P and V. With these modest symbols he minted the semaphore, and thereby taught machines to wait for one another with grace.

What followed was a quiet revolution. The single thread of execution, once so tidy in its linearity, splintered into many. Processes learned to converse across channels. Locks were forged; mutexes were negotiated; monitors kept watch over shared memory as cathedral guards keep watch over relics.

“Concurrency is the art of arranging, in time, the things a machine must do — and then trusting it to arrange them well.” — marginalia, BYTE Magazine, Jun. 1978

Every icon on the adjacent page names a primitive drawn from that long conversation. Regard them as you would regard the glyphs on a medieval astrolabe: small, precise, and capable — in the right configuration — of navigating whole continents of computation.

Fig. 1 — a partial census of concurrent primitives, after the manner of the ACM.

thread

mutex

semaphore

queue

deadlock

fork

join

race

monitor

channel

atomic

barrier

Spread III

The Timeline
Gutter

T+000ms

Thread α acquires lock L₁

The first filament of execution is spun. The scheduler records its birth in the process table and releases it into the scheduler’s quantum.

T+047ms

Thread β blocks on semaphore S₀

A second filament arrives, finds the turnstile latched, and surrenders to the waiting queue. The scheduler dims its indicator lamp.

T+118ms

Channel C₃ transmits message §

A parcel is flung across the void from producer to consumer, pausing not once to wonder at the space it crosses.

T+204ms

Barrier B₁ releases four peers

The congregation has arrived; the gate swings back on elastic hinges; four threads resume their pilgrimage in unison.

T+312ms

Monitor M₀ records the invariant

A sentinel verifies, in a whisper, that the world is still the world. The ledger is updated in tabular numerals.

Spread IV

A Ring of
Waiting

Four processes. Four resources. Each holds what the next demands, and so the clock, for a moment, forgets what time it is.

A holds L1 waits for L2

B holds L2 waits for L3

C holds L3 waits for L4

D holds L4 waits for L1

— coda —

The threads
resolve.

What began as many voices ends as a single sentence. The fork returns to the join; the channel closes politely; the scheduler files its logs in alphabetical order and switches off the desk lamp. What remains is the hum of the disk, and one blinking cursor, and the quiet certainty that somewhere, another process is about to begin.

◊ fin. · and yet the quest continues

Thread α acquires lock L1

Thread β blocks on semaphore S0

Channel C3 transmits message §

Barrier B1 releases four peers

Monitor M0 records the invariant

The threadsresolve.