进程的同步与互斥

1．两种形式的制约关系

资源共享所引起的制约——间接制约关系。

间接制约（indirect condition）是指被制约进程共享某个一次只能供一个进程使用的系统资源，只有得到该资源的进程才那继续往前执行，其他进程在获得资源进程执行期间不允许交叉执行。

进程合作引起的制约——直接相互制约关系

2.临界资源和临界区

临界资源，指的是需要互斥进行访问的资源。

我们在描述一个程序或算法时，总是认为存在一个伪处理机，可以按程序或算法所规定的步骤来执行该程序或算法的。但是，事实上，在实际的系统中则往往不是这样。

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

临界区是由属于不同并发进程的程序段共享公用数据或公用数据变量而引起的。临界区也可以被称为访问公用数据的那段程序。

3.互斥机制应该遵循的规则

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

一组并发进程互斥执行时必须满足如下准则：

（1）不能假设各并发进程的相对执行速度。即各并发进程享有平等的、独立的竞争共有资源的权利，且在不采取任何措施的条件下，在临界区内任一指令结束时，其它并发进程可以进入临界区。

（2）并发进程中的某个进程不在临界区时，它不阻止其它进程进入临界区。

（3）并发进程中的若干个进程申请进入临界区时，只能允许一个进程进入。

（4）并发进程中的某个进程申请进入临界区时开始，应在有限时间内得以进入临界区。

4.互斥的加锁实现

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

设临界区的类名为s。为了保证每一次临界区中只能有一个程序段被执行，又设锁定位key[s]。key[s]表示该锁定位属于类名为s的临界区。加锁后的临界区程序描述如下：

lock(key[S])

<临界区>

unlock(key[S])

设key[S]=1时表示类名为S的临界区可用，key[S]=0时表示类名为S的临界区不可用。则，unlock(key[S])只用一条语句即可实现。即：

key[S]<--1

不过，由于lock(key[S])必须key[S]=0时，不允许任何进程进入临界区，而key[S]=1时仅允许一个进程进入临界区的准则，因而实现起来较为困难。

一种简便的实现方法是：

lock(x)=begin local v

repeat

v<--x

until v=1

x<--0

end

不过，这种实现方法是不能保证并发进程　互斥执行所要求的准则(3)的。

这里，有一点需要注意的是：在系统实现时锁定位key[S]问题总是设置在公有资源所对应的数据结构中的。