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

聿(嗜睡的理发师问题,由图灵奖获得者Dijkstra教授提出。)膃一个理发店由一个有几张椅子的等待室和一个放有一张理发椅子的理发室组成。肁若没有要理发的顾客,则理发师就睡觉。膀一个顾客走进理发店,若发现所有椅子都被等待理发的顾客占用,则该顾客就离开理发店;若理发师正在理发并且有空椅子,则该顾客就找一个空椅子坐下来等待;若理发师在睡觉,则顾客便唤醒他。螈请设计理发师和顾客的同步算法。芃薂分析:袂对于互斥同步,主要解决两个问题: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); 查看有无顾客要求服务螅