进程同步与互斥
操作系统中的并发进程有些是独立的, 有些需要相互协作.进程之间的协作关系包括互斥、同步、通信。
- 互斥：多个进程不能同时使用同一个资源，当某个进程使用某种资源时，其他要使用该资源的进程必须等待。
- 同步：多个进程中发生的事情存在着某种时序关系，某些进程的执行必须先于另一些进程。
- 通信：多个进程之间要传递一定量的信息。
基础概念
- 临界资源: 在某段时间内只允许一个进程使用的资源。
- 临界区: 进程中访问临界资源的那段程序。
进程并发执行的条件(Bernstein condition)
假设R(Pi)={a1,a2,…,am}表示程序Pi在执行期间所要参考的所有变量的集合，称为“读集”。W(Pi)={b1,b2,…,bn}表示程序Pi执行期间要改变的所有变量的集合，称为“写集”。两个程序P1和P2并发执行的条件是：
当且仅当R(P1)∩W(P2)∪R(P2)∩W(P1)∪W(P1)∩W(P2)={}。
进程访问临界区的一般结构
- 进入区：对临界资源进行检查，看他是否正在被访问。如果未被访问则可进入，并设置它正被访问的标志。如正被访问，则不能进入。
- 临界区：访问临界资源。
- 退出区：将临界区正被访问的标志恢复为未被访问。
- 剩余区：除上述之外的区域。
互斥访问的实现方式
实现互斥有多种方法：
- 让希望并发执行的进程自己完成，不需要操作系统提供任何支持；
- 使用专门的机器指令来完成，与具体的硬件系统相关，难成为通用方案；
- 由操作系统提供支持。
硬件实现
禁止中断
在临界区内的进程不能被中断，故保证了互斥进入临界区。只适用于单处理机。
专用机器指令(原子指令/原语操作，防止被调度)
- TS(Test and Set)指令
- Swap指令
都是给临界资源设置一个布尔变量lock，表示资源的两种状态，true表示正被占用；false表示空闲。在进入区中检查lock变量，在退出区中检查
软件实现
通过平等协商方式实现进程互斥。基本思路是在进入区检查和设置一些标志，如果有进程在临界区，则在进入区通过循环检查进行等待；在退出区修改标志。
- 单标志算法
- 双标志、先检查算法
- 双标志、先修改后检查算法
- 先修改、后检查、后修改者等待算法。
上述算法在进程数上有很大局限性，不同的进程数，代码不一样。故很少使用。
信号量和PV操作
信号量：包含一个整型数值s.value和一个s上的等待队列s.queue，信号量只能通过P、V原语来操作。
原语：。。。
信号量的物理意义
s.value表示系统中某种资源的数目(并不是资源本身)，因此又称为资源信号量。
p操作意味着进程请求一个资源，如果无法满足，进程将自我阻塞，并将自己投入s.queue.
v操作意味着进程释放一个资源，当有进程在s.queue上等待时，还会从中唤醒一个进程。
s.value<0时，其绝对值表示等待队列中的进程数。
用信号量解决互斥问题
当s.value=1时，表示仅有一个资源，即仅允许一个进程访问临界区，此时的信号量转换为互斥信号量。通常定义为mutex=1.
在进入区使用P操作申请资源，失败则阻塞自己。 在退出区使用V操作释放资源，从等待队列中唤醒一个阻塞进程。
用信号量解决同步问题
如果进程P2必须在进程P1执行完成之后才执行，则可以设置一个信号量s.value=0. 在P1的尾部V(s), 给信号量+1，在P2头部使用P(s)，即可控制先后顺序。
这类思想，可以推广到多各进程当中，但麻烦之处是，n个先后关系需要n个信号量。