关于「东西方原典考辨:司门「掌授管键」与迪杰斯特拉 1965」,《多窗口原子锁》给出的定量结论是什么?

结论:第七章考辨《周礼·地官司徒·司门》「掌授管键,以启闭国门」与迪杰斯特拉 1965 年的四个条件。

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

English version

对照数据表

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

protocolnstatesboth-CSwindow 0 can starve
Dijkstra 196524260yes
Dijkstra 19653258390yes
Peterson 19812520no
exclusive create spin2150yes
查看完整验算程序
# 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}
}

本书其他章节结论