关于「只靠读写能否互斥:六个入口协议的模型检验与名册下界」,《多窗口原子锁》给出的定量结论是什么?

结论:第二章用模型检验器检验六个只靠读写的入口协议,复现海曼 1966 年错误解法的最短反例,并说明名册是读写算法的命门。

数据口径:书中参数为示意;全部计算由书中程序生成;程序不读写任何文件;本书是非个人化经营建议,任何锁协议的上线变更与孤儿锁裁决须由主事者人工复核放行。 本书把协议的每一步写成原子操作,在内存里模拟文件系统,穷举全部交错调度,并修正蓝图四处:「必有」说的是调度空间,两窗口 16 种调度有 12 种双领,墙钟上的频率取决于出发是否扎堆,四个窗口 2 秒内一拥而上时每批 0.02966;迪杰斯特拉 1965 年恰恰证明只靠读写也能互斥,限制在于名册必须封闭;围栏令牌出自伯罗斯的序列号与克莱普曼的整理,不出自格雷与切里顿;单调计时挡不住进程停顿,时钟完美时仍有 0.000976 的写入迟到。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 1966

protocol (2 windows)statesboth-CSstuckverdict
check-then-set flags3610UNSAFE
set-then-check flags3201SAFE, CAN STALL
strict alternation3004SAFE, CAN STALL
Hyman 19669620UNSAFE
Peterson 19816200SAFE
Dijkstra 1965, n=247700SAFE
查看完整验算程序
# 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}
}

本书其他章节结论