同步和互斥

同步和互斥是操作系统中考察的重中之重，关于各个概念的理解经常在选择题中出现，需要熟练掌握信号量的用法。

临界区和互斥

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

这种机制就叫做互斥：

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

临界资源

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

提示

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

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

为何需要互斥

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

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

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

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

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

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

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

互斥

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

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

互斥锁

互斥锁（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），是计算机体系结构中的一种特殊指令，它们被设计为在单个处理器指令周期内执行完毕，不会被中断或其他线程干扰。

注意

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

一些简单的机器指令，例如将数据从一个寄存器移动到另一个寄存器，通常是原子的。这些指令通常在单个 CPU 周期内完成，不会被中断。

但是现代 CPU 指令集越来越复杂，许多复杂的机器指令，例如涉及多个内存访问或需要多个步骤的指令，可能不是原子的。例如，某些指令可能需要多个 CPU 周期才能完成，或者可能涉及对多个内存位置的访问。在这些情况下，指令的执行可能会被中断，从而导致数据竞争或其他并发问题。

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，表示当前线程占有了锁。

同步

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

补充

互斥和同步的关系？

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

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

简单来说：

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

原则

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

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

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

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

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

条件变量

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

条件变量 具备以下特点：

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

操作

条件变量提供三种操作：

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

信号量

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

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

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

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

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

P 操作

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

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

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

V 操作

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

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

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

实现原理

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

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

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

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

当一个线程尝试执行 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

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

P2() {
    ...
    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，并使用上文中提到的方法使用这种单向同步。

semphore a1 = a2 = b1 = b2 = c = d = e = 0;

S1() {                       S2() {
    ...;                         P(a1);
    V(a1); V(a2);                ...
}                                V(b1); V(b2);
                             }

S3() {                       S4() {     
    P(a2);                       P(b1); 
    V(e);                        V(c);  
}                            }


S5() {                       S6() {
    P(b2);                       P(c); P(d); P(e);
    V(d);                    }
}

管程

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

补充

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

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

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

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

管程的 基本组成：

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

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