同步与互斥

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

• 进程间的直接制约关系源于它们之间的相互合作

互斥：进程的 “并发” 需要 “共享” 的支持。各个并发执行的进程不可避免的需要共享一些资源（如内存、打印机、摄像头）

• 一个时间段内只允许一个进程使用的资源称为 临界资源
• 许多物理设备（摄像机、打印机）都属于 临界资源
• 许多变量、数据、内存缓冲区等也属于临界资源
• 对临界资源的访问，必须 互斥 地进行
• 互斥，也称 间接制约关系。进程互斥指当一个进程访问某临街资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源后，另一个进程才能去访问临界资源

对临界资源的访问，可以在逻辑上分为如下四个部分：

do {

entry section; // 进入区 上锁

critical section; // 临界区

exit section; // 退出区 解锁

remainder seciotn; // 剩余区

}

• 临界区 是进程中 访问临界资源 的代码段
• 进入区 和 退出区 是 负责实现互斥 的代码段
• 临界区也称临界段

互斥访问的原则

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

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

互斥的软件实现方法

单标志法

算法思想

• 共两个进程，一个进程在 访问完临界区后 会把使用临界区的权限交给另一个进程
• 每个进程进入临界区的权限只能被另一个进程赋予

算法规则

// 线程1

while (turn != 0){}

临界区;

turn = 1;

剩余区;

// 线程2

while (turn != 1) {}

临界区;

turn = 0;

剩余区;

优缺点

• 优点：可以保证互斥
• 缺点：两个线程必然交替执行，违背了 空闲让进 原则

双标志先检查

算法思想

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

算法规则

boolean[] flag = new boolean[2];

flag[0] = false;

flag[1] = false;

// 线程1

while (flag[1]){}

flag[0] = true;

临界区;

flag[0] = false;

剩余区;

// 线程2

while (flag[0]){}

flag[1] = true;

临界区;

flag[1] = false;

剩余区;

优缺点

• 优点：可以保证互斥
• 缺点：并发环境下两个线程可能同时进入临界区，违背了 忙则等待 原则
  • 原因在于 进入区 的 检查 和 上锁 两个操作不是一气呵成的
  • 检查之后，上锁前可能发生进程切换

双标志后检查

算法思想

• 双标志先检查法的改版
• 把先检查后上锁，改为 先上锁后检查

算法规则

boolean[] flag = new boolean[2];

flag[0] = false;

flag[1] = false;

// 线程1

flag[0] = true;

while (flag[1]){}

临界区;

flag[0] = false;

剩余区;

// 线程2

flag[1] = true;

while (flag[0]){}

临界区;

flag[1] = false;

剩余区;

优缺点

• 优点：可以保证互斥
• 缺点：并发环境下两个线程可能同时上锁，违背了 空闲让进、有限等待
• 进一步产生 饥饿

Peterson 算法

算法思想

• 如果两个进程都争着进入临界区，可以让进程进行主动让步，主动让对方先使用临界区

算法规则

boolean[] flag = new boolean[2]; // 表示进入临界区意愿的数组，初始值都是 false

int turn = 0; // turn 表示优先让哪个线程进入临界区

// 0 进程

flag[0] = true;

turn = 1;

while (flag[1] && turn == 1) {}

临界区;

flag[0] = false;

剩余区;

// 1 进程

flag[1] = true; // 表示自己想进入临界区

turn = 0; // 可以优先让对方进入临界区

while (flag[0] && turn == 0) {} // 对方想进，且最后一次是自己让步，那么就自旋等待

临界区;

flag[1] = false; // 访问完临界区，表示自己已经不想再访问临界区了

剩余区;

优缺点

• 优点：保证了互斥，遵循了 空闲让进、忙则等待、有限等待
• 缺点：没有遵循 让权等待 原则，没有类似等待队列的结构，自旋等待会消耗 CPU 算力

互斥的硬件实现方法

中断屏蔽法

算法思想

• 利用 开关中断指令 实现

算法规则

关中断;

临界区;

开中断;

优缺点

• 优点：简单、高效
• 缺点：不适用于多处理机；只适用于操作系统内核进程， 不适用于用户进程。因为开关中断指令只能运行在内核态

TestAndSet (TS 指令 / TSL 指令)

算法思想

• 用硬件实现，执行过程中不允许被中断

算法规则

// bool 共享变量 lock 表示当前临界区是否被加锁

// true 表示已加锁, false 表示没加锁

bool TestAndSet(bool *lock)

{

bool old;

old = *lock; // old 用来存放 lock 原来的值

*lock = true; // 无论之前是否已经加锁，都会将 lock 设置为 true

rturn old; // 返回 lock 原来的值

}

使用 TS 指令实现互斥

while (TestAndSet (&lock)); // 上锁并检查

临界区;

lock = false; // 解锁

剩余区;

优缺点

• 优点：检查 、上锁 合并为原子操作，实现简单，无需像软件实现方法那样严格检查是否有逻辑漏洞；适用于多处理机环境
• 缺点：不满足 让权等待 原则，暂时无法进入临界区的进程会占用 CPU 并循环自旋，导致 忙等待

Swap 指令 (XCHG 指令)

算法思想

• Swap 指令通过硬件实现，保证原子性
• 也称 Exchange 指令、XCHG 指令

算法规则

// 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;

剩余区;

优缺点

• 优点：检查 、上锁 合并为原子操作，实现简单，无需像软件实现方法那样严格检查是否有逻辑漏洞；适用于多处理机环境
• 缺点：不满足 让权等待 原则，暂时无法进入临界区的进程会占用 CPU 并循环自旋，导致 忙等待