关于「断电之后:空锁、缺状态与先写临时再链接」,《多窗口原子锁》给出的定量结论是什么?
结论:程序 p31 显示,一次领题被断电打断后,原样写法在滞后模型下可能留下 7 种磁盘状态,其中 3 种是空锁;刷盘把空锁减到 1 种,却消不掉;先写临时再链接把空锁减到零。程序 p32 显示,「空锁即删」的清理规则在 25 种调度里有 10 种造成双领,看两次再删也只把份额从 0.400 降到 0.250。断电留下的半成品,最好的处理是让它不出现在活人身上。可是还有一类更难的情形:窗口没有断电,只是停住了,过一会儿又醒来。租约正是为这类情形设计的,它在多窗口场景里够不够用?
数据口径:书中参数为示意;全部计算由书中程序生成;程序不读写任何文件;本书是非个人化经营建议,任何锁协议的上线变更与孤儿锁裁决须由主事者人工复核放行。 本书把协议的每一步写成原子操作,在内存里模拟文件系统,穷举全部交错调度,并修正蓝图四处:「必有」说的是调度空间,两窗口 16 种调度有 12 种双领,墙钟上的频率取决于出发是否扎堆,四个窗口 2 秒内一拥而上时每批 0.02966;迪杰斯特拉 1965 年恰恰证明只靠读写也能互斥,限制在于名册必须封闭;围栏令牌出自伯罗斯的序列号与克莱普曼的整理,不出自格雷与切里顿;单调计时挡不住进程停顿,时钟完美时仍有 0.000976 的写入迟到。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.250, 0.400, 10, 25
| writer | cleaner | schedules | double | share |
|---|---|---|---|---|
| create, write | none | 5 | 0 | 0.000 |
| create, write | empty once | 25 | 10 | 0.400 |
| create, write | empty twice | 40 | 10 | 0.250 |
| temp + link | none | 4 | 0 | 0.000 |
| temp + link | empty once | 11 | 0 | 0.000 |
| temp + link | empty twice | 16 | 0 | 0.000 |
查看完整验算程序
# Chapter 3. p32: "an empty lock file is an orphan" is unsafe, because a
# live claimant passes through the empty state between create and write.
# A writer W races a cleaner H that deletes empty locks and then claims.
# The lock is (inode, content); W writes through its own open handle,
# so after H deletes the name W's bytes land on an unlinked inode and W
# still believes it holds. Every interleaving is counted exactly.
from functools import lru_cache
W_PLAIN = ("w_create", "w_write", "hold")
W_LINK = ("w_link", "hold") # write temp first, then link()
H_ONCE = ("h_read", "h_clean", "h_create", "hold")
H_TWICE = ("h_read", "h_read", "h_clean", "h_create", "hold")
def step(op, who, lock, seen):
"""Return (new lock, new seen, still running)."""
if op == "w_create":
return (("w", "") if lock is None else lock), seen, lock is None
if op == "w_write":
if lock is not None and lock[0] == "w":
lock = ("w", "W")
return lock, seen, True
if op == "w_link":
return (("w", "W") if lock is None else lock), seen, lock is None
if op == "h_read":
empty = lock is not None and lock[1] == ""
return lock, seen + (empty,), True
if op == "h_clean":
if seen and all(seen):
return None, seen, True
return lock, seen, True
if op == "h_create":
return (("h", "H") if lock is None else lock), seen, lock is None
return lock, seen, True
def count(wprog, hprog):
progs = (wprog, hprog)
@lru_cache(maxsize=None)
def walk(lock, pcs, seen):
live = [i for i in (0, 1)
if pcs[i] is not None and pcs[i] < len(progs[i])]
if not live:
held = [1 for i in (0, 1) if pcs[i] == len(progs[i])]
return 1, (1 if len(held) == 2 else 0)
tot = bad = 0
for i in live:
nl, ns, ok = step(progs[i][pcs[i]], i, lock, seen)
npcs = list(pcs)
npcs[i] = pcs[i] + 1 if ok else None
t, b = walk(nl, tuple(npcs), ns)
tot += t
bad += b
return tot, bad
return walk(None, (0, 0), ())
print("writer cleaner schedules double share")
for wn, w in (("create, write", W_PLAIN), ("temp + link", W_LINK)):
for hn, h in (("none", ("h_create", "hold")),
("empty once", H_ONCE), ("empty twice", H_TWICE)):
tot, bad = count(w, h)
print("%-15s %-16s %9d %7d %5.3f" % (wn, hn, tot, bad,
bad / tot))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《多窗口文件原子锁并发协议、断电孤儿锁自愈与跨窗口交接状态机母典》第 3 章「断电之后:空锁、缺状态与先写临时再链接」(版本 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}
}