进程同步

进程同步也称为直接制约关系，指让进程在某些位置上协调他们的工作次序而产生的制约关系。进程间的直接制约关系源于他们之间的相互合作。说白了就是解决异步性带来的不可预知的执行顺序。

进程互斥

进程互斥也称为间接制约关系，进程间对临界资源的访问，必须是互斥的执行。指一个进程进入临界区访问临界资源的时候，其他进程只能等待。

  1. do {
  2.     entry section;  // 进入区 检查是否可以进入临界区，可以进入，设置访问临界资源的标志，防止其他进程进入
  3.     critical section; // 临界区  访问临界资源的代码
  4.     exit section;    // 退出区  负责解除临界资源访问标志
  5.     reemainder section; // 剩余区  其他处理
  6. } while(true);

注意：
临界区是进程中访问临界资源的代码块。
进入区和退出区是负责实现互斥的代码块。

进程互斥的原则

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

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

进程互斥的软件实现方法

单标志法

image.png
在进入区只做检查，不上锁。在退出区把临界区的使用权交给另一个进程，又给自己上锁。
主要问题：不遵循空闲让进原则（如果P0进程一直不进入临界区，P1进程就会一直阻塞）

双标志先检查

image.png
算法思想：创建一个bool数组标记各个进程进入临界区的意愿。
在进入区先检查后上锁。退出区解锁
主要问题：不遵循忙则等待（①⑤②⑥③⑦…同时访问出现同时访问问题）

双标志后检查

image.png
在进入区先加锁，后检查。退出区解锁。
主要问题：不遵循“空闲让进、有限等待”原则，可能导致饥饿

Peterson 算法

image.png

在进入区“主动争取-主动谦让-检查对方是否想进、己方是否谦让”
主要问题：不遵循“让权等待”，会发生忙则等待。

进程互斥的硬件实现方法

中断屏蔽

利用“开关中断指令”实现（同原语的思想），在某个进程访问临界区 到 临界区访问结束 都不允许被中断，也就是不能发生进程的切换。
关中断 —> 临界区 —> 开中断

优点：简单高效
缺点：不适用于多处理机系统（一个处理机关中断，不会影响其他处理机对临界区的访问）。只适合于操作系统内核进程，不适用于用户进程。（开关中断属于特权指令）

TestAndSet（TS\TSL指令）

TSL指令由硬件实现，执行过程不允许被中断。用c语言描述逻辑
image.png
如果临界区被使用lock的值就是true，old=true，就会一直是true，进程一直在等待。反之，lock是false，就会返回false，停止阻塞，并且在返回之前lock也已经被重新上锁。
适用于多处理环境。不满足让权等待。
**

Swap指令（XCHG指令）

Swap指令由硬件实现，执行过程不允许被中断。用c语言描述逻辑
image.png
原理思想和TSL基本一样。
适用于多处理环境。不满足让权等待。