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