并发

一开始人们写的都是顺序程序，例如先计算再打印，但是由于 CPU 的计算速度远高于其他设备的数据传输速度，这就导致了 CPU 计算资源的闲置浪费。不断进取的人类想出了并发程序，即允许一个进程运行到某一个状态然后暂停转而运行其他进程。

1 基本概念

首先介绍一些最基本的概念，为后面的进程调度和并发冒险做好铺垫。

1.1 进程定义

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

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


五态模型	七态模型

进程的描述。为了更精准的描述一个进程，我们引入「进程映象」的概念，其表示某一时刻的进程状态。下左图取自计算机组成原理教材，描述的相对宏观；下右图取自操作系统教材，描述的相对宏观。


进程映象（计组）	进程映象（OS）

进程控制块。知道了进程的定义、状态和映象描述后，感觉还是难以把握住进程的概念。其实，可以用面向对象的设计理念来具象化进程。具体的，在现代 OS 设计中，每一个进程都会有自己的一个对象实例，也就是所谓的进程控制块 (Process Control Block, PCB)，进程所有的核心信息全都存储在其对应的 PCB 中。那么一个 PCB 都存储了哪些信息呢？或者说一个进程需要存储哪些必要的信息？如下列表所示：

标识信息。如下：
- 进程标识 PID。用于确定一个进程的名字，每一次创建进程时，操作系统都会在 PID 池分配一个给当前进程；
- 进程组标识 ID。
现场信息。如下：
- 程序计数器 Program Counter。存储当前进程执行到的指令地址；
- 寄存器。包括栈指针、通用寄存器等。存储少量关键地址或数据。
控制信息。如下：
- 进程状态。当前进程的状态位。例如五态中的哪一个状态等；
- 调度信息。当前进程被 CPU 调度执行的程序，例如进程优先级、调度队列指针、调度参数、进程使用的 CPU 时间等；
- 内存管理信息。当前进程占用的地址信息。例如基/限长寄存器、段/页表指针等；
- I/O 状态信息。例如分配给该进程的 I/O 设备列表、打开文件列表等。

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

1.2 进程切换

进程的切换。在绪论中我们学习到，一个进程需要通过「系统调用」发起中断请求，使得 CPU 进入核心态来执行固定的系统调用子程序，也就是所谓的「状态切换」。那么进程切换又是个什么原理呢？我们知道，在支持多道程序并发的系统中，会有多个进程在内存中利用同一个 CPU 核心 "同时" 工作。注意这里的同时加上了引号，因为其实并不是同时，只不过 CPU 在执行不同进程的指令时来回切换的太快，以至于人类无法分辨出多个进程的执行顺序而已。

这就引出了「进程切换」的概念。顾名思义，进程切换就是让 CPU 终止当前正在处理的进程，转而切换去执行另一个进程。可以发现进程切换其实就是一个进程打断另一个进程从而让自己占有 CPU 的一个过程。注意到这个阶段 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 所在的状态队列）、分配/回收资源等等。

1.3 线程定义

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

线程的产生背景。当一个进程的任务很复杂以至于也需要并发时，线程就可以充当更细力度的并发单元。也就是说线程的出现是为了解决越来越复杂的进程多任务并发问题的。

线程的三种模式。分别有用户级线程、内核级线程和混合级线程。其中用户级线程 (User Level Thread) 的多线程逻辑顾名思义，就是由程序开发者定义，便于解决「逻辑并行」的问题。内核级线程 (Kernel Level Thread) 的多线程则由系统调用决定，便于解决「物理并行」的问题。

2 进程调度

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

Tip

注：各种名词说法没有统一，下列说法都是等价的：

"作业" \(\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	非抢占式/抢占式	长进程可能会饿死	进程	各种调度算法的权衡

代码实现。为了更好的理解上述 \(7\) 种进程调度算法，尝试从「逻辑上」进行模拟。具体代码见：Explorer-Dong/OS_Simulate。不难发现所有的调度逻辑都只有 3 步，括号内容表示代码没有模拟的部分，如下：

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

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

3 并发冒险

讲了这么多基本的概念和进程调度策略，终于可以开始学习并发了，这一章十分有趣，尤其是并发编程。章节标题是我自己拟的，借鉴了计组中流水线 CPU 的标题，之前课堂上学习时，课件中将这一章叫做 "互斥、同步与死锁"，仅供参考。

3.1 冒险产生

对于现代应用，往往一个程序会启动多个进程（例如 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\) 均为空集，则两个进程不会发生并发冒险，反之就会发生并发冒险，需要我们在编写代码时做出一定的调整。

3.2 冒险解决

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

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

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

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

P (Proberen) 操作表示申请资源，现在常用 semWait 表示；
V (Verhogen) 操作表示释放资源，现在常用 semSignal 表示（注意 P, V 操作是原语）。

并发编程。介绍完了规则中定义的一些 "工具" 后，下面介绍如何利用这些工具来解决并发冒险问题，也就是执行顺序的问题。下面从并发编程的视角来学习常见的两种策略：

面向单个进程进行并发编程。让一个进程一气呵成的完整对临界区的访问/修改操作，教科书称呼这种操作为互斥。对应的并发编程逻辑就是：定义一个互斥信号量 mutex 并将其中的资源容量 value 初始化为 1（当然如果允许 m 个进程访问该资源，就初始化为 m，一般都是 1），然后定义程序的并发逻辑，使得其在访问临界区前后分别申请和释放临界区资源，如果在当前进程正在访问临界区资源时，还有别的进程也尝试申请该资源，那么别的进程就会被阻塞然后进入当前资源的等待队列 wait_que 中，只有在当前临界区资源被释放后，其阻塞队列的进程才会出队，重新进入就绪态来争夺该资源。这样就可以确保同一时刻只有一个进程在访问临界区资源；
面向多个进程进行并发编程。简单来说就是让一个进程带动另一个进程，比如让进程 A 访问完临界区之后显式的唤醒进程 B 去访问临界区资源，教科书称呼这种操作为同步。对应的并发编程逻辑就是：定义一个同步信号量 s 并将其中的资源容量 value 初始化为 0，然后定义多个进程的并发逻辑，假设只有 A 和 B 两个，使得 A 在执行完一定的代码逻辑后主动唤醒 B。这样也可以确保同一时刻只有一个进程在访问临界区资源。

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


面向单个进程进行并发编程（互斥）	面向多个进程进行并发编程（同步）

死锁。上述两种操作已经可以解决大部分的并发冒险问题了，但还是不够完全。最常见的反例就是哲学家就餐问题，如果没有设计好并发的逻辑，就会出现 5 个哲学家各拿一把叉子，然后全部被阻塞的情况。这种情况被称为死锁。死锁的书面化定义是：一个进程集合中的每个进程都在等待，且只能由此集合中的其他进程才能激活，而无限期陷入僵持的局面称为死锁。

死锁是并发编程中常见的一种逻辑漏洞，并且这种漏洞一般难以发现。为此人们又设计出了各种死锁避免、死锁检测、死锁解除等算法，尝试用程序来弥补逻辑漏洞。下面分别介绍「银行家算法」和「资源分配图算法」：

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

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

值得注意的是。该算法只适合用来教学，没有什么实际意义（至少在当下已经完全没有意义了）。从上述对算法的解析不难看出，银行家算法需要提前知道每一个进程所需的资源开销，就光凭这一点就很不切实际了，因为这很难提前预知（就和调度算法中提前知道进程的服务时间一样不切实际）。其次不难发现，银行家算法其实就是 dfs，这种试探性搜索算法会随着资源种类的增加而指数级上升；
资源分配图算法。该算法是一种用于死锁检测和死锁解除的算法。在这种设计思路下， OS 允许发生死锁。OS 通过死锁检测算法来检测当前并发的进程是否发生了死锁，然后再应用死锁解除算法来解除死锁的局面。该算法将「资源」和「进程」抽象成图的两种结点，「进程请求资源」和「资源分配给进程」抽象成图的两种边，如下图所示：

对于死锁检测。按照图中的请求和分配关系逐个结束未阻塞的进程并重新分配资源，如果图出现了环就表示无法继续分配资源了，即出现了死锁状态；对于死锁接触，有以下三种策略：1）将陷入死锁状态的进程全部结束 2）逐个结束陷入死锁状态的进程 3）剥夺陷入死锁状态的进程所占用的资源并重新分配直到死锁状态接触。

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