关于「跨窗口交接状态机:让渡、令牌与只进不退的状态」,《多窗口原子锁》给出的定量结论是什么?

结论:程序 p61 显示,先删后建的交接在 54 种调度里有 40 种被第三方插队,原子替换消除了插队,却仍有 0.250 的调度被交出方的迟到写入损坏;加上令牌之后丢失与损坏都是零。程序 p62 显示,盲写的状态文件在 6 种调度里有 4 种倒退,先读后写仍有 0.333 倒退,每个阶段一个独占标记则为零。至此,从领题、断电、租约、孤儿锁到交接,我们已经用二十世纪下半叶的数学把多窗口协作的锁协议检验了一遍。可是独占与交接并不是计算机时代才有的问题。两千多年前的城门怎样管钥匙?迪杰斯特拉那一页纸的原文究竟说了什么,哪些说法今天仍可检验?下一章回到原典。

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

English version

对照数据表

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

protocolscheduleslostsharedamageshare
H1 delete, then B creates54400.741220.407
H2 replace content, tell B2800.00070.250
H3 replace + token, fenced2800.00000.000
查看完整验算程序
# Chapter 6. p61: three ways for window A to hand a volume to window B
# while window C may try to claim it, and while one write of A's is
# still in flight (it may land at any later moment). Counted over all
# schedules: "lost" = B does not end up holding; "damage" = A's late
# write is the value left in the store after a newer write. Protocols:
# H1 delete the lock, then tell B to create it; H2 replace the lock's
# content with B atomically (temp + rename), then tell B; H3 as H2 but
# the content carries token 2 and the store refuses tokens below the
# highest it has seen. Everything lives in memory.
from functools import lru_cache

PROTOS = {
    "H1 delete, then B creates": (("a_delete", "a_send", "a_late"),
                                  ("b_wait", "b_create", "b_write")),
    "H2 replace content, tell B": (("a_give", "a_send", "a_late"),
                                   ("b_wait", "b_check", "b_write")),
    "H3 replace + token, fenced": (("a_give", "a_send", "a_late"),
                                   ("b_wait", "b_check", "b_write")),
}
C_PROG = ("c_create", "c_write")


def run(name):
    a, b = PROTOS[name]
    progs = (a, b, C_PROG)
    fenced = name.startswith("H3")

    def write(store, val, tok):
        cur, top, newer = store
        if fenced and tok < top:
            return store
        newer = newer or val != "A"
        return (val, max(top, tok), newer)

    @lru_cache(maxsize=None)
    def walk(lock, msg, store, pcs):
        live = []
        for i in range(3):
            if pcs[i] is None or pcs[i] >= len(progs[i]):
                continue
            if progs[i][pcs[i]] == "b_wait" and not msg:
                continue
            live.append(i)
        if not live:
            lost = 0 if pcs[1] == len(b) else 1
            dmg = 1 if store[0] == "A" and store[2] else 0
            return 1, lost, dmg
        tot = lost = dmg = 0
        for i in live:
            op, ok = progs[i][pcs[i]], True
            nl, nm, ns = lock, msg, store
            if op == "a_delete":
                nl = None
            elif op == "a_give":
                nl = "B"
            elif op == "a_send":
                nm = True
            elif op == "a_late":
                ns = write(store, "A", 1)
            elif op == "b_create":
                ok = lock is None
                nl = "B" if ok else lock
            elif op == "b_check":
                ok = lock == "B"
            elif op == "b_write":
                ns = write(store, "B", 2)
            elif op == "c_create":
                ok = lock is None
                nl = "C" if ok else lock
            elif op == "c_write":
                ns = write(store, "C", 2)
            npcs = list(pcs)
            npcs[i] = pcs[i] + 1 if ok else None
            t, l, d = walk(nl, nm, ns, tuple(npcs))
            tot, lost, dmg = tot + t, lost + l, dmg + d
        return tot, lost, dmg
    return walk("A", False, ("A", 1, False), (0, 0, 0))


print("protocol                     schedules  lost  share  damage  share")
for name in PROTOS:
    tot, lost, dmg = run(name)
    print("%-28s %8d %5d  %5.3f %6d  %5.3f"
          % (name, tot, lost, lost / tot, dmg, dmg / tot))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《多窗口文件原子锁并发协议、断电孤儿锁自愈与跨窗口交接状态机母典》第 6 章「跨窗口交接状态机:让渡、令牌与只进不退的状态」(版本 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}
}

本书其他章节结论