关于「东西方原典考辨:司门「掌授管键」与迪杰斯特拉 1965」,《多窗口原子锁》给出的定量结论是什么?
结论:第七章考辨《周礼·地官司徒·司门》「掌授管键,以启闭国门」与迪杰斯特拉 1965 年的四个条件。
数据口径:书中参数为示意;全部计算由书中程序生成;程序不读写任何文件;本书是非个人化经营建议,任何锁协议的上线变更与孤儿锁裁决须由主事者人工复核放行。 本书把协议的每一步写成原子操作,在内存里模拟文件系统,穷举全部交错调度,并修正蓝图四处:「必有」说的是调度空间,两窗口 16 种调度有 12 种双领,墙钟上的频率取决于出发是否扎堆,四个窗口 2 秒内一拥而上时每批 0.02966;迪杰斯特拉 1965 年恰恰证明只靠读写也能互斥,限制在于名册必须封闭;围栏令牌出自伯罗斯的序列号与克莱普曼的整理,不出自格雷与切里顿;单调计时挡不住进程停顿,时钟完美时仍有 0.000976 的写入迟到。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 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 |
查看完整验算程序
# 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"))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《多窗口文件原子锁并发协议、断电孤儿锁自愈与跨窗口交接状态机母典》第 7 章「东西方原典考辨:司门「掌授管键」与迪杰斯特拉 1965」(版本 1.0.0). 5D Library. DOI 待发布
DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 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}
}