同步和互斥

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

临界区和互斥

在并发编程中，临界区（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，表示当前线程占有了锁。

同步

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

注意

互斥和同步的关系？

互斥是同步的一种特殊情况，它确保了对共享资源的独占访问。

同步更关注于线程之间的协作关系，它不仅包括互斥，还包括顺序控制、条件等待和信号传递等。

互斥解决的是“同一时刻只能有一个访问”的问题。同步解决的是“按照某种顺序协同执行”的问题。

条件变量

条件变量（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 操作。

当一个线程尝试执行 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 底层接口的封装，为程序员提供一些更加简单易用的接口。理解管程的概念即可，小概率在选择题考察。