进程同步

在并发系统中，多个进程或线程需要访问共享资源时，如果没有适当的同步机制，就会产生数据竞争和不确定的行为。当两个或多个进程同时修改同一个共享变量时，可能导致数据不一致、计算结果错误或系统状态混乱。这就是我们在计算机系统中经常遇到的问题——多个进程或线程同时访问共享资源时产生的冲突。

在操作系统中，我们经常遇到多个进程需要协作完成任务的情况。 这些进程可能运行在不同的处理器核心上，也可能在同一个核心上轮流执行。 当它们需要访问共享的数据结构时，比如内存中的同一个变量，就会出现我们称之为“竞态条件”的问题。

让我们通过一个具体的例子来理解这个问题。假设我们有一个生产者-消费者系统，生产者负责往缓冲区中放入数据，消费者负责从缓冲区中取出数据。 我们用一个计数器 count 来记录缓冲区中当前有多少个数据项。

生产者进程的代码可能是这样的：

|
while (true) {
    /* 生产一个数据项 */
    while (count == BUFFER_SIZE)
        ; /* 缓冲区满了，等待 */
    buffer[in] = next_produced;
    in = (in + 1) % BUFFER_SIZE;
    count++; /* 增加计数器 */
}

消费者进程的代码可能是这样的：

|
while (true) {
    while (count == 0)
        ; /* 缓冲区空了，等待 */
    next_consumed = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
    count--; /* 减少计数器 */
    /* 消费数据项 */
}

单独来看，这两个进程的代码都是正确的。但是当它们并发执行时，问题就出现了。 假设当前 count 的值是 5，生产者进程和消费者进程同时执行 count++ 和 count-- 操作。 执行完这两个操作后，count 的值可能是 4、5 或 6！而正确的结果应该是 5。

临界区

为了解决这类问题，我们引入了"临界区"的概念。临界区是指一段代码，在这段代码中进程可能会访问和修改与其他进程共享的数据。为了保证数据一致性，同一时刻只能有一个进程执行临界区代码。当一个进程正在执行临界区时，其他试图进入临界区的进程必须等待，直到当前进程完成临界区的执行并退出。这种机制确保了共享资源不会被多个进程同时访问，从而避免了数据竞争和冲突。

因此我们的每个进程都有这样的结构：

|
while (true) {
    entry_section();    /* 进入区 */
    critical_section(); /* 临界区 */
    exit_section();     /* 退出区 */
    remainder_section(); /* 剩余区 */
}

解决临界区问题必须满足三个要求：

• 互斥性：如果进程 Pi 正在执行其临界区，那么其他进程就不能执行它们的临界区。这确保了同一时刻只有一个进程能够访问共享资源，从而保证数据的一致性。
• 进展性：如果没有进程在执行临界区，而某些进程希望进入临界区，那么只有那些不在剩余区执行的进程才能参与决定哪个进程将进入临界区，而且这个选择不能被无限期地推迟。这确保了系统能够持续向前推进，不会因为所有进程都在剩余区而陷入停滞。
• 有限等待：当一个进程请求进入其临界区时，在请求被满足之前，其他进程被允许进入其临界区的次数存在一个界限。这防止了某个进程被无限期地延迟，确保每个进程都有机会执行其临界区。

内核中的竞态条件

在操作系统中，内核负责管理所有进程和系统资源，需要维护大量的共享数据结构。例如，内核维护着文件描述符表，记录哪些进程打开了哪些文件。每当有进程打开或关闭文件时，这个表就需要更新。如果两个进程同时尝试修改这个表，就可能出现数据不一致的情况，这就是我们所说的"竞态条件"。

考虑一个典型的场景：两个进程 P0 和 P1 几乎在同一时刻都调用了 fork() 系统调用，各自需要创建一个新进程。操作系统需要为每个新进程分配一个唯一的进程标识符（PID）。如果没有适当的互斥保护机制，可能会出现两个新进程被分配到相同 PID 的情况，这会导致进程管理混乱，系统无法正确识别和调度这些进程。

内核中的许多共享数据结构都容易受到竞态条件的影响，包括内存分配表、进程控制块链表、中断处理相关的数据结构等。这些数据结构可能被多个进程或中断处理程序同时访问。为了确保操作系统的正确性和稳定性，内核开发者必须使用适当的同步机制来保护这些共享数据，防止并发访问导致的数据损坏。

抢占式与非抢占式内核

操作系统的内核负责进程调度和资源管理，决定哪个进程能够使用 CPU 资源。根据内核是否允许在进程执行内核代码时被其他进程抢占，我们可以将内核分为两种类型：非抢占式内核和抢占式内核。

非抢占式内核的特点是，一旦一个进程进入内核模式执行系统调用或中断处理，它就会一直执行直到主动放弃 CPU 控制权。在内核模式下，进程不会被其他进程强制中断，只有当前进程自愿阻塞、完成系统调用返回用户模式，或者发生中断时，其他进程才有机会获得 CPU。这种设计的好处是实现简单，由于内核代码的执行不会被意外中断，内核数据结构的访问相对安全，不容易出现并发访问导致的竞态条件。

抢占式内核则允许系统在任何时候中断正在执行的进程，即使该进程正在内核模式下运行。当更高优先级的进程需要执行，或者时间片用尽时，系统可以强制当前进程让出 CPU，切换到其他进程。这种设计使得系统能够更快地响应外部事件和实时任务，提高系统的响应性和公平性。

不过，抢占式内核的实现更加复杂。在多处理器系统中，可能有多个进程在不同的 CPU 核心上同时执行内核代码，它们可能同时访问和修改相同的内核数据结构。设计抢占式内核时，开发者必须仔细考虑所有可能的并发场景，使用适当的同步机制来保护共享数据结构，防止数据竞争和系统状态不一致。

尽管实现复杂，抢占式内核在现代操作系统中被广泛采用，因为它能够提供更好的系统响应性和实时性能。对于需要快速响应外部事件的场景，如实时系统、交互式应用等，抢占式内核能够确保高优先级任务能够及时得到处理。而非抢占式内核虽然实现简单、数据访问更安全，但在响应性方面存在不足，可能导致高优先级任务被低优先级任务长时间阻塞。

Peterson 解决方案

接下来，我们介绍一个经典的软件解决方案来解决临界区问题，这就是 Peterson 解决方案。 这个解决方案是由计算机科学家 Gary L. Peterson 提出的，它展示了如何仅使用软件算法来实现进程同步。

Peterson 解决方案适用于两个进程的情况，这两个进程在它们的临界区和剩余区之间交替执行。 我们将这两个进程编号为 P0 和 P1。为了便于描述，当我们讨论进程 Pi 时，我们用 Pj 表示另一个进程，即 j 等于 1 - i。

Peterson 解决方案要求两个进程共享两个数据项：

|
int turn;
boolean flag[2];

变量 turn 表示轮到哪个进程进入其临界区。也就是说，如果 turn == i，那么进程 Pi 被允许在其临界区中执行。 flag 数组用于指示进程是否准备好进入其临界区。例如，如果 flag[i] 为真，Pi 就准备好进入其临界区。 Peterson 解决方案的算法如下：

|
while (true) {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j)
        ; /* 等待 */
    /* 临界区 */
    flag[i] = false;
    /* 剩余区 */
}

这个算法的工作原理是这样的：要进入临界区，进程 Pi 首先将 flag[i] 设置为真，然后将 turn 设置为值 j，从而断言如果另一个进程希望进入临界区，它可以这样做。如果两个进程同时尝试进入，turn 将被设置为 i 和 j，但只有一个赋值会保留，另一个会被立即覆盖。turn 的最终值决定了两个进程中哪个被允许首先进入其临界区。

硬件同步支持

我们刚刚描述了一个基于软件的临界区问题解决方案。然而，正如我们所提到的一样，基于软件的解决方案在现代计算机架构上并不能保证正确工作。 所以在这一部分，我们介绍三种硬件指令，它们为解决临界区问题提供支持。

内存屏障

之前我们看到系统可能会重新排序指令，这种策略可能导致不可靠的数据状态。计算机架构如何确定它将为应用程序提供什么内存保证，这被称为其内存模型。 一般来说，内存模型分为两类：

• 强序内存模型：一个处理器上的内存修改立即对所有其他处理器可见。
• 弱序内存模型：一个处理器上对内存的修改可能不会立即对其他处理器可见。

内存模型因处理器类型而异，所以内核开发者不能对共享内存多处理器上内存修改的可见性做任何假设。 为了解决这个问题，计算机架构提供了指令，可以强制内存中的任何更改传播到所有其他处理器，从而确保内存修改对其他处理器上运行的线程可见。 这样的指令被称为内存屏障或内存栅栏。

当执行内存屏障指令时，系统确保所有加载和存储操作在任何后续加载或存储操作执行之前完成。 因此，即使指令被重新排序，内存屏障也确保存储操作在内存中完成并对其他处理器可见，然后才执行未来的加载或存储操作。

硬件指令

现代处理器架构提供了一些特殊的硬件指令，这些指令能够以原子方式执行内存的读取、修改和写入操作。这些指令在执行过程中不会被中断，保证了操作的完整性和一致性。通过合理使用这些原子指令，我们可以构建高效的同步机制来解决临界区问题，确保多个进程能够有序地访问共享资源。

其中一个指令是测试并设置指令， test_and_set() 指令可以定义如下：

|
boolean test_and_set(boolean *target) {
    boolean rv = *target;
    *target = true;
    return rv;
}

这个指令的重要特征是它是原子执行的。因此，如果两个 test_and_set() 指令同时执行（每个在不同的核心上），它们将按某种任意顺序顺序执行。

如果机器支持 test_and_set() 指令，那么我们可以通过声明一个初始化为假的布尔变量 lock 来实现互斥。进程 Pi 的结构如下：

|
do {
    while (test_and_set(&lock))
        ; /* 什么都不做 */
    /* 临界区 */
    lock = false;
    /* 剩余区 */
} while (true);

另一个指令是比较并交换指令， compare_and_swap() 指令（CAS）就像 test_and_set() 指令一样，原子地操作两个字，但使用基于交换两个字内容的机制。 CAS 指令操作三个操作数，定义如下：

|
int compare_and_swap(int *value, int expected, int new_value) {
    int temp = *value;
    if (*value == expected)
        *value = new_value;
    return temp;
}

只有当表达式 (*value == expected) 为真时，操作数 value 才被设置为 new_value。无论如何，CAS 总是返回变量 value 的原始值。这个指令的重要特征是它是原子执行的。

使用 CAS 的互斥可以按如下方式提供：声明一个全局变量（lock）并将其初始化为 0。第一个调用 compare_and_swap() 的进程将 lock 设置为 1。然后它将进入其临界区，因为 lock 的原始值等于期望值 0。对 compare_and_swap() 的后续调用将不会成功，因为 lock 现在不等于期望值 0。当进程退出其临界区时，它将 lock 设置回 0，这允许另一个进程进入其临界区。

原子变量

compare_and_swap() 指令本身很少直接用来实现互斥锁，它更多是作为构建更高级同步原语的基础组件。原子变量就是基于这些硬件指令构建的常用同步工具。

原子变量是指对基本数据类型（如整数、布尔值）进行的操作能够保证原子性，即这些操作要么完全执行，要么完全不执行，不会被其他线程的操作打断。例如，如果我们有一个计数器，多个线程都需要对其进行递增操作。如果使用普通的非原子操作，可能出现两个线程同时读取相同的值，各自加一后写回，导致最终结果只增加了一次而不是两次。使用原子变量后，每次递增操作都是完整且独立的，不会出现这种数据竞争问题。

现代操作系统和编程语言都提供了原子类型和相应的原子操作函数。这些原子操作的底层实现通常依赖于 compare_and_swap() 等硬件指令，既保证了操作的原子性，又具有较高的执行效率。

互斥锁

直接使用硬件指令来实现临界区保护虽然可行，但实现复杂且容易出错，对普通程序员来说不够友好。因此，操作系统设计者提供了更高级的同步原语，这些工具封装了底层的复杂性，使用起来更加简单和安全。

互斥锁（mutex）是最基础和常用的同步工具。互斥锁提供了获取锁和释放锁两个基本操作。进程在进入临界区之前必须先获取锁，如果锁已被其他进程持有，当前进程必须等待直到锁被释放。进程完成临界区的执行后必须释放锁，允许其他等待的进程获得锁并进入临界区。通过这种方式，互斥锁确保了同一时刻只有一个进程能够执行临界区代码，从而保护共享资源不被并发访问。

互斥锁有一个布尔变量 available，其值表示锁是否可用。 如果锁可用，对 acquire() 的调用就会成功，然后锁被认为是不可用的。尝试获取不可用锁的进程会被阻塞，直到锁被释放。

acquire() 的定义如下：

|
acquire() {
    while (!available)
        ; /* 忙等待 */
    available = false;
}

release() 的定义如下：

|
release() {
    available = true;
}

对 acquire() 或 release() 的调用必须原子地执行。因此，互斥锁可以使用我们在刚刚中描述的 CAS 操作来实现。

我们前面描述的互斥锁实现方式通常被称为"自旋锁"。自旋锁的特点是，当进程尝试获取锁但发现锁已被持有时，它会在一个循环中不断检查锁的状态，而不是进入阻塞状态。这种等待方式被称为"自旋"，因为进程在原地循环等待，消耗 CPU 资源但保持运行状态。

自旋锁的优势在于避免了进程上下文切换的开销。当锁的持有时间很短时，自旋等待可能比阻塞等待更高效，因为阻塞和唤醒进程需要操作系统进行上下文切换，这本身就有一定的开销。在多处理器系统中，如果一个线程在一个 CPU 核心上自旋等待锁，而持有锁的线程在另一个 CPU 核心上执行，锁可能很快就会被释放，自旋等待就能立即获得锁。因此，自旋锁在现代操作系统中被广泛使用，特别适合锁持有时间很短、竞争不激烈的场景。

信号量

互斥锁提供了基本的互斥机制，确保同一时刻只有一个进程能够访问共享资源。但在某些场景下，我们需要更灵活的同步机制，不仅能够控制互斥访问，还能协调多个进程的执行顺序和资源分配。信号量就是这样一种更通用的同步工具。

信号量是一个整数变量，只能通过两个原子操作来修改：wait() 和 signal()。这两个操作都是原子执行的，不会被其他操作打断。信号量的概念由荷兰计算机科学家 Edsger W. Dijkstra 提出。在原始术语中，wait() 操作被称为 P 操作（来自荷兰语"proberen"，意为测试），signal() 操作被称为 V 操作（来自荷兰语"verhogen"，意为增加）。

wait() 的定义如下：

|
wait(S) {
    while (S <= 0)
        ; // 忙等待
    S--;
}

signal() 的定义如下：

|
signal(S) {
    S++;
}

wait() 和 signal() 操作中对信号量整数值的所有修改都必须原子地执行。 也就是说，当一个进程修改信号量值时，没有其他进程可以同时修改同一个信号量值。 此外，在 wait(S) 的情况下，对 S 整数值的测试（S ≤ 0）以及其可能的修改（S--）必须不间断地执行。

信号量的使用

根据信号量的取值范围，我们可以将其分为两类：计数信号量和二进制信号量。

计数信号量的值可以是任意非负整数，用于管理有限数量的资源。例如，如果系统中有 5 个可用的资源实例，我们可以将信号量初始化为 5。每当一个进程需要使用资源时，它执行 wait() 操作，信号量的值减一。如果信号量的值大于 0，进程可以继续执行；如果信号量的值变为 0，表示所有资源都已被占用，后续的 wait() 操作会使进程阻塞，直到有资源被释放。当进程使用完资源后，执行 signal() 操作，信号量的值加一，唤醒一个等待的进程。

二进制信号量的值只能是 0 或 1，实际上就是计数信号量的特例。二进制信号量的功能与互斥锁类似，用于保证互斥访问。如果系统没有专门的互斥锁实现，可以使用二进制信号量来达到相同的效果。当信号量的值为 1 时，表示资源可用；为 0 时，表示资源被占用。

计数信号量适用于管理有限数量的同质资源，如缓冲区槽位、连接池中的连接等。二进制信号量则主要用于实现互斥，确保同一时刻只有一个进程能够访问临界区。当信号量的值变为 0 时，后续尝试获取资源的进程必须等待，直到有进程释放资源使信号量的值大于 0。

我们也可以使用信号量来解决各种同步问题。例如，考虑两个并发运行的进程：P1 有语句 S1，P2 有语句 S2。 假设我们要求只有在 S1 完成后才执行 S2。我们可以通过让 P1 和 P2 共享一个初始化为 0 的公共信号量 synch 来轻松实现这个方案。 在进程 P1 中，我们插入语句：

|
S1;
signal(synch);

在进程 P2 中，我们插入语句：

|
wait(synch);
S2;

因为 synch 被初始化为 0，P2 只有在 P1 调用了 signal(synch) 之后才会执行 S2，这是在语句 S1 被执行之后。

信号量的实现

我们之前讨论的互斥锁实现使用了忙等待（自旋）的方式，这种方式会持续消耗 CPU 资源。同样，如果信号量的 wait() 和 signal() 操作也采用忙等待方式，当资源不可用时，进程会在循环中不断检查信号量的值，浪费 CPU 资源。

为了解决这个问题，我们可以让等待的进程进入阻塞状态，而不是持续占用 CPU。具体实现方式是：当进程执行 wait() 操作时，如果发现信号量的值不大于 0，表示资源不可用，进程将自己挂起并加入到信号量的等待队列中，同时将进程状态设置为阻塞。这样，CPU 可以调度其他就绪的进程执行，提高了系统资源的利用率。

当其他进程执行 signal() 操作释放资源时，信号量的值增加。如果等待队列中有被阻塞的进程，系统会从队列中选择一个进程唤醒（使用 wakeup() 操作），将其状态从阻塞改为就绪，并重新加入到可调度的进程队列中，等待 CPU 调度执行。

通过引入等待队列机制，信号量实现了高效的进程同步，避免了忙等待带来的 CPU 资源浪费。每个信号量都维护一个等待队列，确保等待资源的进程能够有序排队，并在资源可用时被及时唤醒。

|
typedef struct {
    int value;
    struct process *list;
} semaphore;

每个信号量都有一个整数值和一个进程列表。当进程必须在信号量上等待时，它被添加到进程列表中。 signal() 操作从等待进程列表中移除一个进程并唤醒该进程。 现在，wait() 信号量操作可以定义为：

|
wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        add this process to S->list;
        sleep();
    }
}

signal() 信号量操作可以定义为：

|
signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        remove a process P from S->list;
        wakeup(P);
    }
}

sleep() 操作挂起调用它的进程。wakeup(P) 操作恢复挂起进程 P 的执行。这两个操作由操作系统作为基本系统调用提供。

管程

信号量虽然功能强大，能够解决各种进程同步问题，但在实际使用中容易出现错误。这些错误往往难以发现，因为它们只在特定的执行顺序下才会出现，在大多数情况下可能不会暴露问题。

我们之前讨论的生产者-消费者问题就展示了这种复杂性。如果同步机制使用不当，可能出现数据不一致的情况，例如计数器的值与实际缓冲区中的数据项数量不匹配。这正是为什么需要互斥锁和信号量等同步工具来确保数据一致性。

然而，即使使用了互斥锁或信号量，如果使用方式不正确，仍然可能出现同步错误。例如，在使用二进制信号量 mutex 保护临界区时，进程必须在进入临界区前调用 wait(mutex)，在退出临界区后调用 signal(mutex)。如果操作顺序错误，比如先执行 signal(mutex) 再执行 wait(mutex)，就可能导致多个进程同时进入临界区，违反互斥要求。

这些错误可能源于程序员的疏忽，也可能是因为不同进程的代码由不同开发者编写，导致同步协议不一致。只要有一个进程没有正确遵循同步协议，整个系统的正确性就会受到影响。因此，虽然信号量功能强大，但使用时必须严格遵守协议，否则容易引入难以调试的并发错误。

假设程序交换了信号量 mutex 上的 wait() 和 signal() 操作的执行顺序，导致以下执行：

|
signal(mutex);
...
critical section
...
wait(mutex);

在这种情况下，几个进程可能同时在其临界区中执行，违反了互斥要求。 只有在几个进程同时在其临界区中活跃时，才可能发现这个错误。

假设程序用 wait(mutex) 替换 signal(mutex)。也就是说，它执行：

|
wait(mutex);
...
critical section
...
wait(mutex);

在这种情况下，进程将在第二次调用 wait() 时永久阻塞，因为信号量现在不可用。 假设进程省略了 wait(mutex)，或 signal(mutex)，或两者都省略。 在这种情况下，要么违反互斥，要么进程将永久阻塞。

这些例子说明了当程序员使用信号量或互斥锁错误地解决临界区问题时，很容易产生各种类型的错误。 处理这类错误的一种策略是将简单的同步工具作为高级语言构造。因此在这一部分中，我们描述一个基本的高级同步构造——管程类型。

管程的使用

抽象数据类型（ADT）封装了数据结构和操作这些数据的函数，隐藏了实现细节，只对外提供接口。管程是一种特殊的抽象数据类型，它不仅封装了数据和操作，还内置了互斥机制，确保同一时刻只有一个进程能够执行管程内的操作。

在管程中，我们可以定义共享变量来维护状态，以及操作这些变量的函数。这些函数只能在管程内部被调用，管程的互斥机制由编译器或运行时系统自动保证，程序员无需手动管理锁的获取和释放。管程的基本结构如下：

|
monitor monitor_name {
    /* 共享变量声明 */
    function P1(...) {
        ...
    }
    function P2(...) {
        ...
    }
    ...
    function Pn(...) {
        ...
    }
    initialization_code(...) {
        ...
    }
}

管程提供了数据封装和自动互斥保护。进程只能通过管程提供的接口函数来访问共享数据，不能直接访问管程内部的变量。管程的互斥机制确保同一时刻只有一个进程能够执行管程内的代码，这种互斥是由系统自动保证的，程序员无需手动编写锁的获取和释放代码，从而减少了出错的可能性。

然而，仅仅保证互斥访问还不够，有时我们需要更复杂的同步机制。例如，某些操作需要等待特定条件满足后才能继续执行。为了支持这种需求，管程引入了条件变量的概念。我们可以在管程中声明 condition 类型的变量，用于实现基于条件的同步：

|
condition x, y;

可以对条件变量调用的唯一操作是 wait() 和 signal()。操作：

|
x.wait();

意味着调用此操作的进程被挂起，直到另一个进程调用：

|
x.signal();

x.signal() 操作恢复恰好一个挂起的进程。如果没有进程被挂起，那么 signal() 操作没有效果；也就是说，x 的状态与操作从未被执行时相同。将此操作与与信号量关联的 signal() 操作进行对比，后者总是影响信号量的状态。

现在假设当进程 P 调用 x.signal() 操作时，存在与条件 x 关联的挂起进程 Q。显然，如果允许挂起的进程 Q 恢复其执行， 发信号的进程 P 必须等待。否则，P 和 Q 将同时在管程内处于活动状态。然而，注意，从概念上讲，两个进程都可以继续其执行。存在两种可能性：

1. 信号并等待：P 要么等待直到 Q 离开管程，要么等待另一个条件。
2. 信号并继续：Q 要么等待直到 P 离开管程，要么等待另一个条件。

采用任一选项都有合理的论据。一方面，由于 P 已经在管程中执行，信号并继续方法似乎更合理。 另一方面，如果我们允许线程 P 继续，那么到 Q 被恢复时，Q 等待的逻辑条件可能不再成立。这 两种选择之间也存在折衷：当线程 P 执行信号操作时，它立即离开管程。因此，Q 立即被恢复。

使用信号量实现管程

我们可以使用信号量来实现管程的互斥机制。每个管程使用一个二进制信号量 mutex（初始值为 1）来保证互斥访问。进程在进入管程时执行 wait(mutex)，退出管程时执行 signal(mutex)，这样确保了同一时刻只有一个进程能够执行管程内的代码。

然而，当管程内的进程执行条件变量的 signal() 操作唤醒等待的进程时，会出现一个问题：被唤醒的进程需要进入管程，但当前进程还在管程内。为了解决这个问题，我们引入一个二进制信号量 next（初始值为 0）和一个计数器 next_count。当进程执行 signal() 操作唤醒其他进程时，它会在 next 上等待，直到被唤醒的进程完成操作并退出管程。next_count 用于记录有多少个进程在 next 上等待。

所以，每次我们写管程里的外部函数 F，都要这样改造一下：

|
wait(mutex);
...
body of F
...
if (next_count > 0)
    signal(next);
else
    signal(mutex);

这样，管程内的互斥就得到了确保。 我们现在也可以描述如何实现条件变量。对于每个条件 x，我们引入一个二进制信号量 x_sem 和一个整型变量 x_count，两者都初始化为 0。操作 x.wait() 现在可以实现为：

|
x_count++;
if (next_count > 0)
    signal(next);
else
    signal(mutex);
wait(x_sem);
x_count--;

操作 x.signal() 可以实现为：

|
if (x_count > 0) {
    next_count++;
    signal(x_sem);
    wait(next);
    next_count--;
}

这种实现方式遵循了 Hoare 和 Brinch-Hansen 提出的标准管程定义。不过，在某些场景下，我们可以使用更简化的实现方式，在保证正确性的同时提高执行效率。

管程内的进程恢复

我们现在转向管程内进程恢复顺序的主题。如果几个进程在条件 x 上挂起，并且某个进程执行了 x.signal() 操作， 那么我们如何确定应该恢复哪个挂起的进程呢？一个简单的解决方案是使用先进先出（FCFS）排序，这样等待时间最长的进程首先被恢复。 然而，在许多情况下，这种简单的调度方案是不够的。在这些情况下，可以使用条件等待构造。这个构造的形式为：

|
x.wait(c);

这里的 c 是调用 wait() 时计算出的一个整数值，可以理解为优先级参数。每个等待的进程都会将自己的标识和优先级参数一起记录在等待队列中。当有进程执行 x.signal() 操作时，系统会选择优先级参数最小的进程（即优先级最高的进程）优先恢复执行。

例如，我们可以设计一个 ResourceAllocator 管程来管理稀缺资源。每个进程在申请资源时，可以指定自己预计使用资源的时间长度作为优先级参数。管程会优先将资源分配给预计使用时间最短的进程，这样可以提高资源的利用率，减少平均等待时间。

需要访问相关资源的进程必须观察以下序列：

|
R.acquire(t);
...
access the resource;
...
R.release();

其中 R 是 ResourceAllocator 类型的实例。

不幸的是，管程概念不能保证前面的访问序列将被观察。特别是，可能出现以下问题：

• 进程可能在没有首先获得资源访问权限的情况下访问资源。
• 进程可能在获得资源访问权限后永远不会释放资源。
• 进程可能尝试释放它从未请求过的资源。
• 进程可能请求相同的资源两次（没有首先释放资源）。

使用信号量时我们也会遇到类似的问题，这正是引入管程的原因之一。虽然管程提供了更高级的抽象和自动互斥保护，但它仍然要求程序员正确使用管程提供的接口。编译器无法检查所有可能的误用情况。

一个可行的解决方案是将所有资源访问操作都封装在管程内部，强制所有进程通过管程接口访问资源。这样做的优势是资源访问的统一管理，但缺点是资源分配策略被限制在管程内部实现的算法，可能无法满足某些特定的调度需求。

要确保系统正确运行，需要满足两个条件：第一，所有进程必须按照规定的协议调用管程操作，不能跳过必要的步骤或改变调用顺序；第二，不能有进程绕过管程直接访问共享资源，所有资源访问都必须通过管程接口进行。只有满足这两个条件，系统才能保证数据一致性和调度算法的正确性。

活跃性

我们使用各种同步工具来确保进程有序地访问临界区，但这种机制可能带来一个副作用：某些进程可能长时间无法获得执行机会，一直处于等待状态。回顾我们之前讨论的临界区问题的三个要求，如果进程一直无法进入临界区，就违反了进展性和有限等待的要求。

活跃性是指系统保证每个进程都能持续向前推进，不会无限期地阻塞在某个状态。如果某个进程长时间无法获得所需的资源或执行机会，就出现了活跃性失败。

活跃性失败有多种表现形式，但都会导致系统性能下降和响应能力降低。最简单的活跃性失败是进程陷入死循环或持续忙等待，无法完成预期任务。在并发编程中，如果互斥锁、信号量等同步工具使用不当，很容易导致进程永久阻塞或长时间等待。接下来，我们讨论几种常见的活跃性失败情况。

死锁

使用等待队列的信号量实现可能导致两个或多个进程无限期地等待只能由其中一个等待进程引起的事件的情况。 相关事件是 signal() 操作的执行。当达到这种状态时，这些进程被称为死锁。

为了说明这一点，考虑一个由两个进程 P0 和 P1 组成的系统，每个进程访问两个信号量 S 和 Q，设置为值 1：

|
P0: wait(S); wait(Q); ... signal(S); signal(Q);
P1: wait(Q); wait(S); ... signal(Q); signal(S);

假设 P0 执行 wait(S)，然后 P1 执行 wait(Q)。当 P0 执行 wait(Q) 时，它必须等待直到 P1 执行 signal(Q)。 类似地，当 P1 执行 wait(S) 时，它必须等待直到 P0 执行 signal(S)。由于这些 signal() 操作无法执行，P0 和 P1 死锁。

死锁可以理解为：一组进程中的每个进程都在等待只能由该组中其他进程才能引发的事件，导致所有进程都无法继续执行。最常见的情况是多个进程以不同的顺序请求多个资源（如互斥锁、信号量），形成循环等待。除了资源获取和释放，其他类型的同步事件也可能导致死锁。我们将在后续章节中详细讨论死锁的成因、检测和预防方法。

优先级反转

优先级反转是指高优先级进程被低优先级进程间接阻塞的现象。考虑一个场景：有三个进程 L（低优先级）、M（中优先级）和 H（高优先级）。进程 L 首先获得了共享资源 S 的锁，正在使用该资源。此时，高优先级进程 H 也需要访问资源 S，但由于锁被 L 持有，H 必须等待 L 释放锁。

正常情况下，L 完成资源使用后会释放锁，H 就能继续执行。但如果此时中优先级进程 M 就绪并抢占 CPU，由于 M 的优先级高于 L，L 无法继续执行，也就无法释放资源 S。结果，高优先级进程 H 被中优先级进程 M 间接阻塞，这就是优先级反转问题。

优先级反转通常发生在具有三个或更多优先级级别的系统中。为了解决这个问题，操作系统实现了优先级继承协议。该协议的基本思想是：当高优先级进程等待低优先级进程持有的资源时，低优先级进程临时继承等待它的最高优先级进程的优先级。在上面的例子中，由于 H 在等待 L 持有的资源，L 会临时继承 H 的优先级，这样 M 就无法抢占 L，L 能够尽快完成资源使用并释放锁，H 就能及时获得资源。当 L 释放资源后，其优先级恢复为原来的低优先级。

优先级继承协议确保了持有被高优先级进程等待的资源的进程能够以足够高的优先级执行，从而尽快释放资源，避免高优先级进程被中优先级进程间接阻塞。

经典同步问题

这一部分我们讨论几个经典的进程同步问题。这些问题在并发编程领域具有代表性，经常被用来验证和演示新的同步机制的有效性。我们在讲解这些问题时，主要使用信号量来实现同步，因为这是最传统和常见的实现方式。在实际开发中，也可以使用互斥锁等其他同步原语来实现，基本原理是相似的。

有界缓冲区问题

有界缓冲区问题描述了生产者和消费者之间的同步关系。系统维护一个固定大小的缓冲区，生产者进程向缓冲区中放入数据，消费者进程从缓冲区中取出数据。当缓冲区满时，生产者必须等待直到有空间可用；当缓冲区空时，消费者必须等待直到有数据可用。

为了协调生产者和消费者的操作，我们需要使用同步原语。以下是生产者和消费者共享的同步变量：

|
int n;
semaphore mutex = 1;
semaphore empty = n;
semaphore full = 0;

缓冲区可以看作是一个有 n 个槽位的数组，每个槽位可以存储一个数据项。为了确保对缓冲区的访问是互斥的，我们使用一个二进制信号量 mutex（初始值为 1）来保护临界区。此外，我们使用两个计数信号量：empty 用于跟踪缓冲区中空闲槽位的数量，初始值为 n；full 用于跟踪缓冲区中已填充槽位的数量，初始值为 0。

生产者和消费者的操作是互补的：生产者负责填充缓冲区，消费者负责清空缓冲区。两者的代码结构对称，通过信号量协调，确保不会出现缓冲区溢出或下溢的情况。

读者-写者问题

读者-写者问题描述了一个典型的共享资源访问场景：多个进程需要访问同一个数据对象，其中一些进程只需要读取数据（读者），另一些进程需要修改数据（写者）。多个读者可以同时访问数据，因为它们不会修改数据，不会产生冲突。但是，如果有写者正在修改数据，其他进程（无论是读者还是写者）都不能同时访问数据，否则可能导致数据不一致。

读者-写者问题的核心要求是：当写者正在访问数据时，其他所有进程（读者和写者）都必须等待；当没有写者访问时，多个读者可以并发访问。这个问题是测试同步机制有效性的经典问题。

读者-写者问题有多种变体，主要区别在于优先级策略。第一类读者-写者问题允许读者优先：只要没有写者正在访问，读者就可以立即访问数据，即使有写者在等待。第二类读者-写者问题要求写者优先：如果有写者在等待，新的读者必须等待，直到所有等待的写者完成访问。

不同的优先级策略可能导致某些进程长时间无法获得访问机会，这被称为"饥饿"问题。第一类方案可能导致写者饥饿，第二类方案可能导致读者饥饿。为了解决这些问题，研究者提出了各种公平的调度策略。接下来，我们以第一类读者-写者问题为例，展示如何使用信号量来解决。

在这个方案里，所有的读者进程会一起用到下面这些变量：

|
semaphore rw_mutex = 1;
semaphore mutex = 1;
int read_count = 0;

我们使用两个二进制信号量：rw_mutex 用于保护共享数据的访问，确保写者与读者之间、写者与写者之间的互斥；mutex 用于保护 read_count 变量的访问，确保对读者计数的更新是原子操作。read_count 用于记录当前正在访问数据的读者数量，初始值为 0。

rw_mutex 信号量由写者和第一个/最后一个读者使用。当第一个读者进入时，它会获取 rw_mutex，阻止写者访问；当最后一个读者离开时，它会释放 rw_mutex，允许写者访问。在读者访问期间，rw_mutex 保持被持有状态，后续的读者可以直接进入，因为它们只需要增加 read_count，而不需要操作 rw_mutex。mutex 信号量用于保护 read_count 的更新，确保多个读者同时修改 read_count 时不会出现竞态条件。

当多个读者同时到达时，它们会依次进入：每个读者首先获取 mutex 来更新 read_count，第一个读者还会获取 rw_mutex 来阻止写者。当读者完成访问后，最后一个离开的读者会释放 rw_mutex，允许等待的写者进入。如果有写者在等待，它会在 rw_mutex 上阻塞；如果有多个读者在等待，它们可能在 mutex 上排队。具体的调度顺序取决于操作系统的调度策略。

为了更方便地实现读者-写者问题的解决方案，现代操作系统和编程语言提供了读写锁（read-write lock）这种专门的同步原语。读写锁区分读操作和写操作：多个线程可以同时持有读锁，但写锁是排他的，与读锁和其他写锁互斥。读写锁特别适合读多写少的场景，虽然实现和开销比简单的互斥锁更大，但能够提高并发读操作的性能。

哲学家就餐问题

哲学家就餐问题描述了一个经典的同步场景：五个哲学家围坐在圆桌旁，每个哲学家面前有一把椅子，桌子中央有一碗米饭，桌上有五根筷子。哲学家大部分时间在思考，当感到饥饿时会尝试吃饭。

哲学家要吃饭，必须同时获得左手边和右手边的两根筷子。哲学家一次只能拿起一根筷子，不能抢夺邻居正在使用的筷子。只有当哲学家同时持有两根筷子时，才能开始吃饭。吃完饭后，哲学家会将两根筷子都放回桌上，然后继续思考。

哲学家就餐问题是操作系统中的经典同步问题，它形象地说明了当多个进程需要同时使用多个有限资源时面临的挑战。这个问题的核心在于如何设计同步机制，既避免死锁（所有哲学家都只拿到一根筷子，无法继续），又避免饥饿（某个哲学家永远无法获得足够的资源）。

信号量的解决办法

我们可以用信号量来表示每一根筷子。每根筷子一开始都是“可用”的，也就是信号量初始值为 1。 哲学家想拿筷子时，就对对应的信号量做 wait() 操作，拿到后信号量变成 0，表示这根筷子被占用了。 吃完饭后，哲学家再对信号量做 signal() 操作，把筷子放回桌上，信号量又变回 1。

我们可以这样定义筷子：

|
semaphore chopstick[5];

将 chopstick 数组中的每个信号量初始化为 1，表示所有筷子初始状态都是可用的。这种实现方式确实能防止相邻的哲学家同时吃饭，但存在一个严重问题：容易发生死锁。如果五个哲学家同时感到饥饿，每个哲学家都先拿起自己左手边的筷子，此时所有筷子都被占用，chopstick 数组中所有元素都变为 0。接下来，每个哲学家都尝试拿起右手边的筷子，但右手边的筷子已被邻居拿走，所有哲学家都无法获得第二根筷子，陷入无限等待，这就是死锁。

为了避免哲学家就餐问题中的死锁，研究者提出了多种解决方案。例如，限制同时就餐的哲学家数量最多为四个，这样至少有一根筷子是空闲的，可以打破循环等待；或者要求哲学家以原子方式同时获取两根筷子，避免部分获取的情况；还有一种方法是让奇数编号的哲学家先拿左手边的筷子，偶数编号的哲学家先拿右手边的筷子，打破对称性，避免所有哲学家执行相同操作导致的死锁。虽然这些方法可以避免死锁，但要彻底解决饥饿问题，还需要考虑公平的调度策略。死锁和饥饿是两个不同的问题：死锁是指所有进程都无法继续执行，饥饿是指某些进程长时间无法获得所需资源。

管程解决方案

接下来，我们通过提出哲学家就餐问题的无死锁解决方案来说明管程概念。 这个解决方案施加限制，即哲学家只有在她的两根筷子都可用时才能拿起她的筷子。 为了编码这个解决方案，我们需要区分我们可能发现哲学家的三种状态。为此，我们引入以下数据结构：

|
enum {THINKING, HUNGRY, EATING} state[5]; // 思考、饥饿、吃饭

哲学家 i 只有在她的两个邻居都不吃饭时才能设置变量 state[i] = EATING：(state[(i+4) % 5] != EATING) 和 (state[(i+1) % 5] != EATING)。 我们还需要声明：

|
condition self[5];

条件变量 self[i] 用于让哲学家 i 在饥饿但无法立即获得两根筷子时进入等待状态，直到条件满足后再继续执行。

筷子的分配和管理由 DiningPhilosophers 管程负责。每个哲学家在想要吃饭时，首先调用 pickup() 操作。如果此时无法获得两根筷子，该操作会使哲学家进入等待状态。当哲学家成功获得两根筷子后，就可以开始吃饭。吃完饭后，哲学家调用 putdown() 操作释放筷子。因此，哲学家 i 的完整流程是：调用 pickup()，吃饭，然后调用 putdown()。

|
DiningPhilosophers.pickup(i);
...
eat
...
DiningPhilosophers.putdown(i);

这种管程实现方法能够保证不会有相邻的哲学家同时吃饭，也不会发生死锁。但需要注意的是，虽然避免了死锁，某些哲学家可能仍然会长时间无法获得就餐机会，出现饥饿现象。如何设计公平的调度策略，确保每个哲学家都能获得就餐机会，是一个值得进一步研究的问题。

实际应用中的同步

Windows 中的同步

Windows 操作系统提供了多种同步原语来支持多线程编程，包括自旋锁、互斥锁、信号量、事件对象和定时器对象。自旋锁适用于锁持有时间很短的场景，线程在等待锁时保持运行状态，不断检查锁是否可用。互斥锁提供了基本的互斥机制，确保同一时刻只有一个线程能够访问受保护的资源。事件对象和定时器对象用于线程间的通知和协调，允许线程等待特定事件发生或时间到达。

当线程尝试访问受保护的资源时，如果同步对象处于信号状态（可用），线程可以立即继续执行；如果同步对象处于非信号状态（不可用），线程会被阻塞并加入等待队列。当资源被释放，同步对象变为信号状态时，等待队列中的线程会被唤醒，排在最前面的线程获得资源访问权。Windows 还提供了临界区对象，这是一种用户态的轻量级锁，在大多数情况下不需要进入内核模式，执行效率较高。只有在竞争激烈、需要内核介入时，临界区才会升级为内核对象。这种设计既保证了线程安全，又尽可能减少了性能开销。

Linux 中的同步

在 Linux 2.6 之前，内核其实是“非抢占式”的，也就是说，只要一个进程在内核里干活，别的进程就算再着急也插不进来。后 来，Linux 变成了“可抢占式”内核，这下就算你在内核里忙活，优先级更高的任务也能随时“插队”进来。

说到同步，Linux 内核里有不少办法。最简单的同步方式就是用“原子操作”来保护数据。 Linux 里有个专门的类型叫 atomic_t，用它来存放那些需要原子操作的整数。 比如说，我们要做一个计数器，每次加减都得保证没人能半路插手，这时候就用 atomic_t。

|
atomic_t counter;
int value;

以下代码说明了执行各种原子操作的效果：

原子整数在需要更新整型变量（如计数器）的情况下特别高效，因为原子操作不需要锁定机制的开销。 然而，它们的使用仅限于这些类型的场景。在有多个变量导致可能的竞态条件的情况下，必须使用更复杂的锁定工具。

Linux 中提供互斥锁来保护内核内的临界区。在这里，任务必须在进入临界区之前调用 mutex_lock() 函数， 在退出临界区后调用 mutex_unlock() 函数。如果互斥锁不可用，调用 mutex_lock() 的任务被放入睡眠状态， 当锁的所有者调用 mutex_unlock() 时被唤醒。

Linux 还提供自旋锁和信号量（以及这两种锁的读写版本）用于内核中的锁定。 在 SMP 机器上，基本的锁定机制是自旋锁，内核被设计为自旋锁只被持有很短的时间。 在单处理器机器上，如只有单个处理核心的嵌入式系统，自旋锁不适合使用，被启用和禁用内核抢占所取代。 也就是说，在具有单个处理核心的系统上，不是持有自旋锁，内核禁用内核抢占；不是释放自旋锁，它启用内核抢占。这总结如下：

在 Linux 内核中，自旋锁和互斥锁都不支持递归获取。如果一个线程已经持有某个锁，在释放该锁之前再次尝试获取同一个锁，会导致线程永久阻塞，形成死锁。

关于内核抢占控制，Linux 提供了 preempt_disable() 和 preempt_enable() 两个函数来禁用和启用内核抢占。内核为每个任务维护一个 preempt_count 计数器，用于跟踪当前任务持有的锁数量。每当任务获取一个锁时，preempt_count 递增；释放锁时，preempt_count 递减。只要 preempt_count 不为 0，内核就不会允许其他任务抢占当前任务，因为当前任务可能正在持有锁，抢占可能导致死锁。只有当 preempt_count 为 0 时，内核才允许抢占，因为此时当前任务没有持有任何锁。

自旋锁和内核抢占控制都是内核级的同步机制，适用于锁持有时间很短的场景。如果需要长时间持有资源，应该使用信号量或互斥锁，这些机制允许等待的线程进入阻塞状态，释放 CPU 资源给其他线程使用。

小结

进程同步机制是操作系统并发控制的核心技术，通过解决竞态条件和临界区问题，确保多进程环境下的数据一致性和系统稳定性。 从基础的 Peterson 算法到硬件支持的原子指令，从互斥锁、信号量到高级的管程抽象，各种同步工具为不同场景提供了多样化的解决方案。 这些机制不仅满足了互斥性、进展性和有限等待的基本要求，还通过死锁预防和优先级继承等技术解决了并发系统中的活跃性问题。

在实际应用中，Windows 和 Linux 等现代操作系统都实现了丰富的同步原语，从内核级的自旋锁到用户态的读写锁，从原子操作到条件变量， 为开发者提供了完整的并发编程工具链。理解这些同步机制的原理和适用场景，对于设计高性能、高可靠性的并发系统至关重要， 也是现代多核编程、分布式系统和实时系统开发的基础。

小练习

1. 信号量的操作序列

假设有一个初始值为3的计数信号量S，现在有5个进程P1、P2、P3、P4、P5按以下顺序执行操作：

• P1: wait(S)
• P2: wait(S)
• P3: wait(S)
• P4: wait(S)
• P5: signal(S)
• P1: signal(S)
• P3: signal(S)

请计算：

1. 每个操作后信号量S的值
2. 哪些进程会被阻塞，哪些进程可以继续执行
3. 最终信号量S的值

2. 有界缓冲区问题

考虑一个有界缓冲区问题，缓冲区大小为5。使用以下信号量：

• mutex = 1（互斥信号量）
• empty = 5（空闲槽位信号量）
• full = 0（已填充槽位信号量）

假设有3个生产者进程和2个消费者进程，它们按以下顺序执行操作：

1. Producer1: wait(empty), wait(mutex), 放入数据, signal(mutex), signal(full)
2. Producer2: wait(empty), wait(mutex), 放入数据, signal(mutex), signal(full)
3. Consumer1: wait(full), wait(mutex), 取出数据, signal(mutex), signal(empty)
4. Producer3: wait(empty), wait(mutex), 放入数据, signal(mutex), signal(full)
5. Consumer2: wait(full), wait(mutex), 取出数据, signal(mutex), signal(empty)

请计算每个操作后empty、full和mutex的值，并说明缓冲区中数据项的数量。

3. 哲学家就餐问题死锁分析

考虑经典的哲学家就餐问题，有5个哲学家围坐在圆桌旁，每根筷子用一个初始值为1的信号量表示。如果所有5个哲学家同时感到饥饿，每个哲学家都执行以下操作：

|
wait(chopstick[i]);        // 拿起左手边的筷子
wait(chopstick[(i+1)%5]);  // 拿起右手边的筷子
// 吃饭
signal(chopstick[i]);
signal(chopstick[(i+1)%5]);

请分析：

1. 如果所有哲学家同时执行第一个wait操作，此时每根筷子的信号量值是多少？
2. 当所有哲学家尝试执行第二个wait操作时会发生什么？
3. 这是否会导致死锁？为什么？