并发性

早期计算机程序按顺序执行，CPU 常因等待 I/O 而闲置。为提高 CPU 的利用率，操作系统引入并发机制，使多个任务在同一时间段内交替占用 CPU，从而提升整体效率。本文就重点讨论操作系统的并发原理。

基本概念¶

进程¶

进程可以理解为运行中的程序。我们知道程序都是一组 01 序列组成的指令集，而进程就是将程序加载到内存后的一种称呼。也就是说程序是静态的固定的，而进程是动态的可变的。

既然进程是动态的，那么就肯定不止一个存在状态，在不同的设计方案下，操作系统会将进程定义出各种状态，也就对应了不同的状态模型。常见的有三态模型、五态模型、七态模型等。五态模型和七态模型如下所示：


五态模型	七态模型

那么进程在内存中的存在方式是什么呢？其实就是一个相对复杂的数据结构。下左图取自计算机组成原理教材，描述的相对宏观；下右图取自操作系统教材，描述的相对宏观。


进程映象（OS 中的图）	进程映象（计组中的图）

进程中最关键的信息存储在进程控制块 (Process Control Block, PCB) 中，主要有以下内容：

标识信息：进程唯一标识 PID、进程组标识 ID 等；
现场信息：程序计数器 (Program Counter, PC)、寄存器、栈指针等；
控制信息：进程状态、调度信息（进程优先级、调度队列指针、调度参数、进程使用的 CPU 时间等）、当前进程占用的地址信息。例如基/限长寄存器、段/页表指针等、分配给该进程的 I/O 设备列表、打开文件列表等。

有了进程的唯一表示，想要通过不同的调度策略来执行不同的进程就跃然纸上了。只需要调度进程对应的 PCB 即可。例如我们可以用各种优先级队列来存储并维护所有的 PCB 信息。

线程¶

线程是从进程引申出来的概念与技术。当一个进程的任务很复杂以至于也需要并发时，线程就可以充当更细力度的并发单元。也就是说线程的出现是为了解决越来越复杂的进程多任务并发问题的。

进程是「资源分配的最小单位」，而线程是「CPU 调度的最小单位」。一个进程下可以有多个线程，每一个线程共享当前进程的所有资源，线程只拥有执行指令的最基本资源，例如 PC、寄存器等。

一个进程下包含多个线程的示意图：

并发¶

在并发的过程中，一个 CPU 核心需要在多个进程/线程之间来回切换。以进程切换为例：

上图展示了 CPU 在进程 0 和进程 1 之间切换的全过程：

进程 1 发起中断请求尝试占用 CPU；
OS 收到进程 1 发起的中断请求，确认可以中断后就中断当前正在执行进程 0 代码逻辑的 CPU；
CPU 在完整地执行完当前的一条指令（原语）后，将进程 0 的执行现场保存到进程 0 的 PCB 中，然后将进程 1 的 PCB 中的信息读取到寄存器中来执行进程 1 的指令逻辑；
进程 0 再主导上述 1-3 步的过程使得 CPU 转而来执行进程 0 的指令逻辑。

可以发现这个进程上下文切换的过程其实就是对所有寄存器做一个快照的过程。每一个进程都通过自己的寄存器组中保存的信息运行在自己的上下文环境中。这可以确保并发时 CPU 可以正确地拿到每一个进程的指令和数据。

原语

如果上图中 CPU 在将进程 0 的信息保存到进程 0 的 PCB 中时，又有别的进程发起中断请求并且 OS 响应了，那么这个保存现场的过程不就被打断了，那么以后重新执行进程 0 的指令逻辑时，CPU 读取到的不就是缺失或者错误的指令/数据了？并不会。为了保证数据或指令的正确性，很多操作是不允许被打断的。我们定义「进程的最小执行单元」，即「原语」，处理器在执行指令时，按照原语进行。常见的原语有：更新进程信息（修改 PCB 中的信息）、更新进程状态（修改 PCB 所在的状态队列）、分配/回收资源等等。

并行¶

并发指的是程序在逻辑上同时处理多个任务的能力，这些任务可能在单个 CPU 核心上通过快速切换来一起推进；而并行则是多个 CPU 核心同时执行多个任务，这是在多核 CPU 出来后才产生的概念。

调度机制¶

上一章在讲解进程切换时，埋下了一个伏笔：当 OS 接收到进程发起的中断请求后，就一定让 CPU 去处理发起中断请求的进程吗？其实不一定，OS 还有可能让 CPU 去处理别的处于等待态的进程。本章我们就来介绍 OS 是如何调度所有的进程，使得这些进程可以获得合理的 CPU 计算资源的。

Tip

早在很久以前 OS 的调度单位就从进程转换为线程了，这里以进程为例只是为了方便。

*注：下列说法都是等价的：

"作业" \(\iff\) "刚启动的程序"
"服务时间" \(\iff\) "预计运行时间"
"阻塞队列" \(\iff\) "等待队列"

调度模式¶

三级调度模式如下列表所示：

高级调度。即七态模型中「无 \(\to\) 创建态 \(\to\) 就绪态」的转换。决定哪些作业从外存进入内存；
中级调度。即七态模型中「就绪态 \(\rightleftharpoons\) 挂起就绪态、阻塞态 \(\rightleftharpoons\) 挂起阻塞态」的转换。决定哪些内存中的进程挂起到外存，或者哪些外存中挂起的进程对换到内存；
低级调度。即七态模型中「就绪态 \(\to\) 运行态」的转换。决定哪些内存中的进程可以获得 CPU 计算资源。

调度指标¶

一些调度度量指标如下图所示：

重点关注周转时间相关的度量指标。大部分题目中，作业周转的开始都会表述成 "作业到达时间"。由于「周转时间 \(=\) 运行时间 \(+\) 等待时间」，因此上述「带权」的含义可以理解为作业处理的效率，取值范围为 \([1,\infty]\)。

调度算法¶

基本的 \(7\) 种调度算法如下列表：

先来先服务 (First Come First Serverd, FCFS)。非抢占式。按照进程进入就绪队列的时间顺序分配进程的计算资源；
短作业优先 (Shortest Job First, SJF)。非抢占式。经典排队打水贪心算法的应用。根据就绪队列中所有进程的预估运行时间进行排序，每次给最小运行时间的进程分配计算资源。显然的，如果一直有很小的运行时间的进程进入就绪队列，就会造成已经存在于就绪队列中但是运行时间较长的进程 "饿死"；
最短剩余时间优先 (Shortest Remaining Time First, SRTF)。短作业优先的抢占式版本。相比于非抢占式，所有的抢占式都需要在有其他进程进入内存时判断是否需要进行调度；
最高响应比优先 (Highest Response Ratio First, HRRF)。非抢占式。每次给响应比最大的进程分配计算资源。响应比定义为 \(\frac{\text{当前已等待时间}+\text{预期运行时间}}{\text{预期运行时间}}\)；
优先级调度 (Priority Scheduling)。既有抢占式，也有非抢占式。按照优先级的定义进行调度；
轮转调度 (Round Robin Scheduling, RR)。抢占式。OS 每次从就绪队列中取出一个进程并执行最多一个时间片长度的时间，如果一个时间片结束后该进程还没执行结束，该进程就会发出时钟中断请求，OS 接收到该中断请求后会将该进程重新压入就绪队列；
多级反馈队列调度 (Multi-Level Feedback Queue, MLFQ)。既有抢占式，也有非抢占式。就是将轮转调度中的等待队列多设置了几个并且每一个等待队列都被设置了一个优先级而已。具体的，新到达的进程首先进入最高优先级的就绪队列，每个就绪队列的调度策略为轮转调度。如果进程在该就绪队列的一个时间片内未能执行完毕，则被转移到下一级就绪队列等待运行。每个就绪队列的时间片通常比上一级就绪队列的时间片长，可以定义第 \(i\) 层就绪队列的时间片长度为 \(2^i\)。

上述 \(7\) 种进程调度算法总结如下表所示：

调度算法	调度思想	抢占与否	饥饿与否	调度对象	调度特点
先来先服务	选择到达内存的最早的分配 CPU	非抢占式	不会饥饿	作业/进程	有利于长作业不利于短作业
最短作业优先	选择运行时间最短的分配 CPU	非抢占式	会饥饿	作业/进程	对长作业不利
最短剩余时间优先	选择剩余运行时间最短的分配 CPU	抢占式	会饥饿	作业/进程	算法 2 的抢占式版本；对长作业不利
最高响应比优先	选择响应比最高的分配 CPU	非抢占式	不会饥饿	作业/进程	结合算法 1,2,3 的优势
最高优先级调度	选择优先级最高的分配 CPU	非抢占式/抢占式	静态优先级可能会导致饥饿	作业/进程	适用于实时操作系统
轮转调度	按照时间片长度分配 CPU	抢占式	不会饥饿	进程	有利于多用户、多交互式进程；时间片太大，算法会退化为先来先服务；时间片太小，进程切换频繁，开销大
多级反馈队列调度	在多级就绪队列上按照时间片长度分配 CPU	非抢占式/抢占式	长进程可能会饿死	进程	各种调度算法的权衡

代码模拟上述调度算法时，所有的调度逻辑都只有 3 步，括号内容表示代码没有模拟的部分，如下：

取出就绪队列的队头进程（进入运行态并获得 CPU 的计算资源执行相关指令）；
维护时钟信息和当前进程信息；
更新就绪队列中其余进程信息。

值得注意的是，非抢占式调度算法的 2 和 3 步是顺序进行的，而抢占式调度算法的 2 和 3 是同时进行的。

并发冒险¶

上面讲的都是操作系统的并发知识，现在讲讲我们在编写并发程序时可能会遇到的问题。

对于现代应用，往往一个程序会启动多个进程（例如 Chrome 中每一个标签页都是一个进程），并且一个进程下又会产生多个线程，这就会遇到一个很显然但又很严重的问题：变量同时引用与修改。这里的变量被称为「临界区」，对应到系统中的资源叫做「临界资源」，例如计算资源、存储资源、外设资源等等。

给出一个明确的并发冒险定义，引入 Brenstein 条件：对于两个进程对变量的引用集 \(R_1,R_2\) 和改变集 \(W_1,W_2\)，如果 \(R_1\bigcap W_2,R_2\bigcap W_1,W_1\bigcap W_2\) 均为空集，则两个进程不会发生并发冒险，反之就会发生并发冒险，需要我们在编码时做出应对策略。

信号量与 PV 操作¶

并发冒险需要解决的问题，本质上就是定义一套规则，让不同的进程/线程在某种顺序下对临界区进行访问/修改。常见的并发管理规则有：Perterson 算法、信号量与 PV 操作、管程机制、进程通信机制等等，我们主要介绍信号量与 PV 操作。信号量与 PV 操作是 Dijkstra 老爷子在上世纪七十年代设计出来的用来解决并发问题的策略，非常巧妙。

当各进程在并发执行时全部都处于运行态，表示不缺任何资源。但是也有可能会因为某种资源的缺少而无法运行，从而转变到等待态，这种转变就是通过信号量与 PV 操作实现的。具体地：

信号量 semaphore 表示某种资源的「容量与使用情况」。每一种信号量代表了一种资源，常用下面的数据类型进行表示：

Python
class Semaphore:
    def __init__(self, ini_value: int):
        self.value = ini_value   # 资源容量
        self.wait_que = deque()  # 等待队列

P (Proberen) 操作表示申请资源，当且仅当资源容量 \(>0\) 时，才能进行后续的逻辑；
V (Verhogen) 操作表示释放资源，将对应的资源容量 \(+1\) 即可。

Tip

P, V 操作是原语。

常见的并发模型¶

实际场景中，常见的并发模型主要有两种：

互斥模型：即多个进程/线程对临界区的访问/修改操作是无序的。我们只需要给这个操作的信号量设置为 1 即可解决这个问题。信号量为 1 的设置被称为互斥锁，也挺形象的。
同步模型：即多个进程/线程需要按照某种顺序执行。假设 B 需要在 A 执行完后才能执行，我们只需要定义一个初始值为 0 的信号量 s，当 A 执行完后将 s 的资源容量 \(+1\)，然后让 B 只有在申请到 s 后才能执行。这样就可以确保无序并发时 A 先执行，B 再执行。

下两图分别展示了上述两种操作下进程的执行逻辑：


互斥模型	同步模型

并发终极 BOSS：死锁¶

尽管信号量可以解决大部分并发控制，但是还有一个问题无法被避免——死锁。死锁的书面化定义是（以进程为例）：一个进程集合中的每个进程都在等待，且只能由此集合中的其他进程才能激活，而无限期陷入僵持的局面。例如哲学家就餐问题，如果没有设计好并发的逻辑，就会出现 5 个哲学家各拿一把叉子，然后全部被阻塞的死锁情况。

也就是说，死锁是并发编程中的一种逻辑错误，并且这种错误一般难以发现。为此人们又设计出了各种死锁避免、死锁检测、死锁解除等算法，尝试用程序来弥补死锁的逻辑漏洞。

银行家算法（死锁避免）。该算法是 Dijkstra 在上世纪六十年代设计出来的（可以发现这早于他发明信号量与 PV 操作），主要用于死锁避免来确定是否需要给申请资源的进程分配资源。

如上图示例，银行家算法一共有 4 个数据类型：1）资源总数向量 2）可用资源向量 3）资源需求矩阵 4）已分配资源矩阵。

值得注意的是。该算法只适合用来教学，没有什么实际意义（至少在当下已经完全没有意义了）。从上述对算法的解析不难看出，银行家算法需要提前知道每一个进程所需的资源开销，就光凭这一点就很不切实际了，因为这很难提前预知（就和调度算法中提前知道进程的服务时间一样不切实际）。其次不难发现，银行家算法其实就是 dfs，这种试探性搜索算法会随着资源种类的增加而指数级上升；

资源分配图算法（死锁检测和死锁解除）。该算法允许死锁发生，通过「死锁检测算法」来判断当前并发的进程是否发生了死锁，如果死锁，就用「死锁解除算法」来解除死锁局面。

该算法将「资源」和「进程」抽象成图的两种结点，「进程请求资源」和「资源分配给进程」抽象成图的两种边，如下图所示：

死锁检测逻辑：按照图中的请求和分配关系逐个结束未阻塞的进程并重新分配资源，如果图出现了环就表示无法继续分配资源了，即出现了死锁状态。

死锁解除逻辑：

将陷入死锁状态的进程全部结束；
逐个结束陷入死锁状态的进程；
剥夺陷入死锁状态的进程所占用的资源并重新分配直到死锁状态接触。

这种算法也有一个很大的问题，其死锁解除的时间开销也是很大的。