What does Atomic Locks for Many Windows conclude, in numbers, about “Classical Sources East and West: the Gatekeeper Who "Keeps and Issues the Keys" and Dijkstra in 1965”?
Answer: Chapter 7 examines "he keeps and issues the keys, to open and close the gates of the state" from the Office of the Gates in the Rites of Zhou and Dijkstra's four conditions of 1965.
Scope of the numbers: Marked boxes separate published evidence, runnable Python calculations (19 programs), classical sources and the author's hypotheses.
Data table
The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 1965
| protocol | n | states | both-CS | window 0 can starve |
| Dijkstra 1965 | 2 | 426 | 0 | yes |
| Dijkstra 1965 | 3 | 25839 | 0 | yes |
| Peterson 1981 | 2 | 52 | 0 | no |
| exclusive create spin | 2 | 15 | 0 | yes |
Show the full program
# Chapter 7. p71: Dijkstra's 1965 n-window protocol, checked for n = 2
# and 3: mutual exclusion, stalls, and whether one window can be passed
# over forever. Each line of the 1965 program is one atomic step; the
# test "if b[k] then k := i" is split into read k, test b[k], write k.
# Starvation: a cycle of reachable states in which window 0 keeps
# trying, takes steps itself, and some other window enters the critical
# section (Knuth 1966). Peterson's two-window lock and a spinning
# exclusive-create loop are checked the same way for contrast.
from collections import deque
REM, CS, HALT = 0, 50, 99
def put(t, k, v):
t = list(t)
t[k] = v
return tuple(t)
def dijkstra(n):
def step(sh, i, pc, r): # sh = b[0..n-1], c[0..n-1], k
b, c, k = sh[:n], sh[n:2 * n], sh[2 * n]
if pc == 1:
return 2, r, put(sh, i, 0)
if pc == 2:
return (7 if k == i else 3), r, sh
if pc == 3:
return 4, r, put(sh, n + i, 1)
if pc == 4:
return 5, k, sh
if pc == 5:
return (6 if b[r] else 2), r, sh
if pc == 6:
return 2, r, put(sh, 2 * n, i)
if pc == 7:
return 8, 0, put(sh, n + i, 0)
if pc == 8:
if r == n:
return CS, 0, sh
if r != i and c[r] == 0:
return 2, 0, sh
return 8, r + 1, sh
if pc == CS:
return CS + 1, r, put(sh, n + i, 1)
return REM, r, put(sh, i, 1)
return step, tuple([1] * (2 * n) + [0])
def peterson(sh, i, pc, r):
j = 1 - i
if pc == 1:
return 2, r, put(sh, i, 1)
if pc == 2:
return 3, r, put(sh, 2, j)
if pc == 3:
return (3 if sh[j] and sh[2] == j else CS), r, sh
return REM, r, put(sh, i, 0)
def spin(sh, i, pc, r): # sh = (lock exists,)
if pc == 1:
return (CS, r, (1,)) if sh[0] == 0 else (1, r, sh)
return REM, r, (0,)
def graph(step, init, n):
start = (tuple([(REM, 0)] * n), init)
seen, edges, todo = {start}, {}, deque([start])
while todo:
s = todo.popleft()
out = []
for i in range(n):
pc, r = s[0][i]
if pc == HALT:
continue
nxt = [(1, r, s[1])] if pc == REM else [step(s[1], i, pc, r)]
if pc == REM:
nxt.append((HALT, r, s[1]))
for npc, nr, nsh in nxt:
t = (put(s[0], i, (npc, nr)), nsh)
out.append((i, t))
if t not in seen:
seen.add(t)
todo.append(t)
edges[s] = out
return seen, edges
def starves(edges):
trying = lambda s: s[0][0][0] not in (REM, HALT, CS, CS + 1)
nodes = [s for s in edges if trying(s)]
sub = {s: [(i, t) for i, t in edges[s] if trying(t)] for s in nodes}
index, low, comp, stack, on, cnt = {}, {}, {}, [], set(), [0]
for root in nodes: # iterative Tarjan
if root in index:
continue
work = [(root, 0)]
while work:
v, k = work.pop()
if k == 0:
index[v] = low[v] = cnt[0]
cnt[0] += 1
stack.append(v)
on.add(v)
if k < len(sub[v]):
work.append((v, k + 1))
w = sub[v][k][1]
if w not in index:
work.append((w, 0))
elif w in on:
low[v] = min(low[v], index[w])
continue
for _, w in sub[v]:
if w in on:
low[v] = min(low[v], low[w])
if low[v] == index[v]:
while True:
w = stack.pop()
on.discard(w)
comp[w] = v
if w == v:
break
for s in nodes:
mine = [1 for i, t in sub[s] if i == 0 and comp.get(t) == comp[s]]
if mine:
for u in nodes:
if comp[u] != comp[s]:
continue
for i, t in sub[u]:
if comp.get(t) == comp[s] and i != 0 and \
t[0][i][0] == CS:
return True
return False
print("protocol n states both-CS window 0 can starve")
rows = [("Dijkstra 1965",) + dijkstra(2) + (2,),
("Dijkstra 1965",) + dijkstra(3) + (3,),
("Peterson 1981", peterson, (0, 0, 0), 2),
("exclusive create spin", spin, (0,), 2)]
for name, step, init, n in rows:
seen, edges = graph(step, init, n)
both = len([s for s in seen
if len([1 for p, _ in s[0] if p == CS]) >= 2])
print("%-22s %d %8d %8d %s" % (name, n, len(seen), both,
"yes" if starves(edges) else "no"))Single source and citation
Fan, Y. (2026). Atomic File-Lock Protocols for Multiple Windows: Self-Recovering Orphan Locks after Power Loss and Cross-Window Hand-Over State Machines (Version 1.0.0), Chapter 7: Classical Sources East and West: the Gatekeeper Who "Keeps and Issues the Keys" and Dijkstra in 1965. 5D Library. DOI pending
DOI pending · monograph page goes live after publication · 5DL-B-254 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026254,
author = {Fan, Yafu},
title = {Atomic File-Lock Protocols for Multiple Windows: Self-Recovering Orphan Locks after Power Loss and Cross-Window Hand-Over State Machines},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}Other chapter answers in this book
- Chapter 1 · The Race Window: Exhaustive Interleavings of Check-then-Create and Their Width on the Wall Clock
- Chapter 2 · Mutual Exclusion from Reads and Writes Alone: Model-Checking Six Entry Protocols and the Roster Bound
- Chapter 3 · After the Power Cut: Empty Locks, Missing Status and Write-Temporary-then-Link
- Chapter 4 · Leases, Clocks and Fencing Tokens
- Chapter 5 · Judging Orphan Locks: How Long a Silence Means Death
- Chapter 6 · State Machines for Hand-Over between Windows: Transfer, Tokens and a Status That Only Moves Forward
- Chapter 8 · Closing the Loop: a Formal Health Check of This Series' Lock Protocol and a Pre-Registered Test