m个进程(Pi,0≤i≤m－1)通过k个等长的缓冲区(Bi,0≤i≤k－1)向n个进程(Qi,0≤i≤m－1)发送消息。每个进程Pi

Question

m个进程(Pi，0≤i≤m-1)通过k个等长的缓冲区(Bi，0≤i≤k-1)向n个进程(Qi，0≤i≤m-1)发送消息。每个进程Pi发送消息的顺序与数量不受限制，每个进程Qi接收消息的顺序与数量也不受限制，但发送进程与接收进程作为两个分别的整体，要求消息发送与接收的整体次序相同。为保证消息发送与接收的充分并行，需要设置(24)。

A．3个信号量，初值分别为1，1，0

B．4个信号量，初值分别为1，0，1，0

C．3个信号量，初值分别为k，1，0

D．4个信号量，初值分别为k，1，0，1

Answer 1

正确答案：D
解析：本题考查的是信号量与P、V操作的概念及其在解决同步、互斥问题中的运用。信号量的值是有物理意义的。如果令信号量S的值为L，当L0时，表示可以允许有L个进程次(允许一个进程多次)连续地通过P(S)操作(意思是这个过程中没有执行V(S)操作)，无须进入等待状态；当L≤0时，表示有-L个进程正在信号量S对应的等待队列中，等待由进程执行V(S)将它们释放。原则上，一个同步条件需要一个信号量来管理。本题中，缓冲区的个数有k个，这意味着发送进程可以连续地向缓冲区组发送k个消息，中间无须接收进程取走消息，只有当缓冲区全装满消息，发送进程才需要等待接收进程取走消息，以便腾空缓冲区可以再放消息。因此设立信号量S1，初值为k。此外，缓冲区有多个，为了保证存放消息的次序，需要约束发送进程，按缓冲区号顺序放入消息。因此需设置一个变量f，指示当前消息放入f号缓冲区，f的初值为零。发送进程放入一个消息后，执行f+1操作，指向下一个缓冲区。这样，变量f为m个发送进程所共享，为保证修改的互斥，需要设置一个信号量S2，初值为1。从接收进程角度来看，Qi取走消息的前提是缓冲区中必须有尚未取走的消息。刚开始时，缓冲区为空，S2的初值应为0。另一方面，为了保证取消息的顺序必须与送入消息的顺序一致，接收进程同样需要一个共享变量t来指示当前需要取走的消息所在的缓冲区号，取走消息后执行t+1操作。还要设置一个信号量S4，初值为0。这样，共需设置4个信号量S1、S2、S3\S4，初值分别为k、1、0、1。下图表示多个发送进程与多个接收进程利用一组缓冲区通信的流程。