操作系统从入门到入土③：内存管理

Posted on 2021-10-12 In 操作系统 Views: Disqus: Reading time ≈ 30 mins.

1. 无存储器抽象

早期大型计算机（20 世纪 60 年代之前）、小型计算机（20 世纪 70 年代之前）和个人计算机（20 世纪 80 年代之前）都没有存储器抽象。每一个程序都直接访问物理内存。

例如：MOV REGISTER1, 1000，计算机会将位置为 1000 的物理内存中的内容移到 REGISTER1 中。

问题 1：保护

如果用户程序可以寻址内存的每个字节，就可以很容易地破坏操作系统，从而使系统慢慢地停止运行。
想要同时运行多个程序是很困难的。如果第一个程序在 2000 的位置写入一个新的值，将会擦掉第二个程序存放在相同位置上的所有内容。

保护键：

对比：与锁的性质类似

IBM 360 的早期模型是这样运行多个程序的

每一个内存单元都会被分配一个 4 位的保护键，保护键存储在 CPU 的特殊寄存器中。
每一个进程有一个 PSW（Program Status Word，程序状态字），PSW 中保存一个 4 位的码。

保护键作为进程和其相关内存的唯一标识。在访问内存的时候，首先查看进程的 PSW 码和这个内存块的保护键是否相同。如果相同就可以访问，如果不同，就禁止该进程访问。因为只有操作系统才能修改保护键，这样就避免了不同程序之间的相互访问。

问题 2：重定位
跳转指令跳转的地址是物理地址，多个程序运行时会出现问题。

a 和 b 为两个程序，依次装载到内存后如 c 所示，b 中的 JMP28 应该跳转至地址 16412，但实际却是跳转到了 28，原因就在于这两个程序中的地址都是绝对物理地址。

静态重定位：
IBM 360 对上述问题的补救方案是静态重定位。只要在装载程序的时候给每一个程序地址加上装载时的地址偏移量就可以了，例如 b 程序被装载到地址 16384，那么 JMP 28 加上偏移量 16384 就行了。
但是这个机制会减慢装载速度，而且装载器需要区分地址和常数，所以程序需要提供区分信息。

2. 地址空间

地址空间是进程可用于寻址内存的一套地址集合，其为程序创造了一种抽象的内存。每个进程都有唯一的专属地址空间，这就使得每个程序内代码中的地址也是唯一的（如上述 JMP 28 的物理地址也有别于别的程序的 28）。

2.1. 基址寄存器与界限寄存器

使用动态重定位，把每个进程的私有地址空间映射到物理内存的不同部分。
早期计算机（Intel 8088、CDC 6600 等）使用基址寄存器与界限寄存器实现：

程序装载到内存中连续的空闲位置且无须重定位。
进程运行时，程序的起始物理地址装载到基址寄存器中，程序的长度装载到界限寄存器中，根据起始点和长度就能确定一段唯一的地址。

每次一个进程访问内存，取一条指令，读或写一个数据字，CPU 硬件会在把地址发送到内存总线前，自动把基址值加到进程发出的地址值上。
同时，它检查程序提供的地址是否等于或大于界限寄存器里的值，如果访问的地址超过了界限，会产生错误并中止访问。

缺点：
每次访问内存都需要进行加法和比较运算，加法运算由于进位传递时间的问题会比较慢。

对比：静态重定位

2.2. 交换技术

针对内存超载的处理方法

交换：把一个进程完整调入内存运行一段时间然后把它存回磁盘。

虚拟内存

开始时内存中只有进程 A。之后创建进程 B 和 C 或者从磁盘将它们换入内存。之后 A 被交换到磁盘，然后 D 被调入，B 被调出，最后 A 再次被调入。
由于 A 的位置发生变化，所以在它换入的时候通过软件或者在程序运行期间通过硬件对其地址进行重定位。例如，基址寄存器和界限寄存器就适用于这种情况。

数据增长：
如果进程的数据段可增长（动态分配内存）
若其与一个空闲区相邻，可把该空闲区分配给该进程。
若其与另一个进程相邻，则要么把该进程移到一个空间足够大的地方，要么把其他进程交换出去以生成一个足够大的空闲区（交换区满了就只能挂起了）。

另一种方法是进程进入内存时分配一些额外的内存。

2.3. 空闲内存管理

在动态分配内存时，操作系统必须对其进行管理。
有两种方法跟踪内存使用情况：位图和空闲区链表。

2.3.1. 位图存储管理

内存被划分成几个字到几千字节的分配单元，每个分配单元对应位图中的一位，0 表示空闲，1 表示占用。

a) 内存：有 abcde 5 个进程和 3 个空闲区
b) 内存对应的位图
c) 空闲区链表形式

缺点：
在决定把一个占 k 个分配单元的进程调入内存时，存储管理器必须搜索位图找出有 k 个连续 0 的串，这比较耗时，因为在位图中该串可能跨越字的边界。

2.3.2. 链表存储管理

维护一个记录已分配内存段和空闲内存段的链表。
链表中的每一个结点都包含以下字段：空闲区或进程的指示标志、起始地
址、长度和指向下一结点的指针。

分配内存算法：

首次适配：存储管理器搜索链表，找到足够大的空闲区，并将其分为两部分，一部分供进程使用，另一部分形成新的空闲区。
下次适配：和首次适配类似，每次找到合适的空闲区都记录当时的位置，以便下次寻找空闲区时从上次结束的地方开始搜索。
最佳适配：搜索整个链表，找到最小适配的空闲区。最佳适配算法会生成大量无用的小空闲区，比首次适配算法浪费更多的内存。
最差适配：与最佳相反，总是分配最大的空闲区，使新的空闲区比较大从而可以继续使用
快速适配：为常用大小的空闲区维护单独的链表。例如，一个链表第一个节点指向大小近似为 4KB 的空闲链表表头的指针，第二个指向 8KB 的，第三个指向 12KB 的……

如果进程和空闲区维护各自的链表，那么算法速度能得到提高，但是链表维护成本也增加了。可以对空闲区列表排序提高最佳适配算法的检索速度

3. 虚拟内存

对比：交换

每个程序拥有自己的地址空间，这个空间被分割成多个块，每一块称作页面（page）。每一页有连续的地址范围。

当程序引用到一部分在物理内存中的地址空间时，由硬件立刻执行必要的映射。
当程序引用到一部分不在物理内存中的地址空间时，由操作系统负责将缺失的部分装入物理内存并重新执行失败的指令。

3.1. 分页

页面是由虚拟地址空间分割成的块，其在物理内存中对应的单元称为页框（page frame），页面和页框大小通常是一样的。RAM 和磁盘之间的交换是以页面为单元进行的。

虚拟地址：
当程序执行指令 MOV REG, 1000 时，它把地址为 1000 的内存单元的内容复制到 REG 中。地址可以通过索引、基址寄存器、段寄存器或其他方式产生。

由程序产生的这些地址称为虚拟地址（virtual address），它们构成了一个虚拟地址空间（virtual addressspace）。

在没有虚拟内存的计算机上，系统直接将虚拟地址送到内存总线上，读写操作使用具有同样地址的物理内存字。
在使用虚拟内存的情况下，虚拟地址不是被直接送到内存总线上，而是被送到内存管理单元（Memory Management Unit, MMU），MMU 把虚拟地址映射为物理内存地址。

MMU 映射机制：

假如程序访问地址 0：MOV REG, 0

将虚拟地址 0 送到 MMU。MMU 发现虚拟地址在页面 0（0k~~4k），其映射到页框 2（8k~~12k），所以把地址变换为 8192 并把变换后的地址送到总线上。

假如程序访问了一个未映射的页面：MOV REG, 32780

MMU 发现虚拟页面 8（32k-36k）没有被映射，于是使 CPU 陷入到操作系统，这个陷阱称为 ** 缺页中断 ** 或 ** 缺页错误（page fault） **。
随后操作系统找到一个不常使用的页框并把它的内容写入磁盘，然后把需要访问的页面读到该页框中，修改映射关系，再重新启动引起陷阱的指令。

MMU 内部结构：

这是 64kb 虚拟内存的 MMU 结构，第一列为页框号，第二列表示是否存在物理内存的映射关系。
输入的 16 位虚拟地址。前 4 位为页号，可以表示 16 个页面；后 12 位为偏移量。

第二列为 0，则说明不存在物理内存的映射关系，这将引起一个陷阱。
第二列为 1，则将页表中查到的页框号复制到输出寄存器的高 3 位中，再加上虚拟地址的低 12 位，就构成了 15 位的物理地址，将其送到内存总线。

页表：
页表的目的是把虚拟页面映射为页框。
页表每一项称为页表项

页框号：通过映射要获得的值，与低位虚拟地址结合组成物理地址。
“在 / 不在” 位：判断是否有页框号，如果不存在则会引起一个缺页中断。
保护位：指出一个页允许什么类型的访问，读、写、执行等。
修改位：在写入一页时由硬件自定设置修改位。
访问位：页面被访问时设置访问位。不再被使用的页面会在缺页中断时被重新选择。
高速缓存禁止位：用于禁止高速缓存

缺页中断过程：

陷入内核。硬件陷入内核，在堆栈中保存程序计数器。再启动一个汇编代码例程保存通用寄存器和其他易失的信息。
得到虚拟页面。操作系统发现缺页中断，得到需要的虚拟页面，通常在硬件寄存器中。

若没有，操作系统必须检索程序计数器，取出这条指令，用软件分析这条指令，看看它在缺页中断时正在做什么。

检查地址。检查这个虚拟地址是否有效，并检查存取与保护是否一致。

如果存取与保护不一致，向进程发出一个信号或杀掉该进程。

选择页框。如果地址有效且没有保护错误发生，系统则检查是否有空闲页框。

如果没有空闲页框，执行页面置换算法寻找一个页面来淘汰。

写回脏页框。如果选择的页框被修改过（脏的），则将该页写回磁盘。

并发生一次上下文切换，挂起产生缺页中断的进程，让其他进程运行直至磁盘传输结束。
该页框被标记为忙，以免因为其他原因而被其他进程占用。

装入磁盘地址。一旦页框是干净的（本就是干净的或写回磁盘后变干净），操作系统查找所需页面在磁盘上的地址，通过磁盘操作将其装入。

该页面正在被装入时，产生缺页中断的进程仍然被挂起，并且如果有其他可运行的用户进程，则选择另一个用户进程运行。
恢复状态。当磁盘中断发生时，表明该页已经被装入，页表已经更新可以反映它的位置，页框也被标记为正常状态。

恢复发生缺页中断指令以前的状态，程序计数器重新指向这条指令。

恢复进程。调度引发缺页中断的进程，操作系统返回调用它的汇编语言例程。

该例程恢复寄存器和其他状态信息，返回到用户空间继续执行，就好像缺页中断没有发生过一样。

策略和机制分离：

出现缺页中断：

缺页中断处理程序找出需要哪个虚拟页面，并发送一条消息给外部页面调度程序告诉它发生了什么问题。
外部页面调度程序从磁盘中读入所需的页面，把它复制到自己的地址空间的某一位置。然后告诉缺页中断处理程序该页面的位置。
缺页中断处理程序从外部页面调度程序的地址空间中清除该页面的映射，然后请求 MMU 处理程序把它放到用户地址空间的正确位置，随后就可以重新启动用户进程了。

3.2. TLB

虚拟地址到物理地址的映射必须非常快。
分页机制使得程序需要访问页表，从而更加频繁的访问内存。
程序每条指令进行一两次或更多页表访问是必要的。如果执行一条指令需要 1ns，页表查询必须在 0.2 ns 之内完成。

由于大多数程序总是对少量的页面进行多次访问，所以可以为计算机设置一个缓存。

概述：

此方案为计算机设置一个 转换检测缓冲区（Translation Lookaside Buffer，TLB，也称快表），将虚拟地址直接映射到物理地址，而不必再访问页表。
它通常在 MMU 中，包含少量的表项（一般不超过 256 个），这些字段与页表中的一致，有效位表示该表项是否有效。

程序将虚拟地址放入 MMU 中进行转换时，硬件首先会通过虚拟页面号在 TLB 中寻找匹配：

能找到且操作不违反保护位则直接返回，违反保护位则产生一个保护错误。
若找不到则会进行正常的页表查询，将查询得到的新项替代 TLB 中的一个淘汰项。新项的所有字段都被复制到 TLB，淘汰项的会将修改位复制会内存里对应的页表项中。

未命中情况：

访问非法地址：程序可能访问了一个非法地址，系统会产生段错误，不需要往 TLB 中添加映射。
软失效：TLB 失效但内存页表未失效，这时只需更新一下 TLB 就行，不需要产生磁盘 I/O。
硬失效：TLB 失效且内存页表失效，引发缺页中断。
- 次要缺页错误：页面可能就在内存中，但未记录在该进程的页表里。

比如该页面可能已由其他进程从硬盘中调入内存，这时只需要把所需的页面正确映射到页表中就行。

严重缺页错误：页面不在内存中，需要从硬盘中重新调入。

硬件采用简单的 TLB 管理方式，就能够获得较高的 TLB 命中率的原因：
应用程序在运行过程中访问内存的模式具有时间局部性和空间局部性。

时间局部性：被访问过一次的内存位置在未来通常会被多次访问。
空间局部性：如果一个内存位置被访问，那么其附近的内存位置通常在未来也会被访问。

软件 TLB 管理：
TLB 表项被操作系统显式地装载。

当 TLB 访问失效时，不再是由 MMU 到页表中查找并取出需要的页表项，而是生成一个 TLB 失效并将问题交给操作系统解决。
系统找到该页面，然后从 TLB 中删除一个项，接着装载一个新的项，最后再执行先前出错的指令。当然，所有这一切都必须在有限的几条指令中完成，因为 TLB 失效比缺页中断发生得更加频繁。

使用软件处理 TLB 失效时，需先在内存中找到页表，以定位到页表项。
但是页表也有自己的虚拟地址，就像查询其他虚拟地址一样，获取页表的物理地址时也会出现 TLB 失效。

3.2.1. TLB 刷新

由于 TLB 是使用虚拟地址进行查询的，所以操作系统在进行页表切换（应用程序切换）的时候需要主动刷新 TLB。

标签：
若在切换应用程序的过程中刷新 TLB，当应用程序开始执行时会发生 TLB 未命中的情况。
一种为 TLB 缓存项打上 “标签” 的设计避免了这样的开销。AArch64 体系结构提供了 ASID（ Address Space IDentifier）功能，x86-64 上对应的功能称为（PCID, Process Context IDentifier）。

操作系统可以为不同的应用程序分配不同的 ASID 作为应用程序的身份标签，再将这个标签写入应用程序的页表基地址寄存器中的空闲位（如 TTBRO_ EL1 的高 16 位）。
同时，TLB 中的缓存项也会包含 ASID 这个标签，从而使得 TLB 中属于不同应用程序的缓存项可以被区分开。因此，在切换页表的过程中，操作系统不再需要清空 TLB 缓存项。

3.3. 针对大内存的页表

如果虚拟地址空间很大，页表也会很大。
假设页面大小为 4kb，32 位的地址空间将有 100 万表项，每个进程都需要自己的页表。

3.3.1. 多级页表

引入多级页表的原因是避免把全部页表一直保存再内存中。

如 a) 所示，32 位地址被划分为 10 位的 PT1 域、10 位的 PT2 域、12 位的 Offset 偏移量域。
因为偏移量是 12 位，所以页面大小是 212 = 4KB。10 位的 PT1 和 10 位的 PT2 一共 20 位，所以共有 220 个页面。

当一个虚拟地址被送到 MMU 时，首先提取 PT1 域将其作为顶级页表的索引。
因为整个 4GB（232 B = 4GB）虚拟地址空间已经按 4KB 大小分块，所以顶级页表中这 1024 个表项的每一个都表示 4M（PT2 的 10 位和偏移量的 12 位，222B = 4M）的块地址范围。

顶级页表的表项 0 指向程序正文的页表，表项 1 指向数据的页表，表项 1023 指向堆栈的页表。

3.3.2. 倒排页表

实际内存中的每个页框对应一个表项，而不是每个虚拟页面对应一个表项。

虽然倒排页表节省了大量的空间，但从虚拟地址到物理地址的转换会变得很困难。
当进程 n 访问虛拟页面 p 时，硬件不能把 p 当作指向页表的一个索引来查找物理页框，必须搜索整个倒排页表来查找某一个表项（n，p），而且每一个内存访问操作都要执行一次。

解决办法是使用 TLB。如果 TLB 能够记录所有频繁使用的页面，地址转换就可能变
得像通常的页表一样快。
但是，当发生 TLB 失效时，需要用软件搜索整个倒排页表。可以建立一张散列表，用虚拟地址来散列，相同散列值的虚拟页面被链接在一起。
如果散列表中的槽数与机器中物理页面数一样多，那么散列表的冲突链的平均长度将会是 1 个表项的长度，这将会大大提高映射速度。一旦页框号被找到，新的（虚拟页号，物理页框号）对就会被装载到 TLB 中。

3.4. 页面置换算法

缺页中断时，操作系统必须在内存中选择一个页面将其换出内存。
如果换出的页面在内存驻留期间被修改过，就必须把它写回磁盘；否则直接淘汰就行了。

3.4.1. 最优算法

缺页中断发生时，下一条指令的那个页面将很快被访问，其他页面则可能要到 10、100 或 1000 条指令后才会被访问，所以每个页面都可以用其被访问前要执行的指令数作为标记。

最优页面置换算法规定应该置换标记最大（最晚执行）的页面。这样，下次调入这个页面发生的缺页中断就会被推迟。

但是当缺页中断发生时，操作系统无法知道各个页面下一次将在什么时候被访问。
当然，通过先在仿真程序上运行程序，跟踪所有页面的访问情况，然后在第二次运行时利用第一次收集的信息是可以实现最优页面置换算法的。

必须清楚以上方法只针对刚刚被测试过的程序和它的一个特定的输入。虽然这个方法对评价其他页面置换算法很有用，但它在实际系统中却不能使用。

3.4.2. 最少使用算法

系统为每一个页面设置了 R/M 位。

当页面被访问时设置 R 位。当启动一个进程时，将其所有的页面的这两个位都设为 0，R 位定期清 0（比如在时钟中断时）
当页面被写入时设置 M 位。

当发生缺页中断时，操作系统检查所有的页面并根据它们当前的 R 位和 M 位，有以下几种情况：

未被访问，未被修改。
未被访问，已被修改。（可能时钟中断导致 R 位清 0）
已被访问，未被修改。
已被访问，已被修改。

NRU（Not Recently Used，最近未使用）算法优先淘汰未被访问的页面，若待选页面的访问位一致，则优先淘汰未被修改的页面。
其原理是在最近一个时钟滴答中淘汰一个没有被访向的已修改页面要比淘汰一个被频繁使用未修改页面好。

3.4.3. 先进先出算法

由操作系统维护一个内存中的页面链表，最新进入的页面放在表尾，最早进入的页面放在表头。
当发生缺页中断时，淘汰表头的页面并把新调入的页面加到表尾。FIFO 可能会淘汰常用页面，由于这一原因，很少使用纯粹的 FIFO 算法。

3.4.4. 第二次机会算法

FIFO 算法可能会把经常使用的页面置换出去。所以我们可以给经常使用的页面一次 “机会”。
第二次机会（second chance）算法在 FIFO 的基础上，只淘汰未被访问的页面。

对 FIFO 做修改，淘汰表头时先检查其 R 位。

如果 R 位是 0，那么这个页面既老又没有被使用，可以立刻置换掉
如果 R 位是 1，就将 R 位清 0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续搜索。

3.4.5. 时钟算法

对比第二次机会算法、先进先出算法

第二次机会算法经常要在链表中移动页面，既降低了效率又不是很有必要。

时钟算法把所有的页面保存再一个环形链表中（顺时针），一个指针指向最先进入的页面，代表表头。

当发生缺页中断时，检查指针指向的页面的 R 位：

若 R = 0：淘汰该页面，将新的页面替换该页面，指针向后移动一位
若 R = 1：将该页面的 R 位清 0，将指针指向下个节点，继续以上流程判断节点的 R 位。

3.4.6. 最近最少使用算法

对比最少使用算法

当缺页中断发生时，置换未使用时间最长的页面，这个策略被称为 LRU（Least Recently Used）。

需要在内存中维护一个所有页面的链表，最近最多使用的页面在表头，最近最少使用的页面在表尾。每次访问内存都必须要更新整个链表。

NFU（Not Frequently Used，最不常用）算法：
将每个页面与一个软件计数器关联，计数器的初值为 0。每次时钟中断时，由操作系统扫描内存中所有的页面，将每个页面的 R 位加到它的计数器上。
这个计数器大体上跟踪了各个页面被访问的频繁程度。发生缺页中断时，则置换计数器值最小的页面。

老化（aging）算法：
修改 NFU 以模拟 LRU，在 R 位被加进之前先将计数器右移一位，然后将 R 位加到计数器最左端的位位，这样最近被访问的页面的计数器（例如 10000000）会比之前访问过的要大（例如 00000010）。发生缺页中断时置换计算器值最小的页面。

图中页面内存的是计数器。
假设在第一个时钟后，页面 0 ~ 5 的 R 位值分别是 101011。即在时钟 0 到 1 期间，访问了页面 0、2、4、5，它们的 R 位设置为 1。对应的 6 个计数器在经过移位并把 R 位插入其左端后的值，如 a) 页面中的计数器所示。

3.4.7. 工作集算法

一个进程当前正在使用的页面的集合称为它的 工作集。

如果整个工作集都被装入到了内存中，那么进程在运行到下一运行阶段之前，不会产生很多缺页中断。
若内存太小而无法容纳下整个工作集，那么进程的运行过程中会产生大量的缺页中断，导致运行速度也会变得很缓慢。

设法跟踪进程的工作集，以确保在让进程运行以前，它的工作集就已在内存中了，该方法称为 ** 工作集模型 **

3.4.8. 工作集时钟算法

当缺页中断发生后，需要扫描整个页表才能确定被淘汰的页面，因此基本工作集算法是比较费时的。

WSClock（工作集时钟）算法基于时钟算法，并且使用了工作集信息，由于它实现简单，性能较好，所以在实际工作中得到了广泛应用。

每次缺页中断时，首先检查指针指向的页面。

如果 R 位为 1，那么该页面在当前时钟滴答中就被使用过，不适合被淘汰。把 R 位设为 0，然后指针指向下一个页面，并重复该算法。如 a) b)。
如果页面的生存时间大于 r 并且该页面未被修改，它就不在工作集中，并且在磁盘上有一个有效的副本。申请此页框，并把新页面放在其中。如 c) d)。
如果此页面被修改过，就不能立即申请页框，因为这个页面在磁盘上没有有效的副本。为了避免由于调度写磁盘操作引起的进程切换，指针继续向前走，算法继续对下一个页面进行操作。

原则上，所有的页面都有可能因为磁盘 I/O 在某个时钟周期被调度。为了降低磁盘阻塞，需要设置一个限制，即最大只允许写回 n 个页面。一旦达到该限制，就不允许调度新的写操作。

4. 分页系统中的设计问题

4.1. 局部分配与全局分配

运行多个进程时发生缺页中断，该如何进行页面置换？

A、B、C 是正在运行的进程，加入 A 发生了缺页中断，有两种方法

局部页面置换：淘汰该进程生存时间最短的页面（A5）
全局页面置换：淘汰内存中生存时间最短的页面（B3）。通常情况下工作得比局部算法好

4.2. 负载控制

即使是使用最优页面置换算法并对进程采用理想的全局页框分配，系统也可能会发生页面频繁置换的情况。

一个方法是将一部分进程交换到磁盘，并释放他们所占有的所有页面。

4.3. 共享页面

只读的页面（程序文本）可以共享，数据页面不能共享。

共享页面上存在一个问题，假设进程 A 和进程 B 同时运行一个编辑器并共享页面。如果调度程序决定从内存中移走 A，撤销其所有的页面并用一个其他程序来填充这些空的页框，则会引起 B 产生大量的缺页中断，才能把这些页面重新调入。

写时拷贝：
UNIX 中 fork 系统调用后，父进程和子进程要共享程序文本和数据。

让这些进程分别拥有它们自己的页表，但都指向同一个页面集合。
一旦某个应用程序对该内存区域进行修改，就会触发缺页异常。这里的缺页异常是由于违反权限导致的，不同于之前所说的换页机制下的缺页异常是由于未映射导致的。
在触发了缺页异常后，CPU 同样会将控制流传递给操作系统预先设置的缺页异常处理函数。
在该函数中，操作系统会发现当前的缺页异常是由于应用程序写了只读内存，而且相应的内存区域又是被操作系统标记成写时拷贝的。

于是，操作系统会在物理内存中将缺页异常对应的物理页重新拷贝一份，并且将新拷贝的物理页以可读可写的方式重新映射给触发异常的应用程序，此后再恢复应用程序的执行。

若其中一个进程更新了数据，就会触发只读保护，并引发操作系统陷阱，生成一个该页的副本，这样每个进程都有自己的专用副本。
这种策略意味着那些从来不会执行写操作的页面是不需要复制的，只有实际修改的数据页面需要复制。

内存去重：
操作系统可以定期地扫描相同内容的物理页，找到其映射的虚拟页，然后只保留其中一个物理页。
并将具有相同内容的其他虚拟页都用写时拷贝的方式映射到这个物理页，然后释放其他的物理页以供将来使用。

内存去重功能会对应用程序访存时延造成影响。当应用程序写一个被去重的内存页时，既会触发缺页异常，又会导致内存拷贝，从而可能导致性能下降。

时间换空间

4.4. 共享库

现代操作系统中，有很多大型库被众多进程使用。一个更加通用的技术是使用 共享库（在 Windows 中称作 DLL 或 ** 动态链接库 **）。

当链接一个程序时，要在链接器的命令中指定一个或多个目标文件，可能还包括一些库文件。链接器会在库中寻找未定义外部函数，找到了则将它们加载到可执行二进制文件中。
静态链接上百个这些库的程序会浪费大量的磁盘空间，装载这些程序时也会浪费大量的内存空间。
当一个程序和共享库链接时，链接器没有加载被调用的函数，而是加载了一小段能够在运行时绑定被调用函数的存根例程（stub routine）。如果其他程序已经装载了某个共享库，就不用再次装载了。

5. 分段

对许多问题来说，有多个独立的地址空间会好得多。
只使用一个虚拟空间时，我们需要管理表的扩张和收缩。
如果一个程序中变量的数量要远比其他部分的数量多时的情况。地址空间中分给符号表的块可能会被装满，但这时其他表中还有大量的空间。

段：
可以在及其上提供多个互相独立的逻辑段地址空间，每个段之间都是隔离的。
每个段由一个从 0 到最大的地址序列构成。段的长度可以是 0 到某个允许的最大值之间的任何一个值。不同段的长度通常情况下也都不相同，并在运行期间长度可变。

如果每个过程都位于一个独立的段中并且起始地址是 0，那么把单独编译好的过程链接起来的操作就可以得到很大的简化。

程序必须提供两部分地址，一个段号和一个段内地址。

6. 内存分配

6.1. 伙伴系统

伙伴系统（buddy system）的基本思想是将物理内存划分成连续的块，以块作为基本单位进行分配。不同块的大小可以不同，但每个块都由一个或多个连续的物理页组成，物理页的数量必须是 2 的 n 次幂。

分裂与合并：
在处理分配请求的过程中，大的块可以分裂成两个小一号的块，这两个块互为伙件。分裂得到的块可以继续分裂，直到得到一个大小合适的块去服务相应的分配请求。
在一个块被释放后，分配器会找到其伙伴块，若伙伴块也处于空闲的状态，则将这两个伙伴块进行合并，形成一个大一号的空闲块，然后继续尝试向上合并。由于分裂操作和合并操作都是级联的，因此能够很好地缓解外部碎片的问题。