进程互斥

什么是进程互斥

一组并发进程中的一个或多个程序段，因共享某一公有资源而导致它们必须以一个不允许交叉执行的单位执行，不允许两个以上的共享该资源的进程同时进入临界区。

由于各进程要求共享资源，而有些资源需要互斥使用，即多个进程不能同时使用同一个资源，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥。

临界区（Critical Section）

把不允许多个并发进程交叉执行的一段程序称作临界区。系统中某些资源一次只允许一个进程使用，这样的资源为临界资源（critical resource）或互斥资源或共享变量。

临界区的访问过程

进入区：在进入临界区之前，检查是否可以进入临界区的一段代码，如果可以，设置正在访问临界区标志。
临界区：进程中访问临界资源的一段代码。
退出区：用于将正在访问临界区标志删除。
剩余区：代码中的其余部分。

临界区准则

有空让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入。
无空等待：不允许两个以上的进程同时进入互斥区。
多中择一：当没有进程在临界区，而同时有多个进程要求进入临界区，只能让其中之一进入临界区，其他进程必须等待。
有限等待：任何进入互斥区的要求应在有限的时间内得到满足。
让权等待：处于等待状态的进程应放弃占用 CPU。
平等竞争：任何进程无权停止其它进程的运行，进程之间相对运行速度无硬性规定。

加锁实现互斥的方式

单标志法

基本思想是设立一个公用整型变量 turn，描述允许进入临界区的进程标识。

进入临界区之前先检查 turn，如果等于进程号，就可以进入临界区，否则循环等待，因此可以实现互斥。

17_进程互斥.png

这个图简单说一下，例如进程 Pi 先进来，现在由于 turn = i 所以不进循环，直接进入临界区，如果这个时候进程 Pj 也想进来，但是却因为 turn = i 所以只能进入循环 while(tuen != j) 直到进程 Pi 从临界区出来后，重新将 trun 设置为 j 后面 Pj 就可以进入临界区了。

特点：

等待期间会耗费处理器时间。
两个进程交替使用处理器，执行速度取决于慢的进程。
如果一个终止（无论是在临界区内还是临界区外），另一个会被永远阻塞。

双标志法（先检查）

双标志是设立一个标志数组 flag[]：描述进程是否在临界区，初值均为 FALSE，表示进程不在临界区。其基本思想是：

先检查，后修改：在进入区检查另一个进程是否在临界区，不在时修改本进程在临界区的标志；
在退出区修改本进程在临界区的标志；

18_进程互斥.png

优点：不用交替进入，可连续使用；

缺点：Pi 和 Pj 可能同时进入临界区。在 Pi 和 Pj 都不在临界区时，假设 Pi Pj 进入区的两部并发执行时，会同时进入临界区。即在检查对方 flag 之后发生进程切换，结果都通过检查。这里的问题出在检查和修改操作不能连续进行。

双标志法（后检查）

19_进程互斥.png

算法 3 类似于算法 2，与算法 2 的区别在于先修改后检查。可防止两个进程同时进入临界区。其缺点为：Pi 和 Pj 可能都进入不了临界区。在 Pi 和 Pj 都不在临界区时，假设按 "Pi (第一步) Pj (第一步) Pi (第二步) Pj (第二步)"顺序并发执行时，会都进不了临界区，即在设置进入临界区的标志后发生进程切换，结果检查都不能通过。

双标志法改进版

20_进程互斥.png

算法 4 结合算法 1 和算法 3，是正确的算法。当同时修改标志时，采用标志 turn 描述可进入的进程。其主要思想是在进入区先修改后检查，并检查并发修改的先后：

检查对方 flag，如果不在临界区则自己进入——空闲则入。
否则再检查 turn：保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入，即先到先入，后到等待。

信号量实现互斥的方式

前面的互斥算法都存在问题，它们是平等进程间的一种协商机制，需要一个地位高于进程的管理者来解决公有资源的使用问题。OS 可从进程管理者的角度来处理互斥的问题，信号量就是 OS 提供的管理公有资源的有效手段。信号量的值代表可用资源实体的数量。

每个信号量 s 除了一个整数值 s.count（计数）, 还有一个进程等待队列 s.queue，其中存储的是阻塞在该信号量的各个进程的标识。

信号量只能通过初始化和两个标准的原语（P、V 原语）来访问——作为 OS 核心代码执行，不受进程调度的打断。信号量在始化时被指定一个非负整数值，表示空闲资源总数（又称为 “资源信号量”）。

在进程执行过程中，信号量的值（即其计数值）可能发生变化：

若为非负值，表示当前的空闲资源数。
若为负值，其绝对值表示当前等待临界区的进程数。

P原语

在互斥问题中，申请使用临界资源时调用 P 原语，其实现原理为：

P(Semaphore s) {
    --s.count; //表示申请一个资源;
     if (s.count <0) { //表示没有空闲资源;
        调用进程进入等待队列 s.queue;
        阻塞调用进程;
    }
 }

V原语

V 原语通常唤醒进程等待队列中的头一个进程，其实现原理为：

V(Semaphore s ) {
	++s.count; //表示释放一个资源；
	if (s.count <= 0) { //表示有进程处于阻塞状态；
		从等待队列 s.queue 中取出一个进程 P;
		进程 P 进入就绪队列;
	}
}

加锁法和信号量法的区别

加锁法	信号量法
加锁过程可以中断	采用 P、V 原语
循环检测锁，系统开销大	系统开销小
未进入临界区的进程无排队等待机制	未进入临界区的进程必须在等待队列中等待