是什么

  • 定义:请求分页系统中,当进程访问的逻辑页面不在物理内存且驻留集已满时,通过页面置换算法(FIFO / Clock / LRU)选出淘汰页换出到外存;结合快表(TLB)与缺页中断重执机制,计算完成一次逻辑地址访问的端到端耗时。

  • 大白话:书架(内存驻留集)位置满了,想看新书(缺页)就得按某种规矩把一本旧书丢回仓库;查书时先看手边备忘录(TLB),没有再去翻目录大表(页表),如果连书都没有就得跑趟仓库,回来后再把书翻开(重新执行指令读数据)。

核心内容

1. 三大经典页面置换算法机制对比

置换算法淘汰依据 / 决策逻辑数据结构与维护开销核心特性 / 考点
FIFO(先进先出)淘汰装入内存时间最早的页面队列记录进入顺序;开销极低会产生 Belady 异常(分配页框变多,缺页次数反而增加)
LRU(最近最少使用)淘汰距当前时刻最久未被访问的页面栈或寄存器记录访问历史;硬件开销大性能接近最优(OPT),严格遵循局部性原理,无 Belady 异常
Clock(时钟/二次机会)顺时针循环扫描,访问位(Use bit)为 0 直接淘汰,为 1 则清 0 免死并后移循环链表 + 扫描指针;软硬件折中最佳方案本质是兼顾 FIFO 简单性与 LRU 局部性的二次机会策略

2. Clock 算法转动淘汰执行流水线

设时钟指针当前指向某物理页框:

  1. 检查指针当前所指页框的访问位 :

    • 若 :立即选中该页框作为淘汰目标,将新页装入该页框,指针顺时针下移一位,置换结束。

    • 若 :获得免死机会,==将访问位清 0()==,指针顺时针下移一位,继续检查下一个页框。

  2. 第二轮兜底:若第一轮所有页框的 原本均为 1,则一圈下来全部被清 0;指针转回起点后,起点页框的 已为 0,必定在第二轮首个被淘汰。

3. 请求分页访问耗时推导流水线(无死角分解)

无论题目如何变化,一次完整的虚拟地址访存耗时必然属于以下三种情形之一:

情形 1:TLB 命中(极速路径)

  • 触发条件:虚页号在 TLB 中存在。

  • 流水线:查 TLB 直接拿物理地址访存读写数据。

  • 计算公式:

    • :访问一次快表(TLB)耗时(如 )。

    • :访问一次主存(Memory)耗时(如 )。

情形 2:TLB 未命中,页表命中(普通路径)

  • 触发条件:虚页号不在 TLB 中,但在主存页表中有效位为 1。

  • 流水线:查 TLB 失败 查主存页表获取页框号并更新 TLB 访存读写目标数据。

  • 计算公式:

    • 第一个 为查页表耗时;第二个 为真正访存读取数据耗时。

情形 3:TLB 未命中,发生缺页中断(慢速异常路径)

  • 触发条件:虚页号在页表中有效位为 0。

  • 流水线(五步闭环):

    1. 查 TLB 未命中(耗时 );

    2. 查主存页表,有效位为 0 触发缺页异常(耗时 );

    3. 执行缺页中断处理:调页、置换、更新页表与 TLB(耗时 );

    4. 重新执行产生缺页的访存指令,查 TLB 必然命中(耗时 );

    5. 访存读取目标数据(耗时 )。

  • 计算公式:

    • :操作系统缺页中断处理平均时间(通常达 )。

物理地址合成的双轨速算法:直接拼接法 vs 二进制对齐法

1. 底层原理:为什么能“直接拼接”?

  • 地址结构本质:在分页存储管理中,无论是逻辑地址还是物理地址,其==页内偏移量 的二进制位数和具体数值在转换前后绝对不变==。

  • 物理地址公式的位运算本质:

    • :物理页框号。

    • :页内偏移量占用的二进制位数(由页面大小 决定)。

    • :页内偏移量(占低 位)。

  • 乘 的物理本质就是“左移 位”:把 放到高位,低 位全部腾出来补 0,再与低 位的 相加,本质就是高低位直接拼在一起。

2. 分支一:直接拼装法(当偏移量位数 为 4 的整数倍时)

  • 判定条件:

    • 十六进制下,1 个 Hex 字符严格等于 4 位二进制(bit)。

    • 若页内偏移量位数 满足 (即 是 4 的整数倍,如 位对应页面大小 4KB),则低 位二进制恰好完整对应十六进制的低 位字符。

  • 计算规则:

    • 无需任何进制转换与乘除运算,直接将 的十六进制写在前面,把 的十六进制写在后面:

  • 经典真题实例(以 2009 年真题为例):

    • 页面大小 位,恰好占用 3 个 Hex 位()。

    • 逻辑地址为 1565H 剥离低 3 位得到 。

    • 查询得到目标物理页框号 。

    • 直接拼接:

3. 分支二:二进制对齐合成法(当偏移量位数 不是 4 的整数倍时)

  • 判定条件:

    • 若页内偏移量位数 满足 (如 位对应页面大小 1KB, 位对应 512B 等)。

    • 此时偏移量 在十六进制中不是整数字符位(如 10 位二进制对应 2.5 个 Hex 位),严禁直接用十六进制字符硬拼,否则会发生位错位。

  • 万能三步计算流程:

    1. 转二进制:将 转换为二进制,将偏移量 转换为补齐的 位二进制。

    2. 拼接对齐:高位写 二进制,低位写 二进制,直接并置形成完整的二进制物理地址。

    3. 4位一组转回 Hex:从最低位开始,每 4 位二进制划分为一组,转换为十六进制输出。

  • 经典真题实例(以 2010 年真题为例):

    • 页面大小 位(不是 4 的倍数)。

    • 逻辑地址为 17CAH,转二进制为 0001 0111 1100 1010,截取低 10 位得到偏移量:

    • 情形 A(FIFO 换入 7 号页框,):

      • (补齐为 6 位即 000111)

      • 拼接二进制(高 6 位 + 低 10 位 ):

        Plaintext

        PFN(7):   0 0 0 1 1 1
        d(3CAH):              1 1 1 1 0 0 1 0 1 0
        -----------------------------------------
        合并后:   0 0 0 1 | 1 1 1 1 | 1 1 0 0 | 1 0 1 0
        Hex对照:     1    |    F    |    C    |    A
        
      • 最终物理地址为:1FCAH。

    • 情形 B(Clock 换入 2 号页框,):

      • (补齐为 6 位即 000010)

      • 拼接二进制(高 6 位 + 低 10 位 ):

        Plaintext

        PFN(2):   0 0 0 0 1 0
        d(3CAH):              1 1 1 1 0 0 1 0 1 0
        -----------------------------------------
        合并后:   0 0 0 0 | 1 0 1 1 | 1 1 0 0 | 1 0 1 0
        Hex对照:     0    |    B    |    C    |    A
        
      • 最终物理地址为:0BCAH。

4. 易错对照速查口诀

“4KB(12位)直接抄字符,1KB(10位)老实拆二进制。”

遇 1KB 页面切忌直接把页框号 7 和 3CA 拼成“73CAH”,因为 1KB 跨度是 400H(不是 1000H),,加上 3CAH 必须是 1FCAH。

例题

例题 1:置换算法具体轨迹对比(2010 统考真题)

  • 题目:

    逻辑与物理空间均为 64KB,按字节编址。页大小 1KB,分配 4 个页框。当前驻留集状态:

    0号页(7号页框,时刻130,访问位1);1号页(4号页框,时刻230,访问位1);2号页(2号页框,时刻200,访问位1);3号页(9号页框,时刻160,访问位1)。

    时刻 260 访问逻辑地址 17CAH:

    1. 求该逻辑地址对应的页号。

    2. 分别用 FIFO 和 Clock(当前指针指向 2 号页框,顺时针方向:2号 4号 7号 9号)计算对应的物理地址。

  • 分析:

    • 页大小 1KB()。17CAH 转二进制低 10 位偏移为 3CAH,高 6 位页号为 。访问 5 号页发生缺页。

    • FIFO:0号页装入时刻最早(130),淘汰 0 号页,将其占用的 7 号页框分配给 5 号页。物理地址 。

    • Clock:当前指针指向 2 号页框。第一轮顺时针扫过 2、4、7、9 号页框,各页访问位均从 1 置 0;指针再次指向 2 号页框时访问位为 0,选中淘汰 2 号页,5 号页装入 2 号页框。物理地址 。

  • 答案:

    1. 逻辑地址 17CAH 对应的页号为 5。

    2. FIFO 算法下的物理地址为 1FCAH;Clock 算法下的物理地址为 0BCAH。

例题 2:缺页重执与访存耗时流水线(2009 统考真题)

  • 题目:

    页面大小 4KB,内存访问时间 100ns,快表(TLB)访问时间 10ns,缺页中断处理时间 (含更新 TLB 和页表时间)。驻留集大小为 2,采用 LRU 置换算法。初始 TLB 为空,主存中驻留:0号页(101H,有效位1)、2号页(254H,有效位1)。逻辑地址访问序列:2362H,1565H,25A5H。

    1. 依次访问三个虚拟地址各需多少时间?

    2. 虚拟地址 1565H 对应的物理地址是多少?说明理由。

  • 分析:

    • 页大小 4KB,低 3 位 Hex 为偏移量。

    • 访问 2362H(2号页):查 TLB 缺失(10ns) 查页表命中(100ns) 访存取数(100ns)。耗时 。2号页入 TLB。

    • 访问 1565H(1号页):查 TLB 缺失(10ns) 查页表缺页(100ns) 调页中断处理(,LRU 淘汰 0 号页,1 号页装入 101H 页框,更新 TLB) 重新执行指令查 TLB 命中(10ns) 访存取数(100ns)。耗时 。

    • 访问 25A5H(2号页):查 TLB 命中(10ns) 访存取数(100ns)。耗时 。

  • 答案:

    1. 访问耗时依次为:2362H 需 210 ns;1565H 需 ;25A5H 需 110 ns。

    2. 1565H 对应的物理地址为 101565H。理由:驻留集满且访问 1 号页缺页,按 LRU 策略淘汰最久未访问的 0 号页,腾出 101H 页框分配给 1 号页,拼接页内偏移 565H 得到 101565H。

⚠️ 易错点

Warning

  • 缺页耗时漏算“指令重执”阶段:

    • 极易算成 。必须牢记:操作系统中断服务程序只负责把数据搬到内存并建立页表映射,==返回后硬件 CPU 必须重走一遍 TLB 命中与访存读数(额外叠加 )==。

  • 混淆“被淘汰的页号”与“所在页框号”:

    • 算物理地址时必须用物理页框号(Page Frame)乘页面大小,严禁直接拿逻辑页号相乘。

  • Clock 算法扫描顺序误区:

    • Clock 算法严格沿表盘顺时针指针顺序轮转,不要擅自按页号(0, 1, 2, 3)的数字升序去检查。

  • 程序访问不需要“按顺序翻页”:

    • 内存置换只针对 CPU 当前指令正在请求的目标页(如直接从 3 跳到 5),无需先将中间未请求的页调入。