逻辑内存和物理内存

计算机的物理内存（Physical Memory, RAM）是一个包含以字（Word）为存储单元的硬件。“字”是一个固定的数据大小单位，通常来说 1 字 = 4 字节（见下表）。物理地址（Physical Address）是一个字在容量为 $N$ 的内存空间中的具体位置。

数字 单位 = 数字 单位
1 字 = 4 字节
1 字节 = 8 比特（Bit）

逻辑地址空间（Logical Address Space）是物理内存的抽象，它包含了一段从 $0$ 到 $M-1$ 的抽象内存地址，其中 $M$ 为逻辑地址空间的大小。一个逻辑地址是对逻辑空间 $0$ 到 $M-1$ 之间所有字的标识。

逻辑地址与物理地址管理

如上图所示，在硬件层面，我们有物理内存，里面分配了 $0$ 到 $14$ 的空间（以字为单位）。还记得在之前的复习中提到的虚拟化吗？操作系统给每个程序虚拟了一个逻辑地址空间，它们都从 $0$ 开始。因此，逻辑地址空间在物理上是不连续存在的，这些程序的数据实际上可能存储在磁盘中（虚拟内存技术）。这么做有几个好处：

  1. 安全性与隔离：如果没有这一层逻辑空间，进程直接在物理内存中进行读写操作，会导致安全隐患，因为进程之间没有隔离措施。通过逻辑分区，进程之间互相不知道对方的存在，保证了进程的安全。
  2. 提高内存利用率：有了这一层逻辑空间，操作系统可以将那些长期没有使用的进程数据置换到磁盘中（Swapping），从而更高效地调度进程对内存的使用（如图中所示，进程 1 的物理存储空间不一定是连续的）。
  3. 用户透明性：通过虚拟化，用户（开发者）不需要自己设计和考虑物理内存的使用。进程会以为自己实际访问的就是连续的内存空间，并且这个内存空间对进程来说好像是“无限大”的。

程序的转换

源模块（Source Module）是用编程语言编写的程序，或者说是程序的组件，它必须通过编译器或解释器转换成可执行的机器码。

目标模块（Object Module）是源代码通过编译后得到的机器语言代码。一个目标模块可以单独运行，也可以和其他模块通过链接器（Linker）链接起来，放入一个加载模块中。

加载模块（Load Module）是一个或多个目标模块组成的程序，它可以被加载到内存中并执行。

程序重定位过程

重定位和地址绑定

由于程序的物理地址在其被送入加载模块之前都无法确定，编译器和链接器假定逻辑地址空间从 $0$ 开始。在程序转换的每个步骤中，指令中出现的逻辑地址和数据都可能会被改变。只有在最后一个步骤——程序加载时，才能被绑定到它的物理地址上。

程序重定位（Relocation）是将程序某个部分从一个地址移到另一个地址的过程。重定位可以是逻辑地址之间的转换，也可以是逻辑地址向物理地址的映射。

静态重定位（Static Relocation）是指在进程被执行之前（加载时），将所有的逻辑地址绑定到物理地址。

动态重定位（Dynamic Relocation）则将逻辑地址到物理地址的绑定延迟到该部分代码需要被执行时才进行。

例如有这样一段代码：

1
mov R1, 200  // 这里的 200 是逻辑地址

在静态重定位下，当程序被加载到内存（假设起始物理地址为 1000）之后，该地址将会被翻译成被分配到的物理地址：

1
mov R1, 1200 // 物理地址 = 1000 + 200

而动态重定位则不改变这部分代码，而是在 CPU 执行到该指令时再进行翻译。

动态重定位的实现

CPU 中可以使用寄存器来实现动态重定位。大多数程序都由三个部分组成：代码段、静态数据段和动态数据段。一个简单的内存管理方法是将这三部分当作一个整体来看，也就是说将它们放在相邻的内存空间中。动态重定位可以通过使用一个重定位寄存器（Relocation Register, RR）来实现，它的值是程序第一行代码的物理内存起始地址。在后面执行其他部分代码需要寻址的时候，该寄存器的值会被自动累加。

重定位寄存器原理

看上面这个例子，内存中有一个进程。在某一时刻，它被加载到物理内存 $500$ 的位置，所以我们的重定位寄存器（Relocation Register）的值是 $500$。当我们执行 load R1, 100 这个操作时（将逻辑地址 $100$ 的值传给 R1），它实际获取的内容是在物理内存空间 (RR + 100) = 600 的位置的内容。过了一会儿，内存通过调整，将该进程移动到了物理地址 $100$ 的位置，重定位寄存器变为 $100$，此时进行 load R2, 20 的时候则是加载物理地址为 (100 + 20) = 120 的数据。

另一个更灵活的方法是将这三个部分分开，每个部分放在不同的内存地址，然后使用三个重定位寄存器来分别记录这三个部分（代码段、数据段、堆栈段）的位置。

空闲空间管理

随着进程的运行和由于内存空间有限而进行的换入换出，进程在内存中会被不停地移动。如果无法将整个内存空间充分利用将十分可惜。另外某些进程在执行到一定程度需要更多的空间，这个时候系统要将其挪到更大的空槽内，我们称这些空槽为空闲分区（Hole）。所以操作系统必须监测内存空间的使用情况。通常来说，当一个程序需要加载到内存的时候，操作系统会用一个链表来找到最合适的空闲分区给程序。我们称那个保持跟进空闲分区的链表为空闲链表。

内存分配示意图

上图展示了一个程序 P 通过空闲链表寻找可用空间的过程。
有多个为程序寻找内存空间的方法：

首次适应算法

首次适应算法（First Fit）永远从链表的第一个元素开始搜索，直到找到第一个能满足进程大小要求的空闲分区为止。

首次适应算法演示

循环首次适应算法

相比首次适应算法每次都从开头搜索，循环首次适应算法（Next Fit）从上次分配空间的位置开始接着搜索。

循环首次适应算法演示

最佳适应算法 (Best Fit)

该算法遍历整个链表，找到可以被程序使用的最小空闲分区（即最接近程序大小的空闲块）。

最坏适应算法 (Worst Fit)

该算法和最佳适应算法相反，总是找最大的空闲分区给程序使用。

注意：每次进程加载到内存或退出后，空闲链表会自动调节

管理内存不足

内存碎片和 50% 法则

外部内存碎片（External Memory Fragmentation）是指由于空闲分区很小，但是数量大，导致的总体可用内存空间充足但无法满足一个大进程的需求。如下图所示，由于每个空闲块都十分小，程序 P 无法加载到内存中；但实际上如果内存规划合理，P 是可以加载到内存中的。

外部内存碎片

50% 法则（Fifty-Percent Rule）是一个经验法则，它指出在使用动态分区分配（如 First Fit）且系统达到稳定状态时，假设寻找一个刚好合适的空间位置给加载的程序的概率无限趋近于 $0$，那么自由分区的数量大约是被利用内存空间块数量的一半。

$$ \text{空闲分区的数量} \approx 0.5 \times \text{已分配内存块的数量} $$

也就是说，物理内存中每出现一个空闲分区，大约就有两个被利用的内存空间块。三分之一的内存空间可能会是空闲分区。

交换和内存压缩

当没有一个单一的空闲分区的大小能被加载进来的程序使用时，有两个解决方案：

  1. 交换（Swapping）：暂时地将某个进程（通常是挂起的）挪出内存空间到外存（磁盘）。一段时间后再将其挪回来继续执行。
  2. 内存压缩（Memory Compaction, 又称碎片整理）：利用一套系统性的方式来挪动内存中的已分配块，使它们相邻。通常来说，这个挪动一般都是往一个方向的，这样就能将许多小的碎片拼成一个大的空闲区域，给剩下的空闲分区留出更大的空间。

共享模块

在上面的加载模块中，我们说到，很多程序会被通过链接器来合成一个大的程序块。比如说 C 语言的标准库里面提供了一个标准输出库，一个简单的 hello world 程序就需要跟它一起被链接器连接起来使用。为了能够充分地利用内存空间，内存管理中引入了一种共享机制。当多个程序都需要用到某个通用模块（如动态链接库 .dll 或 .so）的时候，系统会允许它们在物理内存中调用同一个模块的副本。

分页

页（Page）是一个固定的、逻辑地址空间中相邻的块。

页框（Page Frame）是一个固定的、物理地址空间中相邻的块，它通常用一个数字（页框号）表示。页框是内存管理中物理数据分配的最小单位。

页表（Page Table）是一个用于记录逻辑地址中的页（Page）以及它们所映射的物理内存中的页框（Page Frame）的数组（或更复杂的数据结构）。

页与页框

逻辑地址和物理地址

地址空间的大小通常是以 $2^n$ 的形式存在的，其中 $n$ 是能够完整利用地址的比特数。当地址空间被分割成一个个页的时候，页的大小通常也是 $2^k$，其中 $k$ 是可以代表页内每个字的比特数（页内偏移）。剩下的 $n-k$ 个比特确定了页的数量：$2^{n-k}$。

通过将内存地址分割成两部分，通常来说高 $n-k$ 个比特是页号（p），剩下的低 $k$ 个比特是用来表示该页的页内位移（w, offset）。

假设我们的地址是 $6$ 位的，我们将会需要 $6$ 位二进制的数来表示内存地址（$2^6=64$ 个单元）。假设页的大小为 $8$，我们将会需要 $3$ 位比特来记录位移（$2^3=8$）。剩下的 $3$ 位比特将会用于记录页号（共有 $2^3=8$ 个页）。

分页地址结构

注意：上图所写的 P1, P2, P3 并非进程 process，而是页 page。取决于分页的方式，逻辑内存的页号可能会映射到物理内存中不同的位置（不连续），但是每页的页内位移总是保持不变的。

页映射示意图

上图中，逻辑页号 111 被映射到物理页框 0111 中，但是位移总是保持在 000 - 111 之间。

地址映射

操作系统需要将逻辑内存地址 $(p, w)$ 匹配到物理内存地址 $(f, w)$ 上。其中 $p$ 代表逻辑页号，$f$ 代表物理页框号，$w$ 代表页内位移。从逻辑内存映射到物理内存需要经过以下步骤：

  1. 获取一个逻辑地址 $(p, w)$。
  2. 在线性页表中找到索引为 $p$ 的条目（PTE）。
  3. 读取该条目对应的物理页框号 $f$。
  4. 结合 $f$ 以及页内位移 $w$ 来拼接成对应的物理地址 $(f, w)$。

内部碎片化和边界监测

分页式存储规定了页和页框的大小一致，这样所有的页都可以找到对应的页框，而不至于产生页外的空闲分区。这样一来就可以完全避免外部碎片的产生了。但通常来说存储空间只允许一种或少数几种固定大小的页存在，当进程的最后一部分数据不能填满整个页的时候，就会产生内部碎片（Internal Fragmentation）。

出于安全考虑，当程序被加载到内存中时，或者需要进行地址转换的时候，要保证一个程序的地址访问不会超出它的边界。

内部碎片与边界监测

上图展示了一个程序占用了 3 个页，其中第三个页只有前半部分被使用了（产生了内部碎片）。操作系统必须保证这个程序能够访问的空间只能是 page 1、page 2 以及 page 3 边界（虚线）的前半部分。

分段和分页

在纯分页式存储中，所有程序的代码、数据、栈以及其他数据结构都被放在了逻辑上相连的一组页中。但是程序的每个部分（段）的大小是不一样的，各个部分的自然边界和页的固定边界不完全一致。比如上面这个程序的自然边界在 011, 001，而页边界则是在 011, 111。因为两者的边界不一致，逻辑空间中程序间的共享和保护（例如，只允许读取代码段，不允许修改）将得不到完美的保证。

分段（Segmentation）便是用于解决这种问题的一个方法，它会根据程序的逻辑结构（如代码段、数据段、堆栈段）给每个进程提供可变的逻辑空间。相对应，分段也需要一个分段表（Segment Table）来实现逻辑内存（段号 + 段内偏移）和物理内存之间的映射。

分段存储示意图

地址转换

跟分页一样，分段式存储将每个逻辑地址分成两部分：段号（s）和段内位移（w）。操作系统将一个虚拟地址转化为物理地址需要以下步骤：

  1. 输入一个逻辑地址 $(s, w)$。
  2. 在分段表中找到索引为 $s$ 的条目，读取对应的物理段起始地址（Base, sa）及其大小（Limit, sze）。
  3. 边界检查：如果位移 $w \geq sze$，则认为地址越界，拒绝该地址请求并产生越界中断。
  4. 否则，将物理起始地址与段内位移相加，访问对应的物理地址 (sa + w)。

段页式管理 (Segmentation with Paging)

分段式存储的好处是可以创建多个符合程序逻辑的、可变的地址空间，便于共享和保护；而分页的优势是在物理内存中可以将任意页放到任意页框中，消除了外部碎片，提高了内存利用率。为了能够互取所长，我们可以将两种方式合并起来使用，即段页式存储管理。

在这种模式下，逻辑地址空间包含多个可变的段，但是每个段内部又被分割成大小一样的页。和单独使用分页或分段不同，这次我们要将逻辑地址分成三个部分：段号（s）、页号（p）和页内位移（w）。一个物理地址还是通过组合页框号（f）和页内位移（w）来构成。

每个进程都有一个分段表，分段表的每一行不再是指向物理内存，而是指向一个对应的分页表。操作系统要转换一个地址将要做以下操作：

  1. 输入一个逻辑地址 $(s, p, w)$，用段号 $s$ 查找分段表，找到对应的分页表起始地址和该段的长度。
  2. 边界检查：检查 $(p, w)$ 组合后的段内偏移是否超过了该段的长度，如果超过，则拒绝访问。
  3. 如果合规，利用分页表起始地址找到对应的分页表，利用页号 $p$ 查找物理内存的页框号 $f$。
  4. 将页框号 $f$ 与段内页内位移 $w$ 结合，形成最终的物理地址 $(f, w)$。

这种结合两种方式进行的存储管理方式被称为段页式存储管理。

地址转换的备用缓存 (TLB)

无论是分页还是分段，亦或是段页式管理，它们都要经常用到驻留在内存中的分段表和页表，这意味着每次访存数据实际上至少需要两次物理内存访问（一次查表，一次取数据）。这个转换的过程必须要极高速地运行才能保证程序的流畅。于是转译后备缓冲区（Translation Lookaside Buffer, TLB），又称快表，被发明出来了。这是一个硬件的高速关联存储模块（通常在 CPU 内部），它被用于记录最近的地址转译结果。

当一个逻辑地址 $(s, p, w)$ 需要被转译成物理地址 $(f, w)$ 时，CPU 首先并行查找 TLB。如果找到匹配的 $(s, p)$，则直接获得页框号 $f$（称为 TLB 命中），这几乎不消耗额外时间。如果 TLB 未命中，则通过慢速的内存页表进行查找，并将查到的结果对应保存到 TLB 中，以便下次使用。当另一个地址需要被访问，且它有着和前一个地址相同的段和页号（由于程序的局部性原理，这经常发生）时，TLB 会迅速找到已保存的页框，并且加上新的位移 $w’$ 形成 $(f, w’)$ 来访问该地址。