第 6 章进程同步

Pluveto

Nov 02, 2021 发布

? 次浏览

信号量

wait () 的定义可表示为：

wait(S) {
    while(S <= 0)
        ；// no-op
    S--；
}

signal 的定义可表示为

signal(S) {
    S++;
}

换言之：Lock & Unlock

信号量为什么会有负数？

信号量表示的是当前可用的资源个数，当信号量为负时，申请资源的进程就只能等待了。所以，信号量是负的多少，就表明有多少个进程申请了资源但无资源可用只能处于等待状态。

为什么要互斥？

多个线程并发访问和操作同一数据且执行结果与访问发生的特定顺序有关，称为竞争条件（race condition）。 程序必须避免竞争条件。

临界区（critical section）：只能有一个进程在执行的代码片段。

请求进入临界区的代码段称为进入区（entry section），临界区之后可能有退出区 (exit section)，其他代码为剩余区（remainder section）。

解决临界区问题的协议必须满足三个要求：

不该来的时候不要来：互斥 (mutual exclusion)。
该来的时候要来：前进（progress）。如果临界区没有进程，则应当立即让下一个进程进去。
不来可以，一直不来不行：有限等待（bounded waiting）。一个进程在提出进入临界区请求后，只需要等待临界区被使用有上限的次数后，该进程就可以进入临界区。换言之不能饿死。
（《现代操作系统》）不应对 CPU 的速度和数量做任何假设。

抢占内核（preemptive kernel）：允许处于内核模式的进程被抢占

非抢占内核（nonpreemptive kernel）：不允许处于内核模式的进程被抢占。

实现互斥 —— 忙等待法

连续测试一个变量直到某个值出现为止（通常在循环中实现），称为忙等待（busy waiting）。用于忙等待的锁，称为自旋锁（spin lock）。

屏蔽中断

在单处理器系统中，最简单的方法是使每个进程在刚刚进入临界区后立即屏蔽所有中断，并在就要离开之前再打开中断。屏蔽中断后，时钟中断也被屏蔽。CPU 只有发生时钟中断或其他中断时才会进行进程切换，这样，在屏蔽中断之后 CPU 将不会被切换到其他进程。

总结：我们要防止竞争，而没有进程切换就没有竞争，而没有时钟中断就没有进程切换，而屏蔽中断就没有时钟中断。所以通过屏蔽中断来防止竞争。

缺点：

权限：用户进程不应该拥有屏蔽中断的权力
扩展性：多核处理器就不能用了

共享锁变量（无效方法）

假设景区有一百个人要上厕所（实际上在计算机中，任意两个人还看不到彼此），一种方法是门上挂个牌子。

即测试和标记厕所里是否有人，如果没有人就标记为有人然后进去。出来之后就把牌子翻面表示里面没人。

缺点：如果有两个人都很急，会导致他们几乎在同一个瞬间看到厕所里没人就冲进去，结果导致厕所里最终有两个人的尴尬局面。

严格轮换法

即每个人排个号，叫到自己了再进去。每个人上完厕所，就叫下一个人。

缺点：可能造成无限等待，违反条件三

Peterson 算法

有以下共享内存：

int turn;
boolean flag[2];

i 表示当前进程
j 表示其它进程
turn 表示希望哪个进程进入临界区
flag 表示进程是否想要进入临界区（interest）

当进程 i 想要进入临界区，就设置 flag [i] = 1

我们看看这个程序跑起来会发生什么。假设有两个进程，编号 0，1，同时执行上述代码

flag[0] = true       |      flag[1] = true  // then, flag = [true, true]
turn = 1             |      turn = 0        // then, turn = 0 | 1, not sure
flag[1] = false      |      flag[0] = false // then, flag = [f | t, f | t], not sure

此后，flag 一共四种可能状态，turn 两种可能状态。我们看看会怎样：

   \  turn       0               1
flag \-----------------------------------
false false  无法执行，重试   无法执行，重试
false true   无法执行，重试   仅程序 1 能执行
true  false  仅程序 0 能执行 无法执行，重试
true  true   仅程序 0 能执行 仅程序 1 能执行

这种算法到底是怎么做到的？

关键在于贪婪式谦让。我觉得让梨的故事可以做例子。假设有两个小朋友，都想吃梨（都试图让 flag [i] = true），但是都要做样子让梨（turn = j），那么任何一个小朋友一旦发现自己让梨成功（turn = j && flag [j] = 1）就会等待。一旦对方吃完梨，（flag [i] = false），就会出让梨（自己的循环条件不再满足，立即往下执行），从而避免了无限等待。

回顾：

进程 A 和 B 同时去挤厕所

内卷式竞争 —— 无法互斥

规则：先来的门上挂个牌

进程 A，进程 B：我先来的。（都认为门上的牌是自己挂的）

结果：俩人同时挤进了厕所。寄了。

过度客套 —— 互锁

A 和 B 都想上厕所（flag [A] = 1, flag [B] = 1）

进程 A：您先请（turn = B）

进程 B：您先请（turn = A）

进程 A：您先请（turn = B）……

结果：死锁

严格轮换 —— 饿死

进程 A：没人在等，我来了。

进程 B：没轮到我，我等着（while (turn != B) sleep ();）

进程 A：我好了，下一个来。（turn = B）

另一种情况的 A：我没好，我手机掉下面了。

进程 B：我 TM 憋死了。

Peterson—— 先礼后兵

进程 A：我想上厕所（flag [A] = 1），但您先请 turn = B。您想上就上，我等着（while (flag [B] && turn = B){}）

进程 B：我好了。不想上了（flag [B] = 0）

进程 A：我一个箭步冲进来（不再满足循环条件 while (flag [B] && turn = B){}，往下执行）

进程 A：我好了。不想上了（flag [A] = 0）。谁爱上谁上。

进程 B：（避免了严格轮换的死锁）我也想上厕所（flag [B] = 1），但您先请 turn = A。啥，您不想上？(发现 flag [A] = 0)，那别挡路，我进去了。（不循环条件 while (flag [A] && turn = A){}，直接往下执行）

附：Peterson 的失效

由于编译器和 CPU 的优化，导致指令可能乱序执行。

    flag[0] = true;
    turn = 1;
    while (flag[1] && (turn == 1));

flag [1] 有可能被提前装载，从而未等待。

解决方法:

    flag[0] = true;
    turn = 1;
+   __sync_synchronize();
    while (flag[1] && (turn == 1));

TSL

XCHG

参考：https://www.cnblogs.com/mightycode/p/9226887.html

忙等待的缺点

考虑有领导（高优先级进程） H，工人爷爷 L（低优先级进程）。若工人爷爷处于厕所（临界区），而 H 准备运行，但发现厕所有人所以等着。

这时候工人爷爷 L 的厕所上完了，他想出来。但是根据优先级原则，必须先让领导先被调度。所以调度器不让工人出来。于是领导在外面等了一天也不能上厕所。

忙等待的缺点：

浪费 CPU 时间
造成优先级反转，高优先级进程死锁

生产者 - 消费者模型

队列：大小有限，可能为空，可能为满

生产者：向临界区的队列送入数据项。

消费者：从临界区的队列取走数据项。

问题：

如何避免队列满时，生产者继续送入数据项
如何避免队列空时，消费者从中取出数据项
同时，禁止使用忙等待方法。

简单但是错误的方法：

用一个变量 count 记录队列当前长度，用常量 N 记录队列的最大长度。有唤醒、睡眠两个函数。

两个进程循环读取。

对于生产者，如果 count == N，就休眠，如果 count == 1 就唤醒消费者。

对于消费者，如果 count == 0，就休眠。如果 count == N-1 就唤醒生产者。

结果：有那么一瞬间，生产者往空队列放入了一个数据项，但还没让 count ++，消费者就休眠了。

资源分配图

死锁

可抢占资源（preemptable resource）可以从拥有它的进程中抢占而不会产生任何副作用，存储器就是一类可抢占的资源。

不可抢占资源（nonpreemptable resource）是指在不引起相关的计算失败的情况下，无法把它从占有它的进程处抢占过来。

死锁条件

死锁的四个必要条件：

互斥条件。资源具有排他锁。
占有和等待条件。已经得到了某个资源的进程可以再请求新的资源。
不可抢占条件。已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放。
环路等待条件。死锁发生时，系统中一定有由两个或两个以上的进程组成的一条环路，该环路中的每个进程都在等待着下一个进程所占有的资源。

a 表示资源 R 分配给进程 A。

b 表示进程 B 正在等待资源 S

c 是一种死锁的情况

有四种处理死锁的策略

忽略该问题。
检测死锁并恢复。让死锁发生，检测它们是否发生，一旦发生死锁，采取行动解决问题。
仔细对资源进行分配，动态地避免死锁。
通过破坏引起死锁的四个必要条件之一，防止死锁的产生。

死锁检测和恢复

对于每种资源只有一个的情况

环路检测。深度优先遍历，如果再次遇到历史节点，则说明存在环路。

对于每种资源可能不止一个的情况

当前分配矩阵 E，不同行代表不同进程，不同列代表不同资源。E [i,j] 表示进程 i 占有资源 j 的数量。同理有可用资源矩阵 A，资源需求矩阵 R，表示进程 i 请求获得的资源数量。

死锁检测算法能够标记进程，最后未被标记的进程就是死锁进程。

int findRunnableProc(){
   int pid = requestMat.find(
   	 condition: !marked(i) and row[i] < available[i], 
     return: i
   )
   return pid
}

void detectDeadlock(){
    int pid = findRunnableProc()
    if(pid == NULL){
      return
    }else{
      // 假设它能归还资源
        avaliable[pid] += current[pid]
        mark(pid)
    }
}

算法的本质：找出资源能满足谁的使用，让他用，以便空余出更多资源。最后资源依然不够谁用，谁就在死锁。

死锁恢复

利用抢占恢复。即重新强行改变资源分配。
利用回滚恢复。即回档到没有死锁的时候。
杀死进程。

死锁避免

资源轨迹图

安全状态：存在一个分配序列使得所有的进程都能完成

银行家算法

最右边的三个向量分别表示现有资源 E、已分配资源 P 和可用资源 A

算法：

require - max - allocated[i]
while(true) {
    pid = requireMat.find(i =>
        return when require[i] < avaiable && !terminated[i]
    )
    // 所有的进程都标记为终止，其初始状态是安全的
    if(pid == NULL){
    	safe = terminated.forAll(i == true)
        return
    }
    // 假设它获得所需的资源并运行结束
    allocated[i] += required[i]
    available -= required[i]
    terminated[pid] = true    
}