操作系统概念——第8章 内存管理_操作系统概念复习内存管理

1. 背景

内存是现代计算机运行的中心，由很大一组字或字节组成，每个字或字节都有自己的地址。CPU通过PC的值从内存中提取指令。

1.1 基本硬件

问题：为什么CPU不能直接从磁盘中提取指令与数据？
① CPU能直接访问的存储器只有内存和处理器内的寄存器
② 执行指令以及指令的数据必须在这些可直接访问的存储器上
因此，机器语言可以用内存地址作为参数，而不能使用磁盘地址作为参数。

（1）保证访问物理内存的相对速度
高速缓存：协调速度差异的内存缓存区

（2）内存空间保护
目的： 确保操作系统不被用户进程访问，以及用户进程不被其他用户进程访问。

两种寄存器
① 基地址寄存器：含有最小合法物理内存地址
② 界限地址寄存器：含有地址访问范围

只有操作系统可以（通过特权指令）加载基地址寄存器和界限地址寄存器的值，而不允许用户程序修改它们。

实现方式：
采用基地址寄存器和界限地址寄存器的硬件地址保护，通过对用户模式下产生的每个地址与寄存器的值比较来完成的。

1.2 逻辑地址空间与物理地址空间

定义
① 逻辑地址：由CPU所生成的地址（范围为$0\to max$）
② 物理地址：加载到内存地址寄存器中的地址（范围为$R\to R+max$）
③ 逻辑地址空间：由程序生成的所有逻辑地址的集合
④ 物理地址空间：逻辑地址空间中所有逻辑地址相对应的物理地址

逻辑地址空间绑定到单独一套物理地址空间
用户只生成逻辑地址，且认为进程的地址空间为0到max。这些地址在使用前必须映射到物理地址。

问题：逻辑地址与物理地址相同吗？

不相同。
① 编译时和加载时的地址绑定方法产生的逻辑地址与物理地址相同
② 执行时的地址绑定产生的逻辑地址与物理地址不相同

1.3 地址绑定

（1）地址绑定的几种情况

① 编译时地址绑定
在编译时就知道进程将在内存中的驻留地址，可以直接生成 “绝对代码”

② 加载时地址绑定
在编译时不知道进程将在内存中的驻留地址，则编译器必须生成 “可重定位代码”

③ 运行时地址绑定
如果进程执行时可以从一个内存段转移到另一个内存段，则必须延迟到运行时进行地址绑定。

（2）使用重定位寄存器的动态重定位
硬件
内存管理单元MMU：在运行时完成从虚拟地址到物理地址的映射
重定位寄存器：
实现
物理地址 = 逻辑地址 + 基地址

1.4 动态链接与共享库

（1）动态链接
将链接推迟到运行时
存根：
是一小段代码，二进制镜像中对每个库程序的引用都有一个存根。
它首先检查所需子程序是否已在内存。如果不在，就将子程序装入内存。存根会用子程序地址替换自己，并开始执行子程序。下一在执行该子程序代码时，就可以直接执行。

（2）共享库
多个版本的库可以都装入内存，程序将通过版本信息确定使用那个库版本。

2. 连续内存分配

2.1 内存映射与保护

硬件支持
内存管理单元MMU：在运行时完成从虚拟地址到物理地址的映射
重定位寄存器：含有最小的物理地址值
界限地址寄存器：含有逻辑地址的范围值

保护实现
① CPU产生的每个逻辑地址都需要与寄存器进行核对。
② 每个逻辑地址必须小于界限地址寄存器，MMU动态将逻辑地址加上重定位寄存器的值后映射为物理地址。将映射后的物理地址发送给内存单元。

寄存器初始化
作为上下文切换的一部分，调度程序会初始化重定位寄存器和界限地址寄存器。

2.2 内存分配

（1）多分区方法
将内存分为固定大小的分区，每个分区只能容纳一个进程。
缺点
多道程序的程度会受分区数的限制。

（2）可变分区方法
在任意时刻有一组可用孔大小列表和输入队列，通常一组不同大小的孔分散在内存中。
① 当新进程需要内存时，操作系统为其查找足够大的孔。
② 如果孔太大，就将孔分成两块。一部分分给进程，另一部分还会给孔集合
③ 进程终止时释放内存，将内存还会给孔集合。若新孔与其他孔相邻，则合并成更大的孔。

问题：三种常见的动态分配方式的定义与比较

（3）动态存储分配的三种常用方式
① 首次适应：分配第一个足够大的孔
② 最佳适应：分配最小的足够大的孔
③ 最差适应：分配最大的孔
首次适应和最佳适应在空间方面优于最差适应。
首次适应相对于最佳适应更快。

2.3 碎片

（1）外部碎片问题
定义
当总的可用内存之和可以满足请求但不连续时，就会出现外部碎片问题。
产生原因
连续内存分配会使内存空间被分为分散的小片段
解决方法——紧缩(compaction)
移动内存内容，以便所有空闲空间合并为一整块。（分散 --> 合并）
① 仅在重定位是动态并在运行时可采用。
② 这种方案开销较大。
解决方法——分页、分段
允许进程的物理地址空间是非连续的

（2）内部碎片问题
定义
将内存以固定大小为单位分配，当分配的大小比进程需求大时，会出现内部碎片问题。

3. 分页

3.1 基本方法

（1）基本方法
将物理内存分为固定大小的块，称为帧。将逻辑内存也分为固定大小的块，称为页。

（2）硬件支持

逻辑地址
CPU产生的逻辑地址由页号（P）和页偏移（d）两部分组成
页的大小通常为2的幂。若页大小为$2^n$，逻辑地址空间为$2^m$，则低n位表示页偏移，高m-n位表示页号

物理地址
由每页所在的物理内存的基地址（f）和页偏移（d）组成
逻辑地址映射到物理地址
① 物理地址 = 基地址 * 页大小 + 页偏移
页号作为页表的索引，根据页号可以获得每个页在物理内存的基地址。再通过映射关系获得页在内存上的物理地址。

问题：分页的优缺点

（3）分页的优缺点
优点
① 分页不会产生外部碎片：分页将内存分为固定大小的块，所以在分配内存时不会产生分散的小片段。
② 可以共享公共代码：可以节省空间开销
缺点
① 分页会产生内部碎片：当进程所要求的内存不是页的整数倍时，最后一个帧可能用不完，而产生内部碎片。
② 分页增加了切换时间：操作系统为每个进程维护了一个页表的副本，在上下文切换的时候，CPU调度程序会根据副本定义硬件页表。

（4）采用分页技术的进程的内存管理
帧表
每个条目表示一个帧，表示该帧是空闲还是已占用
特点
用户视角的内存与实际物理内存分离：用户程序将内存作为一整块处理，它只包括这一个进程（逻辑内存）

实现
① 检查进程的大小，进程的每页都需要一帧。
② 检查物理内存大小，如果进程需要n页，而内存至少有n帧，那么就可以把内存分配给新进程
③ 进程的每页装入已分配的帧，帧号放在进程的页表中
④ 操作系统会为每个进程维护一个页表副本，上下文切换时，调度程序会根据副本修改硬件页表。

问题：为什么采用分页技术不会出现外部碎片问题？

理解：分页技术将内存分为固定大小的块。在内存分配时以页（帧）为单位分配内存，从而不会产生分散的小片段。

问题：分页时页的大小越小越好吗？

理解：不是越小越好。
① 页表中的每项也有一定的开销，但随着页的增大而降低。
② 磁盘I/O操作随着传输量的增大会更有效。

3.2 硬件支持

页表的保存
页表包含逻辑内存中每页所在物理内存的基地址。页表的指针和其他寄存器的值一起存入PCB中。当调度程序需要启动一个进程时，它必须首先装入用户寄存器，并根据保存的用户页表来定义正确的硬件页表值。

（1）将页表作为一组专用寄存器
优点： 响应速度快
缺点： 页表较小时，使用寄存器合理。当页表较大时，不可行。

（2）将页表保存在内存中
定义
将页表保存在内存中，并将页表基寄存器（PTBR）指向页表。
优点
① 可以保存非常大的页表
② 降低了切换时间：改变页表是需要改变PTBR就可以。
缺点
① 内存访问速度减半：采用这种访问，访问一个字节需要两次内存访问（一次是查找页表，一次是查找内存中的字节）

问题：采用将页表保存在内存方案的优缺点与内存访问过程

1. 优点
① 可以保存非常大的页表
② 降低了切换时间：改变页表是需要改变PTBR就可以。
2. 缺点
① 内存访问速度较慢：采用这种访问，访问一个字节需要两次内存访问（一次是查找页表，一次是查找内存中的字节），这样内存访问速度减半。
3. 内存访问过程
① 首先用PTBR的值加上页号i的偏移，来查找页表，获得页的对应帧号。
② 然后根据帧号加上页偏移获得真实的物理地址。
过程：（CPU（页号、PTBR） --> 页表（帧号、偏移） --> 物理地址）

（3）采用转换表缓冲区TLB
1. 定义
TLB是关联的快速内存，由两部分键和值组成。当关联内存根据给定值查找时，它会与所有键比较。如果找到条目，就得到对应值域。

问题：带TLB的分页硬件的内存访问过程

2. 访问过程
TLB与页表一起使用。TLB只包括页表的一部分。

① 当CPU产生逻辑地址后，将页号提交给TLB
② 如果在TLB中找到页号，就得到对应的帧号
③ 如果页码不在TLB中，就需要访问页表。
（CPU --> TLB (–>内存页表) --> 物理内存）

3. TLB失效
定义
如果逻辑地址中的页号不在TLB中，则需要访问页表。
过程
当访问页表得到帧号后，就可以访问内存了。同时将页号和帧号增加到TLB中。

4. 地址空间标示符ASID
定义
有的TLB的每个TLB条目还保存着ASID，用来唯一标识进程

作用
① 提供地址空间保护：
确保当前运行进程的ASID与虚拟页相关的ASID相匹配。否则，就当作TLB失效。
② 允许TLB同时包括多个不同进程的条目：
因为①所以能允许保存多个不同进程的条目。如果不支持ASID，每次上下文切换时，TLB都必须被冲刷或删除。

5. TLB命中率与有效内存访问时间
定义
TLB命中的百分比

问题：计算有效内存的访问时间

方法：
① 计算TLB命中下的有效内存访问时间（访问TLB + 访问内存）
② 计算TLB失效下的有效内存访问时间（访问TLB + 2 * 访问内存）
③ 按照TLB命中率加权求值
例题
假设查找TLB需要20ns，访问内存需要100ns：
① 当内存命中率为80%时的有效内存访问时间为：
$0.8\times 120+0.2\times 220=140ns$
（TLB命中时间=20+100，TLB失效时间=20+100+100）

3.3 保护

在分页环境下，内存保护是通过与每个帧相关联的保护位实现的
（1）可读写只读保护位
在计算物理地址的同时，检查保护位验证有没有对只读页进行写操作。对只读页进行写操作会产生硬件陷阱。

（2）有效-无效位
定义
保护位有效时，表示相关页在进程的逻辑地址空间内，是合法页。
保护位无效时，表示相关页不在进程的逻辑地址空间内，是非法也。
操作系统会捕获到无效地址引用。

问题：对非法地址的有效引用

程序的有效地址空间为0~10468，为什么对页5的访问（12287）是有效的？

理解： 采用分页的方式，会将逻辑内存按固定大小的页划分。因为有效地址10468在页5中，所以页5可以有效访问。而多余的部分则是产生的内部碎片。

3.4 共享页

分页的优点之一在于可以共享公共代码。
可重入代码
不能自我修改的代码，它不会在执行期间改变。
实现
① 在物理内存中保存一个可重入代码副本
② 每个进程有自己的寄存器副本和数据存储
③ 将每个用户的页表映射到可重入代码的同一物理副本，数据页映射到不同的帧

4. 页表结构

4.1 层次页表

问题：为什么要采用层次页表？

理解： 假设有32位的逻辑地址空间，如果系统的页大小为4KB($2^{12}$)，则有$2^{20}(1MB)$个条目.假设每个条目有4B(每个条目保存着32位地址，也即4B大小)，每个进程都需要$4MB$的物理地址空间来存储页表本身。我们不可能在内存中连续地分配这个页表
（关注： 页大小、条目大小）

方法（1）：两级分页法
定义：
将页表再分页。采用离散分配的方式，将页表进行分页，然后将各个页面分别存储在不同的物理块解决连续存储的问题。外层页表用来存储所划分的各个页面的首地址。

例如32位系统，一个逻辑地址被分为20位页码和12位页偏移，将页面再分为10位页码和10位页偏移。外部页表条目中保存着对应的内部页表的索引。内部页表的条目保存着对应页得物理基地址。

假如仍以之前一个4KB页大小得32位系统为例，此时：

① 外部页表条目个数为$2^{10}$个，每个页条目的大小为$4B$（存储着10位即1B左右），则在物理地址空间的存储大小为$2^{12}=4KB$。它存储着$2^{10}$个页表的首地址
② 内部第i页的页表条目个数为$2^{10}$个，每个页条目的大小为$2^{2}B$（存储着32位即4B），在物理地址空间的存储大小为$2^{12}=4KB$.内存中分散存储着$2^{10}$页的内部页表，所以在内存中共占$2^{22}=4MB$
③ 若不采用两级分页法，页表得条目个数为$2^{20}$，每个页条目得大小为$2^2$，则在内存中得连续存储大小为$2^{22}=4MB$的页表

参考：https://blog.csdn.net/weiqing_castle/article/details/89642022

VAX体系结构
VAX是32位机器，其页大小位512B($2^9$)。进程的逻辑地址空间被分为4个区，每个区为$2^{30}B$。

每个区表示一个进程的逻辑地址空间的不同部分（这样一个进程就不需要完全装入内存）。操作系统可以只在进程需要时才使用某些分区（对页表进行换页）。

4.2 哈希页表

定义
哈希表中得每一个条目保存一个链表的元素，每个元素包含三个域：
① 虚拟页码。② 所映射得帧号，③ 指向链表中的下一个元素指针

算法步骤
用虚拟页号与链表中每个元素的第一个域比较，如果匹配，就得到相应的帧值。如果不匹配，就对下一个节点进行比较。

4.3 反向页表

解决的问题
如果每个进程都有一个相关页表，该进程使用的每一页都早页表中有一项，那么这些表可能消耗大量的物理内存，却仅用于跟踪物理内存是如何使用的。

定义
反向页表对每个真正的内存页或帧才有一个条目。每个条目包含对应的虚拟地址和拥有该页的进程信息。

实现步骤
① 系统的每个虚拟地址有一个三元组<process-id, page-number, offset>组成
② 当需要内存引用时，由<process-id, page-number>组成的虚拟地址部分送交内存子系统，通过查找反向表寻找匹配。

问题：使用反向表的优缺点

优点
① 减少存储每个页表所需要的内存空间：整个系统只有一个反向页表，每个物理内存页只有一个相对应的条目
缺点
① 查找反向页表可能花费很长时间： 反向页表按物理地址排序，而不是按照虚拟地址排序。因此可能需要查找整个表来需求匹配。

5. 分段

5.1 基本方法

（1）逻辑地址
逻辑地址空间由段号s和段内的偏移d组成的有序对：<segment-number , offset>

5.2 硬件

（1）段表
① 组成： 段表的每个条目都有段基地址和段界限。
段基地址：段在内存中开始的物理地址
段界限：段的长度

② 实现： 一个逻辑地址由段号s和段偏移d组成。段号作为段表的索引，段偏移d需要小于段界限。如果偏移d合法，那么就与段基地址相加获得物理内存地址/

（2）硬件组成
段表是一组基地址和界限寄存器对

问题：试说明分页与分段的联系与区别

① CPU产生逻辑地址的划分
分页：逻辑地址可被划分为“页码”和“页偏移”
分段：逻辑地址被划分为“段号”和“段内偏移”

② 页表与段表的存储方式
页表：小页表可以存储在寄存器中，较大页表存储在内存中。 还可以使用TLB加快页表访问速度
段表：是一组基地址和界限寄存器对。

③ 内存映射方式
页表：通过页号找到对应页表条目获得基地址。将得到的基地址 * 页大小 + 页偏移就获得了物理内存地址。
段表：通过段号获得段基地址。将段基地址 + 段内偏移得到物理内存地址

④ 内存保护方式
CPU产生的每个逻辑地址都需要与寄存器进行核对。
页表：只需要保留一对重定位和界限地址寄存器。上下文切换时需要更新这对寄存器。

段表：段表由一组基地址和界限寄存器组成。

6. 交换

定义
进程可以暂时从内存交换到备份存储上，当需要再次执行时再调回到内存中。

注意点
① 一个交换出的进程需要交换回它原来所占有的内存空间。
② 交换需要备份存储。备份存储通常是快速磁盘
③ 交换时间主要部分是转移时间，转移时间与所交换的内存空间总量成正比
④ 假如要换出一个正在等待I/O操作的进程，如果将该进程换出，I/O操作可能使用现在属于另一进程的内存。因此要么不能换出有待处理I/O的进程，要么I/O操作的执行只能使用操作系统的缓冲区。

问题：理解上下文切换的过程

① 通过中断、系统调用，进入内核模式，然后切换进程的状态。
② 将旧进程的上下文保存在PCB中，装入经调度将要执行的新进程的上下文信息
(new)③ 调度程序需要检查就绪队列中的下一进程是否在内存中。如果不在内存中且没有空闲内存空间，调度程序将一个已在内存中的进程交换出去，并换入需要的进程。然后重新装载寄存器，将控制权交给所选择的进程。

问题：理解短期调度、中期调度、长期调度