同步与互斥

★☆☆ 进程管理

🔥 高优先级

同步和互斥是 解答题同步问题设计 的基础，也是每年必考点，重要性这里就不多赘述了，这一节的每个知识点的细节都要深入掌握。

临界区和互斥

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

这种机制就叫做 互斥 ：

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

临界资源

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

提示

有 进程间的互斥 ，也有 线程间的互斥 。在实际考察过程中，更多考察的是 线程间的互斥 。

下文中介绍互斥相关概念时统一使用 线程 一词替代 进程/线程，请读者区分。

为何需要互斥

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

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

C 语言代码段

汇编代码段

执行完汇编指令后可能立即被中断

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

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

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

需要注意的是，互斥 并不表示线程在执行临界区代码的过程中不会被操作系统 中断 。

互斥是一种逻辑上的概念，它保证了多个线程不能同时进入临界区。线程 A 可能在执行临界区代码的过程中被中断，但是与之互斥的线程 B 同样不能在线程 A 被中断之时进入临界区。

互斥

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

方法说明
软件互斥依赖算法和程序设计来确保 临界资源 的独占
硬件互斥使用 CPU 指令集中的 原子指令 来实现 临界资源 的独占
锁操作系统提供的 API，软件直接调用即可实现资源独占
信号量操作系统提供的 API，可以用 信号量 来实现锁的功能

互斥锁

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

临界资源

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

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

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

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

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

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

实现原理

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

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

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

  • 阻塞 ：

  • 当线程尝试获取一个已经被其他线程持有的 互斥锁 时，该线程会进入一个 等待状态 ，也称为 阻塞状态 。

  • 操作系统维护了一个与该 互斥锁 关联的 等待队列 。尝试获取锁但未成功的 线程 会被放入这个队列中。

  • 被 阻塞 的线程会从“运行”状态转为“等待”或“睡眠”状态。这意味着该线程将不再获得 CPU 时间，直到它被 唤醒 。

    • 唤醒 ：

  • 当持有 互斥锁 的 线程 释放该锁时，操作系统会检查与该锁关联的 等待队列 。

  • 通常，队列中的下一个线程（取决于调度策略，可能是队列的第一个线程或其他）会被选中并被 唤醒 ，允许它获取锁。

  • 被 唤醒 的线程转换为“就绪”状态，并在适当的时候由调度器重新分配 CPU 时间，从而继续执行。

其大致过程如下图所示：

（调用了 acquire，还没有调用 release）

软件互斥

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

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。

原子性

原子性 （Atomicity）指一个操作在并发环境中表现为 不可分割的整体 ： 要么全部完成，要么完全不发生；在执行过程中，不会被其他线程观察到中间状态。

原子指令 （Atomic Instruction）是由 处理器架构定义的一类指令，其对外可观察效果 满足原子性语义 —— 即在多核/多线程并发访问下，不会与其他指令的执行结果交错。是否“原子”，不是由指令是否耗费一个 CPU 周期决定的，而是由体系结构对并发可见性的承诺决定的。

注意

所有机器指令都是原子的吗？

不是。

  • 寄存器-寄存器 、寄存器-立即数 等不涉及共享内存的指令，通常天然不存在并发可见性问题，可视为“原子”的；
  • 涉及内存访问 的指令，并不自动具备原子性。 即使某条指令在硬件上分多步完成，只要架构保证其对并发内存访问是不可分割的，它才是原子指令；
  • 只有被架构明确标注为原子的指令（如 lock 前缀指令、LL/SC、CAS 等），才在多核环境中提供真正的原子性与一致性保证。

在 C 语言层面 ，普通语句都 不具备原子性保证 ：一条 C 语句通常会被编译为多条机器指令，其中的读-改-写过程可能被并发线程打断。

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_swap(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_swap(&mutex, 0, 1) == false); // 基于 CAS 实现自旋锁，则循环等待直到操作成功
    critial section; // 临界代码
    mutex = 0; // 解锁
}

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

同步

同步 是指多个 线程 为了协同完成某项任务，必须按照一定的顺序执行操作。它主要解决 线程 之间在执行过程中如何协调的问题，确保它们以预期的时序进行交互与合作。

补充

互斥和同步的关系？

互斥 是 同步 的一种特例，它用于保证多个 线程 在访问共享资源时不会发生冲突，即在同一时刻最多只有一个 线程 可以访问该资源。

同步 的范畴更广，不仅包括 互斥 控制，还包括 线程 之间的顺序协调、条件等待、信号传递等机制。

简单来说 ：

  • 互斥 ：解决“同一时刻只能有一个 线程 访问共享资源”的问题；
  • 同步 ：解决“线程 之间需要按照某种顺序协同执行”的问题。

原则

在实现 线程 或 进程 同步时，需要遵循以下基本原则：

  • 空闲让进 ：如果没有其他线程处于临界区，则允许当前线程进入；
  • 忙则等待 ：若已有线程在临界区，则其他线程必须等待；
  • 有限等待 ：每个等待进入临界区的线程都有机会在有限时间内进入，避免 “死等”；
  • 让权等待 ：不能进入临界区的线程应主动放弃 CPU（如进入等待队列），避免 “忙等”。

上述的进程同步原则涉及到 “死等” 和 “忙等” 这两个概念：

  • 死等 状态：指一个 线程/进程 长期得不到资源或 临界区 的访问权，即使条件已经满足，也可能因为调度策略、优先级问题或实现缺陷，永远无法被唤醒或执行。
  • 忙等 状态：指 线程/进程 未能进入 临界区 ，但却反复占用 CPU 执行检查操作，不断轮询某个变量或状态，以判断自己是否可以进入 临界区 。

用更加通俗的话说，忙等 的本质就是“空转”，死等 的本质是“永远等不到”。

条件变量

条件变量 （Condition Variable）是一种 同步原语 ，用于在多线程之间进行 有条件的协作 。它允许线程在某个条件未满足时进入等待状态，并在等待期间自动释放已持有的锁，从而让其他线程有机会获取该锁并修改共享数据，使条件得以满足。

条件变量的主要作用：

  • 实现条件同步 ：当线程必须等待某个特定条件才能继续执行时，条件变量提供了一种高效的等待机制。
  • 避免忙等 （busy-waiting）：相比让线程不断轮询检查条件是否满足（浪费 CPU 资源），条件变量使线程在条件未满足时进入休眠，只有在条件被触发时才被唤醒。
操作

条件变量提供三种操作：

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

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

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

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

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

P（wait）| 申请资源| - 信号量>0 → 减1，继续
- 信号量=0 → 阻塞
V（signal）| 释放资源| - 信号量+1
- 若原值为0 → 唤醒一个阻塞线程

P 操作

P 操作又称 wait ，其执行过程如下：

  1. 检查信号量的当前值
  • 若 信号量 > 0，则将其值 减 1 ，线程继续执行后续代码。
  • 若 信号量 = 0 ，则线程被 阻塞 ，直至有线程执行 V 操作把信号量值提升为正数。

简而言之，P 操作是“尝试把信号量减一”。只有在减一后不会使信号量变为负数时，尝试才算成功，线程得以继续；否则线程进入阻塞状态。

V 操作

V 操作又称 signal ，其执行过程如下：

  1. 把信号量值加 1 。
  2. 如果原来的信号量值为 0 （即此时至少有一个线程因 P 操作被阻塞），则从阻塞队列中挑选 一个 线程唤醒。
  • 若原来的信号量值 > 0，说明没有线程在等待，因而不需要唤醒任何线程。

被唤醒的线程随后重新执行它的 P 操作，此时信号量的值会再 减 1 ，于是该线程可以顺利进入临界区或继续执行后续代码。

实现原理

下面不展开底层细节，只从概念上说明 信号量 的工作流程。一个信号量本质上维护三样东西：

  1. 计数值 – 表示当前可用资源的数量。
  2. 运行队列 – 正在执行或可以立即执行的线程集合。
  3. 阻塞队列 – 因资源不足而暂时挂起的线程集合。

在信号量上执行 P 操作和 V 操作和设计到对于线程状态的改变：

  • P 操作

  • 当线程的 P 操作执行 成功 后，线程被加入信号量的 运行队列 。

  • 当线程的 P 操作执行 失败 后，线程被加入信号量的 阻塞队列 。

    • V 操作

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

信号量的阻塞队列

Semaphore S

当一个 线程 尝试执行 P 操作并发现 信号量 的值为 0 或负数时，该操作会导致该 线程 阻塞 。具体地说，线程 会被移出运行队列并放入一个特定的阻塞队列。这个阻塞队列是与 信号量 关联的，其中保存了因该 信号量 被 阻塞 的所有 线程 。

当其他 线程 对该 信号量 执行 V 操作并增加其值时，一个被 阻塞 的 线程 （或多个，具体取决于实现和 信号量 的增量）会从阻塞队列中被选出并被唤醒，随后它可以继续执行。

信号量应用

信号量 比较灵活，可以替代 锁 的功能，也能实现更加复杂的同步操作，这节主要谈论 信号量 最常见的几种用法。

实现锁

当 信号量 的初始值为 1 时，可以把 信号量 当作 锁 使用：

  • 执行 P(sem) 相当于 lock(&mutex)。
  • 执行 V(sem) 相当于 unlock(&mutex)。
semaphore S = 1;

P1() {
    P(S);
    // critical section
    V(S);
}

P2() {
    P(S);
    // critical section
    V(S);
}

实现简单同步

利用 信号量 可以实现线程间的 同步 ，保证不同线程间某些操作的 顺序关系 。
这种简单同步用 条件变量 也可以实现，不过用 信号量 更为简单。

比如下述的代码，可以保证执行完 P1 中的 code1 之后，才会执行 P2 中的 code2：

semphore S = 0;  // 将信号量的初始值设置为 0

    code1;       // 先执行 code1
    V(S);        // 告诉线程 P2，code1 已经完成

    P(S);        // 检查 code1 是否完成
    code2;       // 检查无误，运行 code2

注意实现这种 P1 → P2 的同步关系，需要将 信号量 的初始值设置为 0，并在 P1 中调用 V(S)，并在 P2 中调用 P(S)，P2 中的 V(S) 会一直 阻塞 到 P1 中的 P(S) 执行完。

实现前驱关系

线程的 前驱关系 是指在多线程并发执行的环境中，某些线程的执行必须依赖于其他线程的完成。
这种依赖关系可以通过一个 有向无环图 （DAG）来描述，DAG 中的边表示了线程执行的 依赖关系 。

如下图所示：S2 和 S3 必须在 S1 执行完之后才能执行，S4 和 S5 必须在 S2 执行完后才能执行，S6 必须在 S3、S4、S5 执行完之后才能执行。

两个线程之间的 前驱关系 在 DAG 中 表示为一条边 ，我们可以一个 信号量 来表示这条边，将其初始值设置为 0，并使用 上文中提到的方法 使用这种单向同步。

管程

管程 （Monitor）本质上是一种 对互斥 + 条件同步的高级封装机制 ，通过结构化编程方式将“对共享资源的访问”与“同步控制”统一封装成一个模块，提升了程序的安全性和可读性。

补充

🔍 为什么有了信号量/条件变量，还需要管程？

锁 和 信号量 是更低级的同步原语。尽管它们非常有用并且广泛应用，但在某些情况下直接使用它们可能导致代码复杂且难以理解。另外，使用这些低级原语可能会增加 死锁 、饥饿 或其他同步问题的风险。

管程 的设计是为了将这些低级的细节隐藏起来，并提供一个更高级、更抽象的接口，使得程序员可以更容易地编写 正确、安全 的并发代码。

管程的 核心思想 是确保在任意时刻，最多只有一个线程 能够执行管程内部的代码，从而实现对 共享资源 的自动 互斥 。当其他线程尝试进入管程时，会被 阻塞 ，直到当前线程退出。

管程的 基本组成 ：

  • 共享数据 ：管程封装了需要被多个 线程 共享和访问的数据。
  • 方法 ：定义了如何操作 共享数据 的函数或方法。这些方法是唯一可以访问和修改 共享数据 的方式。
  • 条件变量 ：用于控制 线程 的执行顺序，让 线程 在某些条件下等待，或通知等待的 线程 继续执行。

举个实际例子说明什么是管程，比如我们可以用用管程封装生产者消费者问题。 管程其实就是对 OS 底层接口的封装，为程序员提供一些更加简单易用的接口。

相关笔记

  • 计算机系统概述
  • 操作系统概念
  • 操作系统结构
  • 程序运行环境
← 返回知识点列表