4．内存管理
内存管理的基本概念
链接与装入
（详见教材）
逻辑地址与物理地址空间
（详见教材）
对换与覆盖
（详见教材）
重定位
（详见教材）
内存分配方法
连续内存分配方法
- 单一连续分配
- 简单，无外部碎片
- 只能用于单用户、单任务的操作系统，有内部碎片
- 固定分区分配
- 无外部碎片
- 有内部碎片，存储空间利用率低
- 动态分区分配
- 无内部碎片，有外部碎片
- 动态分区的分配策略（★★★★★）
- 首次适应（★★★★）：按地址从小到大依次寻找空闲分区，将第一个能满足要求的空闲分区分配给程序
- 最佳适应：按容量从小到大依次寻找空闲分区，将第一个能满足要求的空闲分区分配给程序
- 最坏适应（最大适应）：按容量从大到小依次寻找空闲分区，将第一个能满足要求的空闲分区分配给程序
- 邻近适应（循环首次适应）：与首次适应类似，但是查找开始位置为上一次查找结束的位置
- 动态分区的分配策略的比较
- 首次适应，简单，最好、最快
离散（非连续）内存分配方法（★★★★★）
分页
逻辑地址到物理地址的转换
不含快表（两次访存）
- 设页面大小为 L ，逻辑地址 A 到物理地址 E
的转换
- 分析出页号和页面偏移量（根据题设地址结构或者计算得出）：计算页号 P （ P = A / L ）和页面偏移量 W （W = A % L ）
- 判断页号合法性：比较页号 P 和页表长度 M ，若 P ≥ M ，则产生越界中断，否则继续执行。
- 查页表，得块号：页表中页号 P 对应的页表项地址（目的是在内存中找到相应的页表项） = 页表始址 F + 页号 P × 页表项长度，取出该页表项内容 b ，即为物理块号。（注意区分页表长度和页表项长度。页表长度的值指一共有多少页，页表项长度是指页地址占多大的存储空间）
- 拼接块号和页内偏移量：计算 E = b × L + W ，用得到的物理地址E 去访问内存
含快表
- 含快表的地址变换流程
- CPU 给出逻辑地址后，由硬件进行地址转换，将页号送入高速缓存寄存器，并将此页号与快表中的所有页号进行比较
- 若能找到匹配的页号，说明所要访问的页表项在快表中，则直接从中取出该页对应的块号，和页内偏移量拼接形成物理地址。（仅一次访存就可以存取数据）
- 若未找到，类似不含快表对逻辑地址进行转换，并把（页号，块号）对存入快表。若快表已满，则需依据相应的替换算法对快表中的元素进行替换
多级页表
试和索引表比较一下
多级和一级的对比
- 一级页表，其存储页号到块号的存储极限取决于其本身的长度
- 多级页表，其存储页号到块号的存储极限取决于各级页表长度之积
- 总结：乘法比加法更能压缩空间
以二级为例，分析其中的数据关系（注意举一反三）（★★★★★）
- 32 位 逻辑地址空间、页面大小 4 KB、页表项 4
B，以字节为编址单位，试确定满足二级页表的逻辑地址空间格式（即求哪几位代表一级页号、二级页号、页内偏移）
- 页内偏移位数 = \(log_2页面大小\) （本例即 \(log_24K = 12\)）
- 由于顶级页表最多一个页面，故顶级（一级）页表总共能容纳 \(页面大小/页表项大小\) 个页表项（本例为 4KB/4B = 1K），所需位数为 \(log_2(页表项个数)\) （本例为 \(log_2(1K) = 10\)）
- 剩下的 10 位，即为二级页号。
- 所以逻辑地址空间格式如下
- 32 位 逻辑地址空间、页面大小 4 KB、页表项 4
B，以字节为编址单位，试确定满足二级页表的逻辑地址空间格式（即求哪几位代表一级页号、二级页号、页内偏移）
| 一级页号（10位） | 二级页号（10位） | 页内偏移量（12位） |
|---|---|---|
分段（两次访存）
- 逻辑地址 A 到物理地址 E 的转换
- 提取段号和页内偏移量：逻辑地址 A 的结构：前几位是段号 S ，后几位是段内偏移 W
- 判断段号合法性：比较段号 S 和段表长度 M ，若 S ≥ M ，则产生越界中断，否则继续执行
- 查段表，找到段基址、段长，并判段内偏移的合法性：段表中段号 S 对应的段表项地址 = 段表首址 F + 段号 S × 段表项长度，取出该段表项的前几位得到段长 C 。若段内偏移量 ≥ C，则产生越界中断，否则继续执行。
- 取出段基地址，和段内偏移求和：取出段表项中该段的基址 b ，计算 E = b + W
段页（三次访存）
- 逻辑地址 A 到物理地址 E 的转换
- 依据段号查段表，找到页表始址
- 依据页表始址和页号查页表，得到块号
- 将块号和页面偏移量拼接成物理地址
虚拟内存分配方法
虚拟内存的概念
（详见教材）
局部性原理
（详见教材）
实现虚拟内存所需的硬件和软件支持
（详见教材）
请求分页（段）管理
地址变换过程
页面置换算法（★★★★★）
最佳（OPT）置换算法
- 置换标准：淘汰最长时间内不再被访问的页面
- 无法实现
先进先出（FIFO）置换算法
- 置换标准：淘汰最早进入内存的页面（用队列实现）
- 缺页率较高，会产生所分配的物理块数增大而页故障数反减的异常现象
最近最久未使用（LRU）置换算法
- 置换标准：淘汰最近最久未使用的页面
- 性能较好，但需要寄存器和栈的硬件支持。
- 手算思路
- 假想一个链表，其最大长度为内存中能存下最多页面的个数。
- 若页面不在该链表中，且链表长度未超过最大长度，则将这个页面插入到链表头部
- 若页面不在该链表中，且链表长度超过最大长度，则将链表末尾元素删除，并将新个页面插入到链表头部
- 若页面在该链表中，则将新页面移动到链表头部，其他元素位置不变
时钟（CLOCK）置换算法（NRU，最近未用）
- 置换标准：淘汰访问位为 0 的页面
- （具体算法流程详见教材）
- 改进的 CLOCK 算法：多增一位修改位。
- 假设 A 为访问位， M 为修改位，（A, M）所有可能取值，淘汰顺序为
- (0, 0) (0, 1) (1, 0) (1, 1) （优先换出未使用的；若全部都已使用，再考虑优先换出未被修改的）
- （具体算法流程详见教材）
内存保护与共享
（详见教材）
抖动的概念和处理方法
（详见教材）
解题技巧及重要结论
- 物理地址 VS 逻辑地址
- 物理地址（实地址），若其位数为 32 位，意味着实际物理内存为 \(2^{32}B\)
- 逻辑地址（虚地址），若其位数为 48 位，意味着对用户来说内存大小为 \(2^{48}B\) （采用了虚拟内存技术）
- 含多级页表的逻辑地址的划分中的公式总结（对照教材中多级页表理解）
- \(页内偏移位数 =log_2页面大小\)
- \(页号部分总位数 = 逻辑地址总位数 - 页内偏移位数\)
- \(一级页号位数=\frac{页面大小}{页表项大小}\)
- \(页表级数 = \frac{页号部分总位数}{一级页号位数}\)
参考资料
- 计算机操作系统.汤小丹等
- 2020年操作系统考研复习指导.王道论坛