-
- 加为好友
- 发送私信
- 在线聊天
-
 studyboyz
- 等级:
- 可用分等级：
- 总技术分：
- 总技术分排名：
- 结帖率：
|
| 发表于：2008-08-19 21:53:15 楼主 |
理发师问题的描述：
一个理发店接待室有n张椅子，工作室有1张椅子；
没有顾客时，理发师睡觉；
第一个顾客来到时，必须将理发师唤醒；
顾客来时如果还有空座的话，他就坐在一个座位上等待；
如果顾客来时没有空座位了，他就离开，不理发了；
当理发师处理完所有顾客，而又没有新顾客来时，他又开始睡觉。
现在各种参考书上比较时兴的解决理发师问题的算法大概其就是下边这个算法，不同版本大同小异吧。
var mutex,barber,wakeup:semaphore:=1,0,0;
empty:integer:=n+1; //empty表示空座位的数量，接待室加上工作室共n+1个座位
begin
parbegin
customer:begin
wait(mutex); //mutex控制对empty的互斥访问
if empty=0 then begin //如果没有空座，顾客走人，不理发了
signal(mutex); exit();
end
else begin
empty:=emtpy-1;
if empty=n-1 then begin
signal(wakeup); //如果是第一个顾客，得叫醒理发师
signal(mutex);
end
else begin
signal(mutex);
wait(barber); //第一个顾客不用等待，后续的顾客需要等待理发师腾出手来
end
理发;
end //对应else begin
end //customer进程结束
barber: begin
wait(wakeup); //初始状态，理发师在睡觉，一旦被唤醒，就进入下边这个无限循环
repeat
理发; //被唤醒了，直接给第一个顾客理发
wait(mutex); //收拾完一个，要修改空座的数量，争夺empty的控制权
empty:=empty+1;
if empty <n then begin //empty <n表示还有等着的顾客
signal(barber); //表示理发师腾出手来了
signal(mutex);
end
else begin
signal(mutex);
wait(wakeup); //没顾客了，睡觉去，等待唤醒
end //对应else begin
until false;
end //barber进程结束
parend
end
我感觉这个算法有点问题，因为customer进程中的“理发”语句和barber进程中的“理发”语句并不同步，当两个进程进入执行这两个语句的状态时，实际上已经失去了同步性。比如说，customer进程中的“理发”语句先执行完了，那么此时barber在给谁理发呢，barber中的“理发”语句运行还有什么意义呢？反之亦然。
所以，我认为必须用生产者、消费者模型才能完美地解决这个问题。基本思想是：多个顾客就是多个生产者，来到时将自己放入有n个缓冲区的缓冲池，而理发师是消费者，不断地从缓冲区中取出顾客，将其消费掉。这样，理发师所提供的服务和消费者所接受的服务才是完美地同步进行，而不会出现上面那种顾客已经走了，理发师还在空转的现象。算法如下：
var customers:array[0...n-1] of customer;
empty,in,out:integer:=n,0,0;
wakeup,mutex:semaphore:=0,1; //mutex控制对缓冲池,empty,in,out的互斥访问
begin
parbegin
customer:begin
wait(mutex);
if empty=0 then begin
signal(mutex); exit();
end
else begin
customers[in]:=a_customer;
in:=(in+1) mod n;
empty:=empty-1;
if empty=n-1 then signal(wakeup);
signal(mutex);
end
end
barber:begin
wait(wakeup);
repeat
wait(mutex);
if empty=n then begin
signal(mutex);
wait(wakeup);
end
else begin
a_customer:=customer[out]; //相当于将顾客从接待室领到工作室
out:=(out+1) mod n;
empty:=empty+1;
signal(mutex);
将此customer消费掉，即给他理发;
end
until false;
end
parend
end |
|
|
|
20
修改
删除
举报
引用
回复
| |
