软件设计师第5部分工作流程和算法流程

　　●试题2

　　阅读下列说明和图，回答问题1至问题3，将解答填人答题纸的对应栏内。

　　【说明】

　　实现进程的同步与互斥控制的常见方法是信号量，信号量S的P、V操作如下：

　　P(S)：S：=S—l，若s≥0，则执行P操作的进程继续执行;若S<0，则置该进程为阻塞状态，并将其插入阻塞队列。

　　v(s)：s：=S+1，若S>0，则执行V操作的进程继续执行;若S≤0，则从阻塞队列唤醒一个进程，并将其插入就绪队列，然后执行V操作的进程继续执行。

　　【问题1】

　　在某并发系统中，有一个发送进程A、一个接收进程B、一个环形缓冲区BUFF、信号量Sl和 S2。发送进程不断地产生消息并写入缓冲区BUFF，接收进程不断地从缓冲区BUFF取消息。假设发送进程和接收进程可以并发地执行，那么，当缓冲区的容量为N时，如何使用P、V操作才能保证系统的正常工作。发送进程A和接收进程B的工作流程如图5.5所示。请在图5.5中的空(1)一(4)处填入正确的内容。

　　　　【问题2】

　　若系统中有多个发送进程和接收进程，进程间的工作流程如图5.6所示，其中空(1)～(4)的 内容与图5.5相同。发送进程产生消息并顺序地写入环形缓冲区BUFF，接收者进程顺序地从 BUFF中取消息，且每条消息只能读取一次。为了保证进程间的正常通讯，增加了信号量Sa和sb。 ①请说明信号量sa和sb的物理意义，并在图5.6中的空(5)和空(6)处填人正确的内容。 ②请从图5.6的(a)～(1)中选择四个位置正确地插入P(Sa)、V(Sa)、P(Sb)、V(Sb)。
　　 

　　【问题3】

　　设系统中只有进程A和进程B，除了互斥地使用CPU和打印机R外，进程A和B不使用其他 资源。另外，进程8的优先级比A高，而进程A先于8准备好。进程A和B的执行情况如图5.7 所示，其中粗实线表示进程在执行中，细实线表示打印机R在使用中(每个进程具有三种状态：运 行、就绪和阻塞)。

　　清分别说明进程A和B在图5.7所示的t1、t2、t3、t4时刻所处的状态;若是阻塞状态，请说明 阻塞原因。

　　【问题1】解答：

　　A进程在进行P操作之前肯定已经产生一条消息，即(1)处。在向缓冲区中写完数据时，需要 修改缓冲区的当前指针。所以(1)产生一条消息(2)i+←(i+1)mod N。

　　进程B在读取消息之前需要进行P(s2)操作，在读取消息完后，需要今行V(S2)操作，因此 (3)P(S2)(4)V(S2)。

　　【问题2】解答：

　　(5)、(6)均填1，Sa和sb分别表示允许同时对缓冲区进行写操作和读操作的进程数量，此时P

　　(Sa)、V(Sa)、P(Sb)、V(Sb)应分别插入位置(b)、(f)、(h)、(k)。

　　Sa和Sb也可以分别表示允许同时对缓冲区进行读操作和写操作的进程数量，此时 P(Sa)、V(Sa)、P(Sb)、V(Sb)应分别插入位置(h)、(k)、(b)、(f)。

　　【问题3】解答：

　　对于进程A，在t1并口t2时刻等待R工作结束，处于阻塞状态，原因是等待I/0结束，在t3时刻运行，在t4时刻由于不如B的优先级高，因而进入就绪状态。

　　对于进程8，在t1时刻处于运行状态，在t2时刻由于要使用临界资源R而进入阻塞状态，原因即是等待R资源，在t3时刻，进程8由于等待R工作结束而进入阻塞状态，原因即是等待I/O结束。在t4时刻，CPU被分配给进程8，所以它处于运行状态。