硬件和控制结构

1. 分页

image.png

  • 虚拟地址与页表项

image.png

1.1 地址转换

| image.png | 注意点:
- 虚拟地址即逻辑地址
- 页表指针寄存器位于”进程控制块”中
- 由于页表长度基于进程长度而变化,因此页表不能在寄存器中保存,须在内存中且可访问
- 一般每个进程都一个页表,页表可能占据巨大的空间：某系统中,一个进程可有虚存2GB=231,页大小29 ,则一个进程就需要222页
- 解决:在虚存中保存页表—页表本身也使用分页机制
| | —- | —- |

1.2 二级页表

对一个32位机器,当虚拟空间大小4GB,页大小4KB时

  • 一般分页

image.png
当页大小4k,4G/4k=220,需要220页,即220=2MB个页表项,直接放置在内存占据空间

  • 二级分页

image.png

| 👉
在32位机器中,当页大小为4KB,虚拟空间4GB:
2/4k=2,分为2页,当每页都使用一个4B的页表项映射,构成一张二级页表,需要内存空间4*2=4MB | image.png
页目录表(Directory)/一级页表/根页表
页表地址(Table)/二级页表/用户页表 | 👈
把4GB空间分为1024个可被页目录索引的页组(二级页表),每个页组长4MB.包含1024个项,每项对应大小4KB的页.
此时实存中只保存了2个一级页表项 | | —- | —- | —- | | 4B页表项即32b地址,符合32位机 | | | | 2/4k=2,需要2个页目录,则1级是包含1024个项的页目录表/一级页表 | | |

1.3 倒排页表

(Inverted Page Table)
_image.png

多级页表不足 页表大小与虚拟空间大小成正比
倒排 使用散列函数将n位页号映射到散列表得到m位帧号,表中有指向倒排表的指针,倒排表中有页表项.这种结构下,散列表和倒排表各有一项对应一个实存页:
- 散列指针->页表项
- 链->页表项/物理地址

由于多个虚拟地址可能映射到一个散列表项中,需要使用链接技术管理溢出,因此无论有多少进程,支持多少虚拟页,页表只需要实存中的一个固定部分
(类比数据结构散列表有限,但通过散列函数和二次散列等方式保证了散列值的不同)
- 称为”倒排”的原因:使用帧号而非虚拟页号索引页表
|

1.4 转换检测缓冲区(TLB)

快表(TLB: Translation Lookaside Buffer)
image.png
虚存访问的普遍问题:会访问两次物理实存:访问页表、访问物理地址
使用TLB旨在解决该问题:

  • 给定虚拟地址,处理器先检查TLB
    • 若命中,则检索帧号形成物理地址(避免了二次访问)
    • 未命中,使用页号检索页表,当存在位
      • 已置位,直接从页表项中取出帧号形成物理地址,更新TLB
      • 未置位,缺页(page fault)发生,操作系统接管,从外存中取出数据装入页,更新页表

image.png

  • TLB**与cache的关系
    TLB实际上是一块特殊的cache,用于保存最近使用过的页表项,从而避免再次进入内存访问
    TLB从RAM中取数据—cache映射三种:    直接,全关联,组关联**(参考：系统级编程 Ch12 Cache深入)

    1.5 页尺寸

    image.png

    1.6 分页与缺页率

    | image.png |
    - 由a,开始页尺寸加大,缺页率升高,然后又成反比,最终,当页和进程大小一样,没有缺页出现(分段)
    - 由b,当分配的页框数越充裕,缺页率越低
    1.            <br /><br /> |
    | —- | —- |

2. 分段

image.png

| image.png | 基于分段的虚拟内存中,每个进程有唯一的段表

  • 存在位:由于一个进程可能只有一部分段在内存中,因此段表有一位表示段是否存在
    - 修改位:表明上次被装入内存到目前位置其内容是否改变
    | | —- | —- |

3. 段页式

| image.png | 段页式结构中,每个进程使用一个段表和一些页表. 段表项:包含段长和Base,无需存在位和修改位,留在页级处理

  • 页表项:类似纯粹的分页,需要P,M位
    - 程序员角度:逻辑地址=段号+段偏移
    - 系统角度:段偏移即指定的页号+页偏移

    | | —- | —- |

操作系统策略

1. 读取策略

策略意义 决定某页何时取如内存
方式
- 请求分页式(Demand paging):访问到某页时才取入
- 问题:开始可能遇到大量缺页中断
- 预约分页式(Preparing):事先读取多于当前需要的页
- 问题:当大多数页没有用到时,效率低

2. 放置策略

策略意义 决定进程块驻留在实存的什么位置
方式
- 对分段系统和NUMA(nonuniform		 
  1.     memory access非一致存储器访问)系统<br />   - 放置策略影响较大<br />- 对分页或段页式系统<br />   - 放置位置无影响,地址转换和内存访问对不同位置页框执行效率一致<br /> |

3. 置换策略⭐

策略意义 决定读取新页时应该置换出内存中哪一页
方式
- OPT:最佳策略,选择换出下次访问距当前时间间隔最长的页
- 问题:不可能实现,需要预测未来的进程
- LRU:最近最少使用,换出上次访问距今时间最长的页
- 问题:性能接近OPT,实现开销巨大
- FIFO:先进先出队列
- 问题:实现简单,但隐含替换留存时间最久的页,不一定符合局部性原理,中断多
- Clock Policy:时钟策略
- 👇时钟置换策略 ,以较小的开销实现LRU性能

3.1 时钟置换策略

时钟策略给每个页框关联一个”使用位”,实现了较小开销下接近LRU的性能
具体实现⭐:

  1. 当某页第一次被放入内存中,”使用位”置为1,且有一个指针与内存缓冲区关联.
  2. 外存中数据块要换入时,指针扫描缓冲区,查找使用位=0的页框
    • 当遇到使用位=1的页框,置为0
    • 当所有页框都为0,换出第一块
    • 当所有页框都为1,将每个页框使用位置0后,回到起点块换出
  3. 当某页框被置换出后,指针指向该位置的下一个页框 | image.png | 例子: 要换入页727,初始指针在页框2
    ① 页框2处使用位为1,置为0,指针后移
    ② 页框3处使用位为1,置为0,指针后移
    ③ 页框4处使用位为0,换出,将727置入,指针后移 | | —- | —- |

4. 驻留集管理

策略意义 决定给进程分配多少空间,允许其中多少页驻留在内存中
分配方式
- 固定分配策略:分配固定的页框
- 可变分配策略:根据缺页率,可动态调整页框分配
置换范围
- 局部置换:只换出分配该进程内存页框中的页
- 全局置换:可换出内存所有可用页框中的页
组合方式
- 固定+局部：缺页时,从该进程驻留页中选择一页换出
- 可变+局部：评估后,为进程分配不一定等大的页框,缺页时,从当前进程驻留页中换出,但系统不时重新评估,动态调整
- 可变+全局：最易于实现,所有进程页框数一样,但系统维护一个空闲页框列表,当缺页发生,空闲页框可加入进程驻留集,从而改变驻留集大小

5. 清除策略

策略意义 确定何时将已经修改的一页写回辅存
方式
- 请求式(demand		 
  1.     cleaning):当一页被置换时才写回<br />   - 问题:中断解除阻塞前要经过旧页写回和新页读入两次<br />- 预约式(precleaning):将修改的多页在置换前成批写回<br />   - 问题:可能浪费资源,毕竟大部分页在写回后又会修改<br /> |

6. 加载控制

策略意义 影响系统并发度:驻留在内存中的进程数量
影响
- 进程太少:进程运行处于阻塞态的概率较大
- 进程太多:平均到每个进程的驻留集空间不够,频繁缺页中断,发生系统抖动

本章动画: http://williamstallings.com/OS-Animation/Animations.html