关于「竞态窗口:先检查后创建的交错穷举与墙钟宽度」,《多窗口原子锁》给出的定量结论是什么?
结论:程序 p11 数清了全部调度:两个窗口用先检查后创建,16 种调度里有 12 种双领;四个窗口时 74976 种里有 74880 种。原子独占创建在任何窗口数下都没有坏调度。程序 p12 把缝换算到墙钟上:分散出发时撞车罕见,一拥而上时每批约 0.02966。可是本章只回答了「用什么原语」,还没有回答一个更根本的问题:如果文件系统不提供独占创建,只给原子的读和写,多个窗口还能不能互斥?迪杰斯特拉在 1965 年给出了肯定的回答,下一章用一个小小的模型检验器来复核它,并说明这个回答为什么在多窗口场景里用不上。
数据口径:书中参数为示意;全部计算由书中程序生成;程序不读写任何文件;本书是非个人化经营建议,任何锁协议的上线变更与孤儿锁裁决须由主事者人工复核放行。 本书把协议的每一步写成原子操作,在内存里模拟文件系统,穷举全部交错调度,并修正蓝图四处:「必有」说的是调度空间,两窗口 16 种调度有 12 种双领,墙钟上的频率取决于出发是否扎堆,四个窗口 2 秒内一拥而上时每批 0.02966;迪杰斯特拉 1965 年恰恰证明只靠读写也能互斥,限制在于名册必须封闭;围栏令牌出自伯罗斯的序列号与克莱普曼的整理,不出自格雷与切里顿;单调计时挡不住进程停顿,时钟完美时仍有 0.000976 的写入迟到。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 12, 16, 74880, 74976
| protocol | n | schedules | double-hold | share | P(uniform) |
|---|---|---|---|---|---|
| check-then-create 2 | 16 | 12 | 0.7500 | 0.5000 | |
| check-then-create 3 | 702 | 684 | 0.9744 | 0.6667 | |
| check-then-create 4 | 74976 | 74880 | 0.9987 | 0.7500 | |
| exclusive-create | 2 | 4 | 0 | 0.0000 | 0.0000 |
| exclusive-create | 3 | 18 | 0 | 0.0000 | 0.0000 |
| exclusive-create | 4 | 96 | 0 | 0.0000 | 0.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}
}