4.5 进程互斥

4.5.1 互斥的概念

进程之间的直接相互制约是通过进程通信来实现的，它们之间需要交换信息以便达到协调步伐的目的，也就是需要同步。所谓进程同步就是对于进程操作的时间顺序所加的某种限制。例如，“操作 A 应操作 B 之前执行”，“操作 C 必须在操作 A 和操作 B 都完成之后才能执行”等。在这些同步规则中有一个较特殊的规则是，“多个操作决不能在同一时刻执行”，如“操作 A 和操作 B 不能在同一时刻执行”。这种同步规则称为互斥。下面先通过几个例子（如两个进程共享硬件资源、共享公用变量、共享数据表格）来说明临界资源的概念，进而建立互斥和临界区的概念。

假定进程 A 、 B 共享一台打印机，若让它们任意使用，那么可能发生的情况是，两个进程的输出结果将交织在一起，很难区分。解决这一问题的办法是，进程 A 要使用打印机时应先提出申请，一旦系统把资源分配给它，就一直为它所独占。这时，即使进程 B 也要使用打印机，但必须等待，年到 A 进程用完并释放后，系统才把打印机分配给进程 B 使用。

由此可见，虽然系统中可同时有许多进程，它们共享着各种资源，然而有很多资源一次只能为一个进程使用。我们把一次仅允许一个进程使用的资源称为临界资源。许多物理设备，如输入机、打印机、磁带机等都具有这种性质。除了物理设备炊具，还有一些软件资源，如变量、数据、表格、队列等也都具有这一特点。它们虽可被若干进程所共享，但一次只能为一个进程所利用。

并发进程对公用变量进生访问和修改时，必须作某种限制，否则就会产生与时间有关的错误，即进程处理所得的结果与访问公共变量的时间有关。例如，有两个进程共享一个变量 x （ x 可代表某种资源的数量），这两个进程在一个处理机 C 上并发执行，分别具有内部寄存器 r 1 和 r 2 ，两个进程可按第 1 种方式对变量 x 进行访问和修改：

p 1 :x 1 =x; p 1 :r 1 =x

+ + r 1 ; p 2 :r 2 =x;

x=r 1 ; + + r 2 ;

p 2 :r 2 =x; x=r 2

+ + r 2 ; p 1 + + r 1 ;

x=r 2 ; x=r 1 ;

（第 1 种方式） （第 2 种方式）

两个进程各对 x 作加 1 操作，相应地 x 增加了 2 。但如果按第 2 种方式对变量 x 进行修改，虽然两个进程各自对 x 作了加 1 操作，但 x 却只增加了 1.

所以，当两个（或几个）进程可能异步地改变公共数据区内容时，必须防止两个（或几个）进程同时存取和改变数据。如果未提供这种保证，被修改的区域一般就不可能达到预期的变化。当两个进程公用一个变量时，它们必须顺序地使用，一个进程对公用变量操作完毕后，另一个进程才能去访问和修改这一变量。

下面再举一例，此例是两个系统进程公用一张表格。假定 A 进程负责为用户作业分配打印机， B 进程负责释放打印机。它们公用一张如表 4.2 所示的打印机分配表。

表 4.2 打印机分配表

A 进程分配打印机的过程是：

①逐项检查分配标志，找出标志为 0 的台号。

②把该台分配标志置 1 。

③把用户名和设备名填入分配表中相应位置。

B 进程释放打印机的过程是：

①逐项检查分配表的各项信息，找出标志为 1 、并且用户名和设备各与被释放的名字相同的台号。

②该台分配标志置 0 。

③清除该台用户名和设备名。

假定 B 进程在释放用户甲中用的第 0 台打印机时，执行第③步之前被夺走 CPU ，接着执行 A 进程。若 A 发现第 0 台分配标志为 0 ，则把该台分配出去，并填入用户和设备名，然后返回到 B 进程。 B 继续执行第③步，结果把刚才 A 进程填入的名字清除掉。若 B 进程对分配表的访问和修改操作不允许打断，则 A 进程就不会把尚法治完全收回的第 0 台打印机分配出去，而是分配另一台。

我们把允许若干进程均能访问和修改的存储单元称为公共变量。对公共变量或公用存储区这样的临界资源的共享具有这样的特点：共享的各方不能同时读写同一数据区，只有当一方读、写完毕后，另一方才能读、写。到底哪一方首先读、与，要根据问题的性质和设计人员的意图而定。

在操作系统中，当某一进程正在访问某一存伪装区域时，就不允许其他进程来读出或者修改存储区的内容，否则，就会发生后果无法估计的错误。进程之间的这种相互制约关系称为互斥。

互斥的广义概念是，在有多种活动同时进行的系统中，有时要求，当执行某一动作时，不允许进行其他的动作。这种限制条件称为“互斥”。

在每个进程中，访问临界资源的那段程序能够从概念上分离出来，称为临界区或临界段。它就是进程 对公共变量（或存储区）进行审查与修改的程序段，称为相对于该公共变量的临界区。诸进程进入临界区必须互斥。即仅当进程 A 进入临界区对 X 进行操作，并退出临界区后，进程 B 才允许访问其对应的临界区。

如图 4.13 所示的三个并发进程，其中 ab 、 ef 段对某一变量 Q 进行写入操作， cd 段对该变量 Q 进行读出操作。此时， Q 为三个进程共享的临界资源，而 ab 、 cd 、 ef 就是对 Q 进行操作的临界区。这三个进程最多只能有一个可以进入临界区，否则就会造成混乱。

图 4.13 具有临界区的并发进程

值得注意的一点是，临界区是对某一资源而言的，对于不同资源的临界区，它们之间是不相交的，所以不必互斥地执行。而相对于同一公共变量的若干个临界区，则必须互斥地进入，即对公共变量的操作实现互斥执行。

为禁止两个进程同时进入临界区内，可以采用硬件的方法，如：设置“测试并设置”指令；或采用各种不同的软件算法来协调它们的关系。但是，不论是软件算法还是硬件方法都应遵循下述准则：

①当有若干进程欲进入它的临界区时，应在有限时间内进程进入临界区。换言之，它们不应相互阻塞而致使彼此都不能进入临界。

②每次至多有一个进程处于临界区。

③进程在临界区内仅逗留有限的时间。

一般采用同步机构实现进程互斥。下面具体介绍用于实现进程互斥的同步机构。

4.5.2 锁和上锁、开锁操作

在大多数同步机构中，必须用一个标志来代表某种资源的状态。比如，标志为零，表示未被使用，否则表示已被使用。这一标志经常被称为锁或信号灯。所以，锁和信号灯是大多数同步机构所采用的一个物理实体。

对应于每一共唐朝数据块或设备都要有一个单独的锁位。按惯例，常用锁位值为“ 0 ”表示资源可用，而用“ 1 ”表示资源已被占用。这样，进程使用某一共享资源之前必须完成下列动作（即关锁操作）：

①检测锁位的值（是 0 不是 1 ）。

②如果原来的值为 0 ，将锁位置 1 （表示占用资源）。

③如果原来的值为 1 （即资源已被占用），则返回第一步再考虑。

当进程使用完资源后，它将锁位置成“ 0 ”，称为开锁操作。

在测试锁位的值和置锁位的值为 1 这两步这间，锁位不得被其他进程所改变，这是应该绝对保证的。一般地，可采用“原语”来实现，但有些机器在硬件中设置了“测试并设置”指令，保证了第一步和第二步的不可分离性。

系统可提供在一个锁位 w 上的两个原语操作 lock(w)t 和 unlock(w) 。其算法描述见 MODULE4.10 和 MODULE4.11 。

MODULE4.10 上锁原语

MODUILE4.11 开锁原语

在上述简单的关锁原语中， goto 语句使执行 lock(w) 原语的进程占用处理机而等待进入互斥段（称为“忙等待”）。为此，可将上锁原语和开锁原语作进一步修改。修改后的关锁过程和开涣过程见 MODULE4.12 和 MODULE4.13 。

MODULE4.12 改进的上锁原语

MODULE4.13 改进的开锁的原语

4.5.3 用上锁原语和开锁原语实现进程互斥

使用上锁原语和开锁原语可能解决并发进程的互斥问题。任何欲进入临界区的进程，必须先执行上锁原语。若上锁原语顺利通过，则进程可进入临界区；在完成对临界资源的访问后再执行开锁原语，以释放该临界资源。进程使用临界资源的操作步骤

这两个进程关于临界资源的操作可描述为 MODUEL4.14 。

MODUEO4.14 进程互斥