《多窗口文件原子锁并发协议、断电孤儿锁自愈与跨窗口交接状态机母典》各章定量结论
同时开多个写作窗口去领卷号,最常见的写法是先看锁在不在、不在就建,再给锁加一个超时,号称断电后能自愈。立项命题说:先检查后创建必有竞态窗口,只有原子独占创建才保证互斥;租约自愈若不配单调计时与围栏令牌,会出现双持锁。本书把协议的每一步写成原子操作,在内存里模拟文件系统,穷举全部交错调度,并修正蓝图四处:「必有」说的是调度空间,两窗口 16 种调度有 12 种双领,墙钟上的频率取决于出发是否扎堆,四个窗口 2 秒内一拥而上时每批 0.02966;迪杰斯特拉 1965 年恰恰证明只靠读写也能互斥,限制在于名册必须封闭;围栏令牌出自伯罗斯的序列号与克莱普曼的整理,不出自格雷与切里顿;单调计时挡不住进程停顿,时钟完美时仍有 0.000976 的写入迟到。书中参数为示意;全部计算由书中程序生成;程序不读写任何文件;本书是非个人化经营建议,任何锁协议的上线变更与孤儿锁裁决须由主事者人工复核放行。
DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 5DL-B-254 · English version
- 第 1 章 · 竞态窗口:先检查后创建的交错穷举与墙钟宽度
程序 p11 数清了全部调度:两个窗口用先检查后创建,16 种调度里有 12 种双领;四个窗口时 74976 种里有 74880 种。原子独占创建在任何窗口数下都没有坏调度。程序 p12 把缝换算到墙钟上:分散出发时撞车罕见,一拥而上时每批约 0.02966。可是本章只回答了「用什么原语」,还没有回答一个更根本的问题:如果文件系统不提供独占创建,只给原子的读和写,多个窗口还能不能互斥?迪杰斯特拉在 1965 年给出了肯定的回答,下一章… - 第 2 章 · 只靠读写能否互斥:六个入口协议的模型检验与名册下界
第二章用模型检验器检验六个只靠读写的入口协议,复现海曼 1966 年错误解法的最短反例,并说明名册是读写算法的命门。 - 第 3 章 · 断电之后:空锁、缺状态与先写临时再链接
程序 p31 显示,一次领题被断电打断后,原样写法在滞后模型下可能留下 7 种磁盘状态,其中 3 种是空锁;刷盘把空锁减到 1 种,却消不掉;先写临时再链接把空锁减到零。程序 p32 显示,「空锁即删」的清理规则在 25 种调度里有 10 种造成双领,看两次再删也只把份额从 0.400 降到 0.250。断电留下的半成品,最好的处理是让它不出现在活人身上。可是还有一类更难的情形:窗口没有断电,只是停住了,过一会儿又醒来。租约正是为这类… - 第 4 章 · 租约、时钟与围栏令牌
程序 p41 显示,同一个钟的跳变不会制造重叠,混用单调钟与墙钟才会:墙钟跳 5 秒造成 3.000 秒重叠,跳 3600 秒造成 58.000 秒重叠。程序 p42 显示,时钟完美时,60 秒租约留 2 秒余量仍有 0.000976 的写入迟到,几乎全部来自休眠。程序 p43 显示,迟到的 380 次写入在盲写下全部覆盖新数据,在存储端核对令牌时一次也不会。租约解决的是「主人死了怎么办」,可它对主人的死活作出的是一个基于时间的猜测。… - 第 5 章 · 孤儿锁判别:沉默多久才算死
第五章讨论孤儿锁判别:笔记本沉默一小时主人已死的后验很低,一旦允许自动抢锁,连释放都会双领,80 种调度有 12 种,份额 0.150。 - 第 6 章 · 跨窗口交接状态机:让渡、令牌与只进不退的状态
程序 p61 显示,先删后建的交接在 54 种调度里有 40 种被第三方插队,原子替换消除了插队,却仍有 0.250 的调度被交出方的迟到写入损坏;加上令牌之后丢失与损坏都是零。程序 p62 显示,盲写的状态文件在 6 种调度里有 4 种倒退,先读后写仍有 0.333 倒退,每个阶段一个独占标记则为零。至此,从领题、断电、租约、孤儿锁到交接,我们已经用二十世纪下半叶的数学把多窗口协作的锁协议检验了一遍。可是独占与交接并不是计算机时代才… - 第 7 章 · 东西方原典考辨:司门「掌授管键」与迪杰斯特拉 1965
第七章考辨《周礼·地官司徒·司门》「掌授管键,以启闭国门」与迪杰斯特拉 1965 年的四个条件。 - 第 8 章 · 实证闭环:本百卷锁协议的形式化体检与预注册方案
第八章对本百卷正在使用的锁协议做形式化体检:原样零双领,加自动清理者则 48 个终止状态有 45 个双领;给出蒸馏小工具「锁协议竞态穷举器」与预注册方案,零失败证明双领率低于千分之一需 2995 批。书中以标注框区分已发表的证据、可运行的 Python 计算(19 段程序)、原典与作者的假说。
模型示意算例,非实时报价