进程管理

• 1: 进程和线程
• 2: 处理机调度
• 3: 同步和互斥
• 4: 经典同步问题
• 5: 死锁

# 进程管理

## 进程和线程

- 进程、线程概念
- 进程、线程状态和转换
- 线程的实现
- 进程、线程的组织和控制
- 进程间通信

## CPU调度和上下文切换

- 概念和目标
- 调度实现方式
- 调度算法
- 上下文及其切换机制

## 同步与互斥

- 概念
- 软件和硬件实现方法
- 锁
- 信号量
- 条件变量
- 经典同步问题

## 死锁

- 概念
- 死锁预防
- 死锁避免
- 死锁检测和解除

1 - 进程和线程

进程和线程

在多道程序环境下，允许多个程序并发执行，为此操作系统引入了进程(Process)的概念，以便更好地描述和控制程序的并发执行，实 现操作系统的并发性。

进程

进程是 系统资源分配的基本单位。 进程拥有独立的系统资源，包括内存空间、文件描述符、CPU 时间片等，这些资源的分配由操作系统负责。

进程和程序

程序时静态的，进程是动态的，进程可以理解成运行的程序，两者的具体区别如下：

• 程序
  • 程序是一组指令的静态集合，它存储在磁盘等持久性存储介质中。
  • 程序是被动的，它本身并不执行任何操作。
• 进程
  • 进程是程序在内存中执行的实例。
  • 当一个程序被加载到内存中并开始执行时，操作系统会创建一个进程。
  • 进程是动态的，它代表了程序的执行过程。

操作系统在创建进程时，会为进程分配必要的资源，例如内存空间、文件句柄等。 进程是操作系统进行资源分配和调度的基本单位。 一个程序可以多次运行，每次运行都会创建一个新的进程。

进程控制块

操作系统通过 进程控制块（PCB，Process Control Block） 对进程进行管理，进程控制块中包含一系列进程的元信息，这些元信息帮助操作系统对进程进行管理：

上表给出了 PCB 的关键内容，其中进程描述信息用于唯一标识和管理进程，以及实现用户级别的权限控制；进程控制和管理信息用于管理进程的生命周期、调度和执行；资源控制清单记录进程使用的资源，以便进行有效的资源管理和分配；处理机相关信息保存与处理器相关的状态信息，以实现上下文切换。

进程控制块在操作系统进程管理的多个阶段都发挥重要作用：

• 进程创建和终止：在进程创建时，操作系统为它新建一个 PCB（进程控制块）。该结构在进程存在期间常驻内存，可以随时存取，并在进程结束时删除。
• 进程调度：当操作系统进行进程调度时，会根据 PCB 中存储的信息（如优先级、进程状态）来决定哪个进程应该获得 CPU 的控制权。

线程

线程是 系统调度的基本单位 。 多核处理器可以将系统中的不同线程调度到不同的 CPU 逻辑核心上，所以在同一个时刻，系统中的线程可能会在不同的逻辑核心上并行运行。

每个进程启动的时候，都包含一个线程（主线程），可以在主线程外创建更多的线程。

如上图所示，一个进程中的所有线程都共享虚拟地址空间和系统资源，但是每个线程都维护自己的堆栈、寄存器和一些额外信息。

进程的状态

进程状态是指在操作系统中，一个进程在执行过程中的不同阶段。它反映了进程当前正在做什么，以及是否可以被 CPU 执行。

状态种类

不同的操作系统对进程状态的划分可能不同，但常见的包若以下几种：

1. 创建状态（New）：当进程被创建但还未分配资源或执行时，它处于创建状态。
2. 就绪状态（Ready）：在就绪状态中，进程已准备好执行，但由于操作系统调度算法或其他原因，尚未获得 CPU 时间片。
3. 运行状态（Running）：在运行状态中，进程正在执行指令并占用 CPU。
4. 阻塞状态（Blocked）：当进程在等待某些事件发生时，如等待 I/O 操作完成或等待其他资源时，它会进入阻塞状态。在阻塞状态下，进程暂停执行，直到等待的事件发生。
5. 终止状态（Terminated）：当进程执行完毕或被操作系统终止时，它进入终止状态。

状态转化

1. 就绪态 → 运行态：
   • 调度：当操作系统的调度器选择一个就绪状态的进程分配给处理器时，该进程就会从就绪状态转换到运行状态。
2. 运行态 → 就绪态：
   • 时间片用完：如果系统使用时间共享调度，当进程的时间片用完，它会被中断并放回就绪队列。
   • 优先级更高的进程就绪：在优先级调度算法中，如果一个优先级更高的进程变为就绪状态，当前运行的进程可能会被挂起。
   • 自愿放弃 CPU: 进程可能主动放弃 CPU，比如它发出了一个系统调用请求其他资源。
3. 运行态 → 阻塞态：
   • I/O 请求：进程进行 I/O 操作，由于 I/O 设备比 CPU 慢得多，进程会被挂起直到 I/O 完成。
   • 等待资源：进程等待不可用的资源，如信号量、互斥锁等。
   • 等待事件：如等待其他进程的信号、消息或者某个条件的发生。
4. 阻塞态 → 就绪态：
   • I/O 完成：当 I/O 操作完成，相应的进程会被移至就绪队列。
   • 资源获得：进程所等待的资源变得可用，如获得了互斥锁。
   • 事件发生：进程所等待的事件发生了，如接收到了另一个进程发出的信号。

进程内存空间

• 用户空间（User Space）：包含进程执行的用户程序代码和数据。在用户空间中，进程可以执行各种任务，如运行应用程序、访问文件系统等。用户空间对于应用程序是可见的，但对于操作系统中的核心功能是不可见的。
  1. 代码区（Text Segment）：也称为"可执行代码区"，存储了进程的可执行代码，包括程序的指令和只读数据。这个区域通常是只读的，因为程序的指令在运行时不应该被修改。
  2. 数据区（Data Segment）， 数据区分为两个子区域：
     • 初始化数据区（Initialized Data Segment）：存储全局和静态变量以及初始化的数据。这些变量在程序运行前就已经分配了内存并初始化。
     • 未初始化数据区（Uninitialized Data Segment）：也称为"BSS"（Block Started by Symbol）段，存储全局和静态变量，但这些变量没有显式的初始化值。操作系统会在程序启动时自动将这个区域初始化为零。
  3. 堆区（Heap）：堆区是动态分配内存的地方，用于存储程序运行时需要的变量和数据结构。在堆中分配的内存需要手动释放，以避免内存泄漏。
  4. 栈区（Stack）：栈区用于存储函数调用和局部变量。每个函数调用都会在栈上创建一个栈帧，栈帧包含了函数的参数、局部变量以及函数返回地址。栈是一种后进先出（LIFO）的数据结构，它的大小通常有限，由操作系统或编程语言定义。
  5. 内存映射区域（Memory Mapped Region）：这是一些操作系统或运行时库的扩展，用于存储动态链接库（DLL）和共享库的信息以及其他系统数据结构。
• 内核空间（Kernel Space）：内核空间包含了操作系统的核心代码和数据结构，如页表、调度程序和系统调用接口等。内核空间具有更高的特权级别，可以执行特权指令并且访问系统的各种资源，内核空间对于用户程序是不可见的。

函数调用时内存结构

EBP (base pointer) 指向函数栈（栈帧）的底部（高地址），函数执行过程中在栈帧中分配局部变量，栈帧由高地址向低地址增长，ESP（stack pointer）一直指向栈顶。

每个函数的栈帧中包含如下内容：

• 上一个函数的 EBP
• 该函数的局部变量
• 如果函数内有 call 指令的话，还需要保存额外信息：
  • 下一个函数的参数：依次存储从第 n 个到第 1 个，从高地址到低地址
  • 返回地址：当前 PC 指向的位置，即 call 指令的下一条指令的地址

在函数的调用过程中，调用函数叫做 caller，被调用函数叫做 callee。当我们从 caller 中调用 callee 时，callee 的 EBP 指向的物理地址的上下存储单元分别包含 caller 的返回地址以及 caller 所在栈帧的 EBP，当我们在 callee 中执行 ret 指令时，计算机可以跳转到 caller 中 call 指令的下一条并开始执行，同时 caller 的栈帧也会被恢复。

进程间通信

• 共享内存（Shared Memory）：共享内存允许多个进程访问相同的物理内存区域，这样它们可以直接共享数据，而不需要复制数据。这是一种高效的通信方式，但需要谨慎管理共享数据以避免竞态条件。
• 管道（Pipes）：管道是一种单向通信方式，通常用于父子进程之间或兄弟进程之间的通信。有命名管道和匿名管道两种，匿名管道只能在有亲缘关系的进程之间使用。
• 消息队列（Message Queues）：消息队列是一种进程间通信的机制，允许进程通过消息来进行异步通信。消息队列通常由操作系统维护，可以支持多个读者和写者。
• 信号（Signals）：信号是一种轻量级的通信机制，用于通知进程发生了某些事件。进程可以发送信号给其他进程，比如终止信号、挂起信号等。
• 套接字（Sockets）：套接字是一种通用的进程间通信方式，通常用于不同计算机之间的网络通信。它支持多种协议，如 TCP 和 UDP，可以实现客户端-服务器通信。
• 信号量（Semaphores）：信号量是一种计数器，用于控制多个进程对共享资源的访问。信号量可以用于解决竞争条件和进程同步的问题。

用户级线程和内核级线程

• 用户级线程（ULT，User Level Thread）
  • 用户级线程是由应用程序通过线程库来实现的，操作系统内核并不直接感知到这些线程的存在。
  • 线程的创建、调度和管理都由应用程序在用户空间完成。
• 内核级线程（KLT，Kernel Level Thread）
  • 内核级线程是由操作系统内核直接支持的线程。
  • 线程的创建、调度和管理都由操作系统内核完成。

线程模型

操作系统中的线程实现方式称为线程模型，不同的线程模型在用户级线程（ULT）和内核级线程（KLT）的设计上各有不同。

系统中的线程模型可以分为如下三种：

• 纯用户态：所有的线程操作都在用户空间中进行，内核对线程的存在一无所知。
• 纯系统态：线程由操作系统内核直接支持和管理，内核负责线程的创建、调度和管理。
• 混合方案：应用程序可以在用户空间管理多个用户级线程，这些线程映射到较少数目的内核级线程。

混合方案中的映射关系

如果使用混合方案的线程模型的话，用户级线程和内核级线程的映射方式也可以分为如下几种：

• 一对一
• 多对一：
• 多对多：

2 - 处理机调度

调度的指标

系统调度过程

进程调度是计算机操作系统中的一种核心功能，它决定了哪个进程应该在给定的时间段内使用处理器。为了有效地管理和调度进程，操作系统通常采用多级调度机制。这些调度机制分为三个层次：高级调度、中级调度和初级调度。

1. 高级调度（长程调度，Long-term Scheduling）:
   • 功能：高级调度主要决定哪些进程应当被加载到内存中成为一个可运行的进程。
   • 主要目标：保持内存中适当数量的进程。不要过多也不要过少。
   • 当进程首次进入系统时，它们首先被放置在磁盘的一个区域，称为作业池。高级调度器从作业池中选择进程，根据某种策略将其加载到内存中，从而使其成为一个可运行的进程。
2. 中级调度（中程调度，Mid-term Scheduling）:
   • 功能：中级调度涉及到进程的暂停和重启。当系统的进程数超过内存容量时，中级调度器可能会将一些进程从内存移出到磁盘上（这称为交换或页面置换），从而为新的或等待的进程腾出空间。
   • 主要目标：为高级和初级调度器优化内存使用。
   • 中级调度器在必要时将进程从内存交换到磁盘，并在适当的时机将其交换回内存。
3. 初级调度（短程调度，Short-term Scheduling）:
   • 功能：初级调度决定哪个进程应当被赋予 CPU 时间片，即决定下一个运行在处理器上的进程。
   • 主要目标：确保 CPU 的高效利用。
   • 它的决策频率非常高，因为在多任务环境中，每个时间片的长度可能只有几十毫秒。因此，初级调度器必须是非常快速的。

调度的实现

调度器

调度器/调度程序（scheduler）:

• 调度器是操作系统中负责决定下一个要执行的进程或线程的部分。
• 基于特定的调度算法（如轮转、优先级调度、短作业优先等），它决定哪个进程或线程应当获得 CPU 时间。
• 调度器通常分为长程、中程和短程调度器，如前文所述。

调度时机

调度的时机可能包括以下情况：

• 进程进入或退出系统
• 进程从运行状态变为阻塞状态
• 或者一个时间片结束。

调度方式

• 抢占式调度（Preemptive）：在这种调度方式下，当一个进程正在执行时，操作系统可以中断该进程的执行并将 CPU 分配给另一个进程。这常常发生在一个更高优先级的进程变为就绪状态时。
• 非抢占式调度（Non-Preemptive）：在这种方式下，一旦 CPU 分配给一个进程，它会继续运行直到完成或者转为非运行状态（例如，等待 I/O 操作）。

闲逛进程

闲逛进程（Idle Process）是操作系统中的一个特殊进程，当系统没有任何其他可运行的进程时，调度器会将 CPU 的控制权交给这个进程。闲逛进程的主要目的是确保在没有任务可执行的情况下，CPU 不会空转，从而防止 CPU 进入不受控制的状态。

在 Linux 操作系统中，闲逛进程的进程 ID 通常是 0，被称为 swapper 或 idle task。它是系统启动时创建的第一个进程，始终在内核态运行，确保当没有其他可调度任务时，CPU 有事情可做。

在 Windows 系统中，闲逛进程被称为 System Idle Process，同样用于在系统空闲时占据 CPU 时间，以维持系统的运行稳定。如下图所示：

两种线程的调度

• 内核级线程：由操作系统内核直接支持的线程。操作系统知道这些线程的存在，并可以直接进行调度。
• 用户级线程：完全在用户空间中实现的线程，不需要内核的介入。
• 对于内核级线程，操作系统可以直接调度它们，并可以利用多核或多处理器的优势。
• 对于用户级线程，因为内核不知道它们的存在，所以内核无法直接调度它们。线程之间的上下文切换可能比内核级线程更快，但在多处理器系统中，它们可能无法充分利用所有的处理器。

调度算法

根据是否抢占可以对调度算法进行如下分类：

• 非抢占型调度算法：先来先服务、最短任务优先、最高响应比优先
• 抢占型调度算法：时间片轮转、多级反馈队列

先来先服务

先来先服务（First-Come, First-Served，FCFS）按照进程到达的顺序分配依次执行。先到达的进程先执行，后续进程等待直到前一个进程执行才能进一步执行。

最短作业优先

最短作业优先（Shortest Job First，SJF）算法在从就绪队列中选择进程时，会 选择运行时间最短 的进程进行执行。

在题目中进程的运行时间一般都是给定的，所以 SJF 算法比较容易实现。但是在真实的系统中进程的运行时间是不确定的，所以在使用该算法时操作系统需要对进程的运行时间进行预估。

最高响应比优先

最高响应比优先（Highest Response Ratio Next，HRRN）算法从就绪队列中选择 响应比 最高的进程进行执行。

其中响应比（Response Ratio）的计算公式如下：

$$\text{Response Ratio} = \frac{W + B}{B}$$

其中 $W$（Waiting Time） 为进程的等待时间，$B$（Burst Time） 为进程的要求服务时间（从执行开始到结束所需时间）。

这种计算策略可以有效地避免饥饿现象，即一个进程等待了很长时间但仍没有得到执行。一个进程的等待时间越长，其响应比就会更大，进而优先得到执行机会。一个进程的执行时间很长，其响应比就会越小，会优先调度其他进程。

• 时刻 0：只有 P1 到达，执行 P1。
• 时刻 5：P1 执行完成。P2 的响应比为 (4 + 3) / 3 ≈ 2.33，P3 的响应比为 (3 + 8) / 8 = 1.375，P4 的响应比为 (2 + 6) / 6 ≈ 1.33，此时 P2 的响应比最大，执行 P2。
• 时刻 8：P2 执行完成。P3 的响应比为 (6 + 8) / 8 = 1.75，P4 的响应比为 (5 + 6) / 6 ≈ 1.83。此时 P4 的响应比更大，执行 P4。
• 时刻 14：P4 执行完成，只剩下 P3 了，最后执行 P3。

所以进程的执行顺序为 P1、P2、P4、P3，每个进程的时间指标如下表所示：

优先级调度

优先级调度（Priority Scheduling）可以是非抢占式的，也可以是抢占式的。

非抢占式优先级调度总是从等待队列中选取一个优先级最高的进程进行执行。当有进程正在执行时，其他进程必须等待

抢占式优先级调度要确保系统中每个时刻中正在执行的进程的优先级都是最高的。所以当优先级更高的进程到达时，调度器要立刻执行该进程，正在执行的优先级更低的进程会被挂起加入等待队列。

时间片轮转

时间片轮转（Round Robin，RR）这是一种基于时间片的算法，每个进程被分配一个固定的时间片，当时间片用完时，进程被放回队列尾部，下一个进程开始执行。这样可以实现公平的 CPU 时间分配。

上图中给出了每个进程的到达时间和要求服务时间，调度器按照轮询的方式依次遍历进程，每个进程只有执行时间片内的时间，之后便进入等待状态。

多级反馈队列

多级反馈队列（Multilevel Feedback Queue）这是一种混合算法，将进程分为多个队列，每个队列有不同的优先级和时间片大小。新创建的进程进入最高优先级队列，如果没有完成，它将下降到较低优先级的队列，直到完成。

上下文及其切换机制

进程的上下文是进程执行的环境。在操作系统中，它指的是一个进程在特定时间点上的系统状态，包括多种信息，这些信息使得进程在被中断后可以再次恢复并继续执行。当操作系统从一个进程切换到另一个进程时，它会保存当前进程的上下文并恢复下一个进程的上下文。这个过程被称为上下文切换。

进程上下文内容

1. 寄存器值：这包括通用寄存器、程序计数器、栈指针、状态寄存器等。它们保存了进程的当前执行位置和状态。
2. 程序计数器：表示进程的下一个指令的位置。
3. 虚拟内存信息：这包括进程的页表、页目录等信息，描述了进程的地址空间布局。
4. I/O 状态信息：包括打开的文件描述符、网络连接、I/O 指针等。
5. CPU 调度信息：例如进程优先级、计划器状态等。
6. 资源使用情况：这可能包括该进程所使用的各种资源的跟踪信息，如内存、文件句柄等。

上下文切换流程

1. 保存当前进程的状态：操作系统保存当前正在运行的进程的上下文。这意味着它会将当前的寄存器值、程序计数器等保存到进程的进程控制块（PCB）中。
2. 选择下一个要执行的进程：调度器决定下一个要运行的进程。
3. 恢复下一个进程的状态：操作系统从新进程的 PCB 中恢复其上下文信息，包括寄存器值、程序计数器等。
4. 开始执行新进程。

3 - 同步和互斥

临界区和互斥

在并发编程中，临界区（Critical Section）是指一个程序中仅允许一个线程或进程访问的代码片段。这些代码通常会访问共享资源，比如内存、文件、数据库等。当多个线程或进程试图同时访问这些共享资源时，可能会导致数据不一致或其他并发问题。因此，需要一种机制来确保在任何时候，保证在一个时刻只有一个线程或进程能够访问临界区的代码。

这种机制就叫做 互斥：

互斥（Mutual Exclusion）是计算机科学中一种用于防止多个进程或线程同时访问共享资源或临界区的机制。其主要目标是避免资源竞争和数据不一致的问题。互斥保证在任何时刻，最多只有一个线程或进程可以访问特定的共享资源，从而确保数据的完整性。

临界资源

临界资源 就是共享资源，共享资源可以被多个 线程/进程 同时访问。 比如一个进程的全局变量可以被 该进程内的多个线程 同时访问，这个全局变量对于多个线程就是临界资源。 再比如数据库中的某个数据可以被多个进程同时访问，这个数据对于这些进程来说就是临界资源。

为何需要互斥

在 处理器调度 一节我们知道，为了避免进程饥饿，现代操作系统常使用时间片轮转的方式来避免一个进程连续执行过长时间。

这意味着进程可能在执行完当前的机器指令后就被操作系统中断，由运行态进入就绪态，然后等待下一次调度继续执行后续指令。 这种随时可能被中断的特性决定了若没有临界区的互斥，多线程并发执行时 结果可能会出现不一致性。

如上图所示，一条高级语言语句常对应着多条汇编语句，而进程执行完汇编语句后可能立刻会被中断。 所以高级语言语句的执行并不具备原子性，也许在进程在执行到一半的情况下就被迫终止了。

临界区涉及到对于临界资源的访问，如果多个线程同时执行临界区代码访问临界资源时，实际执行的指令序列就具有不可预测性，结果也因此常常 出现不一致的情况。

为了解决以上问题，多线程在访问临界资源时必须是互斥的。也就是说，当一个线程在访问临界资源的过程中，不允许其他线程再访问临界资源。其他线程必须等待到当前访问者访问完，才能进入临界区。

需要注意的是，互斥并不表示线程在执行临界区代码的过程中不会被操作系统中断。 互斥是一种逻辑上的概念，它保证了多个线程不能同时进入临界区。 线程 A 可能在执行临界区代码的过程中被中断，但是与之互斥的线程 B 同样不能在线程 A 被中断之时进入临界区。

互斥

实现互斥的方法主要包含如下几种：

互斥锁

互斥锁（Mutex，Mutal Exclusion）是操作系统提供的同步原语，用以实现多线程对于临界资源的互斥。 互斥锁提供了一种机制，确保在任何时刻只有一个线程能够持有该锁，从而确保共享资源的安全访问。

互斥锁通过以下特点实现线程互斥：

• 任何时候，只有一个线程可以持有互斥锁。其它试图获取该互斥锁的线程将被阻塞，直到持有锁的线程释放该锁。
• 只有锁的持有者才能释放它。这确保了非持有者不能误释放锁。

操作

互斥锁提供 加锁 和 解锁 这两个操作实现互斥：

• 锁定（Lock 或 Acquire）：当线程试图获取互斥锁时，如果锁已被其他线程持有，则该线程将被阻塞，直到锁被释放。
• 解锁（Unlock 或 Release）：持有互斥锁的线程在完成其对共享资源的访问后，应该释放锁以使其他线程可以获取锁。

通过这两个操作，线程即可对 临界区 进行 “上锁”：

mutex mtx;

void thread() {
    non critial section;
    lock(&mtx);
    critial section;
    unlock(&mtx);
    non critial section;
}

线程在进入临界区之前使用 lock(&mtx) 进行加锁，在退出临界区之后使用 unlock(&mtx) 进行解锁。 互斥的底层实现由操作系统完成，线程通过调用 mutex 的系统 API 即可实现互斥。

实现原理

MUTEX 的底层实现原理比较复杂，但是我们可以从逻辑上来理解其实现原理：

当线程尝试获取一个已经被持有的锁时，它会被挂起，并且不会消耗 CPU 资源。只有当锁被释放并且该线程被选择为下一个获取锁的线程时，它才会恢复执行。这样的机制确保了临界区的互斥访问，同时也尽量减少了不必要的 CPU 浪费。

第一个加锁的线程可以直接获取锁，后续加锁的线程会经历 阻塞 和 唤醒 这两个步骤：

• 阻塞：
  • 当线程尝试获取一个已经被其他线程持有的互斥锁时，该线程会进入一个等待状态，也称为阻塞状态。
  • 操作系统维护了一个与该互斥锁关联的 等待队列。尝试获取锁但未成功的线程会被放入这个队列中。
  • 被阻塞的线程会从“运行”状态转为“等待”或“睡眠”状态。这意味着该线程将不再获得 CPU 时间，直到它被唤醒。
• 唤醒：
  • 当持有互斥锁的线程释放该锁时，操作系统会检查与该锁关联的等待队列。
  • 通常，队列中的下一个线程（取决于调度策略，可能是队列的第一个线程或其他）会被选中并被唤醒，允许它获取锁。
  • 被唤醒的线程转换为“就绪”状态，并在适当的时候由调度器重新分配 CPU 时间，从而继续执行。

其大致过程如下图所示：

软件互斥

软件互斥依赖算法和程序设计来确保资源的独占访问。常用的软件互斥算法不依赖特定的硬件支持，主要通过逻辑控制和变量来实现。

Peterson 算法

Peterson’s 算法基于两个线程之间的竞争条件来实现互斥。它使用两个布尔变量和一个整数变量，分别表示两个线程的意愿和当前正在运行的线程。通过这些变量的协作，可以确保只有一个线程能够进入临界区。

Peterson’s 算法通常用于理论教学和理解互斥原理，但在实际多线程编程中并不常用，因为它只适用于两个线程之间的互斥。

// 初始化
bool flag[2] = {false, false};  // 两个线程的意愿
int turn = 0;                   // 当前运行的线程（0 或 1）

// 线程 1 希望进入临界区
void thread0() {
    flag[0] = true;
    turn = 1; // 通知线程 2 你可以运行了
    while (flag[1] && turn == 1) {
    // 等待线程 2 退出临界区或让出 CPU
    }
    // 进入临界区
    // ...
    // 退出临界区
    flag[0] = false;
}

// 线程 2 希望进入临界区
void thread1() {
    flag[1] = true;
    turn = 0; // 通知线程 1 你可以运行了
    while (flag[0] && turn == 0) {
    // 等待线程 1 退出临界区或让出 CPU
    }
    // 进入临界区
    // ...
    // 退出临界区
    flag[1] = false;
}

硬件互斥

上文中我们提到了软件互斥，即用复杂的软件逻辑实现了类似 加锁 和 解锁的操作。 硬件互斥与之类似，不过我们是使用 CPU 指令集中的 原子指令 来实现同等的功能。

使用原子指令实现的锁一般叫做 自选锁，因为加锁的过程需要不断地执行原子指令， 可能会大量占用 CPU。

原子性

原子性是指一个操作是不可分割的，要么完全执行，要么完全不执行。在多线程或多进程环境中，原子性确保操作不会被其他并发操作中断。

原子指令（Atomic Instructions），是计算机体系结构中的一种特殊指令，它们被设计为在单个处理器指令周期内执行完毕，不会被中断或其他线程干扰。

TAS 指令

Test-and-Set（TAS）指令：TAS 指令原子性地设置一个内存位置的值为 1，并返回该位置的先前值。 为了辅助各位读者理解，下述代码使用一个函数描述其内部逻辑。

// TAS 原子指令相当于以下函数被原子性地执行
int test_and_set(bool *lock) {
    bool old = *lock;
    *lock = true;
    return old;
}

在使用 TAS 指令实现自旋锁时，锁可以用一个整数变量表示，0 表示锁是空闲的，1 表示锁已经被占用。 加锁操作可以不断使用 TAS 指令来尝试将锁的值从 0 设置为 1，如果返回的先前值为 0，则表示锁定成功，否则表示锁定失败。 解锁操作将锁的值设置为 0。

mutex = 0;

thread() {
    while (test_and_set(&mutex) == 1); // 基于 TAS 实现自旋锁，如果 mutex 为 1 被占用，则循环等待。
    critial section; // 临界代码
    mutex = 0; // 解锁
}

TAS 实现自旋锁的具体工作原理如下：

• 当一个线程执行 TAS 指令时，它会读取一个共享变量 mutex 的值。
• 如果该值为 0（或 false），则线程将该值设置为 1（或 true），并继续执行临界区代码。
• 如果该值为 1（或 true），则线程将无法获取锁，需要等待锁被释放。
• 当线程完成临界区代码的执行后，它会将共享变量的值重置为 0（或 false），以释放锁。

CAS 指令

Compare-and-Swap（CAS）指令：CAS 指令原子性地比较内存中的一个值与预期值，如果相等，则将内存中的值替换为新值。

// CAS 原子指令相当于以下函数被原子性地执行
bool compare_and_set(bool *lock, bool expected, bool new_value) {
    if (*lock == expected) {
        *lock = new_value;
        return true;  // 操作成功
    } else {
        return false; // 操作失败
    }
}

在使用 CAS 指令实现自旋锁时，锁可以用一个整数变量表示，0 表示锁是空闲的，1 表示锁已经被占用。 加锁操作可以使用 CAS 指令来将锁的值从 0 修改为 1，如果 CAS 操作成功，则表示锁定成功。 解锁操作可以使用 CAS 来将锁的值从 1 修改为 0。

mutex = 0;

thread() {
    while (compare_and_set(&mutex, 0, 1) == false); // 基于 CAS 实现自旋锁，则循环等待直到操作成功
    critial section; // 临界代码
    mutex = 0; // 解锁
}

上述用 CAS 实现自旋锁的思路其实和 TAS 一致，锁都是用一个整数变量表示，原子指令会一直自旋直到 mutex=0 时， 然后原子性地将其设置为 1，表示当前线程占有了锁。

同步

同步是指多个线程之间为了合作完成任务，按照一定的顺序协同执行。 它控制了线程的执行顺序，确保它们按照特定的时序进行交互。

条件变量

条件变量（Condition Variable） 是一种同步原语，用于线程之间的有条件同步。它允许线程等待某个条件成立，同时释放已获取的锁，这样其他线程可以获取锁并可能更改共享数据的状态，使得条件成立。

条件变量具备以下特点：

• 实现同步操作：有时，线程需要等待某个条件才能继续执行。条件变量使线程可以等待，直到其他线程更改了共享数据的状态并满足了该条件。
• 避免忙等（busy-waiting）：而不是使线程不停地轮询共享数据以检查条件是否满足（这会浪费 CPU 资源），条件变量使线程可以休眠直到条件满足。

操作

• wait()：这个操作做两件事。首先，它会释放与条件变量关联的锁，从而使其他线程可以获取锁并更改共享数据的状态。其次，它会使调用它的线程休眠，直到另一个线程来唤醒它。
• signal()：这个操作用于唤醒等待在条件变量上的某个线程。如果多个线程在等待，通常只有一个线程被唤醒（但这取决于具体实现）。唤醒的线程将重新获取锁并从其调用 wait() 的地方继续执行。
• broadcast() 或 notify_all()：这个操作唤醒所有等待在条件变量上的线程。当共享数据的状态变化可能影响多个等待的线程时，这很有用。

信号量

信号量（Semephore）是一个同步原语，相比锁，信号量可以解决一些更加复杂的同步问题。

在逻辑上我们将信号量理解为一个整数计数值，用于表示可用资源的数量。

信号量提供两个原子操作：

• P （proberen，荷兰语的 “尝试” 之意）
• V （verhogen，荷兰语的 “增加” 之意）。

P 操作

P 操作也被称为 wait 操作， P 操作的具体流程如下：

• 如果信号量值 > 0，则减少信号量的值，并继续执行后续代码。
• 如果信号量值 = 0，则执行 P 操作的线程将被阻塞，直到信号量变为正值。

简而言之，就是尝试（正如荷兰语的原义）将信号量的值减一，若不至于将信号量的值减为负数。 则尝试成功，线程可继续执行后续代码。若尝试失败，则线程被阻塞。

V 操作

V 操作也被称为 signal 操作， V 操作的具体流程如下：

• 将信号量的值 +1，如果有任何线程因为 P 操作被阻塞，则选取一个被阻塞的线程并唤醒它。
  • 只有执行 V 操作前信号量值为 0，才会去唤醒阻塞线程。如果信号量的值 > 0，说明当前没有线程在 P 操作被阻塞。
  • 阻塞线程被唤醒后，执行 P 操作，信号量的值 -1。

实现原理

信号量的底层实现机制比较复杂， 这里只需要在逻辑上理解信号量的机制即可： 信号量中有维护有一个整数值、一个运行队列、一个阻塞队列。

• 当线程的 P 操作执行成功后，线程被加入信号量的运行队列。
• 当线程的 P 操作执行失败后，线程被加入信号量的阻塞队列。
• 当线程的 V 操作执行成果后，线程被从运行队列中移除，并尝试从阻塞队列中选取线程继续执行 P 操作。