关于「竞态窗口:先检查后创建的交错穷举与墙钟宽度」,《多窗口原子锁》给出的定量结论是什么?

结论:程序 p11 数清了全部调度:两个窗口用先检查后创建,16 种调度里有 12 种双领;四个窗口时 74976 种里有 74880 种。原子独占创建在任何窗口数下都没有坏调度。程序 p12 把缝换算到墙钟上:分散出发时撞车罕见,一拥而上时每批约 0.02966。可是本章只回答了「用什么原语」,还没有回答一个更根本的问题:如果文件系统不提供独占创建,只给原子的读和写,多个窗口还能不能互斥?迪杰斯特拉在 1965 年给出了肯定的回答,下一章用一个小小的模型检验器来复核它,并说明这个回答为什么在多窗口场景里用不上。

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

English version

对照数据表

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

protocolnschedulesdouble-holdshareP(uniform)
check-then-create 216120.75000.5000
check-then-create 37026840.97440.6667
check-then-create 474976748800.99870.7500
exclusive-create2400.00000.0000
exclusive-create31800.00000.0000
exclusive-create49600.00000.0000
查看完整验算程序
# Chapter 1. p11: every interleaving of n windows claiming one lock file,
# check-then-create against exclusive create, counted exactly.
# Model: an in-memory file system holding one name; no file is touched.
# Each window runs fixed atomic steps; the schedule picks which window
# moves next. Counts are exact (memoised over states); the probability
# column assumes a scheduler that picks a runnable window uniformly.
import math
from functools import lru_cache

# 先检查后创建:check(存在否) -> create(覆盖写) -> hold
# 独占创建:create_x(已存在即失败) -> hold
NAIVE = ("check", "create", "hold")
EXCL = ("create_x", "hold")


def run(prog, n):
    @lru_cache(maxsize=None)
    def walk(exists, procs):
        live = [i for i, (pc, ok) in enumerate(procs)
                if pc < len(prog) and ok]
        if not live:
            held = len([1 for pc, ok in procs if ok and pc == len(prog)])
            bad = 1 if held >= 2 else 0
            return 1, bad, float(bad)
        tot, bad, pr = 0, 0, []
        for i in live:
            pc, ok = procs[i]
            op = prog[pc]
            ex = exists
            if op == "check":
                ok = not exists
            elif op == "create":
                ex = True
            elif op == "create_x":
                ok = not exists
                ex = True
            nxt = list(procs)
            nxt[i] = (pc + 1, ok)
            t, b, p = walk(ex, tuple(nxt))
            tot += t
            bad += b
            pr.append(p)
        return tot, bad, math.fsum(p / len(live) for p in pr)
    return walk(False, tuple((0, True) for _ in range(n)))


print("protocol         n  schedules  double-hold  share   P(uniform)")
for name, prog in (("check-then-create", NAIVE),
                   ("exclusive-create", EXCL)):
    for n in (2, 3, 4):
        tot, bad, prob = run(prog, n)
        print("%-17s %d %9d %11d  %6.4f  %6.4f"
              % (name, n, tot, bad, bad / tot, prob))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《多窗口文件原子锁并发协议、断电孤儿锁自愈与跨窗口交接状态机母典》第 1 章「竞态窗口:先检查后创建的交错穷举与墙钟宽度」(版本 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}
}

本书其他章节结论