2. 同步
2026 旧版 · 非 2027 主源 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 2. 同步
同步亦称直接制约关系，是指为完成某种任务而建立的两个或多个进程，这些进程因为需要协调它们的运行次序而等待、传递信息所产生的制约关系。同步关系源于进程之间的相互合作。
例如，输入进程 A 通过单缓冲向进程 B 提供数据。当该缓冲区空时，进程 B 不能获得所需数据而阻塞，一旦进程 A 将数据送入缓冲区，进程 B 就被唤醒。反之，当缓冲区满时，进程 A 被阻塞，仅当进程 B 取走缓冲数据时，才唤醒进程 A。
## 3. 互斥
互斥也称间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源。
例如，在仅有一台打印机的系统中，有两个进程 A 和进程 B，若当进程 A 需要打印时，系统已将打印机分配给进程 B，则进程 A 必须阻塞。一旦进程 B 将打印机释放，系统便将进程 A 唤醒，并将其由阻塞态变为就绪态。
<!-- page: 110 -->
## 附属说明
▶ 实现临界区互斥必须遵循的准则（2020）
为禁止两个进程同时进入临界区，同步机制应遵循以下准则：
1）空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。
2）忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待。
3）有限等待。对请求访问的进程，应保证能在有限时间内进入临界区，防止进程无限等待。
4）让权等待（原则上应该遵循，但非必须）。当进程不能进入临界区时，应立即释放处理器，防止进程忙等待。
## 2.3.2 实现临界区互斥的基本方法
### 附属说明
▶ 实现互斥的软/硬件方法的特点（2018）
1. 软件实现方法 公众号：小兔网盘 免费分享无水印PDF
在进入区设置并检查一些标志来标明是否有进程在临界区中，若已有进程在临界区，则在进入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。
### （1）算法一：单标态法
该算法设置一个公用整型变量 turn，指示允许进入临界区的进程编号，当 turn = 0 时，表示允许 P₀ 进入临界区；当 turn = 1 时，表示允许 P₁ 进入临界区。进程退出临界区时将临界区的使用权赋予给另一个进程，当 Pᵢ 退出临界区时，将 turn 置为 j（i = 0、j = 1 或 i = 1、j = 0）。
进程 P₀：进程 P₁：
while (turn != 0); while (turn != 1); //进入区
critical section; critical section; //临界区
turn = 1; turn = 0; //退出区
remainder section; remainder section; //剩余区
该算法可以实现每次只允许一个进程进入临界区。但两个进程必须交替进入临界区，若某个进程不再进入临界区，则另一个进程也将无法进入临界区（违背“空闲让进”准则）。这样很容易造成资源利用不充分。若 P₀ 顺利进入临界区并从临界区离开，则此时临界区是空闲的，但 P₁ 并没有进入临界区的打算，而 turn = 1 一直成立，则 P₀ 就无法再次进入临界区。
### （2）算法二：双标态先检查法
该算法设置一个布尔型数组 flag[2]，用来标记各个进程想进入临界区的意愿，flag[i] = true 表示 Pᵢ 想要进入临界区（i = 0 或 1）。Pᵢ 进入临界区前，先检查对方是否想进入临界区，若想，则等待；否则，将 flag[i] 置为 true 后，再进入临界区；当 Pᵢ 退出临界区时，将 flag[i] 置为 false。
进程 P₀：进程 P₁：
while (flag[1]); ① while (flag[0]); ② //进入区
flag[0] = true; ③ flag[1] = true; ④ //进入区
critical section; critical section; //临界区
flag[0] = false; flag[1] = false; //退出区
remainder section; remainder section; //剩余区
优点：不用交替进入，可连续使用。缺点：P₀ 和 P₁ 可能同时进入临界区。按序列①②③④执行时，即检查对方标志后和设置自己的标志前可能发生进程切换，结果双方都检查通过，会同时进入临界区（违背“忙则等待”准则）。原因在于检查和设置操作不是一气呵成的。
### （3）算法三：双标态后检查法
算法二先检查对方的标志，再设置自己的标志，但这两个操作又无法一气呵成，于是导致两个进程出现同时进入临界区的问题。因此，想到先设置后检查的方法，以避免上述问题。算法三先设置自己的标志，再检查对方的标志，若对方的标志为 true，则等待；否则，进入临界区。
<!-- page: 111 -->
[tbl-28.md](tbl-28.md)
按序列①②③④执行时，即两个进程依次设置自己的标志，并依次检查对方的标志，发现对方也想进入临界区，双方都争着进入临界区，结果谁也进不了（违背“空闲让进”准则），于是因各个进程都长期无法访问临界区而导致“饥饿”现象（违背“有限等待”准则）。
## （4）算法四：Peterson算法
### 衡量方法
Peterson算法实现互斥的分析（2010）
Peterson算法结合了算法一和算法三的思想，利用flag[]解决互斥访问问题，而利用turn解决“饥饿”问题。若双方都争着进入临界区，则可让进程将进入临界区的机会谦让给对方。即每个进程进入临界区之前，先设置自己的flag标志，再设置允许进入turn标志；之后，再同时检测对方的flag和turn标志，以保证双方同时要求进入临界区时，只允许一个进程进入。
[tbl-29.md](tbl-29.md)
为进入临界区，Pᵢ先将flag[i]置为true，并将turn置为j，表示优先让对方Pⱼ进入临界区（i=0、j=1或i=1、j=0）。若双方试图同时进入，则turn几乎同时被置为i和j，但只有一个赋值语句的结果会保持，另一个也会执行，但会被立即重写。变量turn的最终值决定了哪个进程被允许先进入临界区，若turn的值为i，则Pᵢ进入临界区。当Pᵢ退出临界区时，将flag[i]置为false，以允许Pⱼ进入临界区，则Pⱼ在Pᵢ退出临界区后很快就能进入临界区。若Pᵢ不想进入临界区，即flag[i] = false（Pⱼ不会陷入while循环），则Pⱼ就可进入临界区。
由此可见，Peterson算法很好地遵循了“空闲让进”“忙则等待”“有限等待”三个准则，但依然未遵循“让权等待”准则。相比于前三种算法，该算法是最好的，但依然不够好。
## 2. 硬件实现方法
理解本节介绍的硬件实现，对学习后面的信号量很有帮助。计算机提供了特殊的硬件指令，允许对一个字的内容进行检测和修正，或对两个字的内容进行交换等。
## （1）中断屏蔽方法
### 衡量方法
关中断指令实现互斥的分析（2021）
当一个进程正在执行它的临界区代码时，防止其他进程进入其临界区的最简单方法是关中断。因为CPU只在发生中断时引起进程切换，因此屏蔽中断能够保证当前运行的进程让临界区代码顺利地执行完，进而保证互斥的正确实现，然后执行开中断。其典型模式为
这种方法的缺点：①限制了CPU交替执行程序的能力，因此系统效率会明显降低。②对内
<!-- page: 112 -->
101
核来说，在它执行更新变量的几条指令期间，关中断是很方便的，但将关中断的权限交给用户则很不明智，若一个进程关中断后不再开中断，则系统可能因此终止。③不适用于多处理器系统，因为在一个CPU上关中断并不能防止进程在其他CPU上执行相同的临界区代码。
（2）硬件指令方法——TestAndSet 指令
借助一条硬件指令——TestAndSet 指令（简称 TS 指令）实现互斥，这条指令是原子操作。其功能是读出指定标志后将该标志设置为真。指令的功能描述如下：
boolean TestAndSet(boolean *lock) {
boolean old;
old = *lock; //old用来存放lock的旧值
*lock = true; //无论之前是否已加锁，都将lock置为true
return old; //返回lock的旧值
}
while TestAndSet(&amp;lock); //加锁并检查
进程的临界区代码段;
lock=false; //解锁
进程的其他代码;
Swap(boolean *a, boolean *b) {
boolean temp = *a;
*a = *b;
*b = temp;
}
boolean key = true;
while (key != false)
<!-- page: 113 -->
```txt
Swap(&amp;lock, &amp;key);
进程的临界区代码段;
lock=false;
进程的其他代码;
acquire(){ //获得锁的定义
while(!available)
; //忙等待
available=false; //获得锁
}
release(){ //释放锁的定义
available=true; //释放锁
}
wait(S) { //相当于进入区
while (S &lt;= 0); //若资源数不够，则一直循环等待
S = S - 1; //若资源数够，则占用一个资源
}
signal(S) { //相当于退出区
S = S + 1; //使用完后，就释放一个资源
}
typedef struct{
int value;
struct process *L;
} semaphore;
void wait(semaphore S) { //相当于申请资源
S.value--;
if (S.value &lt; 0) {
add this process to S.L;
block (S.L);
}
}
void signal(semaphore S) { //相当于释放资源
S.value++;
if (S.value &lt;= 0) {
remove a process P from S.L;
wakeup(P);
}
}
semaphore S=1; //初始化信号量，初值为1
P1(){
...
P(S); //准备访问临界资源，加锁
进程P1的临界区;
V(S); //访问结束，解锁
...
}
P2(){
...
P(S); //准备访问临界资源，加锁
进程P2的临界区;
V(S); //访问结束，解锁
...
}
semaphore S=0; //初始化信号量，初值为0
P1(){
x; //执行语句x
V(S); //告诉进程P2，语句x已经完成
...
}
P2(){
...
P(S); //检查语句x是否运行完成
y; //获得x的运行结果，执行语句y
...
}
semaphore a12=a13=a24=a25=a36=a46=a56=0; //初始化信号量
S1(){
…;
V(a12); V(a13); //S1 已经运行完成
}
S2(){
P(a12); //检查 S1 是否运行完成
…;
V(a24); V(a25); //S2 已经运行完成
}
S3(){
P(a13); //检查 S1 是否已经运行完成
…;
V(a36); //S3 已经运行完成
}
S4(){
P(a24); //检查 S2 是否已经运行完成
…;
V(a46); //S4 已经运行完成
}
S5(){
P(a25); //检查 S2 是否已经运行完成