1. 临界资源#

虽然多个进程可以共享系统中的各种资源，但其中许多资源在同一时刻仅允许一个进程访问，这类资源被称为临界资源。常见的临界资源包括物理设备（如打印机）以及被多个进程共享的变量、数据结构等。

对临界资源的访问必须以互斥方式进行。在每个进程中，访问临界资源的那段代码称为临界区。为了保证临界资源的正确使用，可将对临界资源的访问过程划分为以下四个部分。

1. 进入区。在进入临界区之前，进程需要检查当前是否允许进入。若允许，则设置一个“正在访问临界区”的标志，以阻止其他进程同时进入临界区。
2. 临界区。进程中实际访问临界资源的代码段，也称临界段。
3. 退出区。在离开临界区时，清除“正在访问临界区”的标志，表示已释放该资源。
4. 剩余区。指代码中除上述三部分之外的其余部分。

1
while (true) {
2
    entry section;    // 进入区
3
    critical section; // 临界区
4
    exit section;     // 退出区
5
    remainder section;// 剩余区
6
}

2. 同步（直接制约关系）#

同步是指为完成某种任务而建立的两个或多个进程，由于需要协调彼此的运行次序，而在执行过程中产生等待或传递信息的制约关系。同步关系源于进程之间的相互合作。

例如，输入进程A通过单缓冲向进程B提供数据。当缓冲区为空时，进程B因无法获得所需数据而被阻塞；一旦进程A将数据送入缓冲区，进程B就会被唤醒。反之，当缓冲区已满时，进程A无法写入新数据，会被阻塞；只有当进程B从缓冲区取走数据后，才会唤醒进程A。

3. 互斥（间接制约关系）#

互斥是指当一个进程正在临界区中使用临界资源时，其他试图访问该资源的进程必须等待；只有当占用临界资源的进程退出临界区后，其他进程才被允许进入。

例如，在一个只配备一台打印机的系统中，有两个进程A和进程B。如果进程A需要打印，但此时打印机已被分配给进程B，那么进程A必须进入阻塞状态。一旦进程B完成打印并释放打印机，系统便会唤醒进程A，并将其状态由阻塞态转为就绪态。

为防止多个进程同时进入临界区，同步机制应遵循以下准则。

1. 空闲让进。临界区处于空闲状态时，应允许一个请求进入临界区的进程立即进入。
2. 忙则等待。已有进程在临界区内执行时，表明临界资源正在被访问，其他试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。
3. 有限等待。对任何请求进程，应保证其在有限时间内能进入临界区，避免无限期等待。
4. 让权等待（原则上应该遵循，但非必须）。当进程因无法进入临界区而需要等待时，应主动放弃CPU的使用权，转为阻塞态，而不是在原地循环测试（避免忙等待）。

1. 软件实现方法#

在进入区设置并检查一些标志，用以表明是否有进程正在临界区中。若已有进程在临界区，则其他进程在进入区通过循环检查的方式等待；当进程离开临界区后，在退出区修改相应的标志，以允许其他进程进入。

1
while (turn != 0);      // 进入区
2
critical section;       // 临界区
3
turn = 1;               // 退出区
4
remainder section;      // 剩余区

1
while (turn != 1);      // 进入区
2
critical section;       // 临界区
3
turn = 0;               // 退出区
4
remainder section;      // 剩余区

1
flag[0] = true;             // ①
2
while (flag[1]);            // ② 进入区
3
critical section;           // ③ 临界区
4
flag[0] = false;            // 退出区
5
remainder section;          // 剩余区

1
flag[1] = true;             // ④
2
while (flag[0]);            // 进入区
3
critical section;           // 临界区
4
flag[1] = false;            // 退出区
5
remainder section;          // 剩余区

1
flag[0] = true;             // ①
2
while (flag[1]);            // ③ 进入区
3
critical section;           // 临界区
4
flag[0] = false;            // 退出区
5
remainder section;          // 剩余区

1
flag[1] = true;             // ②
2
while (flag[0]);            // ④ 进入区
3
critical section;           // 临界区
4
flag[1] = false;            // 退出区
5
remainder section;          // 剩余区

1
flag[0] = true;                 // 进入区
2
turn = 1;                       // 进入区
3
while (flag[1] && turn == 1);   // 进入区
4
critical section;               // 临界区
5
flag[0] = false;                // 退出区
6
remainder section;              // 剩余区

1
flag[1] = true;                 // 进入区
2
turn = 0;                       // 进入区
3
while (flag[0] && turn == 0);   // 进入区
4
critical section;               // 临界区
5
flag[1] = false;                // 退出区
6
remainder section;              // 剩余区

2. 硬件实现方法#

现代计算机提供了特殊的硬件指令，能够以原子方式对一个字进行检测和修改，或是交换两个字的内容。因此，可利用它们实现临界区的互斥访问。

实际上，管理临界区时，可将共享标志视为一把锁：“锁开”表示允许进入，“锁关”表示需等待，初始时锁为打开状态。每个欲进入临界区的进程必须先测试该锁：若锁已关，则等待，直至其被打开；一旦发现锁开，就应立即上锁，以阻止其他进程进入临界区。显然，若多个进程几乎同时检测到“锁开”，就可能同时进入临界区，因此测试与上锁必须构成一个原子操作。

1
关中断；
2
临界区；
3
开中断；

1
boolean TestAndSet(boolean *lock) {
2
    boolean old;
3
    old = *lock;     // old用来存放lock的旧值
4
    *lock = true;    // 将lock置为true
5
    return old;      // 返回lock的旧值
6
}

1
while (TestAndSet(&lock));   // 尝试获取锁（忙等待）
2
进程的临界区代码段；
3
lock = false;                // 解锁
4
进程的其他代码；

1
void Swap(boolean *a, boolean *b) {
2
    boolean temp = *a;
3
    *a = *b;
4
    *b = temp;
5
}

1
boolean key = true;
2
while (key != false)
3
    Swap(&lock, &key);
4
进程的临界区代码段；
5
lock = false;
6
进程的其他代码；

1. 整型信号量#

整型信号量用一个整型变量 $S$ 表示某类资源的可用数量。与普通整型变量不同，对其操作仅限于三种：初始化、wait 操作和 signal 操作。其行为可描述如下：

1
wait(S) {              // 相当于进入区（原子操作）
2
    while (S <= 0);    // 若资源数不够，则一直循环等待
3
    S = S - 1;         // 若资源数够，则占用一个资源
4
}
5

6
signal(S) {            // 相当于退出区（原子操作）
7
    S = S + 1;         // 使用完后，就释放一个资源
8
}

在整型信号量机制中，当 $S \le 0$ 时，进程将持续循环测试，处于忙等待状态。这种实现未遵循“让权等待”准则，会浪费CPU时间，尤其是在单CPU系统中效率低下。

2. 记录型信号量#

为了克服忙等待的缺陷，Dijkstra 提出了记录型信号量，它通过阻塞机制实现了“让权等待”。记录型信号量采用结构化数据表示：除整型字段 value（表示当前可用资源数）外，还包含一个进程链表 $L$（等待队列），用于链接所有因请求该资源而被阻塞的进程。其定义如下：

1
typedef struct {
2
    int value;
3
    struct process *L;
4
} semaphore;

相应的 wait(S) 和 signal(S) 操作定义如下：

1
void wait(semaphore S) {   // 相当于申请资源
2
    S.value--;
3
    if (S.value < 0) {
4
        add this process to S.L;
5
        block(S.L);
6
    }
7
}
8

9
void signal(semaphore S) { // 相当于释放资源
10
    S.value++;
11
    if (S.value <= 0) {
12
        remove a process P from S.L;
13
        wakeup(P);
14
    }
15
}

执行 wait(S) 时，进程首先将 S.value 减1，表示请求一个该类资源。若减1后 S.value < 0，则表明该类资源已分配完毕，当前进程应调用 block 原语自我阻塞，主动放弃CPU，并加入等待队列 S.L，从而实现“让权等待”。

执行 signal(S) 时，进程将 S.value 加1，表示释放一个该类资源。若加1后 S.value \le 0，则说明仍有进程在等待该类资源，此时应调用 wakeup 原语，从 S.L 中移出一个进程并将其唤醒。

3. 利用信号量实现进程互斥#

为使多个进程能够互斥地访问某一临界资源，可为该资源设置一个互斥信号量 $S$，其初值设为1（表示该资源的可用数量为1）。随后，将各进程中访问该资源的临界区置于 P(S) 与 V(S) 操作之间。具体而言，每个进程在进入临界区前必须执行 P(S) 操作：若此时资源空闲($S=1$)，则 P(S) 成功，$S$ 被减为0，进程进入临界区；若资源已被占用($S=0$)，则后续进程执行 P(S) 时会因 $S \le 0$ 而被阻塞，并加入该信号量的等待队列。当进程退出临界区后，执行 V(S) 操作，将 $S$ 加1，表示释放资源，并唤醒等待队列中的一个进程（若存在）。其实现如下：

1
semaphore S = 1;          // 初始化信号量，初值为1
2

3
P1() {
4
    P(S);                // 申请临界资源，加锁
5
    进程P1的临界区；
6
    V(S);                // 释放临界资源，解锁
7
}
8

9
P2() {
10
    P(S);                // 申请临界资源，加锁
11
    进程P2的临界区；
12
    V(S);                // 释放临界资源，解锁
13
}

在仅有两个进程竞争该资源的情形下，$S$ 的取值仅可能为1、0或-1。若 $S=1$，表示两个进程均未进入临界区；若 $S=0$，表示有一个进程正在临界区中；若 $S=-1$，则表示一个进程在临界区，另一个进程因请求资源而阻塞在等待队列中，需等待临界区中的进程执行 V(S) 后方可被唤醒。

NOTE

1. 不同的临界资源应配置独立的互斥信号量，避免相互干扰。
2. P(S) 与 V(S) 必须严格成对出现：缺少 P(S) 将无法保证互斥访问，缺少 V(S) 则会导致资源永不释放，使等待进程永久阻塞。
3. 若系统中存在多个同类资源，应将信号量初值设为资源总数，进程申请资源时执行 P(S)，释放时执行 V(S)。

4. 利用信号量实现同步#

进程间的同步源于协作需求。在并发执行中，各进程具有异步性，其推进次序不确定。若某一进程的操作依赖于另一进程的执行结果，则必须确保前者在后者之后执行。例如，进程 $P_1$ 与 $P_2$ 并发执行，其中 $P_2$ 的语句 $y$ 需要使用 $P_1$ 的语句 $x$ 的执行结果，则必须保证语句 $y$ 在语句 $x$ 之后执行。为此，可引入一个同步信号量 $S$，其初值设为0（可理解为：初始时 $P_2$ 所需的某个资源尚未满足，而该资源只能由 $P_1$ 的执行结果提供）。其实现如下：

1
semaphore S = 0;          // 初始化信号量，初值为0
2

3
P1() {
4
    x;                    // 执行语句x
5
    V(S);                 // 通知P2：x已完成
6
}
7

8
P2() {
9
    P(S);                 // 等待x完成
10
    y;                    // 使用x的结果，执行语句y
11
}

该机制的行为取决于两个进程的执行顺序。

• 若 $P_1$ 先执行 V(S)：信号量 $S$ 由0增为1。随后 $P_2$ 执行 P(S) 时，由于 $S=1$，表示此时有可用资源，执行 S-- 后 $S=0$，P操作不会调用 block 原语，而是继续执行语句 $y$。
• 若 $P_2$ 先执行 P(S)：信号量 $S$ 由0减为-1，表示当前无可用资源，因此P操作会调用 block 原语，将 $P_2$ 阻塞。当 $P_1$ 完成语句 $x$ 并执行 V(S) 后，$S$ 由-1增为0，于是V操作会调用 wakeup 原语，唤醒等待队列中的 $P_2$，使其得以继续执行语句 $y$。

PV操作的用法总结：在同步问题中，若某个行为会提供某种资源，则应在该行为之后V这种资源；若某个行为需要使用这种资源，则应在该行为之前P这种资源。在互斥问题中，P、V操作必须紧夹使用临界资源的那个行为，中间不得插入任何无关代码。

5. 利用信号量实现前驱关系#

信号量还可用于描述程序段之间的前驱关系。一个前驱关系示例，其中 $S_1, S_2, \dots, S_6$ 均为简单的程序段（仅含一条语句），箭头表示执行顺序的约束。

每对前驱关系都对应一个同步问题：后继段必须等待前驱段完成。因此，可为每条前驱边设置一个同步信号量，初值均为0。其使用规则如下：前驱段执行完毕后，执行V操作，通知所有直接后继；后继段开始执行前，执行P操作，等待所有直接前驱完成。以图2.11中的依赖关系为例，需满足：$S_1 \to S_2$，$S_1 \to S_3$，$S_2 \to S_4$，$S_2 \to S_5$，$S_3 \to S_6$，$S_4 \to S_6$，$S_5 \to S_6$，为此，分别定义同步信号量 $a_{12}, a_{13}, a_{24}, a_{25}, a_{36}, a_{46}, a_{56}$，其中下标 $ij$ 表示该信号量用于协调 $S_i$ 与 $S_j$ 的前驱关系。各程序段的实现如下：

1
semaphore a12=0, a13=0, a24=0, a25=0, a36=0, a46=0, a56=0;
2
// 初始化所有信号量，初值均为0
3

4
S1() {
5
    ...;           // 执行S1
6
    V(a12); V(a13); // 通知S2和S3：S1已完成
7
}
8

9
S2() {
10
    P(a12);        // 等待S1完成
11
    ...;           // 执行S2
12
    V(a24); V(a25); // 通知S4和S5：S2已完成
13
}
14

15
S3() {
16
    P(a13);        // 等待S1完成
17
    ...;           // 执行S3
18
    V(a36);        // 通知S6：S3已完成
19
}
20

21
S4() {
22
    P(a24);        // 等待S2完成
23
    ...;           // 执行S4
24
    V(a46);        // 通知S6：S4已完成
25
}
26

27
S5() {
28
    P(a25);        // 等待S2完成
29
    ...;           // 执行S5
30
    V(a56);        // 通知S6：S5已完成
31
}
32

33
S6() {
34
    P(a36);        // 等待S3完成
35
    P(a46);        // 等待S4完成
36
    P(a56);        // 等待S5完成
37
    ...;           // 执行S6
38
}

6. 分析进程同步和互斥问题的方法步骤#

1. 关系分析。首先识别参与并发的进程，并厘清其间的关系：互斥关系(多个进程竞争同一临界资源)、同步关系（某进程需等待另一进程的执行结果）、前驱关系(存在明确的执行顺序约束)。每类关系均可映射到前述经典信号量模型。
2. 思路梳理。根据各进程的操作流程，确定关键同步点，并初步规划P、V操作的位置。可参考和类比典型场景，如生产者-消费者、读者-写者、前驱图。
3. 信号量设置。基于上述分析，定义所需的信号量，明确其语义与初值，并将P、V操作嵌入各进程的适当位置，确保逻辑正确，避免死锁与饥饿，且满足所有约束条件。