操作系统漫游（四）存储器管理
计算机系统存储层次大致可以分为：
寄存器 -> 高速缓存 -> 主存储器 -> 磁盘缓存 -> 固定磁盘 -> 可移动存储介质
由于存储器还是一种稀缺资源，操作系统对存储器的管理主要是对主存储器（主存、或者通俗地称内存）的管理。
程序的装入和链接
用户程序在执行前，必须先装入内存，然后才变成一个进程。
这个过程分为以下几步:
- 编译：由编译器（Compiler）对源码进行编译，形成目标模块（Object Module）
- 链接：由链接器（Linker）将 Object Modules 与所需的库函数链接在一起，形成装入模块（Load Module）。包括静态链接和装入时动态链接。
- 装入：由装入器（Loader）将模块装入内存
程序的装入
三种装入方式：
- 绝对装入方式：只适用于单道程序环境，使用的是绝对地址（地址值可由编译器生成或程序员指定）
- 可重定位装入方式：重定位在装入时一次性完成，故也称静态重定位。其程序地址空间也就是逻辑地址空间。
- 动态运行时的装入方式：其物理地址是在程序运行时才确定的。
程序的链接
三种链接方式：
- 静态链接方式
- 装入时动态链接
- 运行时动态链接
动态分区分配算法
根据实际需要，动态地为程序分配内存空间。包括以下算法：
- 首次适应（First Fit）：在分配内存时，从链首开始顺序查找，直到找到一个大小能满足要求的空闲分区。这种算法优先利用低址部分的空闲分区，保留高址部分的大空闲区。
- 最佳适应（Best Fit）：先将所有的空闲分区按容量从小到大排序，然后再找到满足要求的空闲区。这样就能做到把既满足空间大小要求、又是最小的空闲分区分配给作业。
交换技术（Swapping）
存储管理中采用覆盖与交换（swap）技术是为了减少程序占用主存空间。将内存中暂时不会被调用的进程交换到外存上。这有效提高了内存利用率，减少程序所占的主存空间。
Swapping是在逻辑上扩充主存，并不能从物理上扩充主存容量。
Swap中的虚拟内存的容量由内存和外存容量之和决定，取决于逻辑地址位数。
离散分配
如果允许将一个进程 分散地 装入到许多不相邻的分区中，就可以充分地利用内存空间。
分页存储管理方式
分页存储把进程的逻辑地址空间分为若干个页，称为页面，比如第0页、第1页、第2页，每一个都有固定的大小，称为页面大小（通常是2的幂）。
其地址结构如下：
如上图，是一个 32 位的地址结构。其中，第 0 - 11 位叫做 位（偏）移量（也就是页内地址），第 12 - 31 位 是页号，也就是第几页的二进制表示。
于是，给定一个逻辑地址空间A，页面大小为L
- 页号 P 为：P = [INT] A / L
- 页内地址 d 为： [A] MOD L
分段存储管理方式
为了满足用户（程序员）在编程和使用上多方面的要求，引入分段存储管理方式。
这种方式把作业的地址空间划分为若干个段、每个段定义了一组逻辑信息。例如主程序段MAIN、自程序段X、数据段D、栈段S等。
系统为每一个段分配一个连续的分区，一个程序中的各个段，可以载入到内存中不同的分区中。通过段表来实现逻辑段到物理内存的映射。
有以下公式：
偏移量 = 逻辑地址 % 页面大小
物理地址 = 块号 × 页面大小 + 偏移量
段页式存储管理方式
将分页和分段结合起来，既能减少存储碎片，又能方便实现数据和程序的共享。
虚拟存储器
GTA 5这款游戏，解压完以后有大约 65 GB，运行这个游戏，很少有人拥有 65 GB 以上的内存。这时候就要用到虚拟存储器。虚拟存储器是一种从逻辑上实现对内存容量扩充的技术。
传统的存储器管理方式，有两个特征：一次性 和 驻留性。也就是作业必须一次性装入内存，然后才开始运行，装入内存后，执行过的片段依然会驻留在内存里，浪费内存空间。
我们可以利用程序运行的 局部性原理，也就是说，程序运行过程中，在一较短时间内通常只访问某个部分的内存。于是，我们没有必要将应用程序一次性全部装入内存，而仅须将当前要运行的少数页面或段先装入内存，其余部分暂留在硬盘上。然后通过一些算法在内存和外存中置换。
虚拟存储器定义
所谓虚拟存储器，指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其三个特征为：多次行、对换性、虚拟性。
换进和换出能有效地提高内存利用率。
虚拟存储器实现
在分页系统的基础上，增加调页功能和页面置换功能。允许用户程序只装入少数页面的程序（及数据）即可启动运行，然后通过调页功能和页面置换功能陆续地把即将运行的页面调入内存。
硬件支持
首先 请求页表 将用户空间的逻辑地址映射为内存空间中的物理地址。请求页表如下：
- 状态位P：指示该页是否已调入内存
- 访问字段A：记录本页在一段时间内被访问的次数（供给置换算法换进换出时参考）
- 修改位M：标识该页换进内存后是否被修改过（供置换页面时参考）
- 外存地址：指出该页在外存上的地址
此外，还要有一个缺页中断机构，不同于普通中断，表现在：
- 普通中断在一条指令执行结束后，才检查是否有中断请求。缺页中断是在指令执行期间，若发现缺页，便立即产生和处理缺页中断信号，及时把所需的页调入内存。
- 系统中的硬件机构应能保存多次中断时的状态。
置换算法
基本：
- 最佳（Optimal）页面置换算法：把以后不使用的，或者是在最长（未来）时间内不再被访问的页面，置换出去。该算法是无法实现的，因为无法预知未来哪个页面不再被访问。但可以作为其他算法性能的参考。
- 先进先出（FIFO）页面置换算法：顾名思义，最先进入的最先被置换出去。
- 最近最久未使用（LRU，Least Recently Used）置换算法：选择最近最久未使用的页面予以淘汰。
改进：
- Clock置换算法：添加一个访问位，当某页被访问时，将访问位置1。然后将所有页面通过指针链接成循环队列。在选择置换的时候，判断访问位，如果是0，将该页换出，如果是1，将其置0，给予该页第二次驻留内存的机会。指针往后移动。
- 改进型Clock置换算法：在上面的基础上，增加一个修改位。优先淘汰访问位为0且未被修改的页面。