九、同步互斥

并发进程的好处

并发进程的正确性

独立进程
不和其它进程共享资源或状态
确定性:输入状态决定结果
可重现:能够重现起始条件
调度顺序不重要
并发进程：
在多个进程间共享资源
不确定性
不可重现
并发进程的正确性
执行过程是不确定性和不可重现的
程序错误可能是间歇性发生的
这些不确定性和不可重复以意味着bug可能是间歇性发生的，也就是合作是有风险的

问题的原因

以上四条汇编指令的意思是：
1）把next_pid赋值给寄存器1（Reg1）
2）再把这个寄存器1存到了new_pid这个内存单元的去。此时new_pid就具有了next_pid这个值。
3）寄存器1加一操作。
4）完成next_pid的值增加了一个1的操作。
总的实现过程：
先把new_pid = next_pid，然后next_pid再加1.

但是，如果这时有两个进程，就会出现意想不到的情况

问题产生的原因：
在第二次进程的上下文切换时候，进程1的寄存器恢复之后依然100的值，是的next的值无法更新称为102。最终产生了切换使得最终的结果不是想要的结果。这是一种典型的异常现象。

进程并发的好处

1）共享资源
资源是需要共享的，因为进程可能要访问同一个文件。
2）加速
通过并行和并发，可以提高系统的效率，实现更有效的资源的利用。相当于把一个大的任务，拆分成多个小的任务，每个任务通过并行的执行提高系统的性能。
3）模块化
在设计时将一个大的工作，变成一个小的工作，使之具有模块化，使系统便于扩展

生活类比

1.问题

2.解决办法

3.轻量级的解决办法

上下文切换，还是会有问题

如果只是将Note往前面提简单的挪动一下还是不会解决问题，变成谁都不会去买面包了

4.进一步解决

为之前的便签增加一些标签

还是会有问题

需要确保在任何情况下，只有一个进程在临界区中执行，其他的进程需要在外面等待。
一个更加合理的方案解析过程：

程序是有效的，但是导致代码不一样了。

最终解决办法：为共享资源保护一段临界区代码，在任何一个时刻只有一个进程可以进入临界区执行，其它进程等待，直到该进程在临界区中执行完离开，其它进程中的一个才进入临界区执行。

临界区

临界区：进程中访问临界资源的一段需要互斥执行的代码
进入区：检查是否进入临界区的一段代码，如可进入，设置相应"正在访问临界区"标志
退出区:清除"正在访问临界区"标志
剩余区:代码中的其余部分

临界区的访问规则

空闲进入：没有进程在临界区时，任何进程都可进入
忙则等待：有进程在临界区，其他进程均不能进入临界区
有限等待：等待进入临界区的进程不能无限等待
让权等待：不能进入临界区的进程，应该释放CPU(转换到阻塞状态等)

临界区的实现方法

1.硬件禁用中断
2.基于软件的方法
3.更高级的抽象

硬件中断

1.实现
没有中断，也就是没有了上下文切换，因此没有并发。
硬件将中断处理延迟到中断被启用之后
大多数现代计算机体系结构都提供指令来完成
进入临界区时禁用中断，离开临界区时开启中断。这个方法是可以解决问题的。
2. 缺点
禁用中断后，进程无法被停止
整个系统都会为此停下来
可以导致其它线程出于饥饿状态
临界区可能很长
无法确定响应中断所需的时间(可能存在硬件影响)
要小心使用
需要注意：
执行这种课屏蔽中断的指令，只是把自身的响应中断的能力屏蔽了，并不意味着也将其他cpu的响应中断能力屏蔽，所以其实其他的cpu还是可以继续产生中断，所以在多cpu的情况下是无法解决互斥问题的

软件方案

方案1

某一个进程，它想进入临界区，其有一个顺序（次序），根据这个次序决定谁会进入这个临界区。
方法如下所示：

假设这个线程的次序是0，那么当turn=0时，才去继续下面的执行临界区代码，否者在while循环中一直打转。条件满足时，改变使得turn=1。
而进程1的代码也是类似的，只是while循环中的判断条件是不等于0，下面的turn=0.
这个程序的弊端是：
必须进程1执行一次临界区，进程0执行一次临界区，然后两个交替执行，才能保证两进程继续的执行。一旦其中的一个进程不愿意再做这个事情，那按照之前的属性，其他进程先进去就应该能够进去，但是在这种模式下，就无法完成这个前进的属性。

方案2

前面表示了一个turn是不够表示，所以接下来使用一个小数组flag[2]来表示这个进程是否想进入临界区。
flag[0] = 1 //表示进程0想进入临界区执行
flag[1] = 1 //表示进程1想进入临界区执行

方法1如下：

但是这个代码是有问题的，不能满足互斥这个属性。
因为在初始的时候，两个进程都不会想进入临界区，所以两个flag都会赋值为0，表面没有这个需求。这样就是的两个进程都会跳出这个循环，然后都会将直接复制为1，想要进入临界区，也就出现了多买面包的想象

方法2：

满足了互斥，但是倘若两个线程都赋值了1，出现上下文切换的时候，都无法跳出这个循环，也就是出现是死锁的情况

解决上面的问题
1.正确的写法
将以上的两种思考都综合起来使用。三个变量共同的作用。

算法如下：

该算法可以满足互斥，前进和有限等待三个属性。
反证法来证明：
假定，现在两个进程都进入了临界区，都在执行临界区代码，但是turn只是一个值的，所以总会有一个线程会跳出循环的。
2.另一种实现
所需的空间相同，但更加复杂

3.拓展

1、n进程解决方法1 （E&M算法）
除了了针对两个进程之外，还可以拓展到n个进程如何保证互斥。

大致的思路：
对于进程i而言，对于其前面的进程而言，如果有进程想进入临界区，或者已经进入了临界区，那么i进程就必须等待。而对于i进程后面的进程，必须要等待i进程执行之后在进入临界区。这样就可以通过一个循环的方式完成n个进程有序的进入临界区。

2、n进程解决方法2（Bakery算法）

更高级的抽象方法

硬件提供了一些同步原语:中断禁用、原子操作等
操作系统提供更高级的抽象编程来简化进程同步，例如锁、信号量、用硬件原语来构建

原子操作指令
现在CPU体系结构都提供了一些特殊的原子操作指令

1.Test-and-Set
解决忙等的情况：先让其睡眠，在加一步唤醒操作

两者的区别：

忙等：不需要上下文切换，但是利用率低，适用与临界区执行时间短的情况。
不忙等：需要上下文切换，上下文切换开销比较大大，适用于临界区很长，远远大于上下文切换所需要的开销

2.交换方式

解析：
1)当一个进程想要进入临界区的时候，key=1，而且lock的初始值是0，所以当执行到while循环的时候，由于执行了交换，交换执行的过程不会被打断进行上下文切换的操作，而后lock的变成了1，而key变成了0.所以会退出循环，执行临界区的代码。
2)需要注意的是，当进入临界区的时候，lock已经是1，当其他进程进入临界区执行的时候，lock是1，而key也是1，交换之后还是1，一直会循环的等待，进入不了临界区。知道进入临界区的进程，退出临界区之后，完成一个将lock变成0的操作。其他等待的进程才会继续执行exchange

原子操作的特点:
1、优点
1）简单并且容易证明
2）适用于单处理器或者共享主存的多处理器中任意数量的进程
3）可以很容易拓展n个进程，可以用于支持多临界区
4）开销比较小

2、缺点
1）忙等待消耗处理器时间
2）当进程离开临界区并且多个进程在等待的时候可能导致饥饿现象
3）出现死锁的情况（例子：如果一个低优先级的进程拥有临界区并且一个高优先级进程也需求，那么高优先级进程会获得处理器并且等待临界区 — 需要用优先级反转的方式进行处理）

总结

1、锁是更高级的编程抽象 互斥可以使用锁来实现 通常需要一定等级的硬件支持 2、常用的三种实现方法 禁用中断（仅限于单处理器） 软件方法（复杂） 原子操作指令（但处理器或多处理器均可）—更常用 3、可选的实现内容 有忙等待 无忙等待