参考：

• 操作系统导论

---

操作系统介绍

程序运行时会发生什么——执行指令。

处理器从内存中获取（fetch）一条指令，对其进行解码（decode），然后执行它。完成这条指令后，处理器继续执行下一条指令。

实际上，有一类软件负责让程序运行变得容易（甚至允许你同时运行多个程序），允许程序共享内存，让程序与设备交互等工作。这类软件称为操作系统（OperatingSystem, OS），它们负责确保系统既易于使用又正确高效地运行。

操作系统使用虚拟化（virtualization）技术，将物理资源转换为更通用更强大且易于使用的虚拟形式。

为了让用户可以告诉操作系统作什么，操作系统提供了一些接口（API）。实际上，典型的操作系统会提供几百个系统调用（system call），让应用程序调用。有时也会说操作系统为应用程序提供了一个标准库（standard library）。

因为虚拟化让多个程序运行（共享 CPU），让多个程序可以同时访问自己的指令和数据（从而共享内存），让多个程序访问设备（从而共享磁盘），操作系统有时被称为资源管理器。每个 CPU、内存和磁盘都是系统的资源（resource）。

虚拟化CPU

虚拟化 CPU，即系统拥有非常多的虚拟 CPU 的假象，操作系统负责提供这种假像，从而让许多程序看似同时运行。

但一次运行多个程序会引发各种问题。

虚拟化内存

现代机器提供的物理内存（physical memory）模型非常简单。内存就是一个字节数组。要读取内存，必须指定一个地址，才能访问在那里的数据。写入或更新同理。

程序运行时，需要访问内存。程序将所有数据结构保存在内存中，并通过各种指令来访问它们。不要忘记，程序的每个指令都在内存中，因此每次读取指令都会访问内存。

操作系统虚拟化内存，每个进程访问自己的私有虚拟地址空间（virtual address space），它以某种形式映射到机器的物理内存上。

并发

并发并不局限于操作系统，现代多线程（multi-threaded）程序也存在相同的问题。

如果同一个内存空间中有很多并发执行的线程，如何构建一个正确工作的程序？操作系统需要什么原语？硬件应该提供哪些机制，如何利用它们来解决并发问题。

持久性

在内存中，数据容易丢失。因此，我们需要硬件和软件来持久地存储数据。

硬件以某种输入输出设备的形式出现。

操作系统中管理磁盘的软件通常称为文件系统，它负责将用户创建的文件存储在磁盘上。

文件系统是操作系统的一部分，负责管理持久的数据。持久性需要哪些技术才能正确地实现？需要哪些机制和策略才能高性能地实现？面对硬件和软件故障，可靠性如何实现？

为了完成持久化，程序向操作系统发出 3 个调用。这些系统调用被转到文件系统部分，然后处理这些请求，并向用户返回某种错误。

• open() 调用，打开文件并创建它。
• write() 调用，将数据写入文件。
• close() 调用，关闭文件。

设计目标

一个最基本的目标，是建立一些抽象，让系统易于使用。抽象对我们在计算机科学中做的每件事都很有帮助。抽象使得编写一个大型程序成为可能，将其划分为小而且容易理解的部分。

一个目标是提供高性能，最小化操作系统的开销。

另一个目标是在应用程序之间以及在操作系统和应用程序之间提供保护。因为我们希望同时运行多个程序，所以要确保一个程序（偶然或恶意）不会损害其他程序，当然也不能损害操作系统。保护是操作系统基本原理之一的核心，这就是隔离（isolation）。让进程间彼此隔离是保护的关键。

操作系统必须不间断运行。当他失效时，系统上运行的所有应用程序也会失效。因此操作系统力求提供高度的可靠性。

简单历史

• 早期操作系统：只是一些库。
• 超越库：保护
• 多道程序：微型计算机
• 摩登时代：个人计算机

在操作系统的历史中，UNIX 的重要性举足轻重。随着所有权和利润问题，Linux 诞生了，它是免费且开源的。

---

第一部分：虚拟化

---

进程的抽象

进程就是运行中的程序。程序本身是没有声明周期的，它只是村在磁盘上的一些指令（数据）。是操作系统让这些字节运行起来，让程序发挥作用。

一个正常的系统可能有上百个进程同时在运行。

虽然只有少量的物理 CPU 可用，但是操作系统如何提供有无数个 CPU 可用的假想？

操作系统通过虚拟化 CPU 来提供这种假象。通过让一个进程只运行一个时间片，然后切换到其他进程，操作系统提供了存在多个虚拟 CPU 的假象。这就是时分共享（time shariing），允许用户运行多个并发进程，潜在的开销就是性能损失。

要实现好 CPU 的虚拟化，操作系统就需要一些低级机制和一些高级智能。

抽象的进程

操作系统为正在运行的程序提供的抽象，就是所谓的进程（process）。

为了理解构成进程的是什么，必须理解它的机器状态（machine state）：程序在运行时可以读取或更新的内容。

进程的机器状态有一个明显组成部分，就是它的内存，指令和正在读写的数据也在内存中。进程可以访问的内存（地址空间，address space）是该进程的一部分。

进程的机器状态的另一部分是寄存器。许多指令明确地读取或更新寄存器，它对执行该进程很重要。

进程 API

所有现代操作系统都以某种形式提供这些 API：

• 创建（create）：创建新进程的方法。
• 销毁（destroy）：强制销毁进程的接口。
• 等待（wait）：某种等待接口。
• 其他控制（miscellaneous control）：如暂停和恢复等。
• 状态（status）：获取进程信息的接口。

进程创建的细节

操作系统如何启动并运行一个程序？进程创建实际如何进行？

操作系统运行程序必须做的第一件事是将代码和所有静态数据加载到内存中，加载到进程的地址空间中。

在运行任何程序之前，操作系统显然必须做一些工作，才能将重要的程序字节从磁盘读入内存。

将代码和数据加载到内存后，操作系统在运行此进程前还需要执行一些操作。必须为程序的运行时栈（run-time stack）分配一些内存。（C 程序使用栈存放局部变量、函数参数和返回地址。）

操作系统也可能会为程序的堆（heap）分配一些内存。（C 程序使用堆显式请求动态分配数据。）

操作系统还将执行一些其他初始化任务，特别是与 IO 相关的任务。（例如，在 UNIX 系统中，默认情况下每个进程都有 3 个打开的文件描述符，用于标准输入、输出和错误。）

通过将代码和静态数据加载到内存中，通过创建和初始化栈以及执行 IO 相关工作，操作系统终于为程序执行搭建好了舞台。然后，它启动程序，在入口处（main()）运行。通过跳转到主例程，操作系统将 CPU 的控制权转移到新创建的进程中，从而程序开始执行。

进程状态

进程可以处于以下三种状态：

• 运行（running）：在运行状态下，进程正在处理器上运行。这意味着它正在执行指令。
• 就绪（ready）：在就绪状态下，进程已准备好，但由于某种原因，操作系统选择不在此时运行。
• 阻塞（blocked）：在阻塞状态下，一个进程执行了某种操作，直到发生其他时间时才会准备运行。（如进程向磁盘发起了 IO 请求，或等待网络数据包。）

数据结构

操作系统是一个程序，和其他程序一样，它有一些关键的数据结构来跟踪各种相关的信息。例如，为了跟踪每个进程的状态，操作系统可能会为所有就绪的进程保留某种进程列表，以及跟踪当前正在运行的一些附加信息。操作系统还必须以某种方式跟踪被阻塞的进程，当 IO 事件完成时，操作系统应确保唤醒正确的进程，让它准备好再次运行。

除了上面的三种状态之外，有时系统还有一个初始状态（initial）和进程可以处于已退出但尚未清理的最终状态（final）——在基于 UNIX 的系统中称为僵尸进程。最终状态非常有用，因为它允许其他进程（通常是父进程）检查进程的返回码，并查看刚刚完成的进程是否成功执行。完成后，父进程将进行最后一次调用，以等待子进程的完成，并告诉操作系统它可以清理这个正在结束的进程的所有相关数据结构。

---

进程API

本章将讨论 UNIX 系统中的进程创建，即通过 fork() 和 exce()。进程还可以通过调用 wait() 来等待其创建的子进程执行完成。

fork系统调用

系统调用 fork() 用于创建新进程。

在 UNIX 系统中，要操作某个进程，就要通过 PID 来指明。通过 fork 新创建的进程称为子进程，原进程称为父进程。

子进程并不是完全拷贝父进程。具体来说，虽然它拥有自己的地址空间、寄存器、程序计数器等，但他们从 fork 返回的值不同。父进程获得的返回值是子进程的 PID，而子进程获得的返回值是 0。

wait系统调用

有时候父进程需要等待子进程执行完毕，这项任务由 wait() 系统调用。

exec系统调用

系统调用 exec() 可以让子进程执行与父进程不同的程序。

为什么这样设计API

事实证明，这种分离 fork() 及 exec() 的做法在构建 UNIX shell的时候非常有用，因为这给了 shell 在 fork 之后 exec 之前运行代码的机会，这些代码可以在运行程序前改变环境，从而让一系列有趣的功能很容易实现。

---

受限直接执行机制

虚拟化 CPU 的基本思想很简单：运行一个进程一段时间，然后运行另一个进程，如果轮换。

然而，构建这样的虚拟化机制存在一些挑战。第一个是性能：如果不增加系统开销的情况下实现虚拟化？第二个是控制权：如何有效地运行进程，同时保留对 CPU 的控制？在保留控制权的同时获得高性能，这是操作系统的主要挑战之一。

基本技巧：受限直接执行

直接运行（direct execution），直接在 CPU 上运行程序即可。

如果对运行程序没有限制，操作系统将无法控制任何事情。

受限直接执行（limited direct execution）。

问题1：受限制的操作

直接执行的明显优势是快速。该程序直接在硬件 CPU 上运行，因此执行速度与预期的一样快。如果进程希望执行某种受限操作，该怎么办？

采用受保护的控制权转移。硬件通过提供不同的执行模式来协助操作系统。

• 在用户模式（user mode），应用程序不能完全访问硬件资源，运行的代码会受到限制。
• 在内核模式（kernel mode），操作系统可以访问机器的全部资源，运行的代码可以做它喜欢的事，包括特权操作。

如果用户希望执行某种特权操作，应该怎么做？为了实现这一点，硬件提供了用户程序执行系统调用的能力。系统调用允许内核小心地向用户程序暴露某些关键功能（如访问文件系统、创建和销毁进程、与其他进程通信，分配更多内存等）。

要执行系统调用，程序必须执行特殊的陷进指令（trap）。该指令跳入内核并将特权级别提升到内核模式。一旦进入内核，系统就可以执行任何需要的特权操作。完成后，操作系统调用一个特殊的从陷进返回指令（return-from-trap）。该指令返回到发起调用的用户程序中，同时将特权级别降低，回到用户模式。

执行陷阱时，硬件需要小心，因为它必须确保存储足够的调用者寄存器，以便在操作系统发出从陷阱返回指令时能够正确返回。

陷阱如何知道在操作系统内运行哪些代码？内核必须谨慎地控制在陷阱上执行的代码。

内核通过在启动时设置陷阱表（trap table）来实现。

问题2：在进程之间切换

直接执行的另一个问题是实现进程之间的切换。

操作系统如何重新获得 CPU 的控制权，以便于它可以在进程之间切换？

协作方式：等待系统调用

早期的一些操作系统采用称为协作（cooperative）的方式。在此方式下，操作系统相信系统的进程会合理运行。运行时间过长的进程被假定会定期放弃 CPU，以便操作系统可以运行其他任务。

大多数进程通过进行系统调用，将 CPU 的控制权转移给操作系统。

操作系统通常必须处理不当行为，这些程序通过恶意或不小心，尝试做某些不应该做的事情。

如果应用程序执行了某些非法操作，也会将控制权转移给操作系统。

因此，在协作调度系统中，操作系统通过等待系统调用，或某种非法操作发生，从而重新获得 CPU 的控制权。但这种方式太被动了！

非协作方式：操作系统进行控制

事实证明，没有硬件的额外帮助，如果进程拒绝进行系统调用，从而将控制权交还给操作系统，操作系统无法做任何事。唯一的解决方法是重启机器。

重启很有用，因为它会让软件回到已知的状态。重启还可以回收旧的或泄露的资源，否则这些资源可能很难处理。

如何在没有协作的情况下获得控制权？答案是时钟中断（timer interrupt），该硬件功能对于帮助操作系统维持机器的控制权至关重要。

时钟设备可以编程为每隔几毫秒产生一次中断。产生中断时，当前正在运行的进程停止，操作系统中预先配置的中断处理程序（interrupt handler）会运行。此时，操作系统重新获得 CPU 的控制权。

操作系统必须启动时钟，这是一项特权操作。

硬件在发生中断时，要为正在运行的程序保存足够的状态，以便随后从陷阱返回指令能够正确恢复正在运行的程序（各种寄存器）。

保存和恢复上下文

操作系统必须决定：是继续运行当前进程，还是切换到另一个进程？这个决定是由调度程序做出的。

如果决定进行切换，OS 就会执行一些代码，即所谓的上下文切换（context switch）。操作系统要做的就是为当前正在执行的进程保存一些寄存器的值，并为即将执行的进程恢复一些寄存器的值。

为了保存当前正在运行的进程的上下文，操作系统会执行一些底层汇编代码，来保存通用寄存器、程序计数器，以及进程的内核栈指针，然后恢复寄存器、程序计数器、并切换内核栈，供即将运行的进程使用。

上下文切换需要多长时间？现代系统的性能在具有 2GHz 处理器上的性能可以达到亚微妙级。

---

进程调度

介绍一系列调度策略（scheduling policy 或 discipline）。

我们应该如何开发一个考虑调度策略的基本框架？什么是关键假设？哪些指标非常重要？那些基本方法已经在早期的系统中使用？

工作负载

系统中运行的进程统称为工作负载（workload）。工作负载了解的越多，你的策略就越优化。

调度指标

指标用来衡量某些东西。一些指标：如性能、公平和响应时间等。

先进先出

先进先出（FIFO）调度算法，先到先服务。

先进先出有一个问题，那就是护航效应。一些耗时较少的潜在消费者排在了重量级消费者之后，等待时间就会特别长。

最短任务优先

最短任务优先（SJF）调度算法，先运行最短的任务，然后次短的任务，如此下去。

最短完成时间优先

几乎所有现代化的调度程序都是抢占式的（preemptive），非常愿意停止一个进程以运行另一个进程。

向 SJF 添加抢占，称为最短完成时间优先（STCF）或抢占式最短作业优先（PSJF）调度程序。

轮转调度

轮转调度（Round-Robin）。基本思想很简单，RR 在一个时间片内运行一个工作，然后切换到运行队列中的下一个任务，而不是运行一个任务直到结束。它反复执行，直到所有任务完成。因此 RR 有时被称为时间切片。

请注意，时间片长度必须是时钟中断周期的倍数。如果时钟中断是每 10ms 中断一次，则时间片可以是 10ms、20ms等。

时间片太短，突然上下文切换的成本将影响整体性能。因此，系统设计者需要权衡时间片的长度，使其足够长，以便摊销（amoritize）上下文切换成本，而又不会是系统不及时响应。

当系统有某些操作有固定成本时，通常会使用摊销技术。通过减少成本的频度，系统的总成本就会降低。例如，如果时间片设置为 10ms，而上下文切换需要 1ms，那么浪费大约 10% 的时间用于上下文切换。如果要摊销这个成本，可以把时间片增加到 100ms，这样只有 1% 的时间用于上下文切换，因此时间片带来的成本就被摊销了。

重叠（overlap）可以最大限度地提高系统的利用率。如执行磁盘 IO 或发送消息到远程机器时，开始操作然后切换到其他工作都是一个好主意，这也提高了系统的整体利用率和效率。

综合 IO

调度程序显然要在工作发起 IO 请求时做出决定，因为当前正在运行的作业在 IO 期间不会使用 CPU，它被阻塞等待 IO 完成。因此，这时调度程序应该在 CPU 上安排另一项工作。

调度程序还必须在 IO 完成时做出决定。发生这种情况时，会产生中断，操作系统运行并将发出 IO 的进程从阻塞状态移回就绪状态。

---

多级反馈队列调度

多级反馈队列（Multi-level Feedback Queue，MLFQ）调度方法。

多级反馈队列是用历史经验预测未来的一个典型的例子，操作系统中有很多地方采用了这种技术。

MLFQ的基本规则

介绍多级基本队列背后的基本算法。

MLFQ 中有许多独立的队列，每个队列有不同的优先级。任何时刻，一个工作只能存在于一个队列中。它总是执行优先级较高的工作。

当然，每个队列中可能会有多个工作，因此具有同样的优先级。在这种情况下，就需要对这些工作采用轮转调度。

因此，MLFQ 调度策略的关键在于如何设置优先级。比如，如果一个工作长时间占用 CPU，MLFQ 会降低其优先级。一个工作不断放弃 CPU 去等待键盘输入，这是交互型进程的可能行为，MLFQ 因此会让它保持高优先级。

如何改变优先级

在一个工作的声明周期中，MLFQ 如何改变其优先级。

工作负载：长工作、短工作和有 IO 的工作。

提升优先级

一个简单思路是周期性地提升所有工作的优先级。

更好的计时方式

调度程序应该记录一个进程在某一层中消耗的总时间，而不是在调度时重新计时。

MLFQ的调优及其他问题

一个问题是如何配置一个调度程序，例如，配置多少队列？每一层队列的时间片配置多大？为了避免饥饿问题以及进程行为改变，应该多久提升一次进程的优先级？

有些调度程序将最高优先级队列留给操作系统使用，因此通常的用户工作是无法得到系统的最高优先级的。有些系统允许用户设置优先级（通过 nice 工具）。

---

比例份额调度

比例份额（proportional-share）调度，也成为公平份额调度。确保每个工作获得一定比例的 CPU 时间，而不是优化周转时间和响应时间。

一个例子：彩票调度（lottery scheduling）。

彩票数表示份额

彩票调度背后是一个非常基本的概念：彩票数代表了进程占有的资源的份额。一个进程拥有的彩票数占总彩票数的百分比，就是它占有资源的份额。

彩票调度最精彩的地方在于利用了随机性。

彩票机制

彩票调度提供了一些机制，以不同且有效的方式来调度彩票。

一种机制是利用彩票货币的概念。此方式拥有一组彩票的用户以他们喜欢的某种货币，将彩票分给自己的不同工作。之后操作系统再自动将这种货币兑换为正确的全局彩票。

一种机制是彩票转让。通过转让，一个进程可以临时将自己的彩票交给另一个进程。

一种机制是彩票通胀。利用通胀，一个进程可以临时提升或降低自己拥有的彩票数量。

彩票调度的实现

彩票调度中，最不可思议的，或许就是实现简单。只需要一个不错的随机数生成器来选择中将彩票和一个记录系统中所有进程的数据结构，以及所有彩票的总数。

如何分配彩票

这是一个非常棘手的问题，系统的运行严重依赖于彩票的分配。对于给定的一组工作，彩票分配的问题依然没有最佳答案。

---

多处理器调度

本章将介绍多处理器调度（multiprocessor scheduling）的基础知识。由于本章内容相对较深，建议认真学习并发相关内容后再读。

---

地址空间的抽象

早期系统

从内存来看，早期的机器并没有提供多少抽象给用户。

操作系统曾经是一组函数（库），在内存中（从物理地址 0 开始），然后是程序和剩余的内存。

多道程序和时分共享

由于机器昂贵，人们开始有效地共享机器。因此，多道程序系统时代开启，效率提升了。

但很快，人们开始对机器要求更多，分时系统的时代诞生了，交互性提升了。

多个程序同时驻留在内存中，使保护成为重要问题。

地址空间

操作系统需要提供一个易用的物理内存抽象。这个抽象叫做地址空间（address space），是运行的程序看到的系统中的内存。

一个进程的地址空间包含运行的程序的所有内存状态。如代码、栈和堆。

程序运行时，地址空间的两个区域可能增长或收缩，所以如下这样放置。然而，这种放置方法只是一种约定，如果你愿意，可以用不同的方式安排地址空间。

当我们描述地址空间时，所描述的是操作系统提供给运行程序的抽象。

操作系统如何在单一的物理内存上为多个运行的进程构建一个私有的、可能很大的地址空间的抽象？

当操作系统这样做时，我们说操作系统在虚拟化内存。

隔离式建立可靠系统的关键原则。如果两个实体相互隔离，这意味着一个实体的失败不会影响到另一个实体。操作系统力求让进程彼此隔离，从而防止互相造成伤害。通过内存隔离，进一步确保运行程序不会影响底层操作系统的操作。

目标

操作系统不仅虚拟化内存，还有一定的风格。

虚拟内存的一个主要目标是透明（transparency），程序应该是无感知内存被虚拟化了。

虚拟内存的另一个目标是效率（efficiency），包括时间上（不会使程序运行更慢）和空间上（不需要太多额外的内存）。在实现高效率虚拟化时，操作系统不得不依靠硬件支持，包括 TLB 这样的硬件功能。

虚拟内存的第三个目标是保护（protection）。操作系统应确保进程收到保护，不会影响到其他进程。保护能够在进程之间提供隔离的特性，避免其他出错或恶意进程的影响。

实际上，作为用户级程序的程序员，你所打印出的程序地址都是虚拟地址。只有操作系统，通过精妙的虚拟化内存技术，知道这些指令和数据所在的物理内存的位置。

---

内存操作API

本章介绍 UNIX 操作系统的内存分配接口，操作系统提供的接口非常间件。

关键问题：如何分配和管理内存？

内存类型

在运行一个 C 程序的时候，会分配两种类型的内存。第一种称为栈（stack）内存，它的申请和释放操作是编译器来隐式管理的，所以有时也称为自动内存。

第二种是所谓的堆（heap）内存，其中所有的申请和释放操作都由程序员显式地完成。因为它的显式特点，以及它更富于变化，堆内存对用户和系统提出了更大的挑战。

malloc()调用

malloc() 函数非常简单，传入要申请的堆空间的大小，成功就返回一个指向新申请空间的指针，失败就返回 NULL。

free()调用

事实证明，分配内存是等式的简单部分。知道何时、如何以及是否释放内存是困难部分。要释放不再使用的堆内存，程序员只需调用 free() 函数。

在使用 malloc() 和 free() 时会出现一些常见的错误。

许多新语言都支持自动内存管理。在这样的语言中，当你调用 malloc() 的机制来分配内存时，你永远不需要调用某些东西来释放它。实际上，垃圾收集器（gc）会运行，找出你不需要的内存，替你释放它。

一些常见的问题：

• 忘记分配内存
• 没有分配足够的内存
• 忘记初始化分配的内存
• 忘记释放内存
• 在用完之前释放内存
• 反复释放内存
• 错误地调用 free()

底层操作系统支持

malloc() 和 free() 是库调用，而不是系统调用。它们本身建立在系统调用之上，这些系统调用会进入操作系统，来请求更多内存或者将一些内容释放回系统。

一个这样的系统调用叫做 brk，它被用来改变程序分断（break）的位置：堆结束的位置。另一个系统调用 sbrk 类似。

请注意，你不应该直接调用 brk 或 sbrk。它们被内存分配库使用。建议使用 malloc() 和 free()。

最后，你还可以通过 mmap() 调用从操作系统获取内存。

其他调用

内存分配库还支持一些其他调用。如 calloc 分配内存，realloc() 创建一个新的更大的内存空间，将旧区域复制到其中，并返回新区域的指针。

---

地址转换机制

在实现 CPU 虚拟化时，遵循的一般准则称为受限直接执行（LDE, Limited Direct Execution）。LDE的想法很简单，程序运行的大部分指令直接访问硬件，只有在一些关键点（如系统调用或时钟中断）有操作系统接入来确保“在正确的时间，正确的地点，做正确的事”。为了实现高效和虚拟化，操作系统应该尽量让程序自己运行，同时通过在关键点的及时介入，来保持对硬件的控制。高效和控制是现代操作系统的两个主要目标。

在实现内存虚拟化时，将追求类似的战略，在实现高效和控制的同时，提供期望的虚拟化。高效决定了要利用硬件的支持。控制意味着要确保应用程序只能访问它自己的内存空间。

我们希望虚拟内存有相当的灵活性。程序能够以任何方式访问它的地址空间，从而让系统更容易编程。

关键问题：如何高效、灵活地虚拟化内存？

一种称为地址转换的通用技术，有时被称为基于硬件的地址转换（hardware-based address translation）。它可以看成是受限直接执行这种一般方法的补充。利用地址转换，硬件对每次内存访问进行处理，将指令中的虚拟地址转换为实际存储的物理地址。

当然，仅仅依靠硬件不足以实现虚拟内存，因为它只是提供了底层机制来提高效率。操作系统必须在关键位置介入，设置好硬件，以便完成正确的地址转换。因此它必须管理内存，记录被占用和空闲的内存位置，并明智而谨慎地介入，保持对内存使用的控制。

通过虚拟化，操作系统（在硬件的帮助下）将丑陋的机器现实转化成一种有用的、强大的、易于使用的抽象。

基于硬件的动态重定位

基址加界限机制（base and bound），有时又称为动态重定位（dynamic relocation）。

具体来说，每个 CPU 需要两个硬件寄存器：基址（base）寄存器和界限（bound）寄存器，让我们能够将地址空间放在物理内存的任何位置，同时又能确保进程只能访问自己的地址空间。

进程产生的所有内存引用，都会被处理器通过以下方式转换为物理地址：$ physicaladdress = virtualaddress + base $

由于这种重定位是在运行时发生的，而且我们甚至可以在进程开始运行后改变其地址空间，这种技术一般称为动态重定向。

在早期硬件支持重定位之前，一些系统曾经采用软件重定位的方式。基本技术被称为静态重定位，其中一个名为加载程序（loader）的软件接手将要运行的可执行程序，将它的地址重写到物理内存中期望的偏移位置。

然而，静态重定位有许多问题。最重要的是不提供访问保护，另一个缺点是一旦完成，稍后很难将内存空间重定位到其他位置。

在动态重定向中，只有很少的硬件参与，但获得了很好的效果。一个基址寄存器将虚拟地址转换为物理地址，一个界限寄存器确保这个地址在进程地址空间的范围内。它们一起提供了既简单又高效的虚拟内存机制。

这种基址寄存器配合界限寄存器的硬件结构是芯片中的（每个 CPU 一对）。有时我们将 CPU 的这个负责地址转换的部分统称为内存管理单元。

硬件支持总结

硬件要求	解释
特权模式	以防用户模式的进程执行特权操作
基址/界限寄存器	每个 CPU 需要它们来支持地址转换和界限检查
修改基址/界限寄存器的特权指令	在应用程序运行前，操作系统必须能够设置这些值
注册异常处理程序的特权指令	操作系统必须告诉硬件，如果异常发生，执行哪些代码
能够触发异常	如果进程视图使用特权指令或越界的内存

操作系统的问题

硬件支持使操作系统有了一些必须处理的新问题。

• 在进程创建时，为进程的地址空间找到内存空间。
• 在进程终止时，回收它的所有内存。
• 在上下文切换时，必须保存和恢复基址和界限寄存器。
• 操作系统必须提供异常处理程序，或调用一些函数。

---

分段

你可能已经注意到，栈和堆之间，有一大块空闲空间。

如果我们将整个地址空间放入物理内存，那么这个空闲空间并没有被进程使用，却依然占用了实际的物理内存。因此，简单的通过基址寄存器和界限寄存器实现的虚拟内存很浪费。另外，如果剩余物理内存无法提供连续区域来放置完整的地址空间，进程便无法运行。

这种基址和界限的方式看来并不像我们期望的那样灵活。怎么支持大地址空间，同时栈和堆之间可能有大量空闲空间？

设想一个 32 位（4GB）的地址空间，通常程序只会使用几兆内存，但需要整个地址空间都放在内存中。

泛化的基址和界限

为了解决这个问题，分段（segmentation）的概念应运而生。它的想法很简单，在内存管理单元中引入不止一个基址和界限寄存器对，而是给地址空间内的每个逻辑段一对。一个段只是地址空间里的一个连续且定长的区域，在典型的地址空间里有 3 个逻辑不同的段：代码、栈和堆。分段的机制使得操作系统能够将不同的段放到不同的内存区域，从而避免了虚拟地址空间中未使用的部分占用物理内存。

在这种情况下，内存管理单元中的硬件结构来支持分段，需要一组 3 对基址/界限寄存器。

段错误是指在支持分段的机器上发生了非法的内存访问。有趣的是，即使在不支持分段的机器上，这个术语依然保留。

如果我们试图访问非法的地址（比如它超出了堆的边界），你可以想象发生的情况：硬件会发现该地址越界，因此陷入操作系统，很可能导致终止出错进程。这就是术语恐慌（panic）的来源。

引用哪个段

硬件在地址转换时使用段寄存器。它如何知道段内的偏移量，以及地址引用了哪个段？

一种常见的方式（称为显式），是用虚拟地址的开头几位来标识不同的段。有 3 个段，因此需要两位来标识。

硬件还有其他方无法来决定特定地址在哪个段。在隐式方式中，硬件通过地址产生的方式来确定段。

栈怎么办

栈是反向增长的。

我们需要一点硬件支持，处理基址和界限外，硬件还需要知道段的增长方向（用 1 位区分）。

支持共享

随着分段基址的不断改进，系统设计人员很快意识到，通过再多一点的硬件支持，就能实现新的效率提升。具体来说，要节省内存，有时候在地址空间之间共享某些内存段是有用的。尤其是，代码共享很常见，今天的系统仍在使用。

为了支持共享，需要一些额外的硬件支持，这就是保护位。基本位每个段增加了几位，标识程序是否能够读写该段、或执行其中的代码。通过将代码段标记为只读，同样的代码可以被多个进程共享，而不用担心破坏隔离。

虽然每个进程都认为自己独占这块代码，但操作系统秘密地共享了内存，进程不能修改这些内存，所以假象得以保持。

有了保护位，硬件除了检查虚拟地址是否越界，还需要检查特定访问是否允许。

细粒度和粗粒度的分段

目前我们的例子只有很少的段的系统（即代码、栈和堆）。可认为这种分段式粗粒度的，因为它将地址空间分成较大的、粗粒度的块。

一些早期系统更灵活，允许将地址空间划分为大量较小的段，这称为细粒度分段。

支持许多段需要进一步的硬件支持，并在内存中保存某种段表。这种段表通常支持创建非常多的段。

操作系统支持

分段带来了一些新的问题。

操作系统在上下文切换时应该做什么？各个段寄存器的保存和恢复。

如何管理物理内存的空闲空间？一般会遇到的问题是，物理内存很快充满了许多空闲空间的小洞，因而很难分配给新的段，或扩大已有的段。这个问题被称为外部碎片。

如一个进程需要分配一个 20KB 的段。当前有 24KB 空闲，但并不连续。因此，操作系统无法满足这个 20KB 的请求。

该问题的一种解决方案是紧凑物理内存。重新安排原有的段。但是，内存紧凑成本很高，因为拷贝段是内存密集型的，一般会占用大量的处理器时间。

一种更简单的做法是利用空闲列表管理算法，试图保留大的内存块用于分配。相关的算法有很多种。

---

空闲空间管理

管理空闲空间当然可以很容易。如果需要管理的空间被划分为固定大小的单元，就很容易。如果要管理的空闲空间由大小不同的单元构成，管理就变得困难。容易出现外部碎片问题。

要满足变长的分配请求，应该如何管理空闲空间？什么策略可以让碎片最小化？不同方法的时间和空间开销如何？

底层机制

在深入策略细节之前，先介绍大多数分配程序采用的通用机制。

首先，探讨空间分割与合并的基本知识。

其次，看看如何快速并相对轻松地追踪已分配的空间。

最后，讨论如何利用空闲区域的内部空间维护一个简单的列表，来追踪空闲和已分配的空间。

如果堆中的内存空间耗尽，应该怎么办？最简单的方式就是返回失败。大多数传统的分配程序会从很小的堆开始，当空间耗尽时，再向操作系统申请更大的空间。

基本策略

介绍管理空闲空间的一些基本策略。

• 最优匹配（best fit）：首先遍历整个空闲列表，找到和请求大小一样或更大的空闲块，然后返回这组候选者中最小的一块。简单的实现在遍历查找正确的空闲块时，要付出较高的性能代价。
• 最差匹配（worst fit）：尝试找打最大的空闲块，分割并满足用户需求后，将剩余的块加入空闲列表。既需要遍历整个空闲列表，还会导致过量的碎片。
• 首次匹配（first fit）：找到一个足够大的块，将请求的空间返回给用户。剩余的空闲空间留给后续请求。
• 下次匹配（next fit）：维护一个指针，指向上次查找结束的位置。

其他管理方式

还有一些技术和算法来改进内存分配。

• 分离空闲列表
• 伙伴系统
• 等等

---

分页

操作系统有两种方法来解决大多数空间管理问题。

第一种方法：将空间分割成不同长度的分片，就像虚拟内存管理中的分段。遗憾的是，这个方法存在固有的问题。将空间切成不同长度的分片以后，空间本身会碎片化，随着时间的推移，分配内存会变得比较困难。

第二种方法：将空间分割成固定长度的分片。在虚拟内存中，称这种思想为分页（paging）。分页不是将一个进程的地址空间分割成几个不同长度的逻辑段（即代码、堆、栈），而是分割成固定大小的单元，每个单元称为一页。相应地，我们把物理内存看成是定长槽块的阵列，叫做页帧。

如果通过页来实现虚拟内存，从而避免分段的问题？

页表存在哪里

为了记录地址空间的每个虚拟页放在物理内存中的位置，操作系统通常为每个进程保存一个数据结构，称为页表（page table）。

页表可以变得非常大，没有在内存管理单元中利用任何特殊的片上硬件，来存储当前正在运行的进程的页表，而是将每个进程的页表存储在内存中。

页表中究竟有什么

页表是进程的一种数据结构，用于将虚拟地址映射到物理地址。因此，任何数据结构都可以采用。最简单的形式称为线性页表，就是一个数组。

如：

• 有效位：通常用于只是特定地址转换是否有效。
• 保护位：表明页是否可以读取、写入或执行。
• 存在位：表示该页是在物理存储器还是在磁盘上。
• 脏位：表明页面被带入内存后是否被修改过。
• 参考位：有时用于追踪页是否被访问，也用于确定哪些页很受欢迎。

阅读因特尔架构手册，以获取有关 x86 分页支持的更多详细信息。

分页也会让速度变慢

内存中的页表，它们可能太大了。事实证明，它们也会让速度变慢。

对于每个内存引用，分页都需要我们执行一个额外的内存引用，以便首先从页表中获取地址转换。工作量很大！

现在可以看到。有两个必须解决的实际问题。如果不仔细设计硬件和软件，页面会导致系统运行速度过慢，并占用太多内存。

---

分页中快速地址转换

使用分页作为核心机制来实现虚拟内存，可能会带来较高的性能开销。

如何才能加速虚拟地址转换，尽量避免额外的内存访问？需要什么样的硬件支持？操作系统该如何支持？

想让某些东西更快，操作系统通常需要硬件的帮助。我们要增加所谓的地址转换旁路缓冲存储器（translation-lookaside buffer, TLB），它就是频繁发生的虚拟到物理地址转换的硬件缓存。因此，更好的名称应该是地址转换缓存。

对每次内存访问，硬件先检查 TLB，看其中是否有期望的转换映射。如果有，就完成转换，不用访问页表。TLB 带来了巨大的性能提升。

尽可能地利用缓存

缓存是计算机系统中最基本的性能改进技术之一，一次又一次地用于让常见的情况更快。硬件缓存背后的思想是利用指令和数据引用的局部性。通常有两种局部性：时间局部性和空间局部性。

时间局部性是指，最近访问过的指令或数据项可能很快会再次访问。空间局部性是指，当程序访问内存地址 x 时，可能很快会访问邻近 x 的内存。

硬件缓存，无论时指令、数据还是地址转换，都利用了局部性，在小而快的芯片内存储器中保存一份内存副本。处理器可以先检查缓存中是否存在就近的副本，而不是必须访问内存来满足请求。如果存在，处理器就可以很快地访问它，避免花很多时间来访问内存。

既然缓存这么好，为什么不做更大的缓存？如果想要快速地缓存，它就必须小，因为光速和其它物理限制会起作用。大的缓存注定慢，因此无法实现目的。所以，我们只能用小而快的缓存。剩下的问题就是如何利用好缓存来提升性能。

谁来处理TLB未命中

谁来处理 TLB 未命中？可能有两个答案：硬件或软件（操作系统）。

以前的硬件有复杂的指令集（复杂指令集计算机，CISC），硬件全权处理 TLB。为了做到这一点，硬件必须知道页表在内存中的确切位置，以及页表的确切格式。发生未命中时，硬件会遍历页表，找到正确的页表项，取出想要的转换映射，更新 TLB。一个例子是 x86 架构，它采用固定的多级页表。

更现代的体系结构都是精简指令集计算机（RISC），有软件管理 TLB。发生未命中时，硬件系统会抛出一个异常，这回暂停当前的指令流，提升到内核模式，跳转到陷阱处理程序，查找页表中的转换映射，更新 TLB，并从陷阱返回。

软件管理的方法，主要优势是灵活性：操作系统可以用任意数据结构来实现页表，不需要改变硬件。另一个优势是简单。

复杂和精简指令集

复杂指令集计算（CISC, Complex Instruction Set Computing），倾向于拥有许多指令，每条指令比较强大。

精简指令集计算（RISC, Reduced Instruction Set Computing），它的关键观点是指令集实际上是编译器的最终目标，所有编译器实际上需要少量简单的原语，可以用于生成高性能的代码。尽可能地从硬件中拿掉不必要的东西，让剩下的东西简单、统一和快速。

TLB的内容

典型的 TLB 有 32项、64项或 128项，并且是全相联的。一条 TLB 项内容可能像下面这样：虚拟页号(VPN) | 物理帧号(PFN) | 其他位。硬件并行地查找这些项，看看是否匹配。

上下文切换对TLB的处理

TLB 中包含的虚拟到物理地址的映射只对当前进程有效，对其他进程是没有意义的。所以发生进程切换时，硬件或操作系统必须注意确保即将运行的进程不要误读了之前进程的地址映射。

进程切换时如何管理 TLB 的内容？

一些可能的解决方案：一种方法是：在上下文切换时，简单地清空 TLB。但是，有一定的开销：每次进程运行，当它访问数据和代码页时，都会触发 TLB 未命中。如果操作系统频繁地切换进程，这种开销会很高。

为了减少这种开销，一些系统增加了硬件支持，实现跨上下文切换的 TLB 共享。

TLB替换策略

TLB 和其它缓存一样，需要考虑缓存替换（cache replacement）问题。具体来说，向 TLB 中插入新项时，会替换一个旧项，这样问题就来了：应该替换哪一个？目标当然是减少未命中率，从而改进性能。

一种常见的策略是：替换最近最少使用（LRU, least-recently-used）的项。另一种典型策略是：随机策略。

实际系统的TLB表项

以下示例来自 MIPS R4000，它是一种现代的系统，采用软件管理 TLB。

随机存取存储器（RAM）暗示你访问的任意部分都一样快。虽然一般这样想 RAM 没错，但因为 TLB 这样的硬件/操作系统功能，访问某些内存页的开销较大，尤其是没有被 TLB 缓存的页，可能导致严重的性能损失。

---

分页中较小的表

现在来解决分页引入的第二个问题：页表太大，因此消耗的内存太多。通常系统中每个进程都有一个页表！

如何让页表更小？

更大的页

一种简单的方法减小页表的大小：使用更大的页。

然而，这种方法的主要问题在于，大内存页会导致每页内的浪费，这被称为内部碎片问题。因此，大多数系统在常见的情况下使用相对较小的页大小：4KB（如 x86）或 8KB（如 SPARCv9）。

分页和分段的混合

在生活中，每当有两种合理但不同的方法时，你应该总是研究两者的结合，看看能否两全其美。

将分页和分段相结合，以减少页表的内存开销。

这种方法并非没有问题。首先，它仍然要求使用分段。其次，这种杂合导致外部碎片再次出现。出于这些原因，人们继续寻找更好的方式来实现更小的页表。

多级页表

如何去掉页表中的所有无效区域，而不是将它们全部保留在内存中？将这种方法称为多级页表（multi-level page table）。因为它将线性页表变成了类似树的东西，这种方法非常有效，许多现代系统都用它（如 x86）。

多级页表的基本思想很简单。首先，将页表分成页大小的单元。然后，如果整页的页表项无效，就完全不分配该页的页表。为了追踪页表的页是否有效，使用了名为页目录的新结构。页目录因此可以告诉你页表的页在哪里，或者页表的整个页不包含有效页。

页表的每个部分都可以整齐地放入一页中，从而更容易管理内存。操作系统可以在需要分配或增长页表时简单地获取下一个空闲页。有了多级结构，我们增加了一个间接层，使用了页目录，它指向页表的各个部分。这种间接方式，让我们能够将页表页放在物理内存的任何地方。

多级页表是有成本的。在 TLB 未命中时，需要从内存加载两次，才能从页表中获取正确的地址转换信息。另一个缺点是复杂性，通常我们愿意增加复杂性以提高性能或降低管理费用。

反向页表

在反向页表中，可以看到页表世界中更极端的空间节省。在这里，保留一个页表，其中的项代表系统的每个物理页，而不是有许多页表。页表项告诉我们哪个进程正在使用此页，以及该进程的哪个虚拟页映射到此物理页。

将页表交换到磁盘

到目前为止，我们一直假设页表位于内核拥有的物理内存中。有一些系统将页表放入内核虚拟内存，从而允许系统在内存压力大较大时，将这些页表中的一部分交换（swap）到磁盘。

---

超越物理内存的机制

到目前为止，我们一直假设所有页都常驻在物理内存中。但是，为了支持更大的地址空间，操作系统需要把当前没有在用的那部分地址空间找个地方存储起来。在现代系统中，硬盘满足这个需求。

增加交换空间让操作系统为多个并发运行的进程都提供巨大地址空间的假象。这是现代所有虚拟内存系统都会做的事情。

注意性能问题，交换空间的速率远低于物理内存。

交换空间

在硬盘上开辟一部分空间用于物理页的移入和移出。在操作系统中，一般称之为交换空间（swap space）。因为我们将内存中的页交换到其中，并在需要的时候又交换回去。为了达到此目的，操作系统需要记住给定页的硬盘地址。

存在位

需要在系统中增加一些更高级的机制，来支持从硬盘交换页。通过存在位（present bit）标识页存在于内存上还是硬盘上。

访问不在物理内存中的页，通常称为也错误（page fault）。

页错误

几乎所有的系统都在软件中处理也错误。由于性能和简单的原因，使用操作系统来处理页错误。

如果一个页不存在，它已被交换到硬盘，在处理页错误的时候，操作系统需要将页交换到内存中。

请注意，当 IO 运行时，进程将处于阻塞状态。因此，当也错误正常处理时，操作系统可以自由地运行其他可执行的进程。

内存满了怎么办

交换出不合适的页会导致程序性能上的巨大损失。

页错误处理流程

交换何时真正发生

为了保证有少量的空闲内存，大多数操作系统会设置高水位线和低水位线，来帮助决定何时从内存中清除页。

---

超越物理内存的策略

在内存不够的情况下，由于内存压力迫使操作系统换出一些页，为常用的页腾出空间。操作系统确定要从内存中踢出哪些页，这个由替换策略做出。

缓存管理

由于内存只包含系统中所有页的子集，因此可以将其视为系统中虚拟内存页的缓存（cache）。因此，在为这个缓存选择替换策略时，我们的目标是让缓存未命中（cache miss）最少，即从磁盘获取页的次数最少。或者，让缓存名中（cache hit）最多，即在内存中找到待访问页的次数最多。

在现代系统中，磁盘访问的成本非常高，即使很小概率的未命中也会有很大的性能影响。

最优替换策略

最优替换策略（很难实现），替换内存中在最远将来才会被访问到的页，可以达到缓存为命中率最低。

虽然最优策略不切实际，但作为其他研究的比较者还是非常有用。

先进先出替换策略

先进先出（FIFO）替换策略，实现相当简单。

随机替换策略

随机替换策略，随机选择一个页进行替换，实现也很简单，但在挑选哪个页时不够智能。

最不经常使用替换策略

最不经常使用替换策略（LFU），利用历史数据，替换最不经常使用的页。越近被访问过的页，也许再次被访问的可能性就更大。

近似LRU

从计算开销的角度来看，近似 LRU 更为可行，实际上也是许多现代系统的做法。这个想法需要硬件增加一个使用位（use bit）。系统中的每个页有一个使用位，然后这些使用位存储在某个地方。每当页被应用时，硬件将使用位设置为1.但是，硬件不会清除改位，这由操作系统负责。

考虑脏页

如果页已被修改并因此变脏（dirty），则踢出它就必须将它写回磁盘，这很昂贵。如果它没有被修改（因此是干净的，clean），踢出就没有成本。物理帧可以简单地重用与其他目的而无需额外的 IO。因此，一些虚拟机系统更倾向于踢出干净页，而不是脏页。

为了支持这种行为，硬件应该包括一个修改位（又名脏位，dirty bit）。每次写入页都会设置此位，因此可以将其合并到页面替换算法中。

其他虚拟内存策略

页面替换不是虚拟内存子系统采用的唯一策略（尽管它可能是最重要的）。例如，操作系统还必须决定何时将页载入内存，该策略有时称为也选择策略。

另一个策略决定了操作系统如何将页面写入磁盘。当然，可以简单地一次写出一个。然而，许多系统会在内存中收集一些待完成写入，并以一种更高效的方式将它们写入硬盘。这种行为通常称为聚集写入（分组写入），这是因为硬盘的性质，执行单次大的写操作，比许多小的写操作更有效。

抖动

当内存被超额请求时，操作系统应该做什么？在这种情况下，系统将不断地进行换页，这种情况有时被称为抖动（thrashing）。

目前的一些系统采用更严格的方法处理内存过载。如 Linux 会运行 OOM killer，这个守护进程选择一个内存密集型进程并杀死它，从而以不怎么委婉地方式减少内存。请注意，它虽然减轻了内存压力，但却导致了应用程序不可用。

---

VAX/VMS虚拟内存系统

数字设备公司（DEC）在 1970 年代末推出了 VAX 小型机体系结构，该系统的操作系统被称为 VAX/VMS。

VAX/VMS 操作系统的虚拟内存管理器，它特别干净漂亮。

内存管理硬件

VAX-11 为每个进程提供了一个 32 位的虚拟地址空间，分为 512 字节的页。因此，虚拟地址由 29 位 VPN 和 9 位位偏移组成。此外，VPN 的高两位用于区分页所在的段。因此，该系统是分页和分段的换合体。

一个真实的地址空间

页替换

VAX 中的页表项（PTE）包含以下位：一个有效位，一个保护字段（4位），一个脏位，为系统使用保留的字段（5位），一个物理帧号码（PFN）将页面的位置存储在物理内存中。

没有引用位！因此，VMS 替换算法必须在没有硬件支持的情况下，确定哪些页是活跃的。

开发人员也会担心一些程序占用大量内存，是其他程序难以运行。

为了解决这两个问题，开发人员提出了：分段的先进先出替换策略和页聚集。

其他漂亮的虚拟内存技巧

VMS 有另外两个现在成为标准的技巧：按需置零（demand zeroing）和写入时复制（copy-on-write）。这些惰性优化。

惰性可以使工作推迟，但出于多种原因，在这操作系统中是有益的。首先，推迟工作可能会减少当前操作的延迟，从而提高响应能力。其次，惰性有时会完全避免完成这项工作。

---

第二部分：并发

---

并发介绍

本章将介绍为单个运行进程提供的新抽象：线程（thread）。每个线程独立，但它们共享地址空间，从而能访问相同的数据。

因此，单个线程的状态与进程状态非常类似。线程有一个程序计数器（PC），记录程序从哪里获取指令。每个线程有自己的一组用于计算的寄存器。所以，如果两个线程运行在一个处理器上，线程切换时必定发生上下文切换。对于进程，需要将状态保存到进程控制块（PCB），线程则是线程控制块（TCB）。

线程和进程之间的另一个区别在于栈。在简单的传统进程地址空间模型（可称之为单线程进程）中，只有一个栈。然而在多线程进程中，每个线程独立运行，每个线程都有一个栈。

多个栈破坏了地址空间的布局。以前，堆和栈可以互不影响地增长，知道空间耗尽。多个栈就没有这么简单了。幸运的是，通常栈不会很大（除了大量使用递归的程序）。

线程创建示例

线程让生活变得复杂：很难说出什么时候会运行了！没有并发，计算机也很难理解。有了并发，情况变得更糟。

线程共享数据

你应该学习使用工具，帮助你编程、调试和理解计算机系统，如反汇编程序。如果对可执行程序执行反汇编程序，它会显示组成程序的会变指令（如 objdump -d 二进制文件）。

objdump 反汇编程序，gdb 调试器，valgrind（Linux） 或 purify（Windos）内存分析器，这些工具都应该尝试学习。

线程不可控的调度

竞态条件（race condition）：结果取决于代码的时间执行。事实上，每次执行可能都会得到不同的结果。因此，称这个结果是不确定的。

由于执行这段代码的多个线程可能导致竞争状态，因此我们将此段代码成为临界区（critical section）。临界区是访问共享资源的代码片段，一定不能由多个线程同时执行。

真正想要的代码就是所谓的互斥（mutual exclusion）。这个属性保证了如果一个线程在临界区内执行，其他线程将被阻止进入临界区。

原子性愿望

解决这个问题的一种途径是拥有更强大的指令，单步就能完成要做的事，从而消除不合时宜的中断的可能性。

原子方式的意思是作为一个单元，有时我们说 全部或没有。

因此，我们要求硬件提供一些有用的指令，可以在这些至零上构建一个通用的集合，即所谓的同步原语（synchronization primitive）。通过使用这些硬件同步原语，加上操作系统的一些帮助，能够构建多线程代码，以同步和受控的方式访问临界区，从而可靠地产生正确的结果。

关键并发术语：

• 临界区（critical section）：是访问共享资源的一段代码，资源通常是一个变量或数据结构。
• 竟态条件（race condition）：出现在多个执行线程大致同时进入临界区时，它们都试图更细共享的数据结构，导致了非预期的结果。
• 不确定性（indeterminate）：程序由一个多个竟态组成，程序的输出因运行而异，具体取决于哪些线程在何时运行。
• 互斥（mutual exclusion）：为了避免这些问题，线程应该使用某种互斥原语。这样可以保证只有一个线程进入临界区，从而避免出现竟态，并产生确定的结果。

等待另一个线程

一个线程在继续之前必须等待另一个线程完成某些操作。如执行磁盘 IO 操作。

为什么操作系统要研究并发

操作系统是是第一个并发程序，许多技术都是在操作系统内部使用的。后来，在多线程的进程中，应用程序也必须考虑这些事情。

原子操作时构建计算机系统最强大的基础技术之一，从计算机体系结构到并行代码、文件系统、数据库管理技术，甚至是分布式。将一系列动作原子化（atomic）背后的想法可以简单用一个短语表打：全部或没有。要么所有活动都发生了，要么它们都没有发生，不会看到中间状态。有事，将许多行组合为单个原子动作成为事务（transaction）。

---

线程 API

本章介绍主要的线程 API。

线程创建

编写多线程程序的第一步就是创建新线程，因此必须存在某种线程创建接口。

在 POSIX 中，使用 pthread_creat()。

线程完成

上面创建了一个线程。如果你想等待线程完成，你需要调用 pthread_join()。

使用 pthread_create() 创建线程，然后立即调用 pthread_join()，这是创建线程一种非常奇怪的方式。

事实上，有一个更简单的方法来完成这个任务，它被称为过程调用（procedure call）。显然，我们通常会创建不止一个线程并等待它完成，否则根本没有太多的用途。

并非所有的多线程代码都是用 join 函数。如多线程 Web 服务器可能会创建大量的工作线程，然后使用主线程接受请求，并将其无限期地传递给工作线程。

锁的介绍

POSIX 线程库提供的最有用的函数集，可能是通过锁（lock）来提供互斥进入临界区的那些函数。

如果你意识到有一段代码是一个临界区，就需要通过锁来保护，以便像需要的那样运行。

条件变量

所有线程库还有一个主要组件，就是存在一个条件变量（condition variable）。当线程之间必须发生某种信号时，如一个线程等待另一个线程继续执行某些操作，条件变量就很有用。

线程API指导

当使用 POSIX 线程库（或任何线程库）来构建多线程程序时，需要记住：

• 保持简洁：线程之间的锁和信号的代码应该尽可能简洁。
• 让线程交互减到最少：尽量减少线程之间的交互。
• 初始化锁和条件变量：未初始化的代码有时正常，有时失败，会产生奇怪的结果。
• 检查返回值：任何 Unix 程序，都应该检查返回值。
• 注意传给线程的参数和返回值：具体来说，如果传递在栈上分配的变量的引用，可能就是在犯错误。
• 每个线程都有自己的栈：因此，线程局部变量应该是线程私有的，其他线程不应该访问。线程之间共享数据，值要在堆或其他全局可访问的位置。
• 线程之间总是通过条件变量发送信号：切记不要用标记变量来同步。
• 多查手册

---

锁

本章介绍锁（lock），用于解决原子性问题。程序员在源代码中加锁，放在临界区周围，确保临界区能够像单条原子指令一样执行。

锁的基本思想

锁保存了某一时刻的状态，它要么可用，要么被占用。

锁为程序员提供了最小程度的调度控制。我们把线程视为程序员创建的实体，但是被操作系统调度，具体方式由操作系统选择。锁让程序员获得了一些控制权。通过给临界区加锁，可保证临界区内只有一个线程活跃。锁将原本由操作系统调度的混乱状态变得更为可控。

Pthread锁

POSIX 库将锁称为互斥量（mutex），被用来提供线程之间的互斥。

实现一个锁

我们需要硬件和操作系统的帮助来实现一个可用的锁。各种计算机体系结构的指令集都增加了一些不同的硬件原语。

评价锁

锁的标准：

• 提供互斥。是否能够阻止多个线程进入临界区？
• 公平性。是否有竞争锁的线程会饿死，一直无法获得锁？
• 性能。使用锁之后的时间开销。

控制中断

最早提供的互斥解决方案之一，就是在临界区关闭中断。这是为单处理器系统开发的。

此方法优点是简单。没有中断，线程可以确信它的代码会继续执行下去，不会被其他线程干扰。

缺点很多。一是允许调用线程执行特权操作（开关中断），即信任此机制不会被滥用。二是不支持多处理器。三是关闭中断导致中断丢失。四是效率低。

测试并设置指令

因为关闭中断的方法无法工作在多处理器上，所以系统设计者开始让硬件支持锁。

最简单的硬件支持是测试并设置指令（test-and-set instruction），也叫作原子交换（atomic exchange）。

当第一个线程正处于临界区，如果另一个线程调用锁，它会在 while 循环中自旋等待（spin-wait），直到第一个线程释放锁。

实现可用的自旋锁

一些硬件系统提供了这一指令。在 SPARC 上叫做 ldstub（load/store unsigned byte，加载/保存无符号字节）；在 X86 上是 xchg（atomic exchange，原子交换）。

自旋锁（spin lock）是最简单的一种锁，一直自旋，利用 CPU 周期，直到锁可用。

比较并交换指令

某些系统提供了另一个硬件原语，即比较并交换指令。在 SPARC 系统是 compare-and-swap，在 x86 系统是 compare-and-exchange。

它的基本思路是检测指针指向的值是否和期望相等。如果是，更新指针所指的值为新值。否则，什么也不做。

检查标志是否为 0，如果是，原子地交换为 1，从而获得锁。锁被持有时，竞争锁的线程会自旋。

比较并交换指令比测试并设置更强大。

链接的加载和条件式存储指令

一些平台提供了实现临界区的一对指令。如 MIPS 架构中的链接的加载（load-linked）和条件式存储（store-condition）可以用来配合使用，实现其他并发结构。

链接的加载指令和典型加载指令类似，都是从内存中取出值存入一个寄存器。关键区别来自于条件是存储指令，只有上一次加载的地址在期间都没有更新时，才会成功。

代码越少越好（劳尔定律）。程序员倾向于吹嘘自己使用了大量的代码实现某功能，这样做本质上式不对的。我们应该吹嘘以很少的代码实现给定的任务。简洁的代码更易懂，缺陷更少。

获取并增加指令