操作系统导论（Operating Systems: Three Easy Pieces）笔记

0 内容提要

本文主要是对Arpaci-Dusseau教授夫妇所著书籍《Operating Systems: Three Easy Pieces》（中文译名为：操作系统导论，后文中简称为“该书”）的摘要和读后感。以操作系统相关的三个话题展开，针对每一种技术的历史沿革做出相应的梳理，并强调一些问题解决的思维和对于科研的理解（后者中包含大量本文作者主观观点，注意甄别）。为了保持完整性，其中还加入了部分MIT6.S081（操作系统工程）、UCRCS202（高级操作系统）的部分课程内容、Linux文档内容等。

1 操作系统三大话题

All problems in computer science can be solved by another level of indirection. ---- David Wheeler

在冯诺伊曼体系中，程序对机器码读取并执行，而在现代的操作系统设计中（意味着需要考虑到多程序同时运行），程序并不直接访问硬件（需要保护硬件资源），这时就需要一个软件来协调二者：通过受保护的方式分配资源给各个程序；这一软件就是操作系统，因此操作系统也可以看作硬件与应用程序间的抽象层。

操作系统这一抽象（abstraction）的设计原则也是计算机科学中的常用手法。本节开头引述的David Wheeler的这句名言超前地预言了计算机科学的现状。这句名言中的‘level of indirection’也会被故意错误地被引用为‘layer of abstraction’（后者的说法更接近当下流行的语言）。实际上，抽象使得构建一个更大型的系统更加容易，例如在使用高级语言编程的时候不用去关心下层的汇编、数字电路或者晶体管的细节；在网络栈中传输应用数据的时候不需考虑物理电缆是否可靠；在操作系统中运行程序的时候也不用去关心硬件资源的使用和保护。

该书提出操作系统的三大话题是：virtualization, concurrency 和 persistency；细分下来，分别对应了操作系统中的数个组件（或技术）。

三大话题	对应技术 - 抽象	技术目标
虚拟化（virtualization）	CPU虚拟化- 进程	对每个程序提供“该系统拥有无限数量的CPU”的假象
虚拟化（virtualization）	内存虚拟化 - 虚拟内存	对每个程序提供“该程序独占系统的所有内存空间”的假象
并发（concurrency）	多线程并发 - 同步机制	让多个同时进行的程序以预期的顺序执行并得到预期的结果
持久性（persistency）	单机数据持久 - 文件系统	保持存储的数据长期稳定安全
持久性（persistency）	联机数据持久 - 分布式文件系统	使用不可靠的机器提供可靠的文件系统服务

实际上，最后一项技术已经涉及了分布式系统的领域，在本篇笔记中只会略微提及。

2 技术演进

Life is not always perfect. Accept it. ---- 改编自西方俚语

对于这每一项技术目标，先后有无数的研究人员提供了自己的解决方案，有的被采用、有的被替代、有的被抛弃，而有的则启发着后来的方案。实际上，与其他的领域一样，学术界的竞争也很激烈，对于一个技术问题，所有科研人员都能拿出自己的方案（A solution），这些方案都有一定的道理，但都不是完美的方案；最后被广泛采用（经受住了时间考验）的那一个则是其中总体上成本低、收益高（不仅是性能，还需要考虑实际因素）的折中（trade-off）方案（THE solution）。

Der Teufel stecktim Detail. (The devil is in the details.) ---- Friedrich Wilhelm Nietzsche

想出一个方案的大致思路很容易，这样的思路通常来自于科研人员的直觉，或者是受到其他问题的启发。该书中就说，一个学术人员常犯的错误就是认为掌握了主要想法（general idea）就行了，而其他的则只是该想法的补充说明。事实上，主要想法很容易通过直觉提出，也很容易被理解，但在理解或者构建一个真正能够被采用的解决方案的时候，它面对各种正常和异常情况时的处理、系统的性能和开销等都是需要考虑在内的。

Why eat just chocolate or plain peanut butter when you can instead combine the two in a lovely hybrid known as the Reese’s Peanut Butter Cup? ---- 引用自该书第20章

除开通过直觉、类比、启发、推广等方式开发原创的解决方案，一个更加简单高效的方式是将若干种现行的好方案结合到一起：这样的方法被称为杂合方法（hybrid approach）。当人们需要一种吃的比马少、干活比驴多的生物的时候，骡子（马和驴的杂合物种）就诞生了；而在计算机科学中，这样的例子也比比皆是，例如段页式内存、两段锁、设备交互协议等。这样的方法自然比不过在深刻理解一个问题后得出的新的更统一的解决方案，但是它是能在已有方案下快速提升性能的手段。

3 关于“抽象-机制-策略”

本节解释几个在该书中反复提到的概念：抽象（abstraction）、机制（mechanism）、策略（policy）。

抽象前面已经提到，是一种展现其外观而隐藏其细节的手段。例如操作系统是一层提供接口给程序而隐藏了对硬件细节的抽象；而进程、虚拟内存、文件等这些概念则是对相应资源或者数据的抽象。

机制则一般与策略成对出现，机制作为一个解决方案里的框架，相对模糊和广泛，而策略则规定了其中有限的细节，这种关系就像是应用程序与配置文件之间的关系。例如CPU调度是一种机制，具体使用哪种方法（如轮转调度、优先级调度等）则是策略；缓存替换是一种机制，而具体替换掉哪一个（例如LRU替换、随机替换等）则是策略。

本文接下来的部分则会依照技术进行分节，分别叙述其对应的抽象、抽象关联的机制、机制关联的策略，尽量以时间为线索展开各个技术的发展：从最初的直觉方案开始，到如今被Linux等主流操作系统采用的方案。

4 CPU虚拟化

CPU虚拟化的技术目标就是产生一种存在无限多CPU的假象，这一目标主要通过时分共享（time sharing）实现。时分共享中的执行单位/调度单位就是进程。

（摘自MIT6.S081课）进程本身不是CPU，但是它们对应了CPU，它们使得你可以在CPU上运行计算任务。应用程序不能直接与CPU交互，只能与进程交互。操作系统内核会完成不同进程在CPU上的切换。所以，操作系统不是直接将CPU提供给应用程序，而是向应用程序提供“进程”，进程抽象了CPU，这样操作系统才能在多个应用程序之间复用一个或者多个CPU。

4.1 抽象：进程

进程指正在执行中的程序。操作系统使用进程列表记录当前的所有进程，进程列表由一系列进程控制块（PCB）组成（可以是数组或者双向链表等），进程的相关属性信息存储在进程控制块中，典型的进程属性信息包括：PID、状态、地址空间、硬件状态等。

• PID：进程的标识符，除了本身的PID以外，还应当记录parent PID。
• State：进程状态，例如ready（可以被调度）、running（正在执行）、waiting（因需要某种资源而等待）。
• Address space：进程的虚拟内存地址空间，包括主存（用户空间、内核空间）、寄存器（一般寄存器、控制寄存器）、外部设备（文件、socket、其他内存映射IO设备）等。将在第5节中详细描述。
• Hardware state：特指关键的寄存器如PC、SP等。

一个进程可以被创建（从程序创建并转为ready状态）和销毁（被terminate）。一个进程只能被另一个进程所创建。Linux中关于进程的API有：

• fork()：复制出与当前进程一样的子进程，当前进程与子进程同时运行（按照调度规则），根据fork对当前进程与子进程的返回值不一样，（按照返回值作为判断依据的分支）执行不同的程序片段直到返回。
• wait()：在使用了fork已经创建了子进程的情况下， 当前进程执行到wait处时等待子进程返回后才接着运行。
• exec()/execve()：使用exec后，新的进程将直接替代当前进程（而不是创建子进程的并结束当前进程），新进程覆盖原来的内存空间（例如数据段、代码段、栈等）并接着运行直到返回。
• kill()：向进程发送一个信号（虽然名字是kill但不一定是结束进程）。

本人绘制了一些示意图说明它们的区别与联系：

4.2 进程如何执行

4.2.1 策略：直接执行（Library OS Model）

直接在硬件上执行进程，而操作系统则充当一个库，对进程的要求做出服务：这就是Library OS的模型。当程序运行，操作系统将其载入内存成为进程，然后将PC寄存器改为main入口点的地址，然后程序就开始执行直到返回。

这样的做法存在一定的问题：如果进程出现错误一直不返回，或是恶意的进程执行危险的操作，或者进程长时间占用CPU导致其他进程无法运行，这样的情况下，library OS对其束手无策。因此这个策略只能在程序互信的环境下使用（例如某些实时操作系统）。

因此需要解决两个问题：（1）限制进程可以执行的指令、（2）（抢占式OS）操作系统强制获得CPU控制权。

4.2.2 策略：受限直接执行（Sleep Beauty Model）

操作系统的睡美人模型（Sleep Beauty Model）认为操作系统是一个事件处理器（event handler），平常都处在沉睡之中，直到有事件（event）发生的时候才将被唤醒，来按照一定规则处理这些事件。这种策略体现了操作系统设计中的隔离性（isolation）。所有的“事件”按属性被分为如下4种：

	Unexpected	Delibrate
Synchronous（进程等待CPU完成处理才能继续）	Fault / Exception（执行指令时的错误），例如Page fault	System call / Trap（由用户发起），例如fork
Asynchronous （进程无需等待可以直接继续）	Interrupt（来自外部设备），例如键盘输入	Signal，例如进程间通信

操作系统应当对所有的四类事件都有解决方案，这体现在IVT（interrupt vector table）中。当事件发生，操作系统跳停下当前用户进程，转到内核模式（称为陷入，trap），并在IVT中寻找对应处理方案（handler）程序的入口地址，然后跳转。当然，预先制作所有情况下的handler是不可能的，因而操作系统也会出现内核错误（kernel panic），表现为蓝屏或死机。

针对直接执行面临的两个问题，使用Sleep Beauty Model如此解决：

• 限制进程可以执行的指令
  为了区别对待普通的指令和敏感指令，现代操作系统基本都引入了用户和内核两种模式。进程一般在用户模式下运行（只能执行普通指令），当需要执行敏感指令的时候则跳转到内核模式（一般通过system call / trap），因此这种模式叫做受限直接执行（LDE）。
• 抢占式操作系统中强制回收控制权
  在非抢占式OS中，进程不会主动放弃CPU。现代主流的一般目的（general purpose）操作系统则一般是抢占式的，操作系统会在一定条件下强制收回CPU控制权，以免单个进程占用过长时间，这也是time sharing系统的关键。具体的方法是使用时钟中断（timer interrupt），时钟硬件定时发送一个中断（例如几毫秒一次），操作系统则会停下当前进程，进入内核模式，处理该中断，而收回控制权。

4.2.3 如何切换

受限直接执行策略的trap过程中，需要使用到某种切换机制：无论是从用户进程跳转到内核，还是反过来（进程之间的切换是通过进程A-内核-进程B的方式完成的），都要保证回到进程的时候进程正确地回到之前运行的位置。这种切换机制就是上下文切换（context switch），具体的做法如下：

（1）事件产生
（2）将当前用户进程的寄存器压入该进程的内核栈
（3）修改mode register（其中存储hardware status）为内核态
（4）查找IVT，找到对应的handler入口
（5）执行handler
（6）从用户进程的内核栈恢复寄存器
（7）恢复mode register为用户态
（8）执行用户进程

值得一提的是在该书6.3节中的示例（如图）。

前面文字部分展示的上下文切换过程（将当前用户进程的寄存器压入该进程的内核栈，操作完成后从栈恢复到寄存器）是由硬件隐式完成的，在进程调度式发生类似的过程（从进程A切换到进程B，内核先保存A的寄存器到A的PCB，然后从B的PCB中恢复寄存器）则是在软件层面显式完成的。

二者的区别在于（1）硬件的上下文切换针对当前正在运行的进程，在发生中断时自动进行，保证中断前后的一致；软件的上下文切换针对整体调度，保证调度前后的一致性（2）软件层面的切换将上下文保存到PCB中，硬件则是保存在内存栈中。

4.3 进程调度

进程调度，顾名思义就是内核如何安排接下来要运行的进程。一般来说，在时钟中断的时候，或者某进程因为缺少资源而进入内核的时候，内核会安排进程调度程序来选择退出内核态的时候接下来运行的进程。进程调度的底层机制就是上下文切换。

进程调度的评价指标包括周转时间（turnaround time）和响应时间（response time）。周转时间是性能指标，评价一个任务从到达到完成的耗时；响应时间是公平性指标，评价一个任务从到达到开始执行的耗时。

4.3.1 进程调度策略的发展线索

策略	内容	演化	缺点
FIFO	先到达的任务先执行	最符合直觉的策略	先到达的长任务让后到达的短任务饿死
SJF (1954)	最短的任务先执行	比FIFO优化了周转时间	任务会随时到达，而在长任务执行时到达的短任务饿死
STCF	能够以最短完成时间可以抢占其他任务	比SJF增加了抢占机制	无法确定任务的完成时间
Round Robin	所有进程轮番使用时间片	优化了响应时间	并不是所有的程序都能用完整个时间片，例如IO密集任务
（重叠式）RR	需要IO的任务让出时间片并在完成前不参与调度	比RR多了对IO考虑	周转时间差于SJF（但总体来说是有效的）
MLFQ (1962)	（见4.3.2）	在没有任务长短的先验知识下，同时优化了周转时间和响应时间	稍显复杂（但被Windows、MacOS和Unix系统采用）
Lottery (1994)	给每个进程分发一定量的彩票，每次调度时随机抽出一个号码，被抽中的进程获得CPU	在给定优先级的环境下优化了公平性	只能在互信环境中使用，需要提前给定彩票数
Stride (1995)	给每个进程分发一定量的彩票，按彩票数的倒数计算步长，程序被调度一次则累计一次步长值，每次调度已经走过步长值最小的那一个	在给定优先级的环境下到达绝对公平，比Lottery优化了确定性	只能在互信环境中使用，需要提前给定彩票数
CFS (2007)	（见4.3.3）	在给定优先级的情况下保持绝对公平，比Stride拥有更多细节	稍显复杂（但是提出后迅速被Linux系统采用）

4.3.2 Unix的策略：MLFQ

多级反馈队列（multi-level feedback queue）在没有关于任务时间的先验知识（prior knowledge）的情况下，同时要降低响应时间和周转时间。现今的Windows系统使用的就是优化后的MLFQ调度方式。
MLFQ包含许多队列，每个队列代表一个优先级（例如Windows有32个优先级）并且对应一个时间配额（time allotment，一般来说高优先级队列的配额低）；进程在这些队列中，并且拥有一个记录其剩余时间配额的“账户”，首次进入一个队列时“账户”的值被设置为该队列的时间配额值。MLFQ调度遵循如下规则：

• 当新进程到达的时候（假定该进程完成时间短），将其加入最高优先级的队列；
• 调度的时候会选择优先级最高的非空队列，并将该队列中的进程轮转（RR）运行；
• 当一个进程被调度后，对该进程的运行时间计时，并在该进程的“账户”中减去对应时长；
• 当一个进程的“账户”归零（即用完了该层的时间配额）的时候，进入下一级队列；
• 定期将所有进程提升至最高优先级队列。

注：调度的单位实际上是调度实体，这里简化称为进程。

4.3.3 Linux的策略：CFS

CFS（completely fair scheduler）中，每个进程：
（1）拥有一个nice值，与优先级相关，从-20到+19，值越小越优先，默认为0；根据nice值可以计算出进程权重，权重越大越优先，计算方法为weight = 1024 / (1.25^nice)；
（2）拥有一个记录标准化CPU使用时间变量vruntime（virtual runtime，类似于stride调度中的pass属性) ，该值等于实际使用CPU的时间*1024/进程权重，也就等于实际使用CPU的时间*(1.25^nice)；简单来说，vruntime是记录该进程使用CPU的“电表”，初始值为0。

CFS规定了一个调度周期（schedule latency），在一个调度周期内，所有可被调度的进程都被调度一次，而且所有进程的实际使用CPU的时间严格按照进程权重分配；换句话说，所有进程经历的vruntime相同（即在一个调度周期内获得的虚拟时间片长度相同），都等于调度周期/进程数量。现今的Linux系统使用的就是CFS，该方法出现后立即代替了Linux之前的O(1)调度。CFS按如下规则运行：

• 调度时选择当前进程中vruntime最小的运行；
• 当一个进程被调度后，vruntime按照其实际使用的时间更新（将运行时间计入“账户”）；
• 当新进程加入的时候，该进程的初始值会以当前所有vruntime中的最小值min_vruntime为基准来设置（而不是直接设置为0，否则会让新进程长时间占用CPU）；

此外，还有一些补充说明：

• 如果当前系统中的进程过多，导致每个虚拟时间片太短（从而导致上下文切换开销太大），那么每个虚拟时间片应该提高（具体做法是，如果虚拟时间片小于sched_min_granularity_ns，则设置为sched_min_granularity_ns，同时调度周期应该按照新的虚拟时间片重新计算，即进程数量*sched_min_granularity_ns）；
• 当新进程加入的时候，起初是值先是设置为min_vruntime，如果START_DEBIT被设置为1，那么会在min_vruntime上额外增加一定值推迟其运行；
• 就绪的进程信息存储在红黑树中（按vruntime值插入树），这样的树每个CPU核心拥有一个（每个核心单独调度），在寻找当前vruntime最小的进程时即搜索了红黑树，时间复杂度为O(logN)。

5 内存虚拟化

内存虚拟化的技术目标是为进程产生自己独占大量的私有内存的假象，这一目标通过地址映射（mapping）来实现。地址映射/地址转换将进程看到的虚拟地址空间对应到硬件的物理内存地址上。

5.1 抽象：虚拟地址空间

地址空间是程序所能看到的系统内存，包含程序运行所需要的代码（指令）和数据；每个程序都运行在自己的地址空间，并且这些地址空间彼此之间相互独立，因此实现了强隔离。用户进程所能够使用的所有地址都是虚拟地址（VA, virtual address），通过基于硬件（例如使用MMU内存管理单元）的地址转换（也需要操作系统介入）变成硬件能访问的物理地址（PA, physical address）。

物理地址布局（memory map）的设计与硬件平台有很大关系，一般在物理地址空间中不仅包含物理内存RAM，还有IO设备的内存映射、boot ROM等。内核虚拟地址空间（kernel address space）的布局由内核设计者决定，包含内核代码、内核数据、为进程保存的内核栈、可分配给用户的空闲内存、trampoline等内核需要用到的部分；而用户进程的虚拟地址空间（user address space）由内核提供，包含了用户进程代码、数据、栈、堆等。

一个典型的Linux（使用X86硬件）用户进程虚拟地址空间布局（layout）如图所示：

C语言中直接声明变量的时候使用的是栈内存（自动内存），对于堆（heap）内存需要使用内存分配库手动分配和释放：

• malloc()：申请一块指定大小的堆内存，成功返回地址，失败返回NULL
• free()：释放一块申请过的内存

两种内存的区别在于：堆内存可以跨越到函数外长期使用，而栈内存在当前函数返回后就自动释放了。该书中提到关于堆内存的一些使用问题（1）释放堆内存的时候不需要传入大小，内存分配库自己有记录（2）忘记释放内存导致内存泄露，由于不会被垃圾收集器自动释放（除非进程退出），进程或操作系统会慢慢耗尽内存（3）悬挂指针和重复释放导致内存分配库很困惑。

由于进程看到的地址都是虚拟地址，因此提供的API操作也都是针对虚拟地址。

内存分配库的底层使用的实际是如下几个系统调用（以Linux为例）：

• brk()：调整程序间断点（program break）到指定地址
• sbrk()：将程序间断点增加或减少指定字节数

由于program break是当前堆结束的位置（堆与数据段、代码段相连，但与栈之间有大量空白内存，因此将堆结束位置称为程序间断点），brk和sbrk在移动program break的时候实际上是在增加或减少程序内存。例如program break向高地址移动，进程会访问更高的地址，操作系统则需要提供更高地址对应的地址转换，也就是增加了内存。

另外还有一些与内存相关的系统调用，这与MMIO（内存映射IO）机制相关：

• mmap()：将文件（Linux认为设备、socket等都是文件）的指定部分映射到内存
• munmap()：取消文件映射到内存

5.2 地址转换

5.2.1 地址转换策略发展线索

策略	解释	硬件支持	演进	缺点
分块 / 基址+界限（base and bound）	对于进程分配整块内存，以分配的位置为base，大小为bound。PA=VA+base, 限制条件：VA<bound	MMU中需要有一对寄存器，分别存放当前进程的base和bound，并且需要检测是否越界、在进程切换的时候保存和恢复这两个寄存器	直觉策略	空间效率低，整块分配内存，但不能完全使用，即存在大量内部碎片
分段（segmentation）	考虑地址空间可以按作用分为数个部分，例如栈、堆、数据、代码等段；VA的前几位表示段，后续位表示偏移量。seg= (VA&SEG_MASK)>>SEG_SHIFT, offset= VA&OFFSET_MASK, PA= segBase(seg)+offset*direction, 限制条件：offset<段大小且权限合适	MMU中需要有若干寄存器，存放：段的编号、段基址、段的大小、增长方向（即direction，栈是朝向小地址增长而其他的朝向大地址）、权限（代码段允许读和执行，数据段允许读写）。仅需要这些段（粗粒度分段）的时候，MMU按照段的数量提供相应套寄存器；当需要支持更多段（细粒度分段）的时候，段表存放在内存中。	按照需要分段，减少内部碎片	由于段的大小不一样，导致段与段之间存在大小不等的无法分配的空闲空间，即存在大量外部碎片
分页 （paging）	按照固定长度将内存分片，每一片空间即页帧（page frame）；按同样的固定长度将进程地址空间分片，每一片即页（page）；按照页表中存储的映射关系将页（以及VA）与页帧（以及PA）对应：VA的前几位表示虚拟页号VPN，后续位代表偏移量，页表以VPN为索引，存储对应的物理页帧号PFN。VPN= (VA&PG_MASK)>>PG_SHIFT, offset= VA&OFFSET_MASK, PFN= pageTable[VPN], PA= PFN<<PG_SHIFT+offset，限制条件：页表项有效且权限合适。	MMU中需要：页表基址寄存器（存储当前进程的页表的物理地址，并负责在进程切换的时候保存和恢复它）、根据页表内容进行地址转换的硬件单元。页表存储在内存中，每一个进程拥有一个自己的页表*。	使用固定大小进行分页，让碎片内存可以按页分配	页表在内存中，MMU进行地址转换需要额外的访存操作（耗时）；进程的虚拟内存很大，需要预留巨大的空间给页表，但实际使用的内存很少（严重空间浪费）
【杂合策略】段页式（segmented paging）	VA的前几位表示段号，中间几位表示页号，后续位表示偏移量；对每一个段保留一个页表，而不是整个进程地址空间。seg= (VA&SEG_MASK)>>SEG_SHIFT, VPN= (VA&PG_MASK)>>PG_SHIFT, offset= VA&OFFSET_MASK, sptBase= segPageTable(seg), PFN= sptBase[VPN], PA= PFN<<PG_SHIFT+offset，限制条件：页表项有效且权限合适。	MMU中需要段页表基址寄存器、地址转换硬件单元，内存中存放段页表、页表。（参考分段和分页需要的硬件支持）	减少页表大小，消除页表中那些对应着不使用内存页面的存储空间。	如果有大且稀疏的堆，仍然会产生一个大页表（空间浪费）；页表本身的大小不固定，给页表本身分配内存空间有外部碎片的问题。
【时空折中】分页+多级页表（multi-level page table）	VA按照页表级数将前面若干位视为多个目录级别，对于每一个目录级别在内存中储存一个页目录，目录指向下一级目录，最低级是页表。（见5.2.2、5.2.3）	MMU与分页式一致，内存中需要存放页目录和页表。	减少页表大小且不依赖段，不给不使用的内存分配页表	页目录和页表都在内存中，进行地址转换需要更多额外的访存操作（耗时）（但仍被Windows、Linux等操作系统采用）

*注：下图展示了一个典型页表项（PTE）的结构。

5.2.2 RISC-V硬件（XV6）的策略：三级页表

XV6系统（名字来源于Unix V6）基于多核RISC-V平台实现。
64位的RISC-V硬件规定：PA有56位（因此只需要56根地址线），VA有39位，L2、L1、L0三级索引共27位，偏移量12位（即页面大小4KB），硬件提供satp寄存器，保存L2级页目录的起始地址。L2级页目录中包含L1级页目录的地址，并且以L1值索引；L1级页目录中包含L0级页目录的地址，并且以L0值索引。XV6中将各级统称页目录，因为无论目录项（PDE）还是表项（PTE）的结构都类似。RISC-V硬件的页表项则由44位物理页号、为操作系统保留的3位标志位、脏位（是否被写入）、访问位（是否被访问）、global、用户（是否为用户页）、执行权限、写入权限、读取权限、有效位（该项是否有效）组成。

下图很好的解释了地址转换的过程（摘自XV6手册）：

如果只有一个内存页面的时候，会使用3*4KB的空间存放页表，相比普通页表需要的2^18*4KB空间节省了不少，但代价就是需要进行反复的访存操作，耗时更长。

5.2.3 X64硬件（Linux）的策略：四级页表

Linux（内核版本2.6.11后）地址结构与X64硬件中规定一致，就是各级目录的名字不一样，Linux（如下图所示）的分别叫做PGD（Page global directory）、PUD（Page upper directory）、PMD（Page middle directory）、PTE（Page table entry），而X64则是PML4T（Page Map Level4 Table）、PDPT（Page Directory Pointer Table）、PDT （Page Directory Table）、PT（Page Table）。

最高级目录的起始地址放在CR3寄存器中，逐级查表的过程与5.2.2中一样，不再重复。

另外，X86版本的Linux使用的是二级页表（22-31页目录，12-21页表，0-11偏移量）。

5.3 缓存和交换

在构造完地址转换的策略之后，新的问题就是，即使使用了分页+多级页表这一时空折中的主流方法，仍然面临几个问题：
（1）每次进行地址转换要进行多次的访存查找页表操作，耗费时间；
（2）页表仍有可能占用内存过大，或者进程本身占用内存过多，导致RAM空间被耗尽。

这两个问题则通过借助存储层级（memory hierarchy）来解决，通过：
（1）使用比RAM更小而更快的硬件TLB来缓存（cache）将来会使用到的VA-PA映射关系条目；
（2）使用比RAM更大而更慢的硬件外部存储（例如磁盘）来交换（swap）过多的内存页面。

5.3.1 机制：TLB

TLB全名是translation-lookaside buffer，但是按照性质来说，不应该叫缓冲（buffer）更应该是缓存（cache），因此该书中认为更好的名字是address-translation cache。由于使用了特殊的全相联硬件，可以实现并行查找，所以效率很高。

在TLB中缓存着近期使用过并且认为将来会重复使用的页表中的信息：当一次访存发生的时候，硬件会查找页表，寻找待查找VPN的对应页表项中的PFN和其他标志，当找到后，TLB便会缓存这个VPN-PFN的映射关系以及重要的标志信息到一个TLB表项中。一个典型的TLB表项应该由如下部分组成：VPN、PFN、有效位（该TLB项是否有效）、ASID字段（表明当前项属于那一个进程，如果没有TLB flush则需要有该位）、权限位等。

当访问内存的时候，首先在TLB中查找是否有符合的项，如果有则可以直接访存；如果没有则触发TLB miss的硬件异常，并进入内核模式，再按照一般的查找多级页表的流程进行，找到后将这一项记录在TLB中。

当上下文切换的时候，可以选择直接清空TLB表，称为TLB flush，具体做法是将每一项的有效位置0；或者选择使用ASID字段，即address space identifier，表明该项属于那一个进程的地址空间，切换时则不用flush，而是按照当前进程对应的ASID查表。

当TLB满时，需要替换一个表项，来加入新的项。替换哪个表项由替换策略（见5.3.3）决定。

5.3.2 机制：页面交换

在二级存储（例如磁盘）中划分出一片区域，称为交换空间（swap space），用于存放从内存移出（page out）的页面；当然，操作系统也要记住这些页面在磁盘上的位置，方便将来把这些页面重新移入内存（page in）。为了标明一个页是在内存中还是在磁盘中，页表项中需要有一个存在位（present bit）。

当需要访问该页面的时候，如果发现该页不在内存中，则引发页错误（page fault，详见5.3.4），陷入内核并从磁盘中调取该页进入内存。

当内存中存在页数量接近低水位线的时候，需要换出多个页，并换入新的页直到存在页数量达到高水位线。替换哪个页由替换策略（见5.3.3）决定。

5.3.3 替换策略发展线索

策略	解释	演化	缺点
MIN/OPT最优替换策略	替换掉最远的将来才会访问的项目	只是一个假设	无法决定哪个页在最远的将来才会访问，实际上根本无法实现
FIFO	替换掉最先进入的项目	直觉策略	缓存容量非常影响命中率，因为存在抖动（thrashing）现象
随机	随机替换掉一个项目	直觉策略	命中率也很随机
LRU最近最少使用	替换掉最长时间没有被使用的项目（使用一个计数器，每次访问项目计数器加1，替换时替换计数器值最低的项目）	考虑时间局部性	实现成本高，因为每次访问都要更改计数器
Approximating LRU（近似LRU）	将被访问的项目做标记（例如将页表项中的accessed bit置1），定期（例如每100ms）清除所有标记（accessed bit置0），替换掉首个没有标记的项目	降低实现成本	清理标记的周期参数影响命中率 （但仍为主流实现）
考虑脏页的近似LRU（适用于交换）	在LRU的基础上优先选择干净的（即没有被修改过的）页来替换，修改过的页写回磁盘需要额外开销	考虑IO开销	与近似LRU类似

5.3.4 页错误

Page fault分为几种：

• Hard page fault：当内存页不在物理内存中，需要从磁盘中换入
• Soft page fault：当内存页在物理内存中，但不在虚拟内存中，需要建立映射关系（例如刚刚malloc分配但没有映射的内存）
• Segment fault：当尝试访问一个不在虚拟内存中的地址

5.4 关于内存虚拟化的其他机制

• Lazy allocation：使用brk或者sbrk后不立即分配内存，而只是修改program break的位置，直到使用到没分配的内存的时候，触发page fault时才分配
• Zero fill on demand：初始化全0大内存区域的时候，不立即更改内存，而是将提前准备好的全0区域返回，如果进程尝试写入该区域，触发page fault，才进行实际分配
• Copy-on-write fork：fork时，将产生的子进程的虚拟页先指向父进程的物理页，同时将二者的权限改为只读，当二者之一尝试写内存的时候触发page fault，再实际分配子进程的物理页并修改页表
• Demand paging：加载程序的时候不加载全部代码和数据，而是等到实际使用的时候才按需从磁盘加载对应部分
• Prefetching：当代码页被访问时，认为下一代码页也即将被访问，预先调取该页
• 聚集写入：页面换入磁盘的时候，可以一次将一组页都写入，节省IO成本
• Memory mapped IO（或memory mapped files）: 将IO设备的寄存器或者文件映射到内存中进行读写，当然这一过程也是lazy的，先建立映射关系，等到实际读写的时候才真正操作内存

注：本文省略了该书17章的内存空闲空间管理相关内容。

6 并发

在多线程用户程序中，（a）线程被打断的位置不定、线程被调度的顺序不定，线程共享地址空间（和地址空间里的数据），因此造成运行结果的不确定；（b）线程之间有一定的先后运行的逻辑，一个线程需要等待另一个线程完成某个动作才能开始。按照期望完成线程间的这两种交互所用到的机制就是同步机制。（6.1-6.2）

另一方面，在操作系统内核设计中，也要考虑并发，这主要来自于多核（multicore）处理器的广泛使用；当操作系统内核在多个CPU核心上同时执行任务（如系统调用），这些内核线程也共享数据，也需要内核同步机制来管理线程。（6.3）

6.1 线程

进程的观点是，一个被加载到内存中的程序，拥有自己的虚拟地址空间，和单一的执行点（表现为一个程序计数器PC），而线程（thread）则拥有多个执行点（每个线程一个PC），但所有线程共用一个虚拟地址空间，因此所有线程共享资源和数据。

相比于进程，线程有如下特点：

• 调度单位由进程变成了线程；
• 每个线程拥有一个存储线程控制信息的数据结构TCB（thread control block）；
• 每个线程拥有一个对应的栈（用户空间）；
• 当发生上下文切换的时候（线程到内核或内核到线程），将状态寄存器保存到线程的TCB/从线程TCB恢复状态寄存器；

线程由进程创建、控制和回收。在Unix/Linux中，pthread库（POSIX线程库）中线程相关的API有：

• pthread_create(thread_pointer, attr, func, args)：使用thread_pointer表示创建的线程，设置线程属性attr，线程开始于func函数，使用args作为参数。
• pthread_join(thread_pointer, return_value)：等待thread_pointer返回，返回值存储在return_value中。

6.2 线程的同步

6.2.1 线程同步机制

线程中存在的同步问题是：

• 线程之间共享资源和数据，而线程随时可以被打断，下一个被调度的线程不能提前预知，例如：可能出现线程A在对变量进行某一指令（例如判断）后立刻被打断，线程B被调度，修改了该变量，导致A的判断失效；这个变量是共享资源，访问这个变量的代码区域称为critical section（常译为“临界区”，但直译是“重要部分”），多个线程同时进入critical section的情况被称为race condition（常译为“竞态条件”，但直译是“竞争情况”），因此造成了不确定性（indeterministic）。
• 一个线程必须等待另一个线程完成或者达到某种条件后才可以被调度，例如：在网络包处理程序中，需要等待缓冲区中有数据，才能调用线程将数据读取，或者是处理线程需要等待读取线程完成后，才能被调度。

针对第一种问题，最符合直觉的想法就是引入一种互斥（mutual exclusion, mutex）锁（lock）机制，当一个线程进入critical section时，阻止其他线程进入；对于第二种问题，最符合直觉的想法则是使用条件变量（condition variable），线程在条件变量符合预期时才继续进行，另外的线程则负责控制条件变量的值。

pthread库中关于互斥锁的API有：

• pthread_mutex_init(lock_pointer, attr)：初始化互斥锁。
• pthread_mutex_lock(lock_pointer)：尝试加锁；成功加锁后才会进行下一步，失败会停在此处（自旋或休眠）直到成功。
• pthread_mutex_destroy(lock_pointer)：销毁锁。
• pthread_mutex_trylock(lock_pointer)：尝试加锁，若成功加锁进行下一步，失败会返回错误并进行下一步。
• pthread_mutex_timedlock(lock_pointer, timeout)：尝试加锁，若成功加锁进行下一步，失败会停在此处（自旋或休眠）直到成功或超时（取决于哪个先发生）。

pthread库中关于条件变量的API有：

• pthread_cond_init(cond_pointer)：初始化条件变量。
• pthread_cond_wait(cond_pointer, mutex_pointer)：等待条件，并且在等待时睡眠，睡眠时释放互斥锁，唤醒时获得互斥锁。
• pthread_cond_signal(cond_pointer)：发出信号声明条件已经满足。
• pthread_cond_destroy(cond_pointer)：销毁条件变量。

6.2.2 互斥锁实现策略发展线索

名称	细节	演化	缺点
Naive自旋锁（spinlock）	使用TestAndSet原子交换指令实现自旋和原子修改		性能开销大，但在多CPU上开销低；公平性低，导致饿死
放弃CPU	在自旋发生的时候，deschedule自身进程	降低等待开销，提高公平性	自旋过多的时候上下文切换开销大
Bakery锁	当需要等待锁的时候，将当前ticket值加1并作为自己的ticket，当锁被释放时turn值加1，ticket=turn的线程运行	提高公平性，解决饿死问题	自旋过多的时候上下文切换开销大
休眠/唤醒（futex）	当需要等待锁的时候，进入休眠并进入队列，当锁被释放的时候唤醒休眠队列中的一个线程	降低等待和上下文切换的开销	可能产生其他竞争
【杂合策略】两阶段锁（Dahm lock）	第一阶段先自旋等待锁，一段时间如果没有获得锁，进入第二阶段，即休眠等待唤醒	结合两种方式的优点	过程较复杂（但是是Linux锁采用的方法）

6.2.3 条件变量的使用注意

该书第30章提到，一个典型的条件变量使用过程应当是：

// WAIT 
mutex_lock(&m); // mandatory
while (var==0){ // optional
cond_wait(&c, &m);
}
mutex_inlock(&m); // mandatory

//SIGNAL
mutex_lock(&m); // optional 
var = 1;
cond_signal(&c); 
mutex_unlock(&m); // optional

在使用wait的时候前后必须加锁，并且建议使用while循环检测目标变量时候符合条件；而signal则是建议加锁。

使用wait前后必须加锁的原因在于wait本身会休眠释放锁并在唤醒时获得锁，来防止休眠时产生的race condition。

6.2.4 并发中的问题：非死锁与死锁

首先，无论是死锁还是非死锁问题，产生的根本原因都是线程的调度时机和顺序任意：随时可能被打断、调度到的线程无法预知。

并发问题中的非死锁问题，即违反原子性和违反顺序（这两种占到非死锁问题的97%），可以分别通过锁（强制critical section的原子性）和条件变量（约定执行顺序）解决。

并发问题中另一类则是死锁问题，即线程间循环等待资源的释放。死锁（deadlock）的产生原因是大型代码中，组件间有强相互依赖，并且模块化的编程原则和锁之间并不契合。产生死锁的条件有4个：互斥（使用互斥锁，抢到资源的线程会阻止其他线程）、拥有并等待（线程有部分资源，但又在等待其他资源）、非抢占（已经获得的资源不能被抢占）、循环等待（存在一个环路，环路上每个线程拥有下一线程等待的某种资源）。

针对这四个条件，有4种预防方案：顺序抢锁（所有线程都根据某种偏序获得锁），原子抢锁（当一个线程开始抢锁，它会不被打断地运行至抢锁完成），放弃已有锁（如果不能抢到所有需要的锁，那么就放弃已经抢到的锁，但是会产生活锁/livelock问题，即线程间一直互相测试并放弃锁），使用无等待数据结构。

还有针对死锁的2种避免方案：调度避免（按照线程对锁的需求进行聪明的线程调度），银行家算法（线程需要说明对各类资源的需求量，如果都符合，才会给予对应资源，否则等待至资源被释放）。

6.3 Linux内核同步原语

除了线程库中，需要有相关的手段来维持线程间的同步。在内核中，也需要有同步机制来维持内核对系统资源的管理和对共享数据的正确使用，比如：

（摘自MIT6.S081课）如果系统调用并行的运行在多个CPU核上，那么它们可能会并行的访问内核中共享的数据结构，例如proc（进程控制块PCB）、ticks等。当并行的访问数据结构时，例如一个核在读取数据，另一个核在写入数据，我们需要使用一些机制来协调对于共享数据的更新，以确保数据的一致性、确保共享的数据是正确的。

这些同步机制在Linux中称为同步原语。

名称	描述	库名和函数	范围
Per-CPU variables 每CPU变量	在CPU之间复制数据结构。将该变量为每个CPU复制一个副本，副本之间相互独立	include\linux\percpu.h，DECLARE_PER_CPU(type, name)、alloc_percpu(type)、free_percpu(pointer)	All CPUs
Atomic operation 原子操作	对一个计数器原子地“读-修改-写”的指令。 原子操作可以保证指令以原子的方式执行，执行过程不被打断。它通过把读取和修改变量的行为包含在一个单步中执行，从而防止了竞争的发生。	atmoic_ 开头的系列函数	All CPUs
Memory barrier 内存屏障	避免指令重新排序。保证编译程序让放在屏障操作之前的汇编指令执行完后才执行之屏障后的指令。	mb()、rmb()、wmb()、smp_mb()、smp_rmb()、smp_wmb() ，对应汇编级别的ifence	Local CPU
Spinlock 自旋锁	加锁时忙等待（见6.2.2）	spin_lock_init()、spin_lock()、spin_unlock()、spin_unlock_wait()、spin_is_lock()、spin_trylock()	All CPUs
Semaphore 信号量	加锁时阻塞等待（见6.3.1）	include/asm-i386/semaphore.h，sem_init()、sem_post()、sem_wait()	All CPUs
Seqlock 顺序锁	基于访问计数器的锁 （见6.3.2）	write_seqlock、write_sequnlock、read_seqbegin等	All CPUs
Local interrupt disabling 禁止本地中断	禁止单个CPU上的中断处理。即使当硬件设备产生了一个IRQ信号时，中断禁止也让内核控制路径继续执行。	local_irq_disable()、local_irq_enable()	Local CPU
Local softirq disabling 禁止本地软中断	禁止单个CPU上的可延迟函数处理。在由内核执行的几个任务之间有些不是紧急的的，在必要情况下它们可以延迟一段时间。禁止在那个CPU上的软中断，可以禁止可延迟函数的执行。	local_bh_disable()、local_bh_enable()	Local CPU
RCU（Read-Copy Update）	通过指针而不是锁来访问共享数据结构。（见6.3.3）	rcu_read_lock()、rcu_read_unlock()	All CPUs

6.3.1 Semaphore

信号量的相关操作有：

• sem_post()：申请资源；信号量的值减1，若为负（说明资源不足）则休眠。
• sem_wait()：释放资源；信号量的值加1，若为负（说明有线程在等待）则唤醒一个休眠的。

信号量可以用作：

• 锁：初始值为1，说明可用资源为1个，当加锁后，值为0。
• 条件变量：初始值为0，wait后为-1，说明条件不满足，当signal后为0，说明条件满足。
• 计数器：初始值为可用资源数。

6.3.2 Seqlock

Seqlock初始值为0，

• 对于writer，若为奇数等待，偶数则获取锁，获取锁的时候加1，释放时仍加1。
• 对于reader，若为奇数等待，偶数则读取。

这样做可以使得当writer写时，与其它线程互斥（看到此时是奇数则不会获得锁），而在reader读时，可以有多个reader进入（此时为偶数说明没有在写）。

6.3.3 RCU

在一个对象被更改后的一段时间内，保留其副本一段时间。适用于读多写少的情况。

• 对于reader，直接读取。
• 对于writer，先写更改后的数据到新的地址，然后等待旧的数据没有reader在使用（即grace period后），再修改指针到新的地址。
• 这样做，reader读取的可能是旧版本的数据。但整个过程不需要加锁

注：本文省略了该书第29章关于并发数据结构（包括sloopy counter和可扩展并发队列）的内容。

7 持久存储虚拟化

操作系统将物理资源抽象成虚拟资源，例如将内存抽象为虚拟内存、CPU和内存抽象为进程；而对于磁盘，操作系统则提供文件这一抽象。

（摘自MIT6.S081课）文件是磁盘的抽象。应用程序不会直接读写挂在计算机上的磁盘本身，并且在操作系统中这也是不被允许的。在Unix中，与存储系统交互的唯一方式就是通过文件：可以对文件命名，读写文件等等；在这背后，操作系统会决定如何将文件与磁盘中的块对应，确保一个磁盘块只出现在一个文件中，并且确保用户A不能操作用户B的文件。

用单一CPU抽象出无限个vCPU采用的是时分复用（time sharing），而用单一磁盘抽象出多个文件则是空分复用（space sharing）。

文件系统的目标是使用下层的持久存储（persistent storage）设备作为资源，为上层提供文件抽象和与文件相关的读写操作。

7.1 抽象：文件和目录

文件是一个线性的字节数组。文件系统中，一个文件抽象对应一个inode，inode由inode号（inumber）标识，inode包含（一级或多级）索引，这些索引直接或间接指向文件实际对应的那些数据块。

目录包含若干个文件或下级目录。文件系统中，一个目录抽象也对应一个inode，也有相应的inumber，inode包含索引，这个索引指向目录数据块，目录数据块包含“所含文件或下级目录的名称->所含文件或下级目录的inode”的映射列表。

最高级的目录是根目录，这个目录包含的文件或下级目录递归地包含文件系统中所有的文件或目录数据。根目录的inode号应当是周知的，因此从根目录（的inode）开始，可以查找任何文件系统中的文件。

Unix文件系统的API如下：

• open：从根目录开始，递归查找（或创建）指定文件路径，然后返回文件描述符fd（文件描述符由进程私有）
• read：给定文件描述符，读取指定长度的数据，并且隐式更新offset（offset由操作系统跟踪，与文件描述符绑定，即系统跟踪当前进程打开文件下一个读写操作发生的位置）
• write：给定文件描述符，写入指定长度的数据（到内存buffer中，并在合适的时候写回磁盘），并且隐式更新offset
• lseek：给定文件描述符，用参数指定的值（和方式）修改offset
• fsync：立即写入文件到磁盘（write不会立即写到磁盘），写入成功后才返回
• link(path1,path2)：创建硬连接，实际上是在path2目录的映射列表中创建一个新条目，并将该条目的inode号指向path1文件的inode，并增加inode中的引用计数
• unlink：删除文件，实际上是删除了当前目录中该文件与inode之间的映射条目，减少inode中的引用计数，注意inode和文件数据只有在引用计数为0的时候才会真正删除
• rename：重命名文件
• stat/fstat：查看文件元数据
• mkdir：创建目录
• opendir/readdir/closedir：打开/读取/关闭目录
• rmdir：删除空目录
• mkfs：创建文件系统
• mount：挂载文件系统，实际上是将目录树复制粘贴

此外还有创建符号链接（没有接口，但可以用“ln -s”命令），符号链接本质上是一个特殊文件，指向一个已经存在的文件。

7.2 存储设备：磁盘

7.2.1 外部设备

一个标准的外部设备包括硬件接口和内部实现两个部分，接口上包含一系列寄存器，用于与系统交换状态、命令和数据，内部实现则取决于硬件本身，通常包含硬件自己的CPU、内存等芯片。

硬件与系统的交互方式分为：轮询（polling, CPU询问硬件是否有数据要传输）、中断（interrupt，硬件向CPU发出中断请求）、杂合（先轮询后中断）、DMA（特殊的硬件，用于将硬件数据直接复制到内存中不需要CPU参与，完成后发出中断）。

设备与系统通信的方法有：特权指令（使用in/out特权指令与硬件传输数据）、内存映射IO（MMIO，设备直接映射到虚拟内存中）

设备通过一系列抽象接口连接到应用程序，例如文件系统栈中，应用程序使用文件系统提供的POSIX API（如7.1中提到的），文件系统使用操作系统的通用块接口负责无视设备细节的数据块读写，而操作系统则需要设备驱动提供的具体块接口与特定硬件交互。

7.2.2 磁盘

7.3 文件系统实现方案

VSFS

FFS

LFS

Linux的方案：Ext3/4

8 难度升级：多核心

多核心调度

多核心并发

参考
https://www.jianshu.com/p/673c9e4817a8
https://zhuanlan.zhihu.com/p/327860921
https://blog.csdn.net/Apollon_krj/article/details/54565768
https://github.com/huihongxiao/MIT6.S081
https://pdos.csail.mit.edu/6.828/2020/schedule.html
https://blog.csdn.net/don_chiang709/article/details/89373337