9 同步互斥
9.1 背景、问题和基本概念
对于独立程序
- 不和其他程序共享资源
- 输入状态决定结果，具有确定性
- 可重现起始条件
- 调度顺序不重要
但对于并发进程来说，多个进程间有资源共享，可能会因为不同顺序出现相互的干扰。从而
- 产生不确定性
- 不可重现
- 未定义行为，程序错误是间歇性发生的
实际上我们又希望使用多进程并发执行，提升效率、实现协同、模块化设计等，所以我们需要使用一些方式来克服并发设计的坏处。
我们以并发创建进程时的标识分配为例，来说明并发进程带来的问题。
程序可以调用函数fork()来创建一个新的进程
- 操作系统需要分配一个新的且唯一的标识符
- 在内核中，这个系统调用会运行
new_pid = next_pid++; - 两个进程并发创建时，预期结果是，两个进程的结果不同，且
next_pid加两次，但我们正常假设四条赋值加一的指令是一次执行的。 - 当进程并发时由于共享资源混用和切换可能会使上述四条分步运行（比如进程A），从而发生混乱，如下图，会导致两个新进程id相同且
next_pid只加1
解决上述问题的思想就是将被打断的四条命令“打包”成一个原子操作，消除上述的执行的不完整性。
原子操作（Atomic Operation）指一次不存在任何中断或者失败的操作，要么操作完成，要么没有执行，不会出现半途而废、部分执行。
操作系统需要利用同步机制，在并发执行的同时，保证一些操作是原子操作。
9.2 临界区
进程的交互关系，根据相互感知程度的不同分为如下三种：
| 相互感知的程度 | 交互关系 | 进程间的影响 |
|---|---|---|
| 相互不感知 | 独立 | 一个进程的操作对于其他进程的结果没有影响 |
| 间接感知（双方都与第三方方交互，如共享资源 ） | 通过共享进行协作 | 一个进程的结果依赖于共享资源的状态 |
| 直接感知（双方直接交互，如通信） | 通过通信进行协作 | 一个进程的结果依赖于从其他进程获得的信息 |
同步问题的解决方案主要基于间接感知的部分，其中主要会有如下三种状态：
- 互斥（mutual exclusion）：一个进程占用资源，其他进程无法使用
- 死锁（deadlock）：多个进程各占用部分资源，形成循环等待
- 饥饿（starvation）：其他进程轮流占用资源，一个进程一直得不到资源
其中最为基本的状态称为互斥，这即是一个良好的原子操作的思路。
我们将互斥资源存放的位置称为临界区，其上资源同时只允许一个进程的访问，临界区附近的代码结构通常如下：
- 进入区：检查是否可以进入临界区的一段代码，如果可以进入，则设定“正在进入临界区”标志
- 临界区：进程中访问临界资源的一段需要互斥执行的代码
- 退出区：清除“正在访问临界区”标志
- 剩余区：跟同步互斥无关的代码
临界区的访问规则如下：
- 空闲则入：没有进程在临界区时，任何进程可以进入
- 忙则等待：有进程在临界区时，其他进程均不能进入临界区
- 有限等待：等待进入临界区的进程不能无限等待
- 让权等待(可选)：不需要访问临界区的进程，应当释放CPU
在具体实现过程当中，我们必须满足前三条规则。
9.3 实现方法
9.3.1 禁用中断
禁止硬件中断响应，因而对一个正在运行的不会发生上下文切换，且没有并发。
- 硬件将中断处理延迟到中断使能之后
- 现代计算机体系结构都提供指令来实现禁用中断
缺点：
- 禁用中断之后，进程无法停止
- 整个系统都会为此停下来
- 可能导致其他进程处于饥饿状态
- 临界区可能很长，无法确定中断响应时间
所以谨慎使用。
9.3.2 软件方法
设置一些全局的共享变量，来标识两个线程对互斥资源的占用情况，从而实现同步。
通常的代码结构如下：
do{
enter section
critical section
exit section
remainder section
} while (1);
我们的设计主要基于enter section和exit section。
尝试的过程主要是要实现闲则进入、忙则等待。
结合冰箱中没有面包时买面包（在本篇笔记中略去）的案例，我们的想法是既要让人知道该去买了，也要知道谁已经出发买了。
前者保证有人买面包，后者保证不买重复。即前者保证闲则进入，后者保证忙则等待。
在两线程的结构中这是非常经典的Peterson算法。
前者常用flags数组表示，后者用一个变量turn表示，谁后意识到则turn就是谁，标志着不需要出发。
do {
flag[i] = true;
turn = j;
while (flag[j] && turn == j);
//CRITICAL SECTION;
flag [i] = false;
//REMAINDER SECTION;
} while (true)
缺点
- 复杂，需要两个进程间的共享数据项
- 需要忙等待，浪费CPU时间
对于Peterson算法，还有更容易扩展为多个线程的Dekkers算法。
flag[0] := false; flag[1] := false; turn :=0
do {
flag[i] = true;
while flag[j] == true {
if turn not = i {
flag[i] := false
while turn not= i {}
flag[i] := true
}
}
//CRITICAL SECTION
turn := j
flag[i] = false;
//REMAINDER SECTION
} while (true);
绝大多数的线程都会卡在里层循环。只有当前线程执行完之后释放资源，才将下一个turn轮到的线程唤醒。
N线程的Eisenberg和McGuire算法：
这时候就可以实现有效的轮流。但多线程、多临界区的debug会变得更加困难。
9.3.3 更高级的抽象方法
将上述的想法抽象成一个二状态的数据结构，称为锁（lock）。
它有两个主要API：
- Lock::Acquire()
- Lock::Release()
将相关的互斥操作封装好之后，使用锁来控制临界区访问就会变得非常简单。
使用test and value或者exchange方法都可以简单地实现Lock::Acquire()。
Lock::Acquire() {
while (test-and-set(value));
}
Lock::Release(){
value = 0;
}
test and value即检查当前值是否为1，如果是1，则说明占用，继续循环，如果没占用，说明当前临界区资源闲置，并将value置1。
但上述的自旋等待锁存在忙等待的问题，我们可以将等待时的循环停下来，避免CPU繁忙。
class Lock {
int value = 0;
WaitQueue q;
}
Lock::Acquire() {
while (ts(value)){
add TCB to q
schedule() # 执行调度算法
}
}
Lock::Release() {
value = 0;
remove t one thread t from q;
wakeup(t);
}
原子操作指令锁适用于单处理器或者共享内存的多处理器中任意数量的进程。（禁用中断只能用于单处理器）
简单且容易证明其正确性。（相比于软件方法来说实现和列举正确性更加容易）
支持多临界区。
缺点：
- 忙等待消耗处理器时间
- 可能会导致饥饿
- 可能会导致死锁：高优先级拥有CPU，低优先级拥有独占资源
