1. 关于本书的对话

忽略~

2. 操作系统介绍

程序执行过程：执行指令，分三步，1）获取指令；2）解码；3）执行。
本书主要内容：虚拟化CPU、虚拟化内存、并发持久化。

3. 关于虚拟化的对话

忽略~

4. 抽象：进程

进程：运行中的程序，拥有独立的资源，如内存、寄存器等。

进程API：create、destroy、wait、miscellaneous control(其他控制)、status

程序加载过程：

加载：程序到进程.png

进程状态：running、ready、blocked

进程：状态转化.png

进程数据结构：

xv6 的 proc 结构.png

用于上下文切换（context switch）时，保存和恢复进程。上下文切换很重，除了保存寄存器内容，如TLB、CPU缓存、分支预测等优化都失效。

5. 插叙：进程API

fork：创建进程
exec：执行进程
wait：等待其他进程执行

6. 机制：受限直接执行

主要挑战：性能和控制权

受限直接执行：
无限制部分：

无限制部分.png

受限制部分：通过初始化陷阱表，执行陷阱，从用户态内陷到内核态，交给操作系统执行

受限制直接执行.png

在进程之间切换：

• 协作方式：等待系统调用。假定程序任务完成后，会自动进行系统调用，把控制权交给系统，如果存在恶意程序，不交出控制权，无能为力。
• 非协作方式：操作系统进行控制。通过时钟中断（timer interrupt），产生时钟中断时，程序将执行权交给操作系统，操作系统中预先配置的中断处理程序（interrupt handler）会执行。操作系统停止老的程序，执行其他程序。

保存和恢复上下文：

首先直接执行协议（时钟中断）

7. 进程调度：介绍

周转时间：T_周转时间=T_完成时间-T_到达时间

FIFO（first in first out，先进先出）：先进的是大任务，后进的是小任务，则平均周转时间长

FIFO调度.png

SJF（shortest job first，最短任务优先）：可解决同时达到问题，但无法解决小任务在大任务后达到问题

SJF调度

STCF（shortest time-to-completion first，最短完成时间优先）：无法解决任务执行时间无法预测问题

STCF调度

响应时间：T_响应时间=T_首次执行-T_达到时间
RR（rotation-robin，轮转）：按照时间片轮转执行。响应时间好，但周转时间差。

RR调度

结合I/O：

结合I/O：重叠执行

8. 调度：多级反馈队列

MLFQ(Multi_level Feedback Queue)：多级反馈队列。
解决两个问题：1）优化周转时间；2）降低响应时间。
基本规则：
规则1：如果A的优先级>B的优先级，运行A；
规则2：如果A的优先级=B的优先级，轮转运行A和B。

尝试改变优先级：
规则3：工作进入系统时，放在最高优先级队列；
规则4a：用完整个时间片后，降低其优先级；
规则4b：如果工作在用完整个时间片前主动放弃CPU，则优先级不变。

存在两个问题：1）饥饿问题：低优先级任务无法获取时间片；2）被程序利用机制，时间片快用完时主动放弃时间片，从而一直保持在高优先级。

提升优先级：
规则5：经过一段时间S，就将系统中所有任务都重新加到最高优先级。
但S很难设置，被称为“恶毒常量（voo-doo constant）”

更好的计时方式：
为了解决被程序愚弄，优化计时，重写规则4。
规则4：一旦一个任务用完了在某一层的时间配额（不论是否主动放弃），则自动降低其优先级。

9. 调度：比例调度

基本概念：彩票数表示份额，一个进程持有的彩票数占总彩票的比例，就是其拥有资源的比例。
其优势是具有随机性，随机性的有点：1）可以避免边角问题，如LRU替换策略无法解决重复序列的问题；2）随机性具有轻量级，无需记录每个任务使用资源的总时间；3）随机性具有性能高的优点。

彩票机制：

• 彩票货币：资源持有的彩票数可以分给子任务，子任务的彩票数可以转换成全局的彩票数
• 彩票转让：可以临时将资源转让给其他进程
• 彩票通胀：一个进程可临时减少或增加自己的彩票数

实现：通过简单的遍历链表，对链表的彩票数做加法运算，第一个求和不小于随机彩票数的任务获得执行权。如下图，假设随机生成的彩票数为300，遍历到A时，和为100，小于300，继续遍历；遍历到B时，和为150（100+50），仍小于300，继续遍历；遍历到C时，和为400，大于随机彩票数，C获得执行权。

彩票链表

可优化成彩票数递减的链表，减少遍历次数

如何分配彩票：对于给定的一组任务，彩票分配的问题没有最佳机制

彩票机制的问题：在短时间内无法保证随机性。可将彩票数转换成每个任务固定步长调度可缓解。假设有三个任务A、B、C，原先各自的彩票数分别为100、50、200，则转换后每个任务的步长为100、200、40。
执行规则为：1）初始任务的计数器为0；2）每次执行计数器最小的任务；3）每次执行任务后，该任务的计数器增加其步长。
一种执行结果如下：

固定步长算法

固定步长算法的缺点是需要全局状态，每个任务都需要记录其计数器的数值。

彩票调度和步长调度因为其彩票数难确定、不能很好的适用于I/O，因此未能很好的推广。

10. 多处理器调度（高级）

多处理器每个处理器都有缓存，有缓存一致性问题。

多处理器共享内存
在基于总线的系统中，可通过总线窥探（bus snooping）的方式解决。每个缓存都通过监听链接所有缓存和内存的总线，来发现内存访问。当缓存的数据被更新时，会作废本地缓存，或更新缓存。

在访问共享数据时，需对数据做加锁同步，否则会出现异常结果。

缓存亲和度问题：进程在CPU上执行时，会在CPU的缓存中维护很多状态。CPU下次再执行该进程时，因有缓存状态，可加快执行速度。多处理器应该考虑缓存亲和度问题，同一进程应在同一个CPU上执行。

单队列多处理器调度（SQMS，Single Queue Multiprocessor Schedule）：

• 优点：很少的修改就可应用于多处理器
• 缺点：
  • 缺乏扩展性：队列是共享数据，需对其加锁来保证原子性。锁的性能损耗大；而且在CPU变多时，竞争带来的时间开销增加，真正处理进程任务的时间减少。

  • 缓存亲和度问题：假设任务有5个。

    
    进程队列
    

    可能的进程调度如下，与缓存亲和度背离：

    
    可能的进程调度
    为了解决这个问题，大部分SQMS调度程序都引入一些缓存亲和度机制，尽可能的让进程在同一CPU上执行，可能会牺牲其他进程的缓存亲和度。
    缓存亲和度机制

多队列多处理器调度（MQMS，Multi-Queue Multiprocessor Schedule）：每个CPU一个任务队列，任务加入可通过随机加入队列，或选择负载最小的队列加入。假设4个进程，2个CPU的情况：

4个进程2个CPU

可能调度过程如下：

MQMS潜在调度
MQMS具有扩展性，也满足缓存亲和度，但存在负载不均的问题。假设上述情况，C提前执行完毕，则目前有3个进程，2个CPU，如下：
3进程2CPU

潜在的调度过程如下：

image.png
A进程的时间片是B和D的2倍。假设A很快执行完，则CPU0空闲，CPU1执行B和D两个进程，存在严重的负载不均衡问题。

可以通过迁移的方式解决负载不均衡问题，
如果B和D在CPU1的队列上，CPU0的队列为空，可将B进程迁移到CPU0的队列上。
但如果是CPU0队列上存在A，CPU1队列上存在B和D，单次迁移不能解决问题，可通过多次迁移解决，不断将B在CPU0和CPU1的队列上迁移。

如何发起迁移？可通过工作窃取（work stealing）的方式实现。工作量上的CPU可不断“偷看”其他队列是否满，如果更满，则触发任务迁移。
工作窃取的方式仍存在问题，如果检查时间长，则仍存在负载不均衡的问题；如果检查时间短，则可能会导致共享数据竞争，降低系统的扩展性。

Linux调度算法：Linux社区一直未达成共识，存在三种调度算法： Q(1)调度程序、完全公平调度程序（CFS）、BF调度程序（BFS）。
Q1和CFS采用多队列，BFS采用单队列。Q(1)调度程序基于优先级，类似MLFQ；CFS采用确定的比例调度，类似步长调度；BFS也采用比例调度，但采用更复杂的调度算法，称为最早最合适虚拟截止时间优先算法（EEVEF）

11. 关于CPU虚拟化总结对话

忽略~

12. 关于内存虚拟化对话

忽略~

13. 抽象：地址空间

早期系统：操作系统实际是一组函数，在内存中。然后是运行的程序，使用剩余内存。

早期操作系统

多道程序和时分共享：未执行的进程程序和数据仍在内存中。

3个进程在：共享内存

地址空间：操作系统虚拟化内存，提供易用的物理内存抽象。

地址空间的例子

目标：

• 透明（transparency）：进程感知不到内存被虚拟化，每个进程都好像拥有私有内存
• 效率（efficiency）：内存虚拟化应尽可能保持空间和时间上的高效
• 保护（protection）：进程之间相互隔离，互相不影响

程序打印出来的都是虚拟地址，地址都从0开始增长，真实的地址会在执行时，由操作系统将虚拟地址转换成机器中的真实地址

14. 插叙：内存操作API

栈内存：其申请和管理由编译器隐形完成，称为自动内存。进入函数时，编译器在栈上开辟空间；函数退出时，编译器自动释放内存。

占内存

堆内存：C语言中，malloc()方法分配，free()方法释放

15. 机制：地址转换

在CPU虚拟化时，一般遵循受限直接访问（Limited Direct Execution，LDE）。LDE的是思想是让程序运行时的大部分指令直接访问硬件，只在一些关键点（如发起系统调用或时钟中断）由操作系统介入。为了实现高效的虚拟化，操作系统应该尽量让程序自己运行，同时通过关键点的及时介入（interposing），来保证对硬件的控制。
虚拟内存追求的目标：

• 高效：要利用硬件的支持
• 控制：程序只能访问自己的内存空间
• 灵活：程序能以任何方式访问自己的地址空间

一种通用的技术是基于硬件的地址转换（hardware-based address translation），简称地址转换（address translation）。

程序的虚拟内存假设占用16KB，其虚拟地址如下：

程序虚拟地址

但在物理内存中，程序的地址不可能都从0开始，其真实地址可能是32-48KB内存空间。

物理内存
虚拟地址需要通过某种方式转换得到真实的物理地址。

动态（基于硬件）重定位：
提供两个硬件：基址（base）寄存器和界限（bound）寄存器，一般把负责地址转换的部分称为内存管理单元（Memory Management Unit，MMU）。基址寄存器记录程序的起始地址，界限寄存器记录程序所占内存的大小。虚拟地址转换成物理地址的算法如下：

physical address = virtual address + base

存在两种CPU模式：

• 特权模式（privilege mode，内核模式，kernel mode）：操作系统可以访问所有机器资源；
• 用户模式（user mode）：应用程序只能做有限的操作。

只要一位就能区分CPU的模式，保存在处理器状态字（processor status word）。

动态重定位：硬件要求

硬件提供：- MMU：基址寄存器和界限寄存器

• 特殊指令：进程切换时，改变基址寄存器和界限寄存器的值（只在内核态，由操作系统修改）
• 在用户非法访问时，CPU必须产生异常（exception），安排操作系统的异常处理器（exception handler）去处理。

受限直接执行协议（动态重定向）
续表

16. 分段

将进程的整个地址空间加载到一整块内存区域，存在两个问题：

• 堆和栈之间有很大的空间未被利用，空间浪费严重

如果地址空间是4G，一般进程通常只占几兆

• 如果剩余空间充足，但不连续时，进程无法运行

分段：泛化的基址/界限
在MMU中引入多个段，每个段占用连续的地址区域。假设分为代码、堆、栈3个段，则需要3个基址寄存器和3个界限寄存器。

分段物理内存
分段寄存器

通过虚拟地址的前几位标识所属段，剩余后几位作为偏移量。假设3个段时，可用2位标识端地址：

虚拟地址

在计算段和便宜量时，可通过与和右移减少计算量。
图中，SEG_MASK 为0x3000，SEG_SHIFT 为12，OFFSET_MASK 为0xFFF。

寻址算法

上图中栈反向增长，需要特殊位标识增长方向：

栈寄存器（支持反向增长）

支持共享，代码共享非常常见。通过保护位（protection bit）实现：

段寄存器（有保护）

细粒度和粗粒度分段：上述例子中只有3个段，属于粗粒度分段。早期机器中，有些可支持成千上万的段。

操作系统支持：

• 上下文切换时，保存切出进程的分段信息，恢复获得执行权进程的分段信息

• 管理空闲地址空间。一般会遇到很多空闲空间的小洞（外部碎片，external fragmentation），有段需要分配时，整体空间足够，但空间不连续，导致无法分配。
  如图空闲空间有24KB，假设有个段需要申请20KB空间，因每个空闲空间都无法满足，空间分配失败。

  
  非紧凑的
  

  通常的解决方案：

• 紧凑（compact）物理内存：终止在运行的程序，数据复制到连续的空间中，并修改段寄存器的值，从而获得更大的连续内存。但拷贝段属于内存密集型操作，效率低
• 空间列表管理算法，试图保留大的地址空间用于分配，算法包括最优匹配（best-fit）、最坏匹配（worst-fit）、首次匹配（first-fit）和伙伴算法（buddy algorithm）

段的问题：

• 内存中分配不同大小的段，会导致外部碎片，需要定期规整内存空间，内存管理困难
• 不足以支持更一般化的稀疏地址空间问题。假设一个很大但稀疏的堆，都在一个逻辑段中，整个堆仍需要全部加载到内存中

17. 空间空闲管理

本章讨论外部碎片，且假设用户进程申请到的是连续空间，且分配后不会再要求增加堆空间。

底层机制：

• 分配与合并：假设有30字节的空间，10-20之间的空间被占用，此时空闲列表如下：

  
  空闲列表
  

  如果10-20之间的空间被释放，需对空间合并，空闲空间变成0-30。

  
  空闲空间合并

• 追踪已分配空间的大小
  在free(void *ptr)时，仅传入指针，未指定要释放空间大小。一般空间分配时，会在分配空间之前加上头块(header)，用于存储空间大小等信息，一般还包括魔数等，简化后的实例如下：

  
  简化的头块
  分配空间（带头块）

• 嵌入空间列表
  简化后的空闲空间列表结构如下：

typedef struct node_t {
    int size;
    struct node_t *next;
} node_t;

进程可通过mmp()向操作系统申请内存空间。

申请空间
假设剩余空间是连续的4KB，系统申请100字节，header占8字节，空间过程如下：
空间分配
假设又分配两个100字节的空间，分配后的结果如下：
空闲空间和3个已分配块
假设释放中间的块，中间块加入到头部：
释放中间块

• 让堆增长：通过sbrk申请

基本策略：

• 最优匹配：遍历一遍空闲列表，找到和请求大小一样，或者更大列表中最小的块。遍历的查找成本高。
• 最差匹配：找到最大的块分配，需遍历整个列表。除遍历成本外，其会产生大量碎片
• 首次匹配：首次匹配到足够大的块即分配。表头很容易产生大量小块
• 下次匹配：第二次匹配到的分配，避免对表头的频繁分割
• 分离空闲空间（segregated list）：如果某个程序经常申请一种（或几种）大小的内存空间，就用一个独立列表，专门管理这样大小的对象，可有效减少碎片，且分配和释放速度快
• 伙伴系统：对空闲空间都一分为二，直到最小可适配空间大小。可更快的合并空闲（兄弟节点只有一位不同，其他都相同）。

18. 分页：介绍

空间管理主要有两种：

• 不同长度的分片，容易产生碎片
• 固定长度的分片，一般称为分页。不再以分段的形式管理内存，分页把物理内存看成定长槽块的阵列，叫做页帧（page frame），每个页帧对应一个虚拟内存页。

假设虚拟地址共64字节，每16字节为1页，共4页。物理地址共128字节，每16字节1页，共8页。虚拟页和物理页帧的对应关系假设为VP0->PF3，VP1->PF7，VP2->PF5，VP3->PF2，空间分布如下：

虚拟地址页和物理地址页分布

虚拟页和物理页帧的对应关系记录在页表（page table），页表的主要作用是为地址空间的每个虚拟页面保存地址转换（address translation）。

虚拟地址结构：
虚拟地址由VPN（虚拟页面号，Virtual Page Number）和偏移量（offset）组成，上述例子64位需要6字节，4个虚拟页面，VPN2位，偏移量4位。

虚拟地址

假设虚拟地址为21，转换成6位为010101，VPN为01，对应的PFN为7，偏移量为0101。

地址转换过程

页表存储：
因页表空间较大，真实32位操作系统，假设虚拟页20位，每个PTE（页表项，Page Table Element）占4字节，每个进程需要4M页表空间，假设操作系统同时运行100个进程，则页表需要400M。页表未存储在类似MMU（内存管理单元，Memory Management Unit）的硬件中，而是存储在内存中。

页表中的数据：

• 页表结构：页表存储VP到PF对应关系的数据结构列表，假设使用线性页表（linear page table）存储映射关系，使用数组实现，通过VPN可获取数组下标，即可获取PTE。线性列表存在空间浪费问题，19章会用多级页表的树形结构存储。

• PTE结构：PTE中存在不同位。有效位（valid bit）指示当前PTE的转换是否有效。保护位（protection bit），表明页是否可读、写、执行。存在位（present bit）表示该页在内存中，还是被已经被交换到磁盘中。脏位（dirty bit）表示页表被带入内存中，是否被修改。参考位（reference bit，访问位accessed bit）追踪页面是否被访问，可确定页面被访问频次，页面替换时（page replacement）会用到这个数据。

  
  image.png

页表不仅占用内存大，而且会导致程序执行变慢，每次获取地址数据时，需要两步：

• 先获取页表，通过转换得到真实的物理地址
• 通过真实的物理地址，获取该地址上的数据

页表存在页表基址寄存器（page-table base register）中，转换如下： 页转换算法

综上所述，上述线性页表的方式存在两个问题：

• 占用内存空间大
• 执行效率低

19. 分页：快速地址转换（TLB）

页表存储在内存中，导致每次地址访问都需要一次额外的内存访问。操作系统借助地址转换旁路缓冲存储器（translation-lookaside buffer，TLB）硬件，缓存部分页表，从而减少绝大多数从内存中获取页表的操作，加速执行效率。

TLB基本算法：

• 从虚拟地址中提取VPN，再从TLB中查找是否存在VPN的转换映射，如果存在，则直接使用，转换得到真实的PF；否则继续执行，

• 如果TLB未命中，硬件访问页表找到映射关系，更新到TLB中。TLB更新后，程序通过TLB获得映射关系，转换得到真实的PF

  
  TLB控制算法

示例：访问数组：
在访问a[0]、a[3]、a[7]时需要额外访问一次内存，其他不需要，TLB缓存命中率70%。

image.png

如何处理TLB未命中：
以前硬件有复杂的指令集（复杂指令集计算机，Complex-Instruction Set Computer，CISC）不信任操作系统，硬件负责获取页表转换，并更新到硬件管理的TLB（hardware-management TLB）中。现代的体系结构都是精简指令集计算机（Reduced-Instruction Set Computer，RISC），有软件管理TLB（software-management TLB）。TLB未命中时，硬件抛出一个异常，暂停当前的指令流，将特权升级到内核模式，跳转到陷阱处理程序（trap handler）。不同于以往的陷阱，返回后执行后一个指令；TLB未命中陷阱返回后，硬件必须从导致陷阱的指令继续执行，因为映射关系已经属性到TLB中，重试会命中

image.png

TLB未命中需注意无限递归的问题，一种解决方案是将TLB未命中陷阱处理程序直接放到物理内存中（他们没有映射过，不用经过地址转换）；或者在TLB中保留一些项，记录永久有效的地址转换，并将其中一些永久地址转换槽块留给处理代码本身，这些被监听的（wired）地址转换总是会命中TLB。

TLB内容：

VPN ｜ PFN ｜ 其他位

其他位包含有效位、保护位等。

上下文切换时对TLB的处理：
一种方式上下文切换时，清空TLB，但会导致下一次执行时重新更新TLB，执行效率低。
为了减少开销，一些系统增加硬件支持，通过在TLB中增加地址空间标识符（Address Space Identifier，ASID），实现跨上下文切换的TLB共享。

可以把ASID看做进程标识符（Processor Identifier，PID），但通常比PID位数少，PID一般32位，ASID一般8位。
为了能标识当前进程，在上下文切换时，需将某个特权寄存器设置为当前进程的ASID。

image.png

TLB替换策略：
在讨论页换出到磁盘的问题时会详细讨论。常见的策略有最近最少使用（least-recently-used，LRU）和随机（random）策略，LRU看似合理，但在TLB有n个，循环长度为n+1的极端情况下，LRU表现极差。

实际系统中的TLB表项：

image.png

20. 分页：较小的表

19章解决了访问效率问题，但线性页表的内存空间占用大的问题仍无法解决。

简单的解决方案：更大的页
一般32位内存，页12位，页表20位。如果增加页大小到14位，则页表减少到18位，页表大小变成原来的1/4(2¹⁸/2²⁰=1/4）。但页过大会导致内部碎片（internal fragmentation）问题。

混合方法：分页和分段
假设分为3个段，00不用，01代码段，02堆段，03栈段，可使用前2位作为段标识。

分页和分段的结合
但段存在的外部碎片问题和稀疏的大堆问题仍无法解决。

多级页表（multi-level page table）：将线性页表变成类似树的数据结构。将页表分成页大小的单元，如果整页的PTE都无效，则不分配该页的页表。为了追踪页表的页是否有效，以及页表所在的位置，使用名为页目录（page dictionary）的新结构，页目录中包含页表的位置。如下图所示，线性表中无论映射关系是否存在，都预先分配空间；多级页表中，增加页目录，如果整页的PTE都无效，则不分配空间（如PFN202和PFN204），从而整体节省空间。

image.png
在简单的两级页表中，第一级为页目录表，存在一个物理页中，包含多个页目录项（Page Dictionary Entities，PDE）。PDE至少包含有效位和PFN，如果PDE有效，则PDE指向的PFN中至少有一个页是有效的映射关系。第二级是虚拟地址对应的真实物理地址PFN，通过PFN可加载真实的数据。
多级页表可有效解决稀疏空间的问题。
如果页表的每个部分都可以整齐的放入一页，可以更容易进行内存管理。线性页表需要将整个页表加载到连续的物理内存中；多级列表无论页表项，还是页表项对应的真实映射关系，都放在一页中，整个页表可分散在物理内存中的各处。

多列表使用时间-空间这种（time-space trade-off）的方式，虽然空间节省，但每次TLB未命中时，相较于线性页表，多级页表需多访问内存，如两级列表，需先获取页表项，再通过页表项获取虚拟地址对应的真实物理地址，通过物理地址加载数据，整体需要3次内存访问，比线性表多1次内存访问。

假设14位虚拟地址，每页64字节，则偏移量为6位，VPN为8位，页表有2⁸=256个。假设每个PTE大小为4字节，每页能存储16（64/4=16）个PTE，需4（16=2⁴）位存储页表索引，剩余4位用作PDE，假设PDE也是4字节，则16个PDE共需64（16*4=64）字节，刚好存储在一页中。
综上共需4位标识页目录索引，4位用来标识页表索引，示意图如下：

image.png

超过两级：
假设虚拟地址为30位，每页512字节，则，偏移量为9位VPN为21位，页表有2²¹个。同样假设每个PTE大小为4字节，每页能存储128（2⁹/4）个PTE，需7（128=2⁷）位用来存储页表索引，剩余14位用作PDE。假设PDE也是4字节，则需要2¹⁶（4*2¹⁴）个字节存储PDE，占用2⁷（2¹⁶/2⁹）个页，而不是1个页。解决方法是页目录索引上再加一层索引，一页能存7个PDE，则PD索引1占用7位，PD索引0留7位，刚好可放在1页中。即三级页表也解决上述问题，其存储结构如下：

三级索引

反向页表（inverted page table）：保留一个页表，项存储物理页，而不是每个进程一个页表。页表项存储哪个进程使用该物理页，以及哪个虚拟页映射到该物理页。为了加速查找，数据结构选用散列表。

将页表交换到磁盘：以上都假设页表能一次加载到内存中，如果内存不足时，一些系统将无法加载的数据放入内核虚拟内存（kernel virtual memory）中，从而允许在内存压力较大时，将这些页表中的一部分交换（swap）到磁盘。

21. 超越物理内存：机制

交换空间（swap space）：内存空间不足时，在硬盘或SSD中开辟一部分空间用于物理页的移入和移除，这部分空间叫swap space。
图中proc0、proc1、proc2部分在内存中，部分在交换空间中，proc3全部在交换空间中（肯定没获得执行权）。

image.png

存在位：通过页表项的存在位（present bit）判断是否在物理内存中，1表示在内存中，0表示在硬盘中。访问不在物理内存的页，称为页错误（page fault），由页错误处理器（page-fault handler）处理。

页错误：页错误由操作系统执行（无论是硬件TLB还是软件TLB，因需做I/O处理，硬件对该过程的加速无意义）。硬盘地址在PTE中的某些位中，类似PFN。当发生page fault时，从PTE中查找硬盘地址，发送给硬盘，读取到内存中。
读取成功后，更新到页表中。TLB重新执行，虽然仍未命中，但此时页已在内存中，可更新到TLB中；再次执行可从TLB中获取虚拟地址映射的内存地址，获得数据或指令。

执行I/O从硬盘获取数据时，进程处于阻塞（blocked）状态，CPU可执行其他进程。

内存已满时，空间换入（page in）前，需做空间换出（page out），如何选择换出的页，称为页交换策略（page-replacement policy）。

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

21. 超越物理内存：策略

最优替换策略：替换出最远将来才会被访问的页，能达到总体未命中数最少，但几乎无法实现
FIFO：First In First Out，缓存命中率低
Random（随机）：缓存命中率也随机，时高时低
LRU（Least-Recently-Used，最近最少使用）：基于局部性原则（principle of locality），此外还有LFU（Least-Frequently-Used，最不经常使用）。相较于FIFO和Random表现较好，但实现困难，需记录并扫描每个页的访问时间。
近似LRU：在硬件中增加一个使用位（use bit，有时成为引用位 reference bit），每个页都有使用位，每当页被使用时，use bit设置为1。一种实现方案是时钟算法（clock algorithm），所有页在一个循环列表中，指针指向其中一个页，如果页的use bit=1，设置成0，继续向下寻找，直到找到use bit=0的页。

考虑脏页：脏页踢出必须将它会写到磁盘，成本较高，可选择踢出干净页。硬件中增加一个修改位（modify bit，或脏位 dirty bit）标识页是否修改。

其他虚拟内存策略：

• 页载入时的页选择（page selection）策略，对大多数按需分页（demand paging）载入。操作系统也可猜测页即将被使用，可提前载入（预取，prefetching）。
• 如何将页面写入磁盘：简单的是一次写入一页，但效率低。很多系统收集一些待完成写入，并以一种更高效的方式写入磁盘，称为聚集（clustering）或者分组写入（grouping）。

执行单次大的写操作，比许多小的写操作高效

抖动：当内存被超额请求时（进程需要的内存超过可用的物理内存），将不断进行换页，这种情况称为抖动（thrashing）。

23. VAX/VMS 虚拟内存系统

略~

24. 内存虚拟化总结对话

略~