Main Memory¶

约 5011 个字预计阅读时间 25 分钟

Memory Management¶

我们不可能将所有进程以及所需的数据都放入 Main Memory 中，因此操作系统必须对内存空间进行合理的划分和有效的动态分配。概括来讲，内存管理的主要功能有：

<1> 内存空间的分配与回收 由操作系统负责内存空间的分配与管理，记录内存的空闲空间、内存的分配情况，并回收已结束进程所占用的内存空间
<2> 地址转换 程序的逻辑地址与内存中的物理地址需要转换
<3> 内存空间扩充 利用虚拟存储技术从逻辑上扩充内存
<4> 内存共享 允许多个进程访问内存的同一部分，并且对内存共享区域进行受控访问
<5> 存储保护 保证各个进程在各自的存储区域运行，互不干扰

Logical & Physical Address¶

Segmentation 和 Paging 是最主流的两种 Memory Management Schemes，这里简要对二者进行一些对比：

对比项目	分段（Segmentation）	分页（Paging）
大小（Size）	段的大小可变，由用户或编译器决定（例如：代码段、数据段、堆栈段）。	页的大小固定（例如 4KB、8KB），由硬件决定。
碎片（Fragmentation）	容易产生外部碎片（因为不同段大小不一，内存分配不连续）。	容易产生内部碎片（因为最后一页可能没被完全用完）。
表结构（Tables）	使用段表（Segment Table），记录每个段的基址和长度，查找速度较快。	使用页表（Page Table），记录页号对应的物理块号。查找相对较慢，但TLB（Translation Lookaside Buffer）可加速。

Legacy-Mode Memory ManagementLong-Mode Memory Management

接下来，我们会使用如下几个 terms 来指代各种不同地址：

Effective Addresses or Segment Offsets
- 段内偏移地址
Logical Addresses
- 逻辑地址，表示形式类似 Seg:Offset
Linear Addresses
- 线性地址，相当于逻辑地址的转译，是连续的地址
- 如果启用了 Paging，Linear Addresses 相当于虚拟地址 Virtual Addresses
Physical Addresses
- 物理地址，在 Memory 中的真实内存布局

此内容来自于我的「汇编与接口」笔记，因此只学操作系统的话可能不知道这几个 Operating Mode 是什么意思

Link & Load¶

一个用户源程序要变为在内存中执行的程序，通常需要以下几个步骤：

当我们写好一个程序时，程序中变量、函数、指令等都只是个“符号名”，没有真实的物理地址。

为了让这些符号名绑定到真正的内存地址上，我们有如下三种地址绑定的时机：

编译时绝对装入 发生在程序 Compile 时，程序被加载到的地址编译时已确定，因此可以直接产生绝对地址代码
- 只适用于单道程序环境，并且要求程序逻辑地址和物理地址完全相同
- 一旦程序起始地址改变，所有指令引用地址都改变，则需要重新编译
装入时静态重定位 发生在程序 Load 时，程序中指令和数据的地址都是相对于起始地址偏移的逻辑地址
- 在装入过程中将目标程序中的相对地址修改为实际的绝对地址
- 一旦加载完成，程序的内存位置即固定，不能再移动
执行时动态重定位 发生在程序 Execute 时，将相对地址的计算推迟到执行时，因此需要一个 relocation register 存储起始地址作为支持（参考 base & limit register）
- 装入内存后的所有地址均为相对地址
- 若程序要在内存中发生移动，则要采用动态的装入方法
- 可以将程序分配到不连续的存储区，在程序运行时只需装入部分代码即可运行，程序运行期间可以动态申请分配内存

逻辑地址和物理地址在 Compile-time 和 Load-time 是等价的，在 Execution-time 不等价

在执行链接时，根据链接的时机不同，我们也可分出以下三种链接方式：

静态链接 运行之前就将程序及所需的库函数链接成一个完整的模块
- 将几个目标模块装配成一个装入模块时，需要将每个模块的外部调用符号转换为相对地址
- 由于编译后的单个目标模块的相对地址都是从自身 0 开始，静态链接后需要修改这些相对地址
装入时动态链接 在装入内存时，边装入边链接
- 优点是便于修改和更新，便于实现对目标模块的共享
运行时动态链接 当程序执行时需要某动态模块时，才对它进行链接
- 优点是加快模块装入过程，节省内存空间
- 可执行文件体积更小，且当库更新时不需要重新链接可执行库

内存中同时运行多个用户进程，为了防止用户进程修改别的进程内存和操作系统内存，我们引入 Relocate Register 和 Limit Register 两个关键寄存器。

寄存器	含义	作用
Relocation Register（重定位寄存器）	存放当前进程在内存中的起始物理地址（最小物理地址）	所有逻辑地址都要加上这个值，才能得到实际物理地址。
Limit Register（界限寄存器）	存放当前进程逻辑地址空间的大小	每个逻辑地址必须小于这个值，否则触发“越界错误”。

加载重定位寄存器和界地址寄存器必须使用特权指令，即只有操作系统内核可以加载

Contiguous Allocation¶

存储管理方式随着操作系统的发展而发展。在操作系统由单道向多道发展时，存储管理方式的变化为单一连续分配 => 固定分区分配 => 动态分区分配。为了更好提高内存的利用率，最后又从连续分配方式发展到离散分配方式——页式存储管理。

Contiguous Allocation 指为一个用户程序分配一个连续的内存空间。内存被划分为系统区和用户区，系统区位于低地址，而用户区位于高地址。

其中单一连续分配指用户区内存中有且仅有一个用户程序，此方式实现简单、无外部碎片、不需要进行内存保护，但是有内部碎片，且内存利用率极低。

固定分区分配，亦即 Multiple-partition Allocation 是最简单的多道程序存储管理方式，它将用户区划分为若干固定大小的分区（hole），每个分区只装入一个作业，分区的大小可以不等，通过分区使用表进行维护。固定分区分配方式也不存在外部碎片，但是当程序小于固定分区大小时，也会产生内部碎片。

动态分区分配也叫做可变分区分配，它的分区的大小和数量是可变的，通过一定算法使得分配的分区大小正好适合进程的需要。

随着时间的推移，动态分区分配方式难免会产生外部碎片，它存在于所有分区的外部，于内部碎片概念相对。例如如下例子：

外部碎片问题可以通过周期性的紧凑技术来克服，即对内存碎片进行整理

动态分区分配方式使用空闲分区链来维护分区。当进程要进入主存时，需要按照一定的分配算法从空闲分区链中选出一个分区。按照分区检索方式，可分为顺序分配方法和索引分配方法：

顺序分配方法 包括 First-Fit，Next-Fit，Best-Fit，Worst-Fit 等
- 通常，First-Fit > Next-Fit ≈ Best-Fit > Worst-Fit
索引分配方法 包括快速适应算法，伙伴系统，哈希算法等

在连续分配中，即便内存有超过 1GB 的空闲空间，但若该 1GB 空间不连续，则仍然无法运行一个 1GB 空间作业，但若采用非连续分配方式，则作业要求的 1GB 空间可以分散在内存的各个区域。

当然，非连续分配方式需要额外的空间存储分散区域的索引，因此非连续分配的存储密度低于连续分配方式。根据分区的大小是否固定，我们将非连续分配划分为分段存储管理和分页存储管理。

Segmentation Architecture¶

分段式是对程序员更友好的一种管理方式，它将一个用户进程的逻辑地址空间划分为大小不等的段，例如主程序段、子程序段、栈段、数据段等。

在保护模式下，段寄存器不再单独存储段地址，而是存储指向 Descriptor Table 中的某一描述符的 Selector。

例如对于指令 MOV [BX], AX，它的访存流程如下：

一个 Descriptor 包含该段在内存中起始地址 Base 和段的长度 Limit。执行中的进程可以通过查找段表找到每段对应的内存区。

Segment-table base register, STBR 指向 Segment Table 的物理起始地址
Segment-table length register, STLR 表示一个程序的分段数量

更详细的内容，可见The Microprocessor and its Architecture - Nimisora's Notes

Paging Architecture¶

分页思想将物理内存空间划分为若干固定大小（通常为 4KB）的分区，称为 Frame，将逻辑内存空间划分为同样固定大小的分区，称为 Page。

分页管理不会产生外部碎片，而内部碎片也只会在系统为进程申请的最后一个分区中出现，每个进程平均只会产生半个块大小的内部碎片。

以下内容也来自我的「汇编与接口」笔记

与计组中学到的分页稍有区别的是，现实 CPU 通常会采用 Multi-level Paging，而不是只通过一个 Page Table 就能转换虚拟地址和物理地址。这是因为 Single-level 往往占用太多内存。

例如，对于 64-bit computer，假定我们设置 4KB page size, 4GB physical memory, 4Byte per page table entry，那么 \(\text{Page Offset}= \log_2 4K=12\ bits\)，那么 \(\text{Virtual Page Number} = 64-12=52\ bits\)，一个 entry 有 4B，那么整个 Page Table 占用内存 \(2^{52}\times 4= 2^{54}\ bytes\)，这已经是物理内存 4GB（\(2^{32}\)）的不知道多少倍了。

现在我们使用 Multi-level Paging 技术。通常，我们设置一个 Page Table 的大小等同于一个 Page 的大小，对于该例即为 4KB。此时一个 Page Table 共有 4KB / 4B = 1024 个 entries。

1024 个 entries 意味着我们只需要 10-bit 就能对一个 Page Table 进行索引，那么层数计算则为 \(\#\text{ of Level}= \frac{52}{10}\ \text{ceiled is } 6\)，即共需要 6 层，其索引结构类似如下：

Key Points

所有 Page Table 的 entry size 均需相同
Page Table 由内到外分别称为
- Page Table, PT
- Page Directory, PD
- Page Directory Pointer Table, PDPT

🌟 类别	🟢 优点 (Pros)	🔴 缺点 (Cons)
内存占用	仅为实际使用的虚拟地址空间分配页表，节省大量内存	页表结构本身更复杂，需要额外的目录页表，占用少量额外空间
稀疏地址空间支持	对于稀疏内存使用的进程非常高效，不会为空洞地址范围浪费页表项	若进程使用地址空间非常密集，多级页表节省的空间优势不明显
可扩展性	适用于大型虚拟地址空间（如 32 位、64 位系统）	随层数增加，页表查找过程更长、更慢
访问速度	——	每增加一级页表，就需要多一次内存访问才能完成地址转换
性能优化	可与 TLB（Translation Lookaside Buffer）配合使用，显著减少查找延迟	若 TLB 命中率低，会出现明显性能下降

Paging 为 OS 提供了将虚拟地址转换为物理地址（Relocation）的抽象层，因此不同应用可以使用各自隔离的虚拟地址空间（Protection），多个应用还可以通过 Shared Mapping 共享同一个物理页（Sharing）。

Virtual Memory¶

Demand Paging¶

基于局部性原理，在程序装入时，仅需将程序当前运行所需的少数 Page 装入内存，而将其余部分暂留在外村，便可启动程序执行。执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存中调入内存，然后继续执行程序，这个过程称为 Demand Paging。

通过 Demand Paging，操作系统就好像为用户提供了一个比实际内存容量大得多的存储器，这就是 Virtual Memory。

相比于基本分页系统，请求分页系统需要知道每个 Page 是否已调入内存；若未调入，还需要知道该页在外存中的存放地址。为了实现页面置换功能，操作系统还需要一些额外信息和算法来决定换出哪个页面，以及被换出的页面是否被修改过。

因此，一个 Page Entry 至少包含如下几个字段：

在请求分页系统中，每当要访问的页面不在内存中时，便会产生一个 Page Fault，其处理流程为：

<1> 检查 PCB 判断访问是否合法
- 如果访问地址不属于该进程，则为非法访问，终止进程
<2> 如果访问合法，但 Page 不再内存，产生 Page Fault 并准备调入
<3> 通过一定算法选择一个空闲 Frame
<4> 从外存中将所需页面读入该 Frame
<5> 更新 Page Table Entry 和 PCB
<6> 重新执行刚刚因 Page Fault 而中断的指令

一条指令在执行期间可能产生多次缺页中断

Frame Allocation¶

将有限的物理 Frames 分配给所有进程，可采用以下几种算法：

1）平均分配算法，将系统中所有可供分配的物理块平均分配给各个进程。
2）按比例分配算法，根据进程的大小按比例分配物理块。
3）优先权分配算法，为重要和紧迫的进程分配较多的物理块。通常采取的方法是将所有可分配的物理块分成两部分：一部分按比例分配给各个进程；一部分则根据优先权分配。

Page Replacement¶

进程运行时，若内存已无空闲空间时但需要调入一个 Page 时，就需要通过页面置换算法从内存中调出一个 Page。

由于 Page 的 swap in 和 swap out 需要磁盘 I/O，开销较大，因此一个好的置换算法应该追求更低的缺页率

FIFO

FIFO 算法优先替换最早进入内存的页面。该算法实现简单，但是并没有利用局部性原理，与实际运行规律不适应，因此性能较差。

除此之外，FIFO 算法还有可能因为系统为该进程分配的物理块增多而出现 Page Fault 次数不减反增的异常现象，这被称为 Belady 异常。

只有 FIFO 会出现 Belady 异常

LRU

LRU 算法优先替换最近最长时间未使用的页面，该算法为每个 Page 维护一个上次访问的时间戳，并淘汰现有页面中值最大的 Page。

根据局部性原理，LRU 算法的性能较好，但实现起来需要寄存器和栈的硬件支持。

另外，在数据库扫描场景下，LRU 的性能有可能比不过 MRU

CLOCK

CLOCK 算法及其变体尝试用更小的开销来接近 LRU 算法的性能，它也被称为 Second-Chance 置换算法。

最简单的 CLOCK 置换算法将内存中的 Page 链接成循环队列，当 Page 首次装入或被访问时，其 Reference Bit 置 1。当需要替换一个 Page 时，一个替换指针会顺序检查循环队列中的 Page，如果遇到 Ref = 0 的 Page，则将其替换；如果遇到 Ref = 1 的 Page，则将其置 0，给予第二次驻留内存的机会。

改进的 CLOCK 算法使用访问位 A 和修改位 M 一起作为替换的依据，根据二者组合，总共有如下四种类型的 Page：

\(A=0, M=0\): 最近未被访问，且未被修改，是最佳的淘汰页
\(A=0, M=1\): 最近未被访问，但已被修改，是次佳的淘汰页
\(A=1,M=0\): 最近已被访问，但未被修改，可能再次访问
\(A=1, M=1\): 最近已被访问，且已被修改，可能再次访问

此时，替换指针扫描总共分为三步：

<1> 从指针当前位置开始扫描一轮，寻找 \(A=0, M=0\) 的 Page 并选中
- 第一次扫描期间不改变 \(A\)
- 有可能找不到符合要求的 Page
<2> 若第一步失败，开始第二轮扫描，寻找 \(A=0, M=1\) 的 Page 并选中；扫描期间，将所有扫描到的 Page 的 \(A\) 置 0
- 此时也有可能失败，即存在所有 Page 的 \(A\) 均为 1 的情况
<3> 若第二步也失败，则重复 <1> 和 <2>，此时一定能找到被淘汰的 Page

改进 CLOCK 算法减少了磁盘 I/O 次数，但算法本身开销增大

Optimal

OPT 置换算法选择淘汰以后永不使用或最长时间内不会再被访问的 Page，保证获得最低的缺页率。然后，进程中哪个页面是未来最长时间内不会被访问的是无法预测的，因此该算法无法实现，但可利用该算法去评价其它算法。

LRU 算法是最接近 OPT 算法的置换算法。

Thrashing¶

一个进程在频繁的进行 Page 换出换进，这一现象称为 Thrashing。

系统发生 Thrashing 的根本原因是分配给每个进程的物理块太少，不能满足进程正常运行的基本要求，导致每个进程运行时频繁缺页。

为此，我们引入进程工作集(Working Set)的概念。工作集是指在某段时间间隔内，进程要访问的 Page 集合。一般来讲，工作集 \(W\) 可通过时间 \(t\) 和工作集窗口尺寸 \(\Delta\) 来确定：

例如对于如上例子，窗口尺寸 \(\Delta=5\)，在 \(t_1\) 时刻，工作集为 \(\{2,3,5\}\)，\(t_2\) 时刻，工作集为 \(\{1,2,3,4\}\)。

工作集反映了进程在接下来的一段时间内可能频繁访问的 Page 集合，因此该进程被分配的物理块个数不能小于工作集大小，否则会在运行过程中频繁缺页。

Memory-Mapped Files¶

内存映射文件是操作系统向应用程序提供的一个系统调用，它与虚拟内存有些相似，会在磁盘文件和进程的虚拟地址空间之间建立映射关系。

Memory-Mapped File I/O 的核心思想是，把磁盘上的文件内容映射到进程的虚拟内存空间中，使文件访问变成普通的内存访问，即从 read/write 变为 load/store。

磁盘文件的读写由操作系统负责完成，对进程而言是透明的。在映射进程的页面时，不会实际读入文件的内容，而只在访问页面时才被每次一页地读入。当进程退出或关闭文件映射时，所有被改动的页面才被写回磁盘文件。

实际上，共享内存的方式就是通过 Memory-Mapped Files 实现的，它将同一份文件映射到两个进程的虚拟地址空间：

Comments: