信号量和P、V操作的一般应用

（一）临界资源和临界区

先看一个互斥的例子。

在计算机系统中必须互斥使用的资源很多，如读卡机、磁带机等硬件资源和一些公用变量、表格、队列、数据等软件资源。下面考虑两个进程共用同一表格的例子。

假定进程Pa负责为用户作业分配打印机，进程Pb负责释放打印机。系统中设立一个打印机分配表，由各个进程共用。表2-2给出打印机分配表的情况。

表2-2 打印机分配表

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

（1）逐项检查分配标志，找出标志为0的打印机号码；

（2）把该打印机的分配标志置1；

（3）把用户名和设备名填入分配表中相应的位置。

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

（1）逐项检查分配表的各项信息，找出标志为1且用户名和设备名与被释放的名字相同的打印机编号；

（2）该打印机的标志清0；

（3）清除该打印机的用户名和设备名。

如果进程Pb先执行，它释放用户Meng占用的第0号打印机，它的三步动作完成后，再执行Pa进程，就能按正常顺序对打印机进行释放和分配。也就是说，只要这两个进程对打印机分配表是串行使用的，那么，结果是正确的，不会出现什么问题。

由于进程Pa和Pb是平等的、独立的，二者以各自的速度并发前进，所以，它们的执行顺序有随机性。如果它们按以下次序运行，就会出现问题。

系统调度Pb运行：

（1）查分配表，找到分配标志为1、用户名为Meng、设备名为PRINT的打印机，其编号为0；

（2）将0号打印机的分配标志置为0。

接着，系统调度Pa运行：

（1）查分配表中的分配标志，找到标志为0的第0号打印机的表项；

（2）将分配标志置为1；

（3）填入用户名Zhang和设备名LP。

然后，系统调度Pb继续执行：

清除0号打印机的用户名Zhang和设备名LP。

这样一来，打印机分配表中的数据就变成如表2-3所示的情况。

表2-3 打印机分配表（出错情况）

由于0号打印机的分配标志为1，又没有用户名和用户定义的设备名，因此，它无法被释放。此后，它就再也不能由进程Pa分给用户使用了。

上述这种情况称作竞争条件（Race Condition），即两个或多个进程同时访问和操纵相同的数据时，最后的执行结果取决于进程运行的精确时序。

可见，Pa和Pb对分配表的使用必须互斥执行：在一个进程使用分配表期间，不允许另外的进程同时使用它。

很显然，包含有竞争条件的程序在运行时其结果不确定。要避免这种错误，关键是找到某种途径来阻止一个以上的进程同时使用这种资源。就是说，多个进程共享这种资源时必须互斥执行。

从上面可以看出，并发进程对共享资源的竞争形成各个进程的互斥关系。这些共享资源都具有一个共同的性质：一次仅允许一个进程使用。我们把这类共享资源称为临界资源（Critical Resource）。例如，打印机、读卡机、公共变量和表格等资源都是临界资源。在每个进程中访问临界资源的那段程序叫做临界区（Critical Section），简称CS区。例如，上节所写的进程Pa和Pb的程序段都是CS区。

进程互斥进入临界区都要遵循一种通用模式：进入前要申请，获准后方可进入；执行后要退出，然后才可以执行其他代码。图2-16为典型进程进入临界区的一般结构。

图2-16 典型进程进入临界区的一般结构

为使临界资源得到合理使用，必须禁止两个或两个以上的进程同时进入临界区内。即欲进入临界区的若干进程要满足如下关系：

（1）如果若干进程要求进入空闲的临界区，一次仅允许一个进程进入。

（2）任何时候，处于临界区内的进程不可多于一个。如果已有进程进入自己的临界区，则其他所有试图进入临界区的进程必须等待。

（3）进入临界区的进程要在有限时间内退出，以便其他进程及时进入自己的临界区。

（4）如果进程不能进入自己的临界区，则应让出CPU，避免进程出现"忙等"现象。

图2-17为进程A和进程B互斥使用临界区的过程。

图2-17 互斥使用临界区

互斥进程遵循上述准则，就能保证安全使用临界资源。由此可见，对系统中任何一个进程而言，它能否正常工作不仅与自身的正确性有关，而且与它在执行过程中能否与相关进程实施正确的同步和互斥有关。所以，解决进程间同步和互斥问题是十分重要的。

（二）互斥实现方式

为了解决进程互斥进入临界区的问题，需要采取有效措施。从实现机制方面来说，分为硬件方法和软件方法。

1．利用硬件方法解决进程互斥问题

利用硬件方法解决进程互斥问题有禁止中断和专用机器指令两种常见方式。

禁止中断是使每个进程在进入临界区之后立即关闭所有的中断，在它离开临界区之前才重新开放中断。由于禁止中断，时钟中断也被禁止，就不会把CPU切换到另外的进程。这种把关闭中断的权利交给用户进程的方法存在很大弊病：一旦某个进程关闭中断后，如果它不再开放中断，那么，系统可能会因此而终止。

另一种方法是设置专用机器指令。很多计算机（特别是多处理器计算机）都有一条名为TSL（Test and Set Lock，即测试并上锁）的指令：TSL RX，LOCK。它把内存字LOCK的内容读到寄存器RX中，然后在该地址单元中存入一个非零值。读数和存数的操作是不可分割的，即在这条指令完成之前，其他进程不能访问该单元。然而，利用TSL指令解决进程互斥进入临界区问题，可能导致“忙式等待”——如果前面已有一个进程进入临界区，则后者就不断利用TSL指令进行测试并等待前者开锁。

2．原语操作

操作系统在完成某些基本操作时，往往利用原语操作来实现。所谓原语（primitive）是机器指令的的延伸，往往是为完成某些特定的功能而编制的一段系统程序，为保证操作的正确性，在许多机器中规定，执行原语操作时，要屏蔽中断，以保证其操作的不可分割性。原语操作也称作“原子操作”，即一个操作中的所有动作要么全做，要么全不做。就好象进入考场参加高考，要么自始至终考完，要么不参加考试或提前交卷，不允许考试中间出考场去打电话，然后又回来继续答卷。

3．利用软件方法解决进程互斥问题

为解决进程互斥进入临界区的问题，可为每类临界区设置一把锁，该锁有打开和关闭两种状态，进程执行临界区程序的操作按下列步骤进行：

（1）关锁。先检查锁的状态，若为关闭状态，则等待其打开；如果已经打开，则将其关闭，继续执行②的操作。

（2）执行临界区程序。

（3）开锁。将锁打开，退出临界区。

一般情况下，锁可用布尔变量表示，也可用整型量表示。例如用变量W表示锁，其值为0表示锁打开，其值为1表示锁关闭。这种锁也称软件锁。关锁和开锁的原语可描述为：

关锁原语lock（W）：

while (W==1);

W=1;

开锁原语unlock（W）:

W=0;

下面用锁操作法写一个实现进程互斥执行的程序段。设系统中有一台打印机，有两个进程A和B都要使用它，以变量W表示锁，预先把它的值置为0。下面是两个进程的部分程序流程：

用上述软件方法解决进程间的互斥问题有较大的局限性，效果不很理想。例如，只要有一个进程由于执行lock（W）而进入互斥段运行，则其他进程在检查锁状态时都将反复执行lock（W）原语，从而造成处理机的“忙等”。虽然对上述算法可进行种种改进以便解决问题，但结果并不令人满意。

（三）信号量及P、V操作原语

信号量及信号量上的P操作和V操作是E.W.Dijkstra在1965年提出的一种解决同步、互斥问题的更通用的方法，并在THE操作系统中得以实现。

信号量，也叫信号灯，一般是由两个成员组成的数据结构，其中一个成员是整型变量，表示该信号量的值，另一个是指向PCB的指针。当多个进程都等待同一信号量时，它们就排成一个队列，由信号量的指针项指出该队列的头，而PCB队列是通过PCB本身所包含的指针项进行链接的。最后一个PCB（即队尾）的链接指针为0。

信号量的值是与相应资源的使用情况有关的。当它的值大于0时，则表示当前可用资源的数量；当它的值小于0时，则其绝对值表示等待使用该资源的进程个数，即在该信号量队列上排队的PCB的个数。图2-18表示信号量的一般结构以及信号量上PCB队列的情况，这种信号量也称作记录型信号量，因为它采用了记录型的数据结构。

图2-18 信号量的一般结构及PCB队列

对信号量的操作有如下严格限制：

（1）信号量可以赋初值，且初值为非负数。信号量的初值可由系统根据资源情况和使用需要来确定。在初始条件下，信号量的指针项可以置为0，表示队列为空。

（2）在使用过程中，信号量的值可以修改，但只能由P和V操作来访问，不允许通过其他方式来查看或操纵信号量。

设信号量为S，对S的P操作记为P（S），对S的V操作记为V（S）。

它们各自的含义是：

P（S）：顺序执行下述两个动作：

① 信号量的值减1，即S=S-1；

② 如果S 0，则该进程继续执行；

如果S 0，则把该进程的状态置为阻塞态，把相应的PCB链入该信号量队列的末尾，并放弃处理机，进行等待（直至其它进程在S上执行V操作，把它释放出来为止）。

V（S）：顺序执行下述两个动作：

① S值加1，即S=S+1；

② 如果S 0，则该进程继续运行；

如果S 0，则释放信号量队列上的第一个PCB（即信号量指针项所指向的PCB）所对应的进程（把阻塞态改为就绪态），执行V操作的进程继续运行。

P操作也称作wait操作，V操作也称作signal操作。

应注意，P和V操作都应作为一个整体实施，不允许分割或相互穿插执行。也就是说，P和V操作各自都好象对应一条指令，需要不间断地做下去，否则会造成混乱。为了保证这一点，在单CPU系统中通常是在封锁中断的条件下执行P和V操作。

从物理概念上讲，信号量S>0时，S值表示可用资源的数量。执行一次P操作意味着请求分配一个单位资源，因此S值减1；当S<0时，表示已无可用资源，请求者必须等待别的进程释放了该类资源，它才能运行下去。所以它要排队。而执行一次V操作意味着释放一个单位资源，因此S值加1；若S 0时，表示有某些进程正在等待该资源，因而要把队列头上的进程唤醒，释放资源的进程总是可以运行下去的。

由于信号量本身是系统中若干进程的共享变量，所以P和V操作本身就是临界区，对它的互斥进入可借助于更低级的硬件同步工具来实现，如关锁、开锁操作等。

（四）用信号量实现进程的互斥和同步

利用信号量机制可以解决并发进程的互斥和同步问题。

1．用信号量实现进程的互斥

下面我们用P和V操作实现对打印机分配表的互斥使用。为此，设一个互斥信号量mutex，其初值为1。这样，Pa（分配进程）和Pb（释放进程）的临界区代码可按下述形式组成：

分析：如果Pb先运行，那么当它执行P（mutex）后，由于mutex=0，Pb进入临界区。在Pb退出临界区之前，若由于某种原因（如时间片到时）发生进程调度转换，选中Pa投入运行；当Pa执行P(mutex)时，因mutex= -1而进入等待队列，直到Pb退出临界区之后，Pa才能进入临界区。反过来，结果也是正确的。

可见，利用信号量实现互斥的一般模型是：

其中，信号量mutex用于互斥，初值为1。

使用P和V操作实现互斥时应注意两点

（1）在每个进程中用于实现互斥的P（mutex）和V（mutex）必须成对出现，即先做P，进入临界区；后做V，退出临界区。

（2）互斥信号量mutex的初值一般为1。

2．用信号量实现进程简单同步

下面我们对缓冲区同步使用问题使用信号量和P、V操作来实现。供者和用者对缓冲区的使用关系如图2-19所示。

图2-19 简单供者和用者的关系

可以看出，供者和用者间要交换两个消息：缓冲区空和缓冲区满的状态。当缓冲区空时，供者进程才能把信息存入缓冲区中；当缓冲区满时，表示其中有可供加工的信息，用者进程才能从中取出信息。用者不能超前供者，即缓冲区中未存入信息时不能从中取出信息；如供者已把缓冲区写满，但用者尚未取走信息时，供者不能再向其中写信息，避免冲掉前面写入的信息。

为此，设置两个信号量：

S1——表示缓冲区是否空（0表示不空，1表示空）；

S2——表示缓冲区是否满（0表示不满，1表示满）。

规定S1和S2的初值分别为1和0，则对缓冲区的供者进程和用者进程的同步关系用下述方式实现：

设供者进程先得到CPU，它执行P（S1），申请空的缓冲区。此时，S1的值变为0，从而它继续执行：启动读卡机，将信息送入缓冲区（因为初始情况下，缓冲区中没有信息）。填满缓冲区之后，执行V（S2），表示缓冲区中有可供用者加工的信息了，S2的值变为1。然后执行goto L1；接着执行P（S1），由于S1的值变为-1，表示无可用缓冲区，于是供者在S1上等待，放弃CPU。以后调度到用者进程，它执行P（S2），条件满足（S2的值变为0），然后从缓冲区取出信息，并释放一个空缓冲区，执行V（S1），由于S1的值变为0，表示有一个进程正在等待空缓冲区资源，于是把该进程（即供者）从S1队列中摘下，置为就绪态。用者继续对信息进行加工和存盘处理。当这批数据处理完之后，它又返回到L2，然后执行P（S2）。但这时S2的值变为-1，所以用者在S2队列上等待，并释放CPU。如调度到供者进程，它就执行P（S1）之后的代码：启动读卡机，把卡片上信息送入缓冲区。这样，保证整个工作过程有条不紊地进行。

如果用者进程先得到CPU，会怎样呢？其实当它执行P（S2）时就封锁住了（因为S2的值变为-1），因而不会取出空信息或已加工过的信息。

在代码中P和V操作出现的顺序与信号量的初值设置有关。本例中若S1和S2的初值都为0，那么供者进程代码中P（S1）应出现在“V（S2）；”之后。请同学们自行把这种初值设置条件下供者和用者的程序代码写完整，并分析其执行结果是否正确。

解析：

用P和V操作实现同步时应注意：

（1）分析进程间的制约关系，确定信号量种类。在保持进程间有正确的同步关系情况下，哪个进程应先执行，哪些进程后执行，彼此间通过什么资源（信号量）进行协调，从而明确要设置哪些信号量。

（2）信号量的初值与相应资源的数量有关，也与 P和V操作在程序代码中出现的位置有关。

（3）同一信号量的P和V操作要“成对”出现，但它们的分别在不同的进程代码中。例如，P（S1）在供者进程中，而V（S1）在用者进程中，若供者进程因执行P（S1）而阻塞，则以后将由用者进程在执行V（S1）时把它唤醒。

（五）生产者-消费者问题

在多道程序环境下，进程同步是一个十分重要而又令人感兴趣的问题。生产者—消费者问题就是其中一个有代表性的进程同步问题。

在计算机系统中，通常每个进程都要使用资源（硬资源和软资源——如缓冲区中的数据、通信的消息等），还可以产生某些资源（通常是软资源）。例如，在上例中，供者进程将读卡机读入的信息送入缓冲区，而用者进程从缓冲区中取出信息进行加工，因此供者进程就相当于生产者，而用者进程就相当于消费者。如果还有一个打印进程，它负责将加工的结果（设放在另一个缓冲区中）打印出来，那么在输出时，刚才的用者进程就是生产者，打印进程就是消费者。

所以，针对某类资源抽象地看，如果一个进程能产生并释放资源，则该进程称做生产者；如果一个进程单纯使用（消耗）资源，则该进程称做消费者。因此，生产者-消费者问题是同步问题的一种抽象，是进程同步、互斥关系方面的一个典型。这个问题可以表述如下：一组生产者进程和一组消费者进程（设每组有多个进程）通过缓冲区发生联系。生产者进程将生产的产品（数据、消息等统称为产品）送入缓冲区，消费者进程从中取出产品。假定缓冲区共有N个，不妨把它们设想成一个环形缓冲池，如图2-20所示。

图2-20 生产者-消费者问题

其中，有斜线的部分表示该缓冲区中放有产品，否则为空。in表示生产者下次存入产品的单元，out表示消费者下次取出产品的单元。

为使这两类进程协调工作，防止盲目的生产和消费，它们应满足如下同步条件：

（1）任一时刻所有生产者存放产品的单元数不能超过缓冲区的总容量（N）。

（2）所有消费者取出产品的总量不能超过所有生产者当前生产产品的总量。

设缓冲区的编号为0 N-1，in和out分别是生产者进程和消费者进程使用的指针，指向下面可用的缓冲区，初值都是0。

为使两类进程实行同步操作，应设置3个信号量：两个计数信号量full和empty，一个互斥信号量mutex。

full：表示放有产品的缓冲区数，其初值为0。

empty：表示可供使用的缓冲区数，其初值为N。

mutex：互斥信号量，初值为1，表示各进程互斥进入临界区，保证任何时候只有一个进程使用缓冲区。

下面是解决这个问题的算法描述。

（1）在每个程序中必须先做P(mutex)，后做V(mutex)，二者要成对出现。夹在二者中间的代码段就是该进程的临界区。

（2）对同步信号量full和empty的P和 V操作同样必须成对出现，但它们分别位于不同的程序中。

（3）无论在生产者进程中还是在消费者进程中，两个P操作的次序不能颠倒：应先执行同步信号量的P操作，然后执行互斥信号量的P操作。否则可能造成进程死锁。

请大家针对以下情况分析上述方案中各进程的运行过程：

解析：

用P和V操作实现同步时应注意：

（1）只有生产者进程在运行，消费者进程未被调度运行；

（2）消费者进程要超前生产者进程运行；

（3）生产者进程和消费者进程被交替调度运行。