关于「孤儿锁判别:沉默多久才算死」,《多窗口原子锁》给出的定量结论是什么?

结论:第五章讨论孤儿锁判别:笔记本沉默一小时主人已死的后验很低,一旦允许自动抢锁,连释放都会双领,80 种调度有 12 种,份额 0.150。

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

English version

对照数据表

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

release by AB isschedulesdoubleshare
read, delete if minecleaner80120.150
read, delete if mineplain claimant1400.000
rename, check, restore cleaner106440.415
rename, check, restore plain claimant2400.000
查看完整验算程序
# Chapter 5. p53: once a cleaner may steal, even releasing becomes a race.
# Window A owns the lock but has been silent; cleaner B deletes A's lock
# and claims; window C claims normally. A then wakes and releases.
# Release "read, then delete if mine" can delete B's fresh lock; the
# "rename to a private tombstone, check, put back" release looks more
# careful yet widens the race. Without a cleaner both are safe.
# Each schedule is counted once; double = B and C both end up holding.
from functools import lru_cache

A_READ = ("a_read", "a_del_if_mine")
A_TOMB = ("a_rename", "a_restore_if_not_mine")
B_CLEAN = ("b_delete", "b_create", "hold")
B_PLAIN = ("b_create", "hold")
C_PLAIN = ("c_create", "hold")


def step(op, lock, tomb, seen):
    """Return lock, tomb, seen, ok."""
    if op == "a_read":
        return lock, tomb, lock, True
    if op == "a_del_if_mine":
        return (None if seen == "A" else lock), tomb, seen, True
    if op == "a_rename":
        return None, lock, seen, True
    if op == "a_restore_if_not_mine":
        if tomb not in (None, "A") and lock is None:
            return tomb, None, seen, True
        return lock, None, seen, True
    if op == "b_delete":
        return None, tomb, seen, True
    if op in ("b_create", "c_create"):
        who = op[0].upper()
        if lock is None:
            return who, tomb, seen, True
        return lock, tomb, seen, False
    return lock, tomb, seen, True


def count(progs):
    @lru_cache(maxsize=None)
    def walk(lock, tomb, seen, pcs):
        live = [i for i in range(3)
                if pcs[i] is not None and pcs[i] < len(progs[i])]
        if not live:
            held = [i for i in (1, 2) if pcs[i] == len(progs[i])]
            return 1, (1 if len(held) == 2 else 0)
        tot = bad = 0
        for i in live:
            nl, nt, ns, ok = step(progs[i][pcs[i]], lock, tomb, seen)
            npcs = list(pcs)
            npcs[i] = pcs[i] + 1 if ok else None
            t, b = walk(nl, nt, ns, tuple(npcs))
            tot += t
            bad += b
        return tot, bad
    return walk("A", None, None, (0, 0, 0))


print("release by A          B is         schedules  double  share")
for an, a in (("read, delete if mine", A_READ),
              ("rename, check, restore", A_TOMB)):
    for bn, b in (("cleaner", B_CLEAN), ("plain claimant", B_PLAIN)):
        tot, bad = count((a, b, C_PLAIN))
        print("%-22s %-14s %7d %7d  %5.3f" % (an, bn, tot, bad,
                                              bad / tot))

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《多窗口文件原子锁并发协议、断电孤儿锁自愈与跨窗口交接状态机母典》第 5 章「孤儿锁判别:沉默多久才算死」(版本 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}
}

本书其他章节结论