操作系统 4：内存与虚拟内存

为什么需要内存管理

给定一个高级语言程序，考虑如下的过程：

编译：从 C 到汇编

汇编与链接：将多个子程序拼接，得到可执行的程序

上面的步骤将得到一个程序，但是这个程序并不能执行——它还不是进程。需要将程序装载到内存中才能执行。而要确定程序的入口位置，一个朴素的想法是，将程序的代码段放在某个确定的位置，数据段放在另一个确定的位置，然后将原来程序中所有的地址（例如，call 指令和分支、跳转指令的目标地址）修正到目标实际的位置。这种为执行程序而对其中出现的地址所做的修改，称为重定位。

重定位的时机不是唯一的：

可以在编译链接时确定——这样的代码称为绝对代码，因为它只能放在事先确定的位置上。
也可以在装载程序时确定——这样的代码称为可重定位代码。但是，一旦程序载入，它也不能移动。
如果程序内存储相对地址，而每次需要用到地址时，都将相对地址换算——称为运行时重定位，需要增加「地址翻译」过程。

于是，引入下面的概念：

虚拟地址：编程时，将代码或数据分成若干个段，每条指令或数据的地址由段名 + 段内偏移构成，这个整体称为虚拟地址。
```
_main + 0xfc
```
逻辑地址：虚拟地址中的偏移部分。
```
0xfc
```
物理地址：实际物理内存中看到的地址。比如，对于上面的例子，如果 _main 段在 0x00114514，那么虚拟地址 _main + 0xfc 的物理地址就是 0x00114610。

称地址的集合为地址空间，则有：

逻辑地址（虚拟地址）的集合称为逻辑地址空间。
CPU 内部地址总线可以访问的所有地址集合称为线性地址空间——CPU 能「看」到的地址空间，32 位系统为 4 GiB。
实际存在的可访问的物理内存地址集合称为物理地址空间。

内存分配与管理方案

连续内存分配

等长分区：操作系统初始化时，将内存等分为若干个分区，请求内存时以块为界。
变长分区：操作系统初始化时，将内存分成若干个有大有小的分区，请求内存时，取可用的最小块。
可变分区：根据请求内存的大小，要多少分多少。
- 需要的数据结构：空闲分区表（记录在什么地方有多长的空闲分区），以及已分配分区表（记录从哪里开始多长的空间被谁占用了）
- 首次适配（first-fit）：按顺序查空闲表，使用找到的第一个满足要求的空间分区。快！可能造成浪费！
- 最佳适配（best-fit）：找最小的满足要求的空闲分区。慢！会产生许多小的空闲分区，日后难以利用！
- 最差适配（worst-fit）：找最大的满足要求的空闲分区。慢！能产生一些大的空闲分区！

分段内存分配

程序是由若干「段」组成的，每个段有自己的特点和用途，如代码段、静态数据段、堆区、栈区。因此，可以以段为单位管理内存。

为不同的段分配一个段号，逻辑地址即可由段号和段内偏移拼接得到。建立进程段表，记录每个段的基址、长度和权限（RWX），通过查进程段表就能完成地址的转换。

分页内存分配

分段技术的问题：

空间是预留的（产生内部碎片）。
空闲空间很大但是不能分配（产生外部碎片）。

考虑使用固定大小的「页」管理内存，将内存分成页。下面是分页内存的翻译流程：

程序产生逻辑地址。分页内存管理之下，逻辑地址由页号与页内偏移组成。

使用页号查页表，得到页框号及权限信息。

将页框号和页内偏移拼接，得到物理地址。

段页结合内存管理

让段面向用户，页面向硬件。软件产生的逻辑地址是「段号 + 段内偏移」，先查段表得到逻辑（线性）地址「页号 + 页内偏移」，再查页表得到物理地址。

虚拟内存

基于局部性原理，将程序暂时用不到的内存页装入硬盘（外存），即段页管理，部分加载，按需调页，换入换出。

优点 1：地址空间 > 物理内存，有连续 4 GiB 空间可以使用，简化编程。
优点 2：内存中可以放入更多的进程，并发度好，效率高，内存利用率高。

页置换算法

每个程序分配得到的页框（即实际存在于物理内存中的可用位）是有限的。当没有空闲页框时，引入一个新的页就需要淘汰一个页到外存。

FIFO：先进先出置换，淘汰最早调入的页。缺页多。
OPT：最佳页面置换，淘汰未来最远将使用的页。最优方案，缺页数最小，不可实现。
LRU：最近最少使用算法，淘汰最近最长时间没有使用的页。

LRU 的准确实现方法有：

计数器法：设置一个全局时钟寄存器，每次页引用时加 1，并将当前的值写到被引用的那个页表项中。当需要置换页时，选择值最小的页。

页码栈法：建立一个容量为有效页框数的页码栈，每次引用一个页，就把它升至栈顶。当需要置换页时，选择栈底的页。

LRU 的近似实现方法有：

时钟算法或再给一次机会（SCR）算法：为每页框设置一个访问位。当某页调入内存时，给此位写 1。当要替换时，将内存中的所有页面视为一个循环队列，并有一个替换指针。
当要替换页时，检查当前指针指向的页的访问位，若为 0 则换出，指针后移；若为 1，则改为 0，指针检查下一页。

改进的时钟算法：考虑「一个页如果在内存中的时被修改过，那么淘汰它时要将修改写回磁盘。否则（如果磁盘原来就有这个页）就不用写回」设置一个访问位和一个修改位。这样，页面有 4 种：
- A = 0, M = 0：最近未被访问，也未被修改，是最佳选择。
- A = 0, M = 1：最近未被访问，但是被修改过，不是最佳的选择。
- A = 1：最近被访问过，之后可能还会被访问。
采用和时钟算法相似的执行过程，如下：
- 寻找 A = 0, M = 0 的页面。若找到则替换，否则
- 寻找 A = 0, M = 1 的页面。扫描过程中，所有扫描过的页面的 A 位都置为 0。若找到则替换，否则
- 将所有页的 A 位置 0，重做第 1 步。

计算机技术学习札记