操作系统原理：进程同步的信号灯实现

进程的同步可以通过信号灯的P、V操作来实现。用信号灯的P、V操作实现进程同步的关键是要分析清楚同步进程之间的相互关系，即什么时候某个进程需要等待，什么情况下需要给对方发一个信息；还需要分析清楚同步进程各自关心的状态。依据分析的结果就可以知道如何设置信号灯，如何安排P、V操作。

在病员看病的例子中，医生的看病进程要与化验室的化验进程同步，可用信号灯的P、V操作来实现。首先设置两个同步用的信号灯s1、s2，然后通过信号灯的P、V操作实现化验进程和看病进程的同步。

信号灯可以解决进程的同步问题。一般同步问题可以分为两类：一类是保证一组合作进程按逻辑需要所确定的执行次序；另一类是保证共享缓冲区（或共享数据）的合作进程的同步。下面先讨论第一类问题的解法。

1.合作进程的执行次序

若干进程为了完成一个共同任务需要并发执行，然而这些并发进程之间根据逻辑上的需要，有的操作可以没有时间上的先后次序，即无论是谁先做，最后的计算结果都是正确的。但有的操作有一定的先后次序，也就是说它们必须遵循一定的同步规则，只有这样，并发执行的最后结果才是正确的。

为了描述的方便，可用一个图来表示进程集合的执行时间轨迹。图的连接描述了进程间开始和结束的次序约束。此图称为进程流图。如用s表示系统中某一任务启动，f表示完成，则可用图4-6所示的进程流图来表示这一组合作进程执行的先后次序。

图4-6（a）说明p1、p2、p3这三个进程依次顺序执行，只有在前一个进程结束后，后一个进程才能开始执行，当p4完成时，这一组进程全部结束。图4-6（b）则表示p1、p2、p3、p4这四个进程可以同时执行。图4-6（c）（d）中描述的进程执行次序是混合式的，既有顺序的、也有并行的。如在图4-6（d）中，p1执行结束后，p2、p5、p7可以开始执行，p2结束后p3、p4可开始执行，而只有当p4、p5都结束时p6才能开始执行等。

图4-6　进程流图

对于这样一类问题如何用信号灯解决，说明如下。

设pa、pb、pc为一组合作进程，其进程流图如图4-7所示。

(www.xing528.com)

图4-7　三个并发程序的进程流图

图4-7说明任务启动后pa先执行，当它结束后，pb、pc可以开始执行，当pb、pc都执行完毕，任务结束。为了确保这一执行顺序，设两个同步信号灯sb、sc分别表示进程pb和pc能否开始执行，其初值均为0。

2.共享缓冲区的合作进程的同步

诸进程的另一类同步问题是共享缓冲区的同步。通过下例可说明这类问题的同步规则及信号灯解法。

设某计算进程cp和打印进程iop共用一个单缓冲。其中进程cp负责不断地计算数据并送入缓冲区buf中，进程iop负责从缓冲区buf中取出数据去打印。这两个进程可以并发执行，但由于它们共用一个缓冲区，所以必须遵循一个同步规则，即对缓冲区的操作应做某种限制，以使最终的输出结果是正确的。

通过分析可知，进程cp和进程iop必须遵循以下同步规则：

①当进程cp把计算结果送入buf时，进程iop才能从buf中取出结果去打印，即当buf内有信息时，进程iop才能执行，否则必须等待；

②当进程iop把buf中的数据取出打印后，进程cp才能把下一个计算结果数据送入buf中，即只有当buf为空时，进程cp才能执行，否则必须等待。

这一同步规则可推广为：如果发送者企图放一个信息到一个满的buf中时，它必须等到接收者从该buf中取走上一个信息；而如果接收者企图从一个空的buf中取下一个信息时，它必须等到发送者放一个信息到这个buf中（假定所有信息的发送次序和接收次序精确相同）。

为了遵循这一同步规则，这两个进程在并发执行时必须通信，即进行同步操作。为此，设置两个信号灯sa和sb。信号灯sa用来表示缓冲区中是否有可供打印的计算结果，其初值为0。每当计算进程把计算结果送入缓冲区后，便对sa执行v（sa）操作，表示已有可供打印的结果。打印进程在执行前须先对sa执行P（sa）操作。若执行P操作后sa=0，则打印进程可执行打印操作；若执行P操作后sa＜0，表示缓冲区中尚无可供打印的计算结果，打印进程被阻。信号灯sb用来表示缓冲区有无空位置存放新的信息，其初值为1。当计算进程算得一个结果，要放入缓冲区之前，必须先对sb做P（sb）操作，看缓冲区是否有空位置。若执行P操作后sb=0，则计算进程可以继续执行；否则，计算进程被阻，等待打印进程从缓冲区取走信息后将它唤醒。打印进程把缓冲区中的数据取走后，便对sb执行v（sb）操作，用以和计算进程通信。即告之缓冲区信息已取走，又可存放新的信息了。