关于「只靠读写能否互斥:六个入口协议的模型检验与名册下界」,《多窗口原子锁》给出的定量结论是什么?
结论:第二章用模型检验器检验六个只靠读写的入口协议,复现海曼 1966 年错误解法的最短反例,并说明名册是读写算法的命门。
数据口径:书中参数为示意;全部计算由书中程序生成;程序不读写任何文件;本书是非个人化经营建议,任何锁协议的上线变更与孤儿锁裁决须由主事者人工复核放行。 本书把协议的每一步写成原子操作,在内存里模拟文件系统,穷举全部交错调度,并修正蓝图四处:「必有」说的是调度空间,两窗口 16 种调度有 12 种双领,墙钟上的频率取决于出发是否扎堆,四个窗口 2 秒内一拥而上时每批 0.02966;迪杰斯特拉 1965 年恰恰证明只靠读写也能互斥,限制在于名册必须封闭;围栏令牌出自伯罗斯的序列号与克莱普曼的整理,不出自格雷与切里顿;单调计时挡不住进程停顿,时钟完美时仍有 0.000976 的写入迟到。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 1966
| protocol (2 windows) | states | both-CS | stuck | verdict |
| check-then-set flags | 36 | 1 | 0 | UNSAFE |
| set-then-check flags | 32 | 0 | 1 | SAFE, CAN STALL |
| strict alternation | 30 | 0 | 4 | SAFE, CAN STALL |
| Hyman 1966 | 96 | 2 | 0 | UNSAFE |
| Peterson 1981 | 62 | 0 | 0 | SAFE |
| Dijkstra 1965, n=2 | 477 | 0 | 0 | SAFE |
查看完整验算程序
# Chapter 2. p21: an explicit-state model checker for two windows that
# share only read/write variables, run over six classic entry protocols.
# Every reachable state is enumerated (breadth first). "both in CS"
# counts states breaking mutual exclusion; "stuck" counts states where
# some window is trying yet no window can ever enter again. A window
# may stop for good in its remainder section (Dijkstra 1965 allows it).
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 naive(sh, i, pc, r): # sh = (flag0, flag1); check, then set
j = 1 - i
if pc == 1:
return [(1 if sh[j] else 2, r, sh)]
if pc == 2:
return [(CS, r, put(sh, i, 1))]
return [(REM, r, put(sh, i, 0))] # exit
def setfirst(sh, i, pc, r): # set own flag, then wait on the other
j = 1 - i
if pc == 1:
return [(2, r, put(sh, i, 1))]
if pc == 2:
return [(2 if sh[j] else CS, r, sh)]
return [(REM, r, put(sh, i, 0))]
def alternate(sh, i, pc, r): # sh = (turn,)
if pc == 1:
return [(CS if sh[0] == i else 1, r, sh)]
return [(REM, r, (1 - i,))]
def hyman(sh, i, pc, r): # sh = (b0, b1, k); b = 1 means idle
j = 1 - i
if pc == 1:
return [(2, r, put(sh, i, 0))]
if pc == 2:
return [(CS if sh[2] == i else 3, r, sh)]
if pc == 3:
return [(3 if sh[j] == 0 else 4, r, sh)]
if pc == 4:
return [(2, r, put(sh, 2, i))]
return [(REM, r, put(sh, i, 1))]
def peterson(sh, i, pc, r): # sh = (flag0, flag1, turn)
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 dijkstra(sh, i, pc, r, n=2): # 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)] # read k into r
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: # scan c[j], j = r
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 + 1:
return [(CS + 2, r, put(sh, n + i, 1))]
return [(REM, r, put(sh, i, 1))]
def moves(alg, state, i):
procs, sh = state
pc, r = procs[i]
if pc == HALT:
return []
if pc == REM:
return [(put(procs, i, (1, r)), sh), (put(procs, i, (HALT, r)), sh)]
if pc == CS:
return [(put(procs, i, (CS + 1, r)), sh)]
return [(put(procs, i, (npc, nr)), nsh)
for npc, nr, nsh in alg(sh, i, pc, r)]
def explore(alg, init):
start = (((REM, 0), (REM, 0)), init)
seen, edges, todo = {start: 0}, {}, deque([start])
while todo:
s = todo.popleft()
out = moves(alg, s, 0) + moves(alg, s, 1)
for t in out:
if t not in seen:
seen[t] = len(seen)
todo.append(t)
edges[s] = out
return seen, edges
def report(name, alg, init):
seen, edges = explore(alg, init)
incs = lambda s: [p for p, _ in s[0] if p == CS]
both = len([s for s in seen if len(incs(s)) == 2])
good = {s for s in seen if incs(s)}
back = {}
for s, out in edges.items():
for t in out:
back.setdefault(t, []).append(s)
todo = deque(good)
while todo:
t = todo.popleft()
for s in back.get(t, []):
if s not in good:
good.add(s)
todo.append(s)
trying = lambda s: [p for p, _ in s[0] if p not in (REM, HALT)]
stuck = len([s for s in seen if trying(s) and s not in good])
verdict = "SAFE" if both == 0 else "UNSAFE"
if both == 0 and stuck:
verdict = "SAFE, CAN STALL"
print("%-22s %6d %8d %6d %s" % (name, len(seen), both, stuck,
verdict))
print("protocol (2 windows) states both-CS stuck verdict")
report("check-then-set flags", naive, (0, 0))
report("set-then-check flags", setfirst, (0, 0))
report("strict alternation", alternate, (0,))
report("Hyman 1966", hyman, (1, 1, 0))
report("Peterson 1981", peterson, (0, 0, 0))
report("Dijkstra 1965, n=2", dijkstra, (1, 1, 1, 1, 0))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《多窗口文件原子锁并发协议、断电孤儿锁自愈与跨窗口交接状态机母典》第 2 章「只靠读写能否互斥:六个入口协议的模型检验与名册下界」(版本 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}
}