《Operating Systems:Three Easy Pieces》 操作系统导论【二】 虚拟化内存

【Operating Systems:Three Easy Pieces 操作系统导论 】

(九) 抽象：地址空间

早期系统

操作系统曾经是一组函数（实际上是一个库），在内存中（在本例中，从物理地址0开始），然后有一个正在运行的程序（进程），
目前在物理内存中（在本例中，从物理地址 64KB 开始）， 并使用剩余的内存。这里几乎没有抽象。

多道程序和时分共享

地址空间

• 代码 ： 程序代码位置，静态的
• 栈 ： 向上增长，不一定放在底部
• 堆 ：向下增长，不一定放在代码段下

这个 0-16KB 的地址空间是虚拟的，不是实际的物理地址（0 物理地址一般是 boot 程序，不可能给一个用户程序用）
内存虚拟化也保证了隔离性和安全性。

目标

• 透明：进程不知道自己运行在虚拟内存环境下，就好像地址都是物理地址一样
• 效率：虚拟化时不应该拖慢调度和运行时间，不应该占用更多内存
• 保护：不会影响操作系统和其他进程的内存空间。

(十) 插叙：内存操作 API

在本章中，我们将介绍 UNIX 操作系统的内存分配接口

内存类型

• 栈内存它的申请和释放操作是编译器来隐式管理的，所以有时也称为自动（automatic）内存。比如，一个函数的局部变量，在进入函数时分配，退出时释放。
• 堆内存申请和释放都是显式的，比如 C 语言的malloc。

void func() { 
    int x; // declares an integer on the stack ...
    //在栈上开辟空间。当你从 该函数退出时，编译器释放内存。
}

void func() {
    int *x = (int *) malloc(sizeof(int));  
    // 用 malloc()时，它会在堆上请求整数的空间，函数返回这样一个整数的地址 ，然后将其存储在栈中以供程序使用。
}
1
2
3
4
5
6
7
8
9

malloc()调用

请使用以下习惯
用法：malloc(strlen(s) + 1)
因为 int x[10]; printf("%d\n", sizeof(x));``输出 40 显然少了 尾号符\0
:::success
提示：它编译过了或它运行了!=它对了 。 在指责别人之前，先撸起袖子调试一下
:::

free()调用

释放 malloc 分配的空间

calloc()调用

类似 malloc()，返回前会将区域全置 0。

realloc()

创建一个更大的内存区域，并将旧区域拷贝到新区域

常见错误

1. 声明指针，但未分配空间

char *src = "hello"; 

char *dst; // oops! unallocated
//改为 char *dst = (char *) malloc(strlen(src) + 1);

strcpy(dst, src); // segfault and die
1
2
3
4
5
6

2. 分配的空间不够，导致溢出

char *src = "hello";
char *dst = (char *) malloc(strlen(src)); // too small! 
strcpy(dst, src); // work properly
1
2
3

一个宝贵的教训：即使它正确运行过一次，也不意味着它是正确的

3. 分配后未初始化

你正确地调用 malloc()，但忘记在新分配的数据类型中填写一些值。

4. 分配后忘记释放（带 GC的语言可以自动回收内存）
5. 在用完前释放了内存（悬挂指针）
6. 重复释放内存 double free
7. free()调用错误 ， 传入的指针参数错误 。

进程结束时操作系统会回收所有内存，即使不进行 free( )
内存分析工具：purify和valgrind

底层操作系统支持

malloc 和 free 依赖于 brk 系统调用，用于改变程序分断(break)位置：堆结束位置。

(十一) 机制：地址转换

在实现 CPU 虚拟化时，我们遵循的一般准则被称为受限直接访问（Limited Direct Execution，LDE）。

高效、灵活地虚拟化内存。需要一种基于硬件的地址转换（hardware-based address translation），简称为地址转换（address translation）。将指令中的虚拟（virtual）地址转换为数据实际存储的物理（physical）地址。

虚拟地址映射

用户进程在物理内存中并不是从 0 地址开始的

动态（基于硬件）重定位(dynamic relocation)

基址加界限机制（base and bound），有时又称为动态重定位（dynamic relocation）
动态重定位只有很少的硬件参与 ， 一个基址寄存器将虚拟地址 转换为物理地址，一个界限寄存器确保这个地址在进程地址空间的范围内。它们一起提供了既简单又高 效的虚拟内存机制。
进程的虚拟地址都是从 0 开始的
进程中使用的内存引用都是虚拟地址（virtual address），硬件接下来将虚拟地址加上基址寄存器中的内容，得到 物理地址 （physical address），再发给内存系统。
还有个界限寄存器，用于限制进程地址空间范围，进程不能访问为超过该值限制的虚拟地址空间，比如限制 16KB，则不能访问 17KB 的内存，硬件应该阻止转换成物理地址

动态重定位：硬件要求

操作系统的职责

操作系统的问题

• 进程创建时，操作系统从空闲列表（free list）找到位置分配内存空间，并标记为已用
• 进程终止时，操作系统需要回收内存到空闲列表
• 上下文切换时，需要保存/加载基址和界限寄存器。比如放在进程结构或进程控制块 PCB 中。当进程暂停时，操作系统可以切换其地址空间，只要分配新空间，拷贝，然后修改进程结构/PCB 里的基址寄存器就行。
• 操作系统必须提供异常处理程序（exception handler），向硬件注册，当进程出现如越界访问等异常操作时，CPU 会执行这段异常处理程序，如终止该进程。

受限直接执行协议（动态重定位）: （下图 展示了大多数硬件与操作系统的交互）

• 系统调用处理程序
• 时钟处理程序
• 非法内存处理程序
• 非常指令处理程序 | |
  | 开始中断时钟 | | |
  | | 开始时钟，在 xms 后中断 | |
  | 初始化进程表 初始化空闲列表 | | |
  | 操作系统@运行（核心模式） | 硬件 | 程序（用户模式） |
  | 为了启动进程 A：
• 在进程表中分配条目
• 为进程分配内存
• 设置基址/界限寄存器(应该是写入进程结构)
• 从陷阱返回（进入 A） | | |
  | | 恢复 A 的寄存器
  转向用户模式
  跳到 A（最初）的程序计数器 | |
  | | | 进程 A 运行
• 获取指令 |
  | | 转换虚拟地址并执行获取 | |
  | | | 执行指令 |
  | | 如果显式加载/保存
• 确保地址不越界
• 转换虚拟地址并执行
• 加载/保存 | |
  | | | …… |
  | | 时钟中断
  转向内核模式
  跳到中断处理程序 | |
  | 处理陷阱
  调用 switch()例程
• 将寄存器（A）保存到进程结构（A）（包括基址/界限）
• 从进程结构（B）恢复寄存器（B）（包括基址/界限）
  从陷阱返回（进入 B） | | |
  | | 恢复 B 的寄存器
  转向用户模式
  跳到 B 的程序计数器 | |
  | | | 进程 B 运行
• 执行错误的加载 |
  | | 加载越界
  转向内核模式
  跳到陷阱处理程序 | |
  | 处理本期报告
• 决定终止进程 B
• 回收 B 的内存
• 移除 B 在进程表中的条目 | | |

参考

(十二) 分段

结合上一篇文章，堆和栈之间有一大块“空闲”空间，如果没被使用，也占用了物理内存。如果虚拟内存地址空间很大，对物理内存也是极大的浪费，回想一下，进程确实有权力拥有这么大的空间，最大可以拥有最大段大小的地址空间，进程完全可以声明自己需要这么大空间，但可能不会使用 （浪费），操作系统总得给它预留这么多。

分段：泛化的基址/界限

补充：段错误
段错误指的是在支持分段的机器上发生了非法的内存访问。有趣的是，即使在不支持分段的机器上 这个术语依然保留。但如果你弄不清楚为什么代码老是出错，就没那么有趣了

为了降低物理内存浪费，我们对段做细分，原来每个进程对应一个段，现在让每个进程对应三个段，典型的为：代码、栈和堆
之后在 MMU 中给每个逻辑段（segment）引入一对基址和界限寄存器。这样就能分别对这三个段做映射，三个段的顺序和位置完全可以在物理地址空间中随意排列，只要映射到虚拟地址中的位置符合进程结构就行：

如图所示，对比上一篇文章中的只有一个段的情况，只有已用的内存才在物理内存中分配空间，因此可以容纳巨大的地址空间，不过其中还是会包含大量未使用的地址空间（有时又称为稀疏地址空间，sparse address spaces）。
段的访问方式和上篇文章相同，通过基址加偏移的方式:

比如访问 100，是在代码段中，物理地址则是 32KB+100=32868，然后判断是否在界限 32KB+2KB 内，合法时发起对物理地址的访问
比如访问 4200，是在堆段中，先找到相对于堆段起始位置偏移量 4200-4096=104，物理地址是 34KB+104=34920
段错误指的是在支持分段的机器上发生了非法的内存访问。越界访问会造成段异常（segmentation violation）或段错误（segmentation fault）

引用段的方式

• 显式（explicit）方式就是用虚拟地址的开头几位来标识不同的段，如01表示堆，11表示栈，00表示代码段（不过这样10开头的虚拟地址就被浪费了）。

// 获取虚拟地址前两位
Segment = (VirtualAddress & SEG_MASK) >> SEG_SHIFT // 一些宏定义
// 获取虚拟地址偏移量
Offset = VirtualAddress & OFFSET_MASK
// 越界检查，Bounds是表示每段边界信息的数组
if (Offset >= Bounds[Segment])
    RaiseException(PROTECTION_FAULT)
else
    PhysAddr = Base[Segment] + Offset
    Register = AccessMemory(PhysAddr)
1
2
3
4
5
6
7
8
9
10

• 隐式（implicit）方式硬件通过地址从哪里产生来确定段。例如，如果地址由程序计数器产生（即它是指令获取），那么地址在代码段。如果基于栈或基址指针，它一定在栈段。其他地址则在堆段

栈的问题

栈的增长方向和代码及堆相反。
除了基址和界限外，硬件还需要知道段的增长方向（用 一位区分，比如 1 代表自小而大增长，0 反之） 0负 1正

假设要访问虚拟地址 15KB，它应该映射到物理地址 27KB。
该虚拟地址的二进制形式是：11 1100 0000 0000（十六进制0x3C00）。硬件利用前两位（11）来指定段为栈段，但然后我们要处理偏移量 3KB。为了得到正确的反向偏移，我们必须从 3KB 中减去最大的段地址：在这个例子中，段可以是4KB(图上显示是 2KB，假设最大是能到 4KB 的)，因此正确的偏移量是 3KB 减去 4KB，即−1KB. 只要用这个反向偏移量（−1KB）加上基址（28KB），就得到了正确的物理地址27KB。用户可以进行界限检查，确保反向偏移量的绝对值小于段的大小。

支持共享

要节省内存，有时候在地址空间之间共享（share）某些内存段是有用的
1111块内存，但操作系统秘密地共享了内存，进程不能修改这些内存，所以假象得以保持
比如同一份二进制文件运行多个进程,可以共享代码段

图中代码段的权限是可读和可执行，因此物理内存中的一个段可以映射到多个虚拟地址空间。
有了保护位，前面描述的硬件算法也必须改变。除了检查虚拟地址是否越界，硬件还需要检查特定访问是否允许。如果用户进程试图写入只读段，或从非执行段执行指令，硬件会触发异常，让操作系统来处理出错进程。

分段的颗粒度

粗粒度 ： 比如只分成三个段，代码、栈、堆
细粒度 ：将段进一步细分。操作系统可以更好地了解哪些段在使用哪些没有，从而可以更高效地利用内存。这需要进一步的硬件支持，如段表，在段表内能保存成千上万段。

操作系统的问题

上下文切换

由于每个进程拥有独立的虚拟地址空间，上下文切换时，段寄存器需要保存和恢复到进程结构中

内存碎片

对段的细分带了了好处：栈和堆之间没有使用的区域就不需要再分配物理内存
但细分后会产生物理内存上的外部碎片（external fragmentation），细小的碎片很难分配给新的段，如左图：

解决方案：

• 紧凑（compact）物理内存，重新安排原有的段操作系统先终止运行的进程，将它们的数据复制到连续的内存区域中去，改变它们的段寄存器中的值，指向新的物理地址，从而得到了足够大的连续空闲空间
• 空闲列表管理算法(碎片处理)试图保留大的内存块用于分配。相关的算法可能有成百上千种，包括传统的最优匹配（best-fit，从空闲链表中找最接近需要分配空间的空闲块返回）、最坏匹配（worst-fit）、首次匹配（first-fit）以及像伙伴算法（buddy algorithm）这样更复杂的算法

(十四) 分页：介绍

一个简单例子

在这个例子中，有 8 个页帧（由 128 字节物理内存构成，也是极小的）

为了记录地址空间的每个虚拟页放在物理内存中的位置，操作系统通常为每个进程保存一个数据结构，称为页表（page table）。页表的主要作用是为地址空间的每个虚拟页面保存地址转换（address translation）
为了转换（translate）该过程生成的虚拟地址，我们必须首先将它分成两个组件：虚拟页面号（virtual page number，VPN）和页内的偏移量（offset）。

检索页表，找到虚拟页 1 所在的物理页面, 物理帧号（PFN）（有时也称为物理页号，physical page number 或 PPN）是7（二进制 111）,最终物理地址是 1110101。

为什么是 7 可以看上图的 18.1 和 18.2

页表存在哪里

一般放在内存中

列表中究竟有什么

最简单的形式称为线性页表（linear page table），就是一个数组。操作系统通过虚拟页号（VPN）检索该数组，并在该索引处查找页表项（PTE），以便找到期望的物理帧号（PFN）。

• PTE 的内容:
  • 有效位（valid bit）特定地址转换是否有效,例如，当一个程序开始运行时，它的代码和堆在其地址空间的一端，栈在另一端。所有未使用的中间空间都将被标记为无效（invalid），如果进程尝试访问这种内存，就会陷入操作系统，可能会导致该进程终止。因此，有效位对于支持稀疏地址空间至关重要。通过简单地将地址空间中所有未使用的页面标记为无效，我们不再需要为这些页面分配物理帧，从而节省大量内存。
  • 保护位（protection bit）表明页是否可以读取、写入或执行
  • 存在位（present bit）表示该页是在物理存储器还是在磁盘上（即它已被换出，swapped out）
  • 脏位（dirty bit）表明页面被带入内存后是否被修改过
• 图 18.5 显示了来自 x86 架构的示例页表项[I09]。它包含一个存在位（P），确定是否允许写入该页面的读/写位（R/W） 确定用户模式进程是否可以访问该页面的用户/超级用户位（U/S），有几位（PWT、PCD、PAT 和 G）确定硬件缓存如何为这些页面工作，一个访问位（A）和一个脏位（D），最后是页帧号（PFN）本身。

分页消耗

假设一个页表基址寄存器（page-table base register）包含页表的起始位置的物理地址。

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
PTEAddr = PageTableBaseRegister + (VPN * sizeof(PTE))
1
2

VPN MASK将被设置为 0x30（十六进制 30，或二进制 110000），它从完整的虚拟地址中挑选出 VPN 位；SHIFT 设置为 4（偏移量的位数），这样我们就可以将 VPN 位向右移动以形成正确的整数虚拟页码。例如，使用虚拟地址 21（010101），掩码将此值转换为 010000，移位将它变成 01，或虚拟页 1，正是我们期望的值。然后，我们使用该值作为页表基址寄存器指向的 PTE 数组的索引。

offset = VirtualAddress & OFFSET_MASK
PhysAddr = (PFN << SHIFT) | offset
// Extract the VPN from the virtual address
VPN = (VirtualAddress & VPN_MASK) >> SHIFT
// Form the address of the page-table entry (PTE)
PTEAddr = PTBR + (VPN * sizeof(PTE))
// Fetch the PTE
PTE = AccessMemory(PTEAddr)
// Check if process can access the page
if (PTE.Valid == False)
  RaiseException(SEGMENTATION_FAULT)
else if (CanAccess(PTE.ProtectBits) == False)
  RaiseException(PROTECTION_FAULT)
else
  // Access is OK: form physical address and fetch it
  offset = VirtualAddress & OFFSET_MASK
  PhysAddr = (PTE.PFN << PFN_SHIFT) | offset
  Register = AccessMemory(PhysAddr)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

内存追踪

一段循环赋值 c 代码：

int array[1000];
...
for (i = 0; i < 1000; i++)
  array[i] = 0;
1
2
3
4

编译：

prompt> gcc -o array array.c -Wall -O
prompt> ./array
1
2

反编译后的汇编：

0x1024 movl $0x0,(%edi,%eax,4)
0x1028 incl %eax
0x102c cmpl $0x03e8,%eax
0x1030 jne 0x1024
1
2
3
4

第一条指令将零值（显示为$0x0）移动到数组位置的虚拟内存地址，这个地址是通过取%edi的内容并将其 加上%eax乘以4 来计算的。%edi 保存数组的基址，而%eax 保存数组索引（i）。(array[i]=0)
第二条指令增加保存在%eax中的数组索引(i++)
第三条指令将该寄存器的内容与十六进制值 0x03e8 或十进制数 1000 进行比较(i<1000)。如果比较结果显示两个值不相等（这就是 jne 指令测试）第四条指令跳回到循环的顶部。
假设一个大小为 64KB 的虚拟地址空间。我们还假定页面大小为 1KB。

• 页表：物理地址 1KB(1024)
• 代码段：虚拟地址 1KB,大小 1KB,VPN=1,映射到物理页 4(VPN 1->PFN 4)
• 数组：4000 字节（1000X4)，int占4字节,我们假设它驻留在虚拟地址 40000 到 44000（不包括最后一个字节）。(VPN 39 → PFN 7), (VPN 40 → PFN 8), (VPN 41 → PFN 9), (VPN 42 → PFN 10)

当它运行时，每个指令将产生两个内存引用：一个访问页表以查找指令所在的物理框架，另一个访问指令本身将其提取到 CPU 进行处理
另外，在 mov 指令的形式中，有一个显式的内存引用，这会首先增加另一个页表访问（将数组虚拟地址转换为正确的物理地址），然后时数组访问本身。
图 18.7 展示了前 5 次循环迭代的整个过程。左边虚拟地址和右边实际物理地址。

1. 访问页表取物理地址，1024 是指令所在内存对应的页表，1174 是数组所在内存对应的页表
2. 访问数组内存
3. 访问代码段内存取指令

小结

分页（paging）不会导致外部碎片，因为分页（按设计）将内存划分为固定大小的单元。其次，它非常灵活，支持稀疏虚拟地址空间
会导致较慢的机器（有许多额外的内存访问来访问页表）和内存浪费（内存被页表塞满而不是有用的应用程序数据）。

(十五) 分页：快速地址转换（TLB）

对每次内存访问，硬件先检查 TLB (translation-lookaside-buffer)，看看其中是否有期望的转换映射，如果有，就完成转换（很快），不用访问页表 （其中有全部的转换映射）。因此，更好的名称应该是地址转换缓存（address-translation cache）。

TLB 的基本算法

TLB 命中（TLB hit）,直接取

VPN = (VirtualAddress & VPN_MASK) >> SHIFT # 计算虚拟页号
(Success, TlbEntry) = TLB_Lookup(VPN) # 在TLB中查找虚拟页号
if (Success == True) # TLB命中
    if (CanAccess(TlbEntry.ProtectBits) == True)  # 如果有访问权限
        Offset = VirtualAddress & OFFSET_MASK # 计算偏移量
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset # 计算物理地址
        AccessMemory(PhysAddr) # 访问物理内存
    else:
        RaiseException(PROTECTION_FAULT) # 如果没有访问权限，抛出保护错误异常
else: #TLB未命中
    PTEAddr = PTBR + (VPN * sizeof(PTE))  # 计算页表项地址
    PTE = AccessMemory(PTEAddr) # 访问页表项
if (PTE.Valid == False):
    RaiseException(SEGMENTATION_FAULT) # 如果页表项无效，抛出段错误异常
else if (CanAccess(PTE.ProtectBits) == False): 
    RaiseException(PROTECTION_FAULT) # 如果没有访问权限，抛出保护错误异常
else:
    TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits) # 将页表项插入TLB
    RetryInstruction()  # 重试指令
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

TLB 未命中，硬件访问页表来寻找转换映射，并用该转换映射更新 TLB，当 TLB 更新成功后，系统会重新尝试该指令

示例：访问数组

访问 a[1]后，TLB 有了 VPN=06 的映射，下次访问 a[2]或 a[0]也能 TLB 命中.
硬件缓存背后的思想是利用指令和数据引用的局部性（locality）。通常有两种局部性：时间局部性（temporal locality）和空间局部性（spatial locality）。时间局部性是指，最近访问过的指令或数据项可能很快会再次访问。空间局部性是指，当程序访问内存地址 x时，可能很快会访问邻近 x 的内存。

谁来处理 TLB 未命中

# 计算虚拟页号
VPN = (VirtualAddress & VPN_MASK) >> SHIFT 

# 在TLB中查找虚拟页号
(Success, TlbEntry) = TLB_Lookup(VPN)

if (Success == True): 
    # TLB命中
    if (CanAccess(TlbEntry.ProtectBits) == True): 
        # 如果有访问权限
        Offset = VirtualAddress & OFFSET_MASK # 计算偏移量
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset # 计算物理地址
        Register = AccessMemory(PhysAddr) # 访问物理内存
    else:
        # 如果没有访问权限，抛出保护错误异常
        RaiseException(PROTECTION_FAULT)
else: 
    # TLB未命中，抛出TLB未命中异常
    RaiseException(TLB_MISS)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 硬件：发生未命中时， 硬件会“遍历”页表，找到正确的页表项，取出想要的转换映射，用它更新 TLB，并重试该指令一个例子是 x86 架构，它采用固定的多级页表（multi-level page table）
• 软件：精简指令集计算机上。发生 TLB未命中时，硬件系统会抛出一个异常（见图 19.3 第 11 行），这会暂停当前的指令流，将特权级提升至内核模式，跳转至陷阱处理程序（trap handler）。接下来你可能已经猜到了，这个陷阱处理程序是操作系统的一段代码，用于处理 TLB 未命中。这段代码在运行时，会查找页表中的转换映射，然后用特别的“特权”指令更新 TLB，并从陷阱返回。此时，硬件会重试该指令（导致 TLB 命中）。可能导致无限递归，比如陷阱处理程序中也有未命中的。可以把 TLB 未命中陷阱处理程序直接放到物理内存中 [它们没有映射过（unmapped），不用经过地址转换]。或者在 TLB 中保留一些项，记录永久有效的地址转换，并将其中一些永久地址转换槽块留给处理代码本身，这些被监听的（wired）地址转换总是会命中 TLB。

TLB 的内容

VPN和PFN是虚拟内存管理中的两个重要概念：

• VPN（Virtual Page Number）：虚拟页号。在虚拟内存系统中，内存被划分为固定大小的单元，称为页。每个页在虚拟内存空间中都有一个唯一的标识符，这就是虚拟页号。
• PFN（Page Frame Number）：页帧号。在物理内存中，内存也被划分为与虚拟内存页相同大小的单元，称为页帧。每个页帧在物理内存中都有一个唯一的标识符，这就是页帧号。

VPN ｜ PFN ｜ 其他位
VPN和PFN同时存在于TLB中，因为一条地址映射可能出现在任意位置（用硬件的术语，TLB 被称为全相联的（fully-associative）缓存）。硬件并行地查找这些项，看看是否有匹配。
其他位:TLB 通常有一个有效（valid）位，用来标识该项是不是有效地转换映射。通常还有一些保护（protection）位，用来标识该页是否有访问权限。例如，代码页被标识为可读和可执行，而堆的页被标识为可读和可写。还有其他一些位，包括地址空间标识符（address-space identifier）、脏位（dirty bit）等。

上下文切换时对 TLB 的处理

TLB 中包含的虚拟到物理的地址映射只对当前进程有效，对其他进程是没有意义的。
一些系统增加了硬件支持，实现跨上下文切换的 TLB 共享。比如有的系统在 TLB 中添加了一个地址空间标识符（Address Space Identifier，ASID）。可以把 ASID 看作是进程标识符（Process Identifier，PID），但通常比 PID 位数少（PID 一般 32 位， ASID 一般是 8 位）。

ASID 标识不同进程，可以存在相同的 VPN。
操作系统在上下文切换时，必须将某个特权寄存器设置为当前进程的 ASID。

上图表示两个进程共享同一物理页（例如代码段的页），因为是只读和执行的，可以共享，比如代码段存放的内存。

TLB 替换策略

• 最少使用（least-recently-used，LRU）
• 随机（random）策略

随机（random）策略可以避免极端情况，如一个程序循环访问 n+1 个页，但 TLB 大小只能存放 n 个页，每次访问内存都会触发 TLB 未命中

实际系统的 TLB 表项

这个例子来自 MIPS R4000[H93]，它是一种现代的系统，采用软件管理 TLB。

MIPS R4000 支持 32 位的地址空间，页大小为 4KB。所以在典型的虚拟地址中，预期会看到 20 位的 VPN和 12 位的偏移量。但是，你可以在 TLB 中看到，只有 19 位的 VPN。事实上，用户地址只占地址空间的一半（剩下的留给内核），所以只需要 19 位的 VPN。VPN 转换成最大 24 位的物理帧号（PFN），因此可以支持最多有 64GB 物理内存（224 个 4KB内 存页）的系统。
3 个一致性位（Coherence，C），决定硬件如何缓存该页（其中一位超出了本书的范围）；脏位（dirty， D），表示该页是否被写入新数据（后面会介绍用法）；有效位（valid, V），告诉硬件该项的地址映射是否有效。还有没在图 19.4 中展示的页掩码（page mask）字段，用来支持不同的页大小。
MIPS 的 TLB 通常有 32 项或 64 项，大多数提供给用户进程使用，也有一小部分留给操作系统使用。操作系统可以设置一个被监听的寄存器，告诉硬件需要为自己预留多少 TLB 槽。这些保留的转换映射，被操作系统用于关键时候它要使用的代码和数据，在这些时候，TLB 未命中可能会导致问题（例如，在 TLB 未命中处理程序中）。
由于 MIPS 的 TLB 是软件管理的，所以系统需要提供一些更新 TLB 的指令。MIPS 提供了 4 个这样的指令：

• TLBP，用来查找指定的转换映射是否在 TLB 中；
• TLBR，用来将 TLB 中的内容读取到指定寄存器中；
• TLBWI，用来替换指定的 TLB 项；
• TLBWR，用来随机替换一个 TLB 项。操作系统可以用这些指令管理 TLB 的内容。

当然这些指令是特权指令

小结

如果一个程序短时间内访问的页数超过了 TLB 中的页数，就会产生大量的 TLB 未命中，运行速度就会变慢。这种现象被称为超出 TLB 覆盖范围（TLB coverage）。可以用更大的页来缩小页的数量，增加命中率
访问 TLB 很容易成为 CPU 流水线的瓶颈，尤其是有所谓的物理地址索引缓存（physically-indexed cache）,这是 CPU 内部的缓存。有了这种缓存，地址转换必须发生在访问该缓存之前，这会让操作变慢。虚拟地址索引缓存（virtually-indexed cache）解决了一些性能问题，但也为硬件设计带来了新问题。
物理地址索引缓存详见Physically indexed, physically tagged (PIPT) caches

(十六) 分页：较小的表

假设一个 32 位地址空间（232 字节）， 4KB（212 字节）的页和一个 4 字节的页表项。一个地址空间中大约有一百万个虚拟页面（232/212）。乘以页表项的大小，你会发现页表大小为4MB。回想一下：通常系统中的每个进程都有一个页表！有一百个活动进程（在现代系统中并不罕见），就要为页表分配数百兆的内存！

简单的解决方案：更大的页

• 减小页表大学 : 使用更大的页

以 32 位地址空间为例，但这次假设用 16KB 的页。因此，会有 18 位的 VPN 加上 14 位的偏移量。假设每个页表项（4 字节）的大小相同，现在线性页表中有 218 个项，因此每个页表的总大小为 1MB，页表缩到四分之一。

补充：多种页大小
另外请注意，许多体系结构（例如 MIPS、SPARC、x86-64）现在都支持多种页大小。通常使用一个小的（4KB 或 8KB）页大小。但是，如果一个“聪明的”应用程序请求它，则可以为地址空间的特定部分使用一个大型页（例如，大小为 4MB），从而让这些应用程序可以将常用的（大型的）数据结构放入这样的空间，同时只占用一个 TLB 项。这种类型的大页在数据库管理系统和其他高端商业应用程序中很常见。然而，多种页面大小的主要原因并不是为了节省页表空间。这是为了减少 TLB 的压力，让程序能够访问更多的地址空间而不会遭受太多的 TLB 未命中之苦。然而，正如研究人员已经说明[N+02]一样，采用多种页大小，使操作系统虚拟内存管理程序显得更复杂，因此，有时只需向应用程序暴露一个新接口，让它们直接请求大内存页，这样最容易。

这种方法的主要问题在于，大内存页会导致每页内的浪费，这被称为内部碎片（internal fragmentation）问题（因为浪费在分配单元内部）。

混合方法：分页和分段

一个进程只使用了部分页，大部分页表都没有使用，充满了无效的（invalid）项。浪费了页表空间

（十二）分段 ，有一个基址（base）寄存器，告诉我们每个段在物理内存中的位置，还有一个界限（bound）或限制（limit）寄存器，告诉我们该段的大小。
基址不是指向段本身，而是保存该段的页表的物理地址。界限寄存器用于指示页表的结尾（即它有多少有效页）。
假设 32 位虚拟地址空间包含 4KB 页面，并且地址空间分为 4 个段。在这个例子中，我们只使用 3 个段：一个用于代码，另一个用于堆，还有 一个用于栈。
用地址空间的前两位确定地址引用哪个段,假设 00 是未使用的段，01 是代码段，10 是堆段，11 是栈段。因此，虚拟地址如下所示：

在硬件中，假设有 3个基本/界限对，代码、堆和栈各一个。当进程正在运行时，每个段的基址寄存器都包含该段的线性页表的物理地址。因此，系统中的每个进程现在都有 3 个与其关联的页表。在上下文切换时，必须更改这些寄存器，以反映新运行进程的页表的位置。
在 TLB 未命中时（假设硬件管理的 TLB，即硬件负责处理 TLB 未命中），硬件使用分段位（SN）来确定要用哪个基址和界限对。从基址寄存器找到页表的起始物理地址，再加上 VPN*sizeof(PTE)就是页表项(PTE)的地址，判断是否超过界限寄存器规定的界限，然后从页表项找到对应页的物理地址。(页表项就是页表线性数组中的一条记录)

| ```python
// 使用 SEG_MASK 位掩码从 VirtualAddress 提取段号（SN），然后右移 SN_SHIFT 位来获取实际的段号
SN = (VirtualAddress & SEG_MASK) >> SN_SHIFT

// 使用 VPN_MASK 位掩码从 VirtualAddress 提取虚拟页号（VPN），然后右移 VPN_SHIFT 位来获取实际的虚拟页号
VPN = (VirtualAddress & VPN_MASK) >> VPN_SHIFT

// 计算页表条目（PTE）的地址。通过基址（Base[SN]，其中 SN 是上面计算得到的段号）加上偏移量（VPN * sizeof(PTE)），我们可以找到虚拟地址对应的 PTE
AddressOfPTE = Base[SN] + (VPN * sizeof(PTE))

 |
| --- |

栈和堆之间未分配的页不再占用页表中的空间（仅将其标记为无效）。(就是分段的特性)
当然分段有的缺点不可避免，如果有一个大而稀疏的堆(堆的基址只有一个，堆内部空间的浪费避免不了)，仍然可能导致大量的页表浪费，同时外部碎片再次出现 。 
## 多级页表
如何去掉页表中的所有无效区域，而不是将它们全部保留在内存中？
将线性页表变成树的形式。我们将这种方法称为`多级页表（multi-level page table）`
[![image.png](https://cdn.nlark.com/yuque/0/2023/png/26665379/1697282663576-453a9810-5fe3-4cd2-89e3-368087f0c80b.png#averageHue=%23222021&clientId=ueafaf582-c4c8-4&from=paste&id=ibMnw&originHeight=576&originWidth=1048&originalType=url&ratio=2&rotation=0&showTitle=false&size=260963&status=done&style=none&taskId=u86fd55c3-a79a-4f47-bde1-6e348e3da44&title=)](https://hjk.life/assets/img/2022-06-13-operating-systems-16/F20.2.jpg)
上图中左边为线性页表，页表位于物理内存的`201`页，由于线性页表使用索引进行查询，所以注定其必须为未使用的页也分配索引(线性索引必须连续)，导致无效信息太多，占用空间大。
上图右边为多级页表，页目录位于物理内存的`200`页，假设页目录中一个页能存`4`个页目录项（`Page Directory Entries，PDE`）（当然实际上一个页有`4KB`，能存`1024个4字节`的`PDE`）。`PDE`也有有效位，表示其管理的PTE至少有一个有效，此时一个`PDE`指向一个页，假设该页包括`4个PTE`；否则`PDE`不指向任何页。
多级页表支持稀疏空间，因为对于没有使用的页一般不分配页表。同时除了页目录需要连续外，页表存放不需要连续，通过`PDE`指向的方式，让我们能够将页表页分散的放在物理内存的任何地方。
在本例中，还有问题，如何定位`PDE`，需要用到虚拟地址 `VPN` 中的开头页目录索引
[![image.png](https://cdn.nlark.com/yuque/0/2023/png/26665379/1697282663436-6884acb9-d2ff-4e9f-aa41-27d235a1f625.png#averageHue=%23211f20&clientId=ueafaf582-c4c8-4&from=paste&id=u63923198&originHeight=141&originWidth=542&originalType=url&ratio=2&rotation=0&showTitle=false&size=44875&status=done&style=none&taskId=u60060199-1709-4b68-abe8-6d5a36e986c&title=)](https://hjk.life/assets/img/2022-06-13-operating-systems-16/F2.jpg)
PDEAddr = PageDirBase +（PDIndex×sizeof（PDE））
(上述表达式也能看出稀疏也是有限制的，至少被页目录索引 PageDirBase 限制了范围)
当然比二级更多层级的页表也是允许的
多级页表是有成本的。在 `TLB` 未命中时，需要从内存加载两次，才能从页表中获取正确的地址转换信息（一次用于页目录，另一次用于 `PTE` 本身），而用线性页表只需要一次加载。因此，多级表是一个时间—空间折中（`time-space trade-off`）的小例子。
另一个明显的缺点是复杂性。无论是硬件还是操作系统来处理页表查找（在 `TLB` 未命中时），这样做无疑都比简单的线性页表查找更复杂。
## 反向页表
反向页表（`inverted page table`）
整个系统只有一个页表，其中的项代表系统的每个物理页，而不是有许多页表（系统的每个进程一个）。	
页表项告诉我们哪个进程正在使用此页，以及该进程的哪个虚拟页映射射物理页。通常在此基础结构上建立散列表，以加速查找。
## 将页表交换到磁盘
一些系统将这样的 页表放入内核虚拟内存（`kernel virtual memory`），从而允许系统在内存压力较大时，将这些页表中的一部分交换（`swap`）到磁盘。
## 小结
在一个内存受限的系统中（像很多旧系统一样），小结构是有意义的。在具有较多内存， 并且工作负载主动使用大量内存页的系统中，用更大的页表来加速 `TLB` 未命中处理，可能是正确的选择。


# (十七) 超越物理内存：机制
## 交换空间
在硬盘上开辟一部分空间用于物理页的移入和移出。一般这样的空间称为交换空间（`swap space`）。
交换空间的作用： 决定系统在某一时刻能够使用的最大内存	
[![image.png](https://cdn.nlark.com/yuque/0/2023/png/26665379/1697356646113-7bdd1027-bd13-48b8-b628-3fd596439670.png#averageHue=%231e1e20&clientId=u8d916fa2-ea66-4&from=paste&id=UHph4&originHeight=276&originWidth=724&originalType=url&ratio=2&rotation=0&showTitle=false&size=137237&status=done&style=none&taskId=u399c9817-8411-42bb-b7f0-9fd2e3fcdde&title=)](https://hjk.life/assets/img/2022-06-14-operating-systems-17/F21.1.jpg)
## 存在位
当硬件在 `PTE` 中查找时，可能发现页不在物理内存中。硬件（或操作系统，在软件管理 `TLB` 时）判断是否在内存中的方法，是通过页表项中的一条新信息，即存在位（`present bit`）。如果存在位设置为` 1`，则表示该页存在于物理内存中，并且所有内容都如上所述进行。如果存在位设置为0，则页不在内存中，而在硬盘上。访问不在物理内存中的页，这种行为通常被称为页错误（`page fault`）。
在页错误时，硬件自己无法处理，操作系统被唤起来处理页错误。一段称为“页错误处理程序（`page-fault handler`）”的代码会执行，来处理页错误。
## 页错误
在 `TLB` 未命中的情况下，我们有两种类型的系统：硬件管理的 `TLB`（硬件在页表中找到需要的转换映射）和软件管理的 `TLB`（操作系统执行查找过程）。不论在哪种系统中，如果页不存在，都由操作系统负责处理页错误。操作系统的页错误处理程序（`page-fault handler`）确定要做什么。
补充：为什么硬件不能处理页错误
我们从`TLB` 的经验中得知，硬件设计者不愿意信任操作系统做所有事情。那么为什么他们相信操作系统来处理页错误呢？有几个主要原因。首先，页错误导致的硬盘操作很慢。即使操作系统需要很长时间来处理故障，执行大量的指令，但相比于硬盘操作，这些额外开销是很小的。其次，为了能够处理页故障，硬件必须了解交换空间，如何向硬盘发起 `I/O` 操作，以及很多它当前所不知道的细节。因此，由于性能和简单的原因，操作系统来处理页错误，即使硬件人员也很开心
操作系统可以用 `PTE` 中的某些位来存储硬盘地址，这些位通常用来存储像页的 `PFN` 这样的数据。当操作系统接收到页错误时，它会在 PTE 中查找地址，并将请求发送到硬盘，将页读取到内存中。
当硬盘 `I/O` 完成时，操作系统会更新页表，将此页标记为存在，更新页表项（`PTE`）的 `PFN` 字段以记录新获取页的内存位置，并重试指令。下一次重新访问 `TLB` 还是未命中，然而这次因为页在内存中，因此会将页表中的地址更新到 `TLB` 中（也可以在处理页错误时更新 `TLB` 以避免此步骤）。最后的重试操作会在 `TLB` 中找到转换映射，从已转换的内存物理地址，获取所需的数据或指令。
请注意，当 `I/O` 在运行时，进程将处于阻塞（`blocked`）状态。因此，当页错误正常处理时，操作系统可以自由地运行其他可执行的进程。因为`I/O` 操作是昂贵的，一个进程进行 `I/O`（页错误）时会执行另一个进程，这种交叠（`overlap`）是多道程序系统充分利用硬件的一种方式。
## 内存满了怎么办
页交换策略（`page-replacement policy`）： 从硬盘中换入（`page in`），换出（`page out`）  有性能损失【看下一节 】
## 页错误处理流程
页错误控制流算法（硬件）:
```cpp
VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)
if (Success == True) // TLB Hit
    if (CanAccess(TlbEntry.ProtectBits) == True)
        Offset = VirtualAddress & OFFSET_MASK
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
        Register = AccessMemory(PhysAddr)
    else
        RaiseException(PROTECTION_FAULT)
else // TLB Miss
    PTEAddr = PTBR + (VPN * sizeof(PTE))
    PTE = AccessMemory(PTEAddr)
    if (PTE.Valid == False)
        RaiseException(SEGMENTATION_FAULT) // 不合法，超界限，段错误
    else
        if (CanAccess(PTE.ProtectBits) == False)
            RaiseException(PROTECTION_FAULT) // 无权限错误
        else if (PTE.Present == True)
            // assuming hardware-managed TLB
            TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits) // 在物理内存，插入TLB
            RetryInstruction()
        else if (PTE.Present == False)
            RaiseException(PAGE_FAULT) // 不在物理内存，页错误
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

页错误处理算法（软件）:

PFN = FindFreePhysicalPage() // 找用于换入的物理内存页
if (PFN == -1)              // no free page found
    PFN = EvictPage()       // run replacement algorithm
DiskRead(PTE.DiskAddr, pfn) // sleep (waiting for I/O)
PTE.present = True          // update page table with present
PTE.PFN = PFN               // bit and translation (PFN)
RetryInstruction()          // retry instruction，重试后TLB还是未命中的，需要再做插入TLB操作
1
2
3
4
5
6
7

交换何时真正发生

为了保证有少量的空闲内存，大多数操作系统会设置高水位线（High Watermark，HW）和低水位线（Low Watermark，LW），来帮助决定何时从内存中清除页。当操作系统发现有少于 LW 个页可用时，后台负责释放内存的线程会开始运行，直到有 HW 个可用的物理页。这个后台线程有时称为交换守护进程（swap daemon）或页守护进程（page daemon）

小结

在页表结构中需要添加额外信息，比如增加一个存在位（present bit，或者其他类似机制），告诉我们页是不是在内存中。如果不存在，则操作系统页错误处理程序（page-fault handler）会运行以处理页错误（page fault），从而将需要的页从硬盘读取到内存，可能还需要先换出内存中的一些页，为即将换入的页腾出空间。

(十八) 超越物理内存：策略

由于内存压力（memory pressure）迫使操作系统换出（paging out）一些页，为常用的页腾出空间。确定要踢出（evict）哪个页（或哪些页）封装在操作系统的替换策略（replacement policy）中。
这章讲的是 cache，就是加速硬盘读取，以页为单位，在内存中创建硬盘页的缓存

缓存管理

最优替换策略

最优（optimal）策略:
替换内存中在最远将来才会被访问到的页，可以达到缓存未命中率最低。
提示：与最优策略对比非常有用
用于自己实现的算法的评估依据。 虽然最优策略非常不切实际，但作为仿真或其他研究的比较者还是非常有用的。比如，单说你喜欢的新算法有 80% 的命中率是没有意义的，但加上最优算法只有82% 的命中率（因此你的新方法非常接近最优），就会使得结果很有意义，并给出了它的上下文。因此，在你进行的任何研究中，知道最优策略可以方便进行对比，知道你的策略有多大的改进空间，也用于决定当策略已经非常接近最优策略时，停止做无谓的优化[AD03]。
遗憾的是，正如我们之前在开发调度策略时所看到的那样，未来的访问是无法知道的，你无法为通用操作系统实现最优策略。在开发一个真正的、可实现的策略时，我们将聚焦于寻找其他决定把哪个页面踢出的方法。因此，最优策略只能作为比较，知道我们的策略有多接近“完美”。

简单策略：FIFO

页在进入系统时，简单地放入一个队列。当发生替换时，队列尾部的页（“先入”页）被踢出。
先进先出（FIFO）根本无法确定页的重要性：即使页 0 已被多次访问，FIFO 仍然会将其踢出，因为它是第一个进入内存的

另一简单策略：随机

在内存满的时候它随机选择一个页进行替换。
有些时候（仅仅 40%的概率），随机和最优策略一样好，有时候情况会更糟糕，随机策略取决于当时的运气。

利用历史数据：LRU

如果某个程序在过去访问过某个页，则很有可能在不久的将来会再次访问该页
页替换策略可以使用的一个历史信息是频率（frequency）。如果一个页被访问了很多次，也许它不应该被替换，因为它显然更有价值。页更常用的属性是访问的近期性（recency），越近被访问过的页，也许再次访问的可能性也就越大。
这一系列的策略是基于人们所说的局部性原则（principle of locality）
补充：局部性类型
程序倾向于表现出两种类型的局部。第一种是空间局部性（spatial locality），它指出如果页 P 被访问，可能围绕它的页（比如 P−1 或 P + 1）也会被访问。第二种是时间局部性（temporal locality），它指出近期访问过的页面很可能在不久的将来再次访问。假设存在这些类型的局部性，对硬件系统的缓存层次结构起着重要作用，硬件系统部署了许多级别的指令、数据和地址转换缓存，以便在存在此类局部性时，能帮助程序快速运行。
当然，通常所说的局部性原则（principle of locality）并不是硬性规定，所有的程序都必须遵守。事实上，一些程序以相当随机的方式访问内存（或磁盘），并且在其访问序列中不显示太多或完全没有局部性。因此，尽管在设计任何类型的缓存（硬件或软件）时，局部性都是一件好事，但它并不能保证成功。相反，它是一种经常证明在计算机系统设计中有用的启发式方法
基于局部性原则，有两种替换策略。“最不经常使用”（Least-Frequently-Used，LFU）策略会替换最不经常使用的页。同样，“最近最少使用”（Least-Recently-Used，LRU） 策略替换最近最少使用的页面。

工作负载示例

当工作负载不存在局部性时，使用的策略 区别不大。LRU、FIFO 和随机都执行相同的操作，命中率完全由缓存的大小决定。

“80—20”负载场景，它表现出局部性：80%的引用是访问 20%的页（“热门”页）。剩下的 20%是对剩余的 80%的页（“冷门”页）访问。

“循环顺序”工作负载，其中依次引用 50 个页，从 0 开始，然后是 1，…，49，然后循环，重复访问。展示了 LRU 或者 FIFO 的最差情况。

实现基于历史信息的算法

如何找到最近最少使用的页，也就是找到更新时间最久的页
硬件可以在每个页访问时更新内存中的时间字段（时间字段可以在每个进程的页表中，或者在内存的某个单独的数组中，每个物理页有一个）。因此，当页被访问时，时间字段将被硬件设置为当前时间。 然后，在需要替换页时，操作系统可以简单地扫描系统中所有页的时间字段以找到最近最少使用的页。
遗憾的是，随着系统中页数量的增长，扫描所有页的时间字段只是为了找到最精确最少使用的页，这个代价太昂贵。

近似 LRU

需要硬件增加一个使用位（use bit，有时称为引用位，reference bit）,系统的每个页有一个使用位，然后这些使用位存储在某个地方（例如，它们可能在每个进程的页表中，或者只在某个数组中）。每当页被引用（即读或写）时，硬件将使用位设置为 1。但是，硬件不会清除该位（即将其设置为 0），这由操作系统负责。
Corbato 的时钟算法：
时钟指针（clock hand）开始时指向随便某个特定的页（哪个页不重要）。当必须进行页替换时，操作系统检查当前指向的页 P 的使用位是 1 还是 0。如果是 1，则意味着页面 P最近被使用，因此不适合被替换。然后，P 的使用位设置为0，时钟指针递增到下一页（P + 1）。该算法一直持续到找到一个使用位为 0 的页，使用位为 0 意味着这个页最近没有被使用过（在最坏的情况下，所有的页都已经被使用了，那么就将所有页的使用位都设置为0）。
这个算法有个问题，就是查找次数不稳定，如果是随机扫描而不是指针递增就好很多

考虑脏页

这章讲的其实不是 swap，而是cache，就是加速硬盘读取，以页为单位，在内存中创建硬盘页的缓存
如果页已被修改（modified）并因此变脏（dirty），则踢出它就必须将它写回磁盘，这很昂贵。如果它没有被修改（因此是干净的，clean），踢出就没成本。物理帧可以简单地重用于其他目的而无须额外的 I/O。因此，一些虚拟机系统更倾向于踢出干净页，而不是脏页。
为了支持这种行为，硬件应该包括一个修改位（modified bit，又名脏位，dirty bit）。每次写入页时都会设置此位，因此可以将其合并到页面替换算法中。例如，时钟算法可以被改变，以扫描既未使用又干净的页先踢出。无法找到这种页时，再查找脏的未使用页面，等等。

其他虚拟内存策略

操作系统还必须决定何时将页载入内存。
操作系统可能会猜测一个页面即将被使用，从而提前载入。这种行为被称为预取（prefetching），只有在有合理的成功机会时才应该这样做。例如，一些系统将假设如果代码页 P 被载入内存，那么代码页 P + 1 很可能很快被访问，因此也应该被载入内存。
这种行为通常称为聚集（clustering）写入，或者就是分组写入（grouping），这样做有效是因为硬盘驱动器的性质，执行单次大的写操作，比许多小的写操作更有效。

抖动

当内存就是被超额请求时，这组正在运行的进程的内存需求是否超出了可用物理内存？系统将不断地进行换页，这种情况有时被称为抖动（thrashing）
当内存超额请求时，某些版本的 Linux 会运行“内存不足的杀手程序（out-of-memory killer）”。这个守护进程选择一个内存密集型进程并杀死它，从而以不怎么委婉的方式减少内存。

小结

终极解决方案：加内存

（十九）VAX/VMS虚拟内存系统

只讲重点，直接看原文就行

分段的 FIFO

防止有“自私贪婪的内存”（memory hog）—— 一些程序占用大量内存， 使其他程序难以运行。
每个进程都有一个可以保存在内存中的最大页数，称为驻留集大小（Resident Set Size，RSS）。每个页都保存在 FIFO 列表中。当一个进程超过其 RSS 时，“先入”的页被驱逐。决定了进程不能占用过大内存
纯粹的 FIFO 并不是特别好。为了提高 FIFO 的性能，VMS 引入了两个 二次机会列表（second-chance list），页在从内存中被踢出之前被放在其中。具体来说， 是全局的干净页空闲列表和脏页列表。当进程 P 超过其 RSS 时，将从其每个进程的 FIFO 中移除一个页。如果干净（未修改），则将其放在干净页列表的末尾。如果脏（已修改），则 将其放在脏页列表的末尾。
如果另一个进程 Q 需要一个空闲页，它会从全局干净列表中取出第一个空闲页。但是， 如果原来的进程 P 在回收之前在该页上出现页错误(不在物理内存中，在磁盘中)，则 P 会从空闲（或脏）列表中回收，从而避免昂贵的磁盘访问。这些全局二次机会列表越大，分段的 FIFO 算法越接近 LRU

页聚集

通过聚集，VMS 将大批量的页从全局脏列表中分组到一起，并将它们一举写入磁盘（从而使它们变干净）。

写时复制（copy-on-write，COW）

如果操作系统需要将一个页面从一个地址空间复制到另一个地址空间，不是实际复制它，而是将其映射到目标地址空间(相当于两个空间是共享的，还是同一个)，并在两个地址空间中将其标记为只读。如果两个地址空间都只读取页面，则不会采取进一步的操作，因此操作系统已经实现了快速复制而不实际移动任何数据。
如果其中一个地址空间确实尝试写入页面，就会陷入操作系统。操作系统会注意到该页面是一个 COW 页面，因此（惰性地）分配一个新页，填充数据，并将这个新页映射到错误处理的地址空间。该进程然后继续，现在有了该页的私人副本。
例子：
fork()会创建调用者地址空间的精确副本,就是原来的程序要复制一份，fork 出的新程序和原来的是一样的,如果后面还有 exec 替换不同的程序，那这个复制操作实际上没有意义。对于大的地址空间，这样的复制过程很慢，并且是数据密集的。更糟糕的是，大部分地址空间会被随后的 exec()调用立即覆盖，它用即将执行的程序覆盖调用进程的地址空间。通过改为执行写时复制的 fork()，操作系统避免了大量不必要的复制，从而保留了正确的语义，同时提高了性能。