理发店问题。有一个理发店,有m个理发师,店内配置了m个理发椅,分别与理发师一一对应;此外还配置了n

Question

理发店问题。有一个理发店，有m个理发师，店内配置了m个理发椅，分别与理发师一一对应；此外还配置了n个等待座席，供顾客在店内等候理发。一旦等候的顾客坐满等候座席，只能在门外排队等候进入理发店。试考虑最简单的方案，用P、V操作来实现能够保证顾客先来先进入理发店的秩序，需要(23)。

A．1个信号量，初值为m+n

B．2个信号量，初值分别为m，n

C．2个信号量，初值分别为m+n，0

D．3个信号量，初值分别为m，n，0

Answer 1

正确答案：C
解析：本题考查的是信号量的概念以及在解决同步、互斥问题中的应用。由于理发店内只有n个等候席，m个理发椅，因此理发店内在同一时刻最多有m个顾客在理发的过程中，n个顾客在等候席上等待。一旦某个顾客理完发，离开座椅，等候席上等待的顾客可以顺序递补，开始理发。当想要理发的顾客人数太多时，等候席上也可能客满，这时顾客不能进入理发店，只能在店外排队等候。只有当一个顾客理完发离开理发椅，等候席上的第一个顾客坐上理发椅，空出了一个等候席，在门外排队等候的第一个顾客才可以进入并坐在等候席上等候理发。本题只有一个同步条件。这里，并不显式地指明顾客在店内的状态。原则上，一个同步或互斥的条件将对应一个信号量，因此本题只设立一个信号量S，它的初值为m+n。这里，能进入理发店的顾客可以达到m+n个，其中，前面m个顾客坐上了理发椅理发，后面n个顾客在等候席上等候。多于m+m个的顾客进入信号量S对应的等待队列中等待，其语义是在理发店门外排队等候。一旦某个顾客理完发并离开理发店，将请门外的第一个顾客进入。当然，这里可以保证顾客先来先进入理发店，但不保证先来的顾客先离开理发店。这也是很自然的，符合实际情况。但是，这种方法却不能保证店内的秩序。顾客流程：P(S)→进入理发店，在等候席上等待，理发→V(S)