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

protocolnstatesboth-CSwindow 0 can starve
Dijkstra 196524260yes
Dijkstra 19653258390yes
Peterson 19812520no
exclusive create spin2150yes
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