“Clock在有限驻留页框上维护环、手指位置h和访问位A。OS 16中一次成功用户访问把对应页的A置1。为选一个可回收页,手指依环前进:遇到被pin或不可回收页就跳过;对可回收且A=1者,清A…”
形式陈述
分页把地址空间理路程序、进程与地址空间Process and address space · OS process · 操作系统进程以程序映像、资源容器与线程执行状态划分进程,说明同一虚地址的隔离、受控共享及fork/exec的不同效果。切成等长虚页,把物理内存切成同长页框。页大小为
页表项PTE记录物理页框号PFN以及当前硬件权限。在OS-16中,一个驻留叶PTE含present, PFN, U, R, W, X;U允许用户态使用,R/W/X分别允许读、写、取指。内核另存合法虚拟区域表,记录哪些尚未驻留页可按需建立。present=0本身不能区分合法缺页和非法地址。
对用户访问a,硬件先确认地址宽度和PTE存在,再检查U与对应访问位。只有通过检查才访问
失败访问不能先写入数据、再向内核报告错误。跨页的多字节访问必须检查所有涉及页,原子性和是否允许部分效果须由指令规格另定;本页计算使用单字节,避免偷偷假定跨页原子写。
页表抽象可由多级页表理路多级页表与稀疏地址空间Multilevel page table · Hierarchical page table逐级拆分VPN并计算PTE的物理地址,给出稀疏页表空间账本、失败停点和未缓存遍历成本。实现。正文中的权限字段是OS-16的字段,不等于任一真实ISA的PTE位布局。
直觉
页表改变的是一整页的起点,偏移保留。页0x12中的第0xAB个字节被放到页框0x30后,仍是该页框中的第0xAB个字节。硬件查到一个页框号还不够:权限检查决定这次特定动作是否允许到达它。
“进程有这个地址”可表示它保留了一个合法区域,也可表示已有驻留页,甚至只表示整数落在地址宽度内。这三句话不等价。保留的堆页可能尚无物理页,代码页可能可执行却不能写。
例子与边界
同一数值的两次转换
B=256=0x100,P和Q的虚页0x12分别映射到PFN0x30和0x50,都允许用户读写。对v=0x12AB,VPN=0x12、offset=0xAB;P得到0x30×0x100+0xAB=0x30AB,Q得到0x50AB。地址空间身份选择页表,VPN选择条目,offset选择字节,三者缺一不可。
| 进程与动作 | PTE或区域状态 | 结果 |
|---|---|---|
| P读0x12AB | present,U,R,W;PFN=0x30 | 读物理0x30AB |
| Q写0x12AB | present,U,R,W;PFN=0x50 | 写物理0x50AB |
| P读0x1305 | PTE不驻留;区域允许匿名读写 | 进入缺页处理,由软件决定补页 |
| P写0x1000 | present,U,R,X;PFN=0x40 | 写权限故障,物理0x4000不变 |
| P读0xFF00 | 无用户合法区域 | 访问无效,不能擅自分配 |
代码页的W=0和COW页的W=0在硬件上都可以产生写故障。是否能修复要看内核元数据;不能把所有只读页都复制成可写页。缺页处理理路按需分页与缺页处理Demand paging · Page fault handling · Lazy page allocation依据合法区域与访问种类分类故障,完成零页分配、文件换入或拒绝访问,并保持失败时的映射和数据不变量。负责这种分类。
页尾与越界
0x12FF仍在VPN0x12,offset255;0x1300已在VPN0x13,offset0。若对0x12FF做两字节写,第二字节不再受0x12的PTE保护。只检查起始地址而使用连续物理地址0x30FF、0x3100,会把不同虚页错误视为相邻页框。
推论与应用
隔离的归纳条件是:用户无法改页表;不存在未经许可的共享映射;每次访存都按当前进程和权限翻译;映射变更后无陈旧翻译继续使用。初始页分配互不重叠,一次允许访问只触及该进程获准页框,因而不改变其他私有页。最后一项需要TLB失效理路TLB与地址翻译失效Translation lookaside buffer · TLB miss · TLB invalidation将翻译缓存键、权限和映射生命周期一起核对,区别TLB未命中与缺页,构造改PTE后仍越权的最短反例。,只检查内存中的PTE并不充分。
映射表空间、查表时间和数据访问时间是三项成本。OS-16的256个虚页若用每项16B的平表,占4096B,即16个物理页;页表本身也要占内存,不能把它当免费数学函数。
数据库影子分页理路影子分页恢复Shadow paging recovery · Shadow paging以页表写时复制和稳定根指针切换发布事务,使崩溃后可在完整旧映射与完整新映射之间选择。中的“页表”把数据库逻辑页号映到存储位置,并以稳定根发布事务。本页页表服务每次CPU地址翻译与权限控制,更新它不会提交数据库事务,也不会让用户数据自动掉电持久。两者可以同时存在于一台机器。
参考资料
- Remzi与Andrea Arpaci-Dusseau,OSTEP: Paging—Introduction,第18章,VPN/offset/PFN与权限;本文地址、表宽和轨迹为OS-16自定。
- Cox、Kaashoek、Morris,xv6教材 rev5,§3.1、§3.6,真实Sv39页表结构与用户映射的教材对照。