关于「断电之后:空锁、缺状态与先写临时再链接」,《多窗口原子锁》给出的定量结论是什么?

结论:程序 p31 显示,一次领题被断电打断后,原样写法在滞后模型下可能留下 7 种磁盘状态,其中 3 种是空锁;刷盘把空锁减到 1 种,却消不掉;先写临时再链接把空锁减到零。程序 p32 显示,「空锁即删」的清理规则在 25 种调度里有 10 种造成双领,看两次再删也只把份额从 0.400 降到 0.250。断电留下的半成品,最好的处理是让它不出现在活人身上。可是还有一类更难的情形:窗口没有断电,只是停住了,过一会儿又醒来。租约正是为这类情形设计的,它在多窗口场景里够不够用?

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

English version

对照数据表

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

writercleanerschedulesdoubleshare
create, writenone500.000
create, writeempty once25100.400
create, writeempty twice40100.250
temp + linknone400.000
temp + linkempty once1100.000
temp + linkempty twice1600.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}
}

本书其他章节结论