操作系统之进程管理（2）

上篇博文我们主要共同学习了进程的一些基本概念，这次我们就要来分析一下进程间的相互作用，即进程的互斥、同步与通信。 进程互斥是进程之间所发生的一种间接性相互作用，这种相互作用是进程本身所不希望的，也是运行进程感觉不到的。进程互斥既可能发生在相

上篇博文我们主要共同学习了进程的一些基本概念，这次我们就要来分析一下进程间的相互作用，即进程的互斥、同步与通信。

         进程互斥是进程之间所发生的一种间接性相互作用，这种相互作用是进程本身所不希望的，也是运行进程感觉不到的。进程互斥既可能发生在相关的进程之间，也可能发生在不相关的进程之间。

         几个概念需要了解：

         共享变量：多个进程均需访问的变量称为共享变量。

         临界区：访问共享变量的程序段称为临界区，也称为临界段。

         临界资源：一次只允许一个进程使用的资源。

         进程互斥：两个或者两个以上的进程不能同时进入关于同一组共享变量的临界区，否则可能发生与时间有关的错误，这种想象称为进程互斥。

         那么如何实现进程互斥呢？

         先给出临界区的框架：

       

         实现互斥就是要编写entrydiv和exit div，保证同一时刻最多只有一个进程处于临界区内。

         下面从软件和硬件两个方面来描述进程互斥的实现：

   l  进程互斥的软件实现

（1）      Dekker互斥算法

      

                                    

         判断一个算法的正确性从三个方面来说明：

u  互斥性原则：任意时刻至多只能有一个进程处于关于同一组共享变量的临界区之中。

u  进展性原则：当临界区空闲时，只有那些执行entry div和exit div的进程参与下一个进入临界区进程的决策，该决策不能被无限期的推迟。

u  有限等待性原则：一个请求进入临界区的进程应当在有限的等待时间内获得进入该临界区的机会。

我们来看看上述算法是否符合这些原则：

先解释一下定义的数据结构:intflag[2];//初值为0  int turn;//初值为0或1

         前者表示进程是想进入或者已经进入临界区，后者表示当前轮流次序。

1.        互斥性：假定P0已经进入临界区，此时flag[0]=1成立，P1欲进入临界区必将在其外层while循环处等待，因而满足互斥性；

2.        进展性：若只有一个进程（设为P0）想要进入其临界区，由于flag[1]=0,P0结束外层while循环，进入其临界区。若两个进程都想进入临界区，假设turn=0，进程P1的if条件成立，将自己的flag[1]置为0，并动态等待P0。P0获得处理器资源运行时，检测到flag[1]不成立，结束外层while循环，进入临界区，因而满足进展性。

3.        有限等待性：假设P0处于临界区中，P1正在执行entry div代码试图进入其临界区。P0离开临界区时，将turn的值置为1，flag[0]=0,这将使P1的内层while循环条件不成立。若P1在判断外层while循环条件之前P0没有再次提出进入临界区的请求，则flag[1]的值为0，P1结束外层while循环进入其临界区；反之，若P1判断外层while循环条件之前P0再次执行entry div代码，则会将flag[0]再次置为1，但是因为flag[1]条件和turn==1条件成立，P0将在其flag[0]标志为0后忙式等待P1，直到P1进入并离开其临界区。因而P1在P0再度进入临界区之前，必能得到进入临界区的机会。

关于软件实现的算法还有很多，诸如Peterson互斥算法、Lamport面包店算法等等，

大家可以自己尝试分析一下，这需要很强的逻辑能力。

l  进程互斥的硬件实现

下面给出一个我认为形式最为简单的算法，开关中断硬件互斥算法

由于中断是实现进程切换的必要条件，所以关中断后，不会发生进程的切换，进入临界区的进程将连续执行临界区中的全部指令，因而满足互斥性。易于证明，也满足进展性。

         关于进程互斥的硬件实现算法也有很多，诸如:基于测试并设置指令的互斥算法、基于“交换”指令的硬件互斥算法等，大家感兴趣也可以找来算法描述自己分析。

         关于进程互斥的问题我们先了解到这，以后再PV操作中还会涉及到，到时候我们就可以自己写原语，来找出现实问题的求解……