返回学习路线

从两个地址空间到断电重启：OS-16的完整账本 ​

这份任务在同一套机器、进程与设备假设中，跟踪两个数值相同的地址为何隔离，fork怎样先共享再分离，父子为何共享文件位置，以及一次成功写入到何时才值得报告“重启仍在”。先独立完成问题，再对照答案。所有地址标0x时为十六进制，其他数量为十进制；物理页框号与设备块号属于不同编号空间。

学习入口与路线 ​

核心八站：进程与地址空间理路程序、进程与地址空间Process and address space · OS process · 操作系统进程以程序映像、资源容器与线程执行状态划分进程，说明同一虚地址的隔离、受控共享及fork/exec的不同效果。 → 页表转换理路页表地址转换与访问权限Page table address translation · VPN PFN offset · 虚实地址转换由虚页号、页内偏移与PTE计算物理地址，分别检查驻留、访问类型和用户权限，并建立可检查的隔离不变量。 → 按需缺页理路按需分页与缺页处理Demand paging · Page fault handling · Lazy page allocation依据合法区域与访问种类分类故障，完成零页分配、文件换入或拒绝访问，并保持失败时的映射和数据不变量。 → COW fork理路fork的写时复制与页生命周期Copy-on-write fork · COW fork · 写时复制进程创建在父子私有内存语义下追踪PTE降权、引用计数、写故障复制、独占快路和退出释放，并核验分配失败不破坏旧状态。 → fd与打开状态理路文件描述符与共享打开状态File descriptor and open file description · OFD · dup fork shared offset区分进程fd表、打开文件描述与inode，逐次计算dup/fork后的共享offset和引用关闭，并处理短读写。 → 页缓存回写理路页缓存、脏页与回写代际Page cache and writeback · Dirty page redirty · Buffered file I/O分离应用缓冲、内核页缓存和设备缓存，追踪同一页回写期间再次变脏，并解释write返回为何不足以证明持久化。 → 文件与目录同步理路文件同步与目录持久化fsync and directory durability · fdatasync · File persistence boundary为write、设备完成、fsync文件与fsync目录各写出准确承诺，区分内容保存、名称保存和多对象原子性。 → 崩溃安全替换理路崩溃安全的单文件替换Crash-safe file replacement · Atomic file replacement protocol用新文件内容先稳定、同目录原子重命名、目录再稳定建立恢复后完整旧版或新版的合同，并区分未知结果与多文件事务。。它们连成问题主线，不是要求把所有阅读顺序都当定义前置。

按需补课：算不出页表项的字节地址时读多级页表理路多级页表与稀疏地址空间Multilevel page table · Hierarchical page table逐级拆分VPN并计算PTE的物理地址，给出稀疏页表空间账本、失败停点和未缓存遍历成本。；不清楚故障怎样进入内核、为什么重试原PC时读trap与系统调用理路陷阱入口与系统调用Trap and system call · 用户态与内核态把受控特权转移分成硬件入口、软件保存、参数验证与返回，区分普通call、缺页重试和调度切换。和精确异常理路精确异常与已完成指令前缀Precise exception · Precise interrupt state把故障时的架构状态约束为顺序执行前缀，区分停止取指、清除年轻操作和保留较老效果。；不理解降W后仍越权时读TLB失效理路TLB与地址翻译失效Translation lookaside buffer · TLB miss · TLB invalidation将翻译缓存键、权限和映射生命周期一起核对，区别TLB未命中与缺页，构造改PTE后仍越权的最短反例。；不清楚运行与等待的区别时读派发理路上下文切换与线程派发Context switch and dispatch · Ready running blocked用就绪、运行、阻塞三态解释CPU执行权交接，逐步核对用户trap frame、内核续点和地址空间恢复。；对inode和名字混淆时读文件身份与路径理路文件对象、目录与路径名Inode directory and pathname · Hard link and symbolic link · 硬链接与符号链接把名称到文件对象的映射与对象本身分开，执行逐分量路径解析、硬链接计数、符号链接与删除后的存活。。页框、堆对象和块三种分配的区别，可比较物理页分配理路物理页分配与安全回收Physical page allocator · Page frame free list把页框所有权、空闲链、发布前清零和最后使用者释放串成分配协议，解释它与用户堆对象分配的不同粒度。、堆对象布局理路堆对象布局与分配Heap object layout and allocation · Object descriptor · Bump-pointer allocation用对象头、字段偏移与指针描述符规定可扫描的堆布局，并给出带溢出检查和初始化约束的顺序分配器。与文件块映射理路文件块映射与空间分配File block mapping · Direct and indirect blocks · 文件块位图分配由文件字节偏移经过inode直接和间接指针找到设备块，并把数据、大小、指针和空闲位图的共同恢复义务列全。。

进阶分支：从设备完成理路设备I/O、DMA与完成边界Device I/O and DMA · Polling interrupt DMA给设备请求建立提交、数据搬运、命令完成和稳定存储四个边界，核验描述符所有权、DMA地址与缓冲生命周期。和文件块映射进入四块日志恢复理路文件系统重做日志与提交边界Filesystem redo journal · Journaling filesystem commit把文件数据、位图、inode和目录组成有界块事务，证明payload、commit、home和清日志的稳定顺序及再次崩溃恢复。，再接既有从稳定日志到第二次重启，研究不同模型下的WAL、CLR和ARIES。另可用Clock理路Clock页替换与回收资格Clock page replacement · Second-chance page replacement用环形指针和访问位近似近期使用，同时把选受害者、撤销映射、脏页保存与实际复用分成不同步骤。核对回收资格，用文件映射理路文件映射与私有修改Memory-mapped file · MAP_SHARED and MAP_PRIVATE把文件偏移映为虚地址，区分共享映射写回、私有COW写和映射生命周期，并检查close、截断与掉电边界。检查无read调用时的文件访问。

入口自测：0x12FF后一个字节是什么地址？同一整数fd=3在两个无关进程中是否必指同一文件？写回某层缓存是否就等于掉电持久？答案依次为0x1300；不一定，需看两份fd表；不是，要指出稳定边界。若三项都能解释，可直接开始。

固定机器、对象与故障范围 ​

OS-16是自定教学机，单核、16位虚实地址、字节寻址、256B页；单字节访问逐个完成，无弱内存或投机效应。两级页表拆分为4位根索引、4位叶索引、8位偏移，每项16B、每表16项。根和叶表来自内核保留帧，不计进下面的数据页引用；根项只有下一层指针与存在位，叶项有PFN与U/R/W/X，软件另记COW和合法区域。所有用户访问必须经当前地址空间权限检查。

P根PFN0x01的索引1指向叶表0x02；Q根0x03的索引1指向叶表0x04。新子C使用另备好的根0x05、叶表0x06。初始数据如下：

进程	VPN	PFN/状态	逻辑权限	初值
P	0x10	0x40，驻留	用户RX	只读代码
P	0x12	0x30，驻留	用户RW	offset0xAB=7；0xF0、0xF1为ASCII X、Y
P	0x13	合法匿名区域，尚未驻留	用户RW	首次使用应全零
Q	0x12	0x50，驻留	用户RW	offset0xAB=9

其他用户地址无合法区域。数据空闲帧依次0x60、0x61、0x62；每个进程对一个私有页最多一个映射，主线无DMA pin、页缓存持有者或私有页别名。数据ref只计用户叶PTE数量，页表帧与内核临时所有权另计。TLB初始为空，有4项，以(ASID,VPN)为键并缓存权限；映射变化及权限收紧须完成对应失效，ASID不在本任务中复用。跨页的多字节原子性不是本实验假设。

文件系统初始有稳定目录d，其中log→inode42、state→inode45。inode42为8B的abcdefgh，一个数据块；inode45为3B的OLD。P已打开log为fd3→O7，O7.offset=0，再dup成fd4。暂无其他fd。文件I/O按列出的顺序完成，无append或信号中断；普通read/write移动OFD共享位置。系统调用拷贝用户数据时也遵守COW隔离。

设备块也是256B，普通写可先进入设备易失缓存，设备可任意选择先稳定哪一个待写块；同一块的版本保持顺序。单块稳定写原子，设备flush成功使队列之前提交的写全部稳定。掉电丢弃DRAM、寄存器、TLB和设备易失缓存，保留稳定块；不含媒体损坏、谎报flush或撕裂稳定块。文件及目录同步、rename恢复原子性分别按后文声明。

题目：按事件维护五份账本 ​

A. 页表、TLB与两类故障 ​

1. 分别计算P、Q读0x12AB的根项物理地址、叶项物理地址、最终物理地址与读值。解释为什么两次都可以TLB miss，却没有page fault
2. P在PC0x1040向0x1305写1。列出故障、区域核验、分配、清零、PTE发布、TLB处理与重试之后的状态
3. P向0x1000写2。指出哪项权限拒绝，数据/空闲帧是否改变。另说明若一个两字节write缓冲从0x12FF开始，为什么必须检查0x13

B. 一次fork与两种COW写路径 ​

P fork出C，继承地址空间初始内容和两项fd。C向0x12AB写8，P随后向同地址写11，C再解除VPN0x13映射。每步给父子PFN、W/COW、ref[0x30/0x60/0x61/0x40]及双方读值，算真实复制字节数。P、C此时暂不退出，继续下一节文件I/O。

再做三个独立错误实验：fork后只改PTE而保留P旧可写TLB；COW分配失败前先减旧ref；内核read复制到子用户缓冲时绕过COW。各给一条最短破坏轨迹和修正。

C. 同一打开状态与同一文件内容 ​

C从fd3读2B到0x1280；P从0x12F0缓冲向fd4写2B；C再独立open log得到fd5→O8，从fd5读3B到0x1282。记录每次返回内容、inode42内存内容、O7与O8的offset和引用数。

依次关闭P:3、C:4、C:3、P:4。哪一步O7消失？O8是否受影响？随后关闭C:5并让P、C退出，完成数据页引用的释放账本。Q继续存在。

D. 写回期间再写，与成功的不同含义 ​

取C节独立O8已经读出abX、尚未执行第一次close时的inode42状态：页缓存为abXYefgh，稳定块仍为abcdefgh，当前代g=1、已完成回写代c=0、稳定代s=0。提交代1的不可变快照；P的后续一次文件写把第0字节改Z（把这一事件安排在O8已读完abX之后、第一次close之前），得到代2。然后代1设备完成、代2提交并完成、最后flush成功。每步给dirty、在途代和允许恢复内容。

设备能否先稳定代1，再通知其命令完成？为什么不能把实际稳定代s与完成通知代c固定写成s≤c？如果有应用stdio缓冲，还欠哪一次交接？

E. 四块日志与单文件替换 ​

为独立验证日志实现，从一份没有/d/new的稳定快照开始。T创建inode43、名称new和数据NEW，改变home块70（数据）、80（位图）、81（inode）、82（目录）。4份after-image在90…93，提交头在94。只允许一个事务，未提交home不得写；日志容量正好4块。

列全以下阶段的掉电结果：payload部分稳定；payload全稳但commit未确认；commit已稳但home仅写完任意子集；home全稳但头未清稳；空头已稳。给出恢复又掉电为什么安全的论证，及省去三道关键屏障各自的反例。

最后回到稳定state→45、内容OLD的应用场景，独占新建同目录tmp→46并写NEW。要求任意崩溃点恢复后state为完整OLD或完整NEW，成功确认后为NEW。请给API次序、每个崩溃窗口的允许答案，以及支撑“旧或新”的额外文件系统条件。

答案与关键推理 ​

A的答案：地址和值都要带身份 ​

0x12AB分成(1,2,0xAB)。P根项在0x0100+16=0x0110，得叶表PFN0x02；叶项在0x0200+32=0x0220，得PFN0x30；最终0x30AB，值7。Q相应为0x0310、0x0420、0x50AB，值9。两次冷TLB都要查表，但页表驻留且有读权限，所以没有fault。计入数据读取、忽略缓存时每次两次PTE读加一次数据读，共3次内存访问。

P的0x1305写故障发生时还未写数据。区域授权后取0x60，清零256B，安装VPN0x13→0x60且U/R/W，失效相关翻译，回到同一PC0x1040重试；最后0x6005为1，其余255B为零，ref[0x60]=1。若把PC直接加4就丢掉了应完成的写。

写0x1000违反代码区域W=0，不能把它当COW；0x40内容与空闲链都不变。两字节缓冲0x12FF和0x1300跨两个虚页，物理页框并不要求连续，不能从0x30FF直接读0x3100当作下一字节。

B的答案：复制一次，故障两次 ​

边界	P的VPN12	C的VPN12	ref30	ref60	ref61	ref40
fork后	30，R/COW	30，R/COW	2	2	0	2
C写8后	30，R/COW	61，RW	1	2	1	2
P写11后	30，RW	61，RW	1	2	1	2
C解除VPN13	30，RW	61，RW	1	1	1	2

表内页号为十六进制。C写时复制256B，P写时因ref30=1直接恢复写权，仍需失效翻译。父子最后分别读11、8。代码页40从未标COW，即使只剩一个引用也不能随意变可写。

遗漏父TLB失效时，P沿旧W=1项直接改30，C立刻见11，违反私有内存语义。分配前减ref又遇到内存不足时，计数不再反映原PTE，父可能错误走独占写路径；先成功准备新页，再发布新PTE和调整旧引用才能保留失败原态。内核copyout通过物理映射也可绕过用户只读位，故它必须调用同一个检查/分离路径；子read缓冲写8时若直接改30，父的7也会变8。

C的答案：两个offset，一个inode ​

fork后O7有P:3、P:4、C:3、C:4四个引用。C读到ab，O7.offset=2；P写XY返回2，文件页变abXYefgh，O7.offset=4。C重新open建立O8，初始offset0，读取3B返回abX后offset3；O7仍4。子用户目标0x1280及0x1282都落在已分离的页61，不再影响父内存。

四次close使O7.refs依次3、2、1、0，最后才释放O7；O8仍refs1、offset3。关闭C:5释放O8。随后P退出使ref30、ref60降0，释放30和60，ref40从2到1；C退出释放61并使ref40到0，释放40。Q的50始终ref1。页表帧另由内核回收，不混入这份数据计数。

在一个独立短写变体中，以abcdef为6B输入，依次返回2、1、3，正确循环分别发送剩余前缀ab、c、def；返回0要报告无进展，不能无穷重试；负值按目标API错误语义处理。read请求0B可在非EOF返回0，因此正长度是本题EOF判断的必要条件。

D的答案：干净也可能尚未稳定 ​

事件	(g,c,w)	dirty	最保守的稳定内容
代1提交	(1,0,1)	是	abcdefgh
再写Z得到代2	(2,0,1)	是	abcdefgh
代1设备完成	(2,1,空)	是	abcdefgh
代2设备完成	(2,2,空)	否	abcdefgh
覆盖代2的flush成功	(2,2,空)	否	ZbXYefgh

表格选择设备尚未主动稳定的合法轨迹，实际也可更早稳定部分已提交版本。完成代1不能清除代2的dirty；普通命令完成不能代替持久化。另一个合法顺序是设备先稳定代1，再通知完成，此时s=1、c=0；s与c分别不大于当前g，但并无全序。应用stdio缓冲还需成功fflush或等价交接，内核才能见到待同步字节。

D中的再写Z是同一进程生命周期内的插入事件，固定放在C节O8已读出abX之后、第一次close之前；其显式位置写不改O7的位置，本实验采用pwrite语义。如果只想复算C节原offset表，可先不插入D事件，它不改变该表。

E的答案：恢复的是提交边界 ​

payload部分稳定、H为空时忽略日志，home保持完整旧；payload全稳、提交头尚未确认时，按稳定头可能旧或新。提交头一旦稳定，全部payload必先稳定；无论home当前完成0、1、2、3或4块，恢复重写全部4块为完整新。home全稳但H仍COMMIT时，重复写完整after-image不改变结果。H稳定清空后，home已全稳，可复用日志。

恢复再次崩溃只会留下“COMMIT仍在，home部分或全部新”，再次重做依然得到完整新。不得在home flush成功前持久清头。省payload屏障会产生稳定COMMIT指向旧payload；省home屏障会产生空头配混合home；清头未稳定便复用日志，会让旧COMMIT配上新一轮payload。这三个错误都有可恢复结果不属于完整旧/新的反例。

4块事务需4次payload写、1次头写、4次home写、1次清头写，共10次块写和4次flush。这是本协议账本，不预测真实磁盘时间，也不声称所有日志文件系统都相同。

应用替换次序为：独占创建同目录tmp；写完NEW并设置元数据；成功fsync(tmp)；rename(tmp,state)；成功fsync(d)；再报告持久成功。旧state及目录原本已稳定、无并发操作者，文件系统保证rename恢复原子性且新对象依赖内容先稳定。rename前恢复OLD；rename后目录未同步时OLD或NEW；目录同步成功后NEW。临时名可能遗留，不能把未发布tmp当作已提交版本。

Linux rename文档的运行时原子替换只排除其他进程看到名称空窗，不单独给出任意断电的旧/新二选一；本题用OS-16日志事务补足该前提。跳过file fsync可能发布半写新内容，跳过dir fsync可能在报成功后回退旧名。已打开inode45的fd可以继续读OLD，新open state才取inode46，这不违反路径发布合同。

迁移与边界自测 ​

1. 把P映射扩到每个根分支至少一页，多级表一定更省吗？答案：否，16张叶表加根共17×256=4352B，超过平表256×16=4096B；稀疏性是关键
2. 若COW页有两个同进程私有别名，只复制故障PTE会怎样？答案：两别名不再指同一对象。需要按别名组更新，或像主模型一样明确排除该情况
3. 若所有Clock候选都被DMA pin，可以丢一个A=0的页吗？答案：不行，访问位只描述近期使用，pin约束生命周期；应等待、选择其他资源或报告无合格页
4. 把state拆成两个文件分别执行替换，是否得到两文件事务？答案：否，允许一新一旧；需额外原子发布清单/根，并保证其引用内容先稳定
5. file fsync成功后继续原地改文件，旧代是否永久保留？答案：否，fsync不是快照。后续部分稳定写可覆盖旧代，若需要旧/新可恢复性，应使用独立对象与发布协议
6. 把页表叫作shadow page table能否直接获得数据库提交？答案：不能，OS页表服务CPU地址权限，数据库影子映射服务稳定版本发布；其对象、观察和故障合同不同

可执行证据与适用范围 ​

下载OS-16标准库复算脚本，用Python 3执行。脚本不访问主机内存、设备或文件系统API，只模拟本文整数地址、PTE、引用图和稳定块状态；它会打印JSON结果并在不变量失败时停止。

2026-10-08实际运行结果：773次断言检查；地址分别0x30AB/0x50AB；COW复制1页256B、写故障2次；C节文件结果abXYefgh，D节再写后为ZbXYefgh，独立O8关闭前offset3；Clock两次扫描4和2槽；日志36个阶段/稳定子集场景及288个恢复再崩溃子集场景均通过。脚本也确认三个省略屏障版本产生混合恢复反例，以及COW分配失败保留原态、内核拷贝分离和零长度进展处理。

有限检查支持这些具体轨迹与枚举范围；一般协议正确性依前述归纳不变量。没有运行真实xv6/Linux内核、物理断电、设备兼容、站点浏览器或构建测试，不能从模拟通过外推这些结果。

模型的来源和参数对照见各概念页参考资料，主要是xv6 rev5（2025-09-02）、OSTEP v1.10相关章节、POSIX.1-2024与Linux man-pages 6.19。OS-16的16位地址、256B块、4槽日志和具体进程数据为本任务构造。