进程管理(九)-进程互斥

临界区

什么是临界区

不允许多个并发进程交叉执行的一段程序称为临界部分（critical section ）或临界区（critical region）

临界区不可能用增加硬件的方法来解决。因此，临界区也可以被称为访问公用数据的那段程序。

为什么要设置临界区

防止进程并发执行的时候，出现冲突，或者由于两个并发进程处于竞争状态，进而导致两者执行顺序不固定，导致程序执行出错。

例子

设计算进程ＰA，ＰB共享内存ＭS。ＭS分为系统区、进程工作区和数据区。数据区划分成大小相等的块，每个块中既可能有数据，也有可能没有数据。系统区主要是堆栈Ｓ，存放空数据块的地址。

令getspace 为取空数据块过程，release(ad)为释放数据块过程。如果堆栈Ｓ非空的话，进程ＰA或ＰB可以任意顺序释放和获取数据块。在进程并发执行时，getspace或 release(ad)将有可能完不成所要求的功能

getspace: begin local g
g←stack[top]
top←top-1
end

release(ad): begin
top ← top+1
stack[top]←ad
end

设时刻t0时，top=h0

首先 release(ad)的第一句执行：
t0：top←top+1 top=h0+1；

接着getspace 执行：
t1：g←stack[top] g=stack[h0+1]；
t2：top←top-1 top=h0；

再是 release(ad)的第二句执行：
t3：stack[top]←ad stack[h0+1]←ad；

调用getspace的进程取到的是h0+1中的一个未定义值;调用release(ad)的进程把释放的空块地址ad重复放入了h0。

间接制约

类

将那些不允许交叉执行的临界区按不同的公用数据划分为不同的集合。

上例中，以公用数据栈Ｓ划分的临界区集合是{getspace, release}。把这些集合称为类（class）

类的描述

设类 {getspace，release} 的类名为sp，getspace和release(ad)可重新描述为：

getspace: 	
when sp 
   do 
       getspce←stack[top]
        top←top-1 
   od

release(ad): 
when sp 
   do 
      top← top+1
      stack [top]← ad 
   od

什么是间接制约

由共享公有资源而造成的对并发进程执行速度的间接制约，简称间接制约。

什么造成了间接制约

由于共享某一公有资源而引起的在临界区内不允许并发进程交叉执行的现象

互斥

什么是互斥

不允许两个以上的共享该资源的并发进程同时进入临界区称为互斥

纯过程

纯过程指在执行过程中不改变过程自身代码的一类过程。

纯过程的优缺点

优点:
把一个过程作成纯过程可便于多个进程共享

缺点:
但由于编制纯过程必须对有关变量和工作区作相应的处理，从而其执行效率往往会受到一定的影响

进程互斥要满足要求

1.各并发进程享有平等的、独立的竞争共有资源的权利，且在不采取任何措施的条件下，在临界区内任一指令结束时，其他并发进程可以进入临界区。
2.并发进程中的某个进程不在临界区时，它不阻止其他进程进入临界区
3.并发进程中的若干个进程申请进入临界区时，只能允许一个进程进入
4.并发进程中的某个进程申请进入临界区时开始，应在有限时间内得以进入临界区

互斥的实现方法

加锁

当某个进程进入临界区之后，它将锁上临界区，直到它退出临界区时为止。并发进程在申请进入临界区时，首先测试该临界区是否是上锁的。如果该临界区已被锁住，则该进程要等到该临界区开锁之后才有可能获得临界区

加锁产生的问题:
1.加锁的方法可以实现进程之间的互斥，但存在影响系统可靠性和执行效率的问题。

例如，如果一组并发进程数量较多，每个进程在申请进入临界区时都需要对锁定位进行测试。循环测试锁定位将损耗较多的 CPU计算时间。

2.使用加锁法实现进程间互斥时，还将导致在某些情况下出现不公平现象

产生原因:一个进程能否进入临界区依靠进程自己调用lock过程去测试相应的锁定位。每个进程能否进入临界区是依靠自己的测试判断！

信号量

提出

信号量的概念和下面所述的P、V原语是荷兰科学家E.W.Dijkstra提出来的

什么是信号量

信号量sem是一整数

1.sem大于等于零时代表可供并发进程使用的资源实体数；
2.sem小于零时表示正在等待使用临界区的进程数。
3.用于互斥的信号量sem的初值应该大于零

建立信号量的过程

建立一个信号量步骤如下：
1.说明所建信号量所代表的意义；
2.为信号量赋初值；
3.建立相应数据结构以便指向那些等待使用该临界区的进程。

PV原语

什么是PV原语

P和V分别是荷兰语 Passeren 和Verhoog 的首字母，相当于英文的pass和increment

sem是与临界区内所使用的公用资源有关的信号量。一次P原语操作使得信号量sem减1，而一次V原语操作将使得信号量sem加1。

V原语

V原语的操作主要动作是：
1.sem加1；
2.若相加结果大于零，进程继续执行；
3.若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进程，然后再返回原进程继续执行或转进程调度

P原语

P原语操作的主要动作是：

1.sem减 1；
2.若sem减1后仍大于或等于零，则进程继续执行；
3.若sem减1后小于零，则该进程被阻塞后放入与该信号相对应的队列中，然后转进程调度。

PV原语解决的问题

利用Ｐ，Ｖ原语和信号量，可以方便地解决并发进程的互斥问题，而且不会产生使用加锁法解决互斥问题时所出现的问题。

进程互斥PV原语的条件

利用Ｐ，Ｖ原语和信号量，可以方便地解决并发进程的互斥问题，而且不会产生使用加锁法解决互斥问题时所出现的问题。

PV原语描述进程互斥

设 sem为互斥信号量，其取值范围为(1,0,-1)。
sem=1表示进程PA和PB都未进入类名为S的临界区;
sem=0表示进程PA或PB已进入类名为S的临界区;
sem=-1表示进程PA和PB中，一个进程已进入临界区，而另一个进程等待进入临界区。