《操作系统补充内容-经典同步问题》由会员分享，可在线阅读，更多相关《操作系统补充内容-经典同步问题（3页珍藏版）》请在金锄头文库上搜索。
1、（嗜睡的理发师问题，由图灵奖获得者（嗜睡的理发师问题，由图灵奖获得者 Dijkstra 教授提出。教授提出。 ） 一个理发店由一个有几张椅子的等待室和一个放有一张理发椅子的理发室组成。 若没有要理发的顾客，则理发师就睡觉。 一个顾客走进理发店，若发现所有椅子都被等待理发的顾客占用，则该顾客就离开理发店；若理发师正 在理发并且有空椅子，则该顾客就找一个空椅子坐下来等待；若理发师在睡觉，则顾客便唤醒他。 请设计理发师和顾客的同步算法。分析： 对于互斥同步，主要解决两个问题：1 正确设置信号量，2 恰当安排 PV 原语的使用顺序。 1 信号量 有无要理发的顾客，m=0； 进入等待室的顾客的理发权，s
2、=1； 等待室中空椅子数量 count=N 及检查时的使用权 t=1。 2 同步算法 顾客： p(t); if count = 0 then v(t); exit; 若无空椅子，则退出理发店； count 1; 坐在一张空椅子上； v(t);v(m);有要理发的顾客； p(s);现在能否理发，若不能则等待； 被叫入理发室； p(t); count + 1;腾出一张空椅子； v(t); 理发；理发师： p(m); 若没有要理发的顾客，则睡觉。 叫入一位顾客进入理发室； v(s); 理发3 竞争合作关系 互斥竞争关系： 1 顾客之间要竞争 N 把空椅子 count，同时要竞争计数检查时的使用权 t
3、； 2 表面看是竞争 N 把空椅子，其实 count 也起到了同步作用，即限制可以等待的顾客的数量，最多 N 个；3 进入等待室的顾客要竞争理发权 s，起到了先来后到的作用。合作同步关系： 1 顾客向理发师发出一个新的理发请求，理发师要查看有无要理发的顾客； 2 每叫入一位顾客到理发室，也表示将理发权传递给下一位等待的顾客。 请同学们也考虑有无其他方案，说明理由，不同教材中也有不同描述。注意：若后来顾客先 p(s)呢，因为理发师叫入顾客是按 v(s)进行的，可能发生后来的先理发，可讨论。 （面包店问题，由图灵奖获得者（面包店问题，由图灵奖获得者 Lamport 提出。提出。 ） 面包店销售面包
4、和蛋糕，店内有 n 个销售员。每个顾客进店后先取一个号，并等待叫号；若有销售员空 闲下来，则叫下一个号并为该号顾客提供销售服务。请描述顾客、销售员之间的同步算法。 分析： 1 顾客之间应互斥取服务号，设 count=1 及其使用权 s=1； 2 顾客取到服务号后，应向销售员表明要求服务的请求 m=0，若销售员空闲，则应查看有无顾客要求服务；3 顾客之间竞争（被）服务权 t=0；（方案 1） 顾客： p(s); 取服务号 count; count+1; v(s); v(m); 有顾客提出服务请求 p(t);申请（被）服务权，等待（被）服务 销售服务；销售员 i： p(m);查看有无顾客要求服务
5、叫起一位等待的顾客并提供销售服务； v(t);注： 1 这里似乎存在漏洞，若后来的先 p(t)，则打乱顺序； 2 叫起顾客应按顺序，可能要设计队列。（方案 2） 1 设服务号 count=1，排队队列 queue 登记服务号，使用权 s=1，顾客应竞争取号； 2 顾客应向销售员发出服务请求 m=0，若销售员空闲，则应查看有无顾客要求服务；顾客： p(s); 取号 count 并排入队列 queue; count+1; v(s); v(m);向销售员发出服务请求 销售服务；销售员 i： p(m);p(s); 从排队队列 queue 中取下一个服务号； v(s); 为该号顾客提供服务；注： 这里也存在不足吗，请考虑。这些同步问题中需要处理的是竞争和合作关系，既有竞争又有合作，竞争的一般是公有资源，合作的一 般是同步信号，即时序关系，有的简单一些，有的复杂一些，我们这里提供的是使用一般信号量机制来 解决，也有需要信号量集机制进行解决的问题，比如哲学家就餐问题，请考虑。
