进程同步与互斥

进程同步

同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作

并发性带来了异步性，有时需要通过进程同步解决这种异步问题。有的进程之间需要相互配合地完成工作，各进程的工作推进需要遵循一定的先后顺序

进程互斥

进程的“并发”需要“共享”的支持。各个并发执行的进程不可避免的需要共享一些系统资源（比如内存，又比如打印机、摄像头这样的 I/O 设备）

资源的两种共享方式

• 互斥共享

系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源，其他进程必须等待，直到该进程使用完毕，其他进程才能访问该资源。

• 同时共享

系统中的某些资源，允许一个时间段内由多个进程“同时”对它们进行访问

临界资源

我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备（比如摄像头、打印机）都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源

对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源

临界资源互斥访问的逻辑

对临界资源的互斥访问，可以在逻辑上分为如下四个部分（代码层面）：

• 进入区

负责检查是否可进入临界区，若可进入，则应设置正在访问临界资源的标志（可理解为“上锁”），以阻止其他进程同时进入临界区

• 临界区

访问临界资源的那段代码

• 退出区

负责解除正在访问临界资源的标志（可理解为“解锁”），以允许其他进程进入临界区

• 其他（剩余）区

做其他处理

临界资源互斥访问的原则

为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则：

1. 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
2. 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待
3. 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）
4. 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待

进程互斥的软件实现方法

对于各软件算法的实现，需要从以下几个方面进行分析：

1. 理解各个算法的思想、原理
2. 结合上面部分的“实现互斥的四个逻辑部分”，重点理解各算法在进入区、退出区都做了什么
3. 分析各算法存在的缺陷（结合“实现互斥要遵循的四个原则”进行分析）

单标志法

• 算法思想

两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予

• 算法实现

申明一个公共变量 turn ：

int turn = 0; // turn 表示当前允许进入临界区的进程号

现有两个进程 P0 、 P1 互斥访问一个设备

P0 进程

while(turn != 0); // 进入区 ①
critical section; // 临界区 ②
turn = 1; // 退出区 ③
remainder section; // 剩余区 ④

P1 进程

while(turn != 1); // 进入区 ⑤
critical section; // 临界区 ⑥
turn = 0; // 退出区 ⑦
remainder section; // 剩余区 ⑧

turn 的初值为 0 ，即刚开始只允许 0 号进程进入临界区。若 P1 先上处理机运行，则会一直卡在 ⑤ 。直到 P1 的时间片用完，发生调度，切换 P0 上处理机运行代码 ① 不会卡住 P0 ， P0 可以正常访问临界区，在 P0 访问临界区期间即时切换回 P1 ， P1 依然会卡在只有 P0 在退出区将 turn 改为 1 后， P1 才能进入临界区

因此，该算法可以实现“同一时刻最多只允许一个进程访问临界区”

• 算法缺点

只能按 P0 → P1 → P0 → P1 …… 这样轮流访问。这种必须“轮流访问”带来的问题是，如果此时允许进入临界区的进程是 P0 ，而 P0 一直不访问临界区，那么虽然此时临界区空闲，但是并不允许 P1 访问。因此，单标志法存在的主要问题是：违背“空闲让进”原则

双标志先检查法

• 算法思想

设置一个布尔型数组 flag[] ，数组中各个元素用来标记各进程想进入临界区的意愿，比如 flag[0]= true 意味着 0 号进程 P0 现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志 flag[i] 设为 true ，之后开始访问临界区

• 算法实现

公共区代码

bool flag[2];
flag[0] = false;
flag[1] = false;

P0 进程

while(flag[1]); // ①
flag[0] = true; // ②
critical section; // ③
flag[0] = false; // ④
remainder section;

P1 进程

while(flag[0]); // ⑤ 如果此时 P0 想进入临界区，P1 就一直循环等待
flag[1] = true; // ⑥ 标记为 P1 进程想要进入临界区
critical section; // ⑦ 访问临界区
flag[1] = false; // ⑧ 访问完临界区，修改标记为 P1 不想使用临界区
remainder section;

• 算法缺点

若按照 ①⑤②⑥③⑦ …… 的顺序执行， P0 和 P1 将会同时访问临界区

因此，双标志先检查法的主要问题是：违反“忙则等待”原则

原因在于，进入区的“检查”和“上锁”两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换

双标志后检查法

• 算法思想

双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查的方法，来避免上述问题

• 算法实现

公共区代码

bool flag[2]; // 表示进入临界区意愿的数组
flag[0] = false;
flag[1] = false; // 刚开始设置为两个进程都不想进入临界区

P0 进程

flag[0] = true; // ①
while(flag[1]); // ②
critical section; // ③
flag[0] = false; // ④
remainder section;

P1 进程

flag[1] = true; // ⑤ 标记为 P1 进程想要进入临界区
while(flag[0]); // ⑥ 如果 P0 也想进入临界区，则 P1 循环等待
critical section; // ⑦ 访问临界区
flag[1] = false; // ⑧ 访问完临界区，修改标记为 P1 不想使用临界区
remainder section;

• 算法缺点

若按照 ①⑤②⑥ …… 的顺序执行， P0 和 P1 将都无法进入临界区

因此，双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待”原则，会因各进程都长期无法访问临界资源而产生“饥饿”现象

Peterson 算法

• 算法思想

结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”（谦让）。做一个有礼貌的进程

简而言之就是：

进入区：

1. 主动争取
2. 主动谦让
3. 检查对方是否也想使用，且最后一次是不是自己说了“客气话”

• 算法实现

公共区代码

bool flag[2]; // 表示进入临界区意愿的数组，初始值都是 false
int turn = 0; // turn 表示优先让哪个进程进入临界区

P0 进程

flag[0] = true; // ①
turn = 1; // ②
while(flag[1] && turn == 1); // ③
critical section; // ④
flag[0] = false; // ⑤
remainder section;

P1 进程

flag[1] = true; // ⑥ 表示自己想进入临界区
turn = 0; // ⑦ 可以优先让对方进入临界区
while(flag[0] && turn == 0); // ⑧ 对方想进，且最后一次是自己“让梨”，那自己就循环等待
critical section; // ⑨ 
flag[1] = false; // ⑩ 访问完临界区，表示自己已经不想访问临界区了
remainder section;

• 算法缺点

Peterson 算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则

Peterson 算法相较于之前三种软件解决方案来说，是最好的，但依然不够好

进程互斥的硬件实现方法

主要了解：

1. 理解各方法的原理了解各方法的优缺点
2. 了解各方法的优缺点

中断屏蔽

• 原理

利用“ 开/关 中断指令”实现（与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况）

• 具体实现

前置代码;
关中断;
临界区;
开中断;
后续代码;

关中断后即不允许当前进程被中断，也必然不会发生进程切换

直到当前进程访问完临界区，再执行开中断指令，才有可能有别的进程上处理机并访问临界区

• 优缺点

  • 优点

    • 实现简单、高效

  • 缺点

    • 不适用于多处理机；只适用于操作系统内核进程，不适用于用户进程（因为 开/关 中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险）

TestAndSet 指令

• 原理

简称 TS 指令，也有地方称为 TestAndSetLock 指令，或 TSL 指令 TSL 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。

• 具体实现

TestAndSet 的逻辑可简化为以下伪代码（实际由硬件直接实现）：

// 共享变量 lock 表示临界区状态：
// true 表示被占用，false 表示空闲
boolean lock = false;

// 原子操作：TestAndSet
function TestAndSet(boolean *lock) {
    boolean oldValue = *lock;  // 读取当前值（测试）
    *lock = true;              // 设置为新值（设置）
    return oldValue;           // 返回操作前的旧值
}

实现互斥代码：

// 进程进入临界区的逻辑
while (TestAndSet(&lock)) {
    // 若返回 true，说明锁已被占用，循环等待（忙等）
}

// 临界区：访问共享资源
...

// 退出临界区时释放锁
lock = false;

若刚开始 lock 是 false，则 TSL 返回的 old 值为 false ， while 循环条件不满足，直接跳过循环，进入临界区。若刚开始 lock 是 true ，则执行 TLS 后 old 返回的值为 true ， while 循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行“解锁”。

相比软件实现方法， TSL 指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作

• 优缺点

  • 优点

  实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞：适用于多处理机环境

  • 缺点

  不满足“让权等待”原则，暂时无法进入临界区的进程会占用 CPU 并循环执行 TSL 指令，从而导致“忙等”

swap 指令

• 原理

有的地方也叫 Exchange 指令，或简称 XCHG 指令
Swap 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用 C 语言描述的逻辑

• 具体实现

Swap 指令

// Swap 指令的作用是交换两个变量的值
Swap(bool *a, bool *b){
bool temp;
temp = *a;
*a = *b;
*b = temp;
}

实现互斥

// 以下是用 Swap 指令实现互斥的算法逻辑
// lock 表示当前临界区是否被加锁
bool old = true;
while(old == true)
    Swap(&lock, &old);
临界区代码段……
lock = false;
剩余区代码段……

逻辑上来看 Swap 和 TSL 并无太大区别，都是先记录下此时临界区是否已经被上锁（记录在 old 变量上），再将上锁标记 lock 设置为 true ，最后检查 old 如果 old 为 false 则说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区，执行临界区代码

• 优缺点

  • 优点

    • 实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞：适用于多处理机环境

  • 缺点

    • 不满足“让权等待”原则，暂时无法进入临界区的进程会占用 CPU 并循环执行 TSL 指令，从而导致“忙等”

互斥锁

解决临界区最简单的工具就是互斥锁（mutex lock）。一个进程在进入临界区时应获得锁：在退出临界区时释放锁。函数 acquire() 获得锁，而函数 release() 释放锁。

每个互斥锁有一个布尔变量 available ，表示锁是否可用。如果锁是可用的，调用 acquire() 会成功，且锁不再可用。当一个进程试图获取不可用的锁时，会被阻塞，直到锁被释放。

acquire() {
    while(!available); // 忙等待
    available = false; // 获得锁
}

release() {
    available = true; // 释放锁
}

acquire() 或 release() 的执行必须是原子操作，因此互斥锁通常采用硬件机制来实现。
互斥锁的主要缺点是忙等待，当有一个进程在临界区中，任何其他进程在进入临界区时必须连续循环调用 acquire() 。当多个进程共享同一 CPU 时，就浪费了 CPU 周期。因此，互斥锁通常用于多处理器系统，一个线程可以在一个处理器上等待，不影响其他线程的执行。

需要连续循环忙等的互斥锁，都可称为自旋锁（ spinlock ），如 TSL 指令、 swap 指令、单标志法

• 特性、

  • 需忙等，进程时间片用完才下处理机，违反“让权等待”
  • 优点:等待期间不用切换进程上下文，多处理器系统中，若上锁的时间短，则等待代价很低
  • 常用于多处理器系统，一个核忙等，其他核照常工作，并快速释放临界区
  • 不太适用于单处理机系统，忙等的过程中不可能解锁

信号量机制 👍

在之前的所有的解决方案都无法实现“让权等待”

为了解决这个问题 1965 年，荷兰学者 Dijkstra 提出了一种卓有成效的实现进程互斥、同步的方法——信号量机制

用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步

信号量其实就是一个变量（可以是一个整数，也可以是更复杂的记录型变量），可以用一个信号量来表示系统中某种资源的数量，比如:系统中只有一台打印机，就可以设置一个初值为 1 的信号量

原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由 关中断/开中断 指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题

一对原语： wait(S) 原语和 signal(S) 原语，可以把原语理解为我们自己写的函数，函数名分别为 wait 和 signal ，括号里的信号量 S 其实就是函数调用时传入的一个参数

wait 、 signal 原语常简称为 P 、 V 操作（来自荷兰语 proberen 和 verhogen ）。因此，做题的时候常把 wait(S) 、 signal(S) 两个操作分别写为 P(S) 、 V(S)

整型信号量

• 概念

用一个整数型的变量作为信号量，用来表示系统中某种资源的数量

提示

与普通整数变量的区别：对信号量的操作只有三种即：初始化、 P 操作、 V 操作

• 具体实现

eg. 某计算机系统中有一台打印机……

int S = 1; // 初始化整型信号量 S ，表示当前系统中可用的打印机资源数

void wait(int s) { // wait 原语，相当于“进入区”
    while(s <= 0); // 如果资源数不够，就一直循环等待
    S=S-1; // 如果资源数够，则占用一个资源
}

void signal(int s) { // signal 原语，相当于”退出区”
    S=S+1; // 使用完资源后，在退出区释放资源
}

对于需要使用对应资源的进程 P0 ，他需要按以下步骤调用资源

...
wait(S); // 进入区，申请资源
使用打印机资源... // 临界区，访问资源
signal(s); // 退出区，释放资源
...

• 特点

“检查”和“上锁”一气呵成！避免了并发、异步导致的问题

存在的问题：不满足“让权等待”原则，会发生“忙等”

记录型信号量 👍

整型信号量的缺陷是存在“忙等”问题，因此人们又提出了“记录型信号量”，即用记录型数据结构表示的信号量

• 具体实现

/* 记录型信号量的定义 */
typedef struct {
    int value; // 剩余资源数，为负数时表示正在等待资源的进程数
    struct process * L; // 等待队列
} semaphore;

/* 某进程需要使用资源时，通过 wait 原语申请 */
void wait(semaphore S) {
    S.value--;
    if(S.value < 0) {
        block(S.L); // 阻塞进程，加入等待队列
    }
}

/* 某进程使用完资源后，通过 signal 原语释放 */
void signal(semaphore S) {
    S.value++;
    if(S.value <= 0) {
        wakeup(S.L); // 唤醒等待队列中的第一个进程
    }
}

对于需要使用对应资源的进程 P0 ，他需要按以下步骤调用资源

...
wait(S); // 进入区，申请资源
使用打印机资源... // 临界区，访问资源
signal(s); // 退出区，释放资源
...

注意

如果剩余资源数不够，使用 block 原语使进程从运行态进入阻塞态，并把挂到信号量 S 的等待队列（即阻塞队列）中

释放资源后，若还有其他进程在等待这种资源，则使用 wakeup 原语唤醒等待队列中的一个进程，该进程从阻塞态变为就绪态

• 特点

在考研题目中 wait(S) 、 signal(s) 也可以记为 P(S) 、 V(S) 这对原语可用于实现系统资源的“申请”和“释放”

S.value 的初值表示系统中某种资源的数目

对信号量 S 的一次 P 操作意味着进程请求一个单位的该类资源，因此需要执行 S.value-- ，表示资源数减 1 ，当 S.value < 0 时表示该类资源已分配完毕，因此进程应调用 block 原语进行自我阻塞（当前运行的进程从运行态→阻塞态），主动放弃处理机，并插入该类资源的等待队列 S.L 中。可见，该机制遵循了“让权等待”原则不会出现“忙等”现象

对信号量 S 的一次 V 操作意味着进程释放一个单位的该类资源，因此需要执行 S.value++ ，表示资源数加 1 若加 1 后仍是 S.value <= 0 ，表示依然有进程在等待该类资源，因此应调用 wakeup 原语唤醒等待队列中的第个进程（被唤醒进程从阻塞态→就绪态）

注意

若考试中出现 P(S) 、 V(S) 的操作，除非特别说明，否则默认 S 为记录型信号量。

信号量机制实现进程互斥

• 步骤

1. 分析并发进程的关键活动，划定临界区（如：对临界资源打印机的访问就应放在临界区）
2. 对每个临界资源，设置一个信号量 mutex ，初值为 1
3. 在进入区和退出区分别执行 P(mutex) 、 V(mutex) 操作

• 示例

/* 信号量机制实现互斥 */
semaphore mutex = 1; // 初始化信号量

P1(){
    ...
    P(mutex); // 使用临界资源前需要加锁
    临界区代码段...
    V(mutex); // 使用临界资源后需要解锁
    ...
}

P2(){
    ...
    P(mutex);
    临界区代码段...
    V(mutex);
    ...
}

提示

要会自己定义记录型信号量，但如果题目中没特别说明，可以把信号量的声明简写成这种形式（ struct ）

代码块中的 semaphore 是记录型信号量，并且初始化的方式代表给该数据结构内的 value 赋值

注意

1. 对不同的临界资源需要设置不同的互斥信号量

2. P 、 V 操作必须成对出现。缺少 P(mutex) 就不能保证临界资源的互斥访问。缺少 V(mutex) 会导致资源永不被释放，等待进程永不被唤醒

信号量机制实现进程同步

• 步骤

1. 分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作（或两句代码）
2. 设置同步信号量 S ,初始为 0
3. 在“一前”执行的操作（或代码）后执行 V(S) 操作，在“一后”执行的操作（或代码）前执行 P(S) 操作；前 V 后 P

• 示例

eg. 现有如下进程，此时需要保证 代码4 一定是在 代码2 之后执行

semaphore S = 0; // 初始化同步信号量，初始值为 0

P1(){
    代码1;
    代码2;
    V(S); // 释放同步信号量
    代码3;
}

P2(){
    P(S); // 申请同步信号量
    代码4;
    代码5;
    代码6;
}

• 对于上述示例有以下两种情况

  • 若先执行到 V(S) 操作，则 S++ 后 S = 1 。之后当执行到 P(S) 操作时，由于 S = 1 ，表示有可用资源，会执行 S-- 后 S = 0 ，P2 进程不会执行 block 原语，而是继续往下执行 代码4

  • 若先执行到 P(S) 操作，由于 S = 0 ， S-- 后 S = -1 ，表示此时没有可用资源，因此P操作中会执行 block 原语，主动请求阻塞。之后当执行完 代码2 ，继而执行 V(S) 操作， S++ ，使 S 变回 0 ，由于此时有进程在该信号量对应的阻塞队列中，因此会在 V 操作中执行 wakeup 原语，唤醒 P2 进程。这样 P2 就可以继续执行 代码4 了

信号量机制实现前驱关系

使用实现进程同步的原理，对于前驱关系可以创建多个信号量进行指示

eg. 进程 P1 中有句代码 S1 ， P2 中有句代码 S2 ， P3 中有句代码 S3 ... P6 中有句代码 S6 。这些代码要求按如下前驱图所示的顺序来执行：

代码执行前驱关系示例图

每一对前驱关系都是一个进程同步问题（需要保证一前一后的操作）

因此：

1. 要为每一对前驱关系各设置一个同步信号量
2. 在“前操作”之后对相应的同步信号量执行 V 操作
3. 在“后操作”之前对相应的同步信号量执行 P 操作

遵循上述思想下，可以推导出对应进程的代码结构

P1

P1() {
    ...
    S1;
    V(a);
    V(b);
    ...
}

P2

P2() {
    ...
    P(a);
    S2;
    V(c);
    V(d);
    ...
}

P3

P3() {
    ...
    P(b);
    S3;
    V(g);
    ...
}

P4

P4() {
    ...
    P(c);
    S4;
    V(e);
    ...
}

P5

P5() {
    ...
    P(d);
    S5;
    V(f);
    ...
}

P6

P6() {
    ...
    P(e);
    P(f);
    P(g);
    S6;
    ...
}