操作系统补充内容-经典同步问题.doc

Forpersonaluseonlyinstudyandresearch;mercialuse(嗜睡的理发师问题,由图灵奖获得者Dijkstra教授提出。)一个理发店由一个有几张椅子的等待室和一个放有一张理发椅子的理发室组成。若没有要理发的顾客,则理发师就睡觉。一个顾客走进理发店,若发现所有椅子都被等待理发的顾客占用,则该顾客就离开理发店;若理发师正在理发并且有空椅子,则该顾客就找一个空椅子坐下来等待;若理发师在睡觉,则顾客便唤醒他。请设计理发师和顾客的同步算法。Forpersonaluseonlyinstudyandresearch;mercialuse分析:对于互斥同步,主要解决两个问题:1正确设置信号量,2恰当安排PV原语的使用顺序。1信号量有无要理发的顾客,m=0;进入等待室的顾客的理发权,s=1;等待室中空椅子数量count=N及检查时的使用权t=1。2同步算法顾客: p(t); ifcount=0then{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,起到了先来后到的作用。合作同步关系:1顾客向理发师发出一个新的理发请求,理发师要查看有无要理发的顾客;2每叫入一位顾客到理发室,也表示将理发权传递给下一位等待的顾客。请同学们也考虑有无其他方案,说明理由,不同教材中也有不同描述。注意:若后来顾客先p(s)呢,因为理发师叫入顾客是按v(s)进行的,可能发生后来的先理发,可讨论。(面包店问题,由图灵奖获得者Lamport提出。)面包店销售面包和蛋糕,店内有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); 查看有无顾客要求服务 叫起一位等待的顾客并提供销售服务; 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); 向销售员发出服务请求 销售服务