《操作系统.ppt》由会员分享，可在线阅读，更多相关《操作系统.ppt（79页珍藏版）》请在金锄头文库上搜索。
1、2.4 经典进程的同步问题,2.4.1 生产者-消费者问题 2.4.2 哲学家进餐问题 2.4.3 读者-写者问题,同步解题步骤总结：,1.分析同步、互斥关系。,找前驱关系AB,找共享资源,2.设置信号量，赋初值。,互斥：,同步：,设置一个公有信号量。Mutex=1,0,描述临界资源的初始状态。,有几重同步关系就设置几个私有信号量。,例:AB，S描述进程B开始执行的条件是否满足。,S,3.用P-V操作实现。,【单个缓冲区的同步问题】,get,put,父亲,女儿,儿子,单生产者多消费者问题:桌上有一个空盒，盒内只允许存放一个水果。爸爸向盒内放水果（苹果或者橘子）.儿子只吃盒中的苹果，女儿只吃盒中
2、的橘子。用PV操作来协调3人的关系，实现3人正确的活动。,1、【2009考研真题（7 分）】三个进程 P1、P2、P3 互斥使用一个包含 N（N0）个单元的缓冲区。P1 每次用 produce（）生成一个正整数并用 put（）送入缓冲区某一空单元中；P2 每次用 getodd（）从该缓冲区中取出一个奇数并用countodd（）统计奇数个数；P3 每次用 geteven（）从该缓冲区中取出一个偶数并用 counteven（）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述。,定义信号量 mutex 控制进程间互斥使用缓冲区。 odd控制 P
3、2 ；even 控制 P3 之间的同步；empty控制P1；程序如下：,Var odd=0,even=0,empty=N,mutex=1; Parbegin P1:beginX=produce(); /*生成一个数*/P(empty); /*判断缓冲区是否有空单元*/P(mutex); /*缓冲区是否被占用*/Put(); V(mutex); /*使用完缓冲区，释放*/If x%2=0V(even); /*如果是偶数，向 P3 发出信号*/elseV(odd); /*如果是奇数，向 P2 发出信号*/ end.,P2:beginP(odd); /*收到 P1 发来的信号，已产生一个奇数*/P(
4、mutex); /*缓冲区是否被占用*/Getodd();Countodd( )V(mutex); /*释放缓冲区*/V(empty); /*向 P1 发信号，多出一个空单元*/end. P3:beginP(even) /*收到 P1 发来的信号，已产生一个偶数*/P(mutex); /*缓冲区是否被占用*/Geteven( );Counteven( );V(mutex); /*释放缓冲区*/V(empty); /*向 P1 发信号，多出一个空单元*/end.,【思考题】,2.用P.V操作解决下图之同步问题:,磁盘,缓冲区1,缓冲区2,read,copy,print,有三个进程PA、PB和PC
5、合作解决文件打印问题：PA将文件记录从磁盘读入主存的缓冲区1，每执行一次读一个记录；PB将缓冲区1的内容复制到缓冲区2，每执行一次复制一个记录；PC将缓冲区2的内容打印出来，每执行一次打印一个记录。缓冲区的大小等于一个记录大小。请用P、V操作来保证文件的正确打印。,磁盘,缓冲区1,缓冲区2,read,copy,print,读数据缓冲区1空？记录存缓冲区1缓冲区1满,缓冲区1满？ 从缓冲区1取 缓冲区1空缓冲区2空？ 记录存缓冲区2 缓冲区2满,缓冲区2满？从缓冲区2取缓冲区2空 打印,read,copy,print,Var empty1,full1,empty2,full2:semaphore
6、:=1,0,1,0; BeginparbeginPread:beginrepeat从磁盘读一个记录；p(empty1);将记录存入缓冲区1；v(full1);until false;end,Pcopy:beginrepeatp(full1);从缓冲区1取记录；v(empty1);p(empty2);将记录存入缓冲区2v(full2);until false;end,Pcopy:beginrepeatp(full2);从缓冲区2取记录；v(empty2);打印； until false;end,进程互斥,P1,P2,例1：过独木桥,分析：进程p1、p2因竞争独木桥而成为互斥关系,Var m:se
7、maphore:=1; BeginparbeginP1:begin,p(m);从西向东过独木桥；V(m); end,2、某图书馆有100个座位，每位进入图书馆的读者要在登记表上登记，退出时要在登记表上注销。要几个程序？有多少个进程？ （1）当图书馆中没有座位时，后到的读者在图书馆为等待（阻塞） （2）当图书馆中没有座位时，后到的读者不等待，立即回家。,思路分析： 当没有座位时，读者等待（阻塞）,读者 无座位则等待（申请座位） 有座位则先登记 进入图书馆阅读 离开时先注销 离开 ,座位为共享资源，故设置资源性信号量：S=100表示可用座位;,登记本为共享资源，故设置信号量：mutex=1表示对登
8、记本的使用权限;,Var S,mutex: semaphore: =100,1,思路分析： 当没有座位时，读者等待（阻塞）,读者 无座位则等待（申请座位） 有座位则先登记 进入图书馆阅读 离开时先注销 离开 ,P(S)P(MUTEX)登记V(MUTEX)阅读P(MUTEX)注销V(MUTEX)V(S),Var S,mutex: semaphore: =100,1,（2）当无座位时，后到的读者不等待，立即回家 设互斥性信号量MUTEX=1表示对登记本的修改权限。整型变量 COUNT=100对可用座位进行计数;,IF (COUNT=0)RETURN; else COUNT=COUNT-1;P(MU
9、TEX);登记V(MUTEX);阅读P(MUTEX);注销V(MUTEX); COUNT=COUNT+1;,读者 无座位则离开 有座位则先登记 进入图书馆阅读 离开时先注销 离开 ,P(MUTEX); IF (COUNT=0) V(MUTEX);RETURN; COUNT=COUNT-1; 登记 V(MUTEX); 阅读 P(MUTEX); COUNT=COUNT+1; V(MUTEX);,例3：,在南开大学和天津大学之间有一条弯曲的小路，其中从S到T有一段路每次只允许一辆自行车通过，但是，其中有一个小的安全岛M（同时允许两辆自行车停留），可以供两辆自行车错车时使用，如图所示，试设计一个算法以
10、确保来往自行车的顺利通过,分析：sk、tl段互斥，M允许两辆自行车，南开到天津及天津到南开各只能有一辆自行车 应设5个信号量， ST表示是否允许从南开到天津，初值为1； TS表示是否允许从天津到南开，初值为1； K表示是否允许车子过S到K路段，初值为1； L表示是否允许车子过T到L路段，初值为1； M表示安全岛上可以放的自行车数量，初值为2；,Totianjin() p(ST);P(k);从S到K；p(M);v(K);进入安全岛；p(L);v(M);从L到T；V(L);v(ST); ,Tonankai() p(TS);P(L);从T到L；p(M);v(L);进入安全岛；p(K);v(M);从K
11、到S ；V(K);v(TS); ,例4：,一个供应商用汽车给某超市送货，并把汽车上的货物用超市的三轮车运到仓库中。超市的工作人员也用三轮车从仓库中取货去出售。假设共有3辆三轮车，仓库中只能容纳10辆三轮车的货物，(且每次从汽车上取货只能供给一辆三轮车，)仓库也只能容纳一辆三轮车进人。考虑相关信号量的定义及初值，并写出用P、v操作实现向仓库中送货及从仓库中取货的同步算法。,Var tricycle,empty,full,mutex:semaphore:=3,10,0,1,送货进程 while(true)Wait（tricycle）;从汽车上取货到三轮车；swait（empty，mutex）；送货
12、到仓库；Ssignal（full，mutex）signal（ tricycle ） ,取货进程 while(true)Wait（tricycle）;swait（empty，mutex）；从仓库取货；Ssignal（full，mutex）送货到超市； signal（tricycle）,有一个仓库，可以存放A和B两种产品，但要求： （1）每次只能存入一种产品（A或B）； （2）NA产品数量B产品数量M。 其中，N和M是正整数。试用P、V操作描述产品A与产品B的入库过程。,分析：,A最多可以放？ B最多可以放? 放一个A意味着B可以放的个数增加1； 放一个B 意味着A可以放的个数增加1；,2.4.2
13、哲学家进餐问题,问题描述：有五个哲学家围在一张圆桌边思考边吃面条，桌上放五个碗和五支筷子。当哲学家饥饿时只有拿起其左右两支筷子才能进餐，进餐完毕又把筷子放下。,分析： （1）筷子为临界资源，五支筷子用五个信号量表示。 （2）让哲学家们饥饿时总是先拿左边的筷子，然后在拿右边的筷子。,p0,p4,p3,p2,p1,0,1,2,3,5,2.4.2哲学家进餐问题,利用记录型信号量解决哲学家进餐问题,Var chopstick: array0, , 4 of semaphore; Repeatwait(chopsticki);wait(chopstick(i+1)mod 5);eatsignal(cho
14、psticki);signal(chopstick(i+1)mod 5);think; Until false,死锁问题,死锁问题：所有哲学家同时拿着左边的筷子等待右边的筷子。 解决办法： ？,解决办法： （1）当哲学家左右筷子均可用时，才能拿起筷子进餐。,2.4.2哲学家进餐问题,1.利用AND信号量解决哲学家进餐问题,Var chopstick: array0, , 4 of semaphore:=(1,1,1,1,1); processi Repeatthink;Swait(chopstick(i+1)mod 5,chopsticki);eatSsignal(chopstick(i+1)
15、mod 5,chopsticki); Until false,解决办法： （1）当哲学家左右筷子均可用时，才能拿起筷子进餐。 （2）限制同时只允许4个哲学家进餐。,semaphore chopstick5=1，1，1，1，1; semaphore count=4; Repeatthink(); wait(count); /请求进餐 wait(chopsticki); /请求左手边的筷子 wait(chopstick(i+1)%5); /请求右手边的筷子 eat(); signal(chopstick(i+1)%5); /释放右手边的筷子 signal(chopsticki); /释放左手边的筷
16、子 signal(count); /释放信号量count until false ,解决办法： （1）当哲学家左右筷子均可用时，才能拿起筷子进餐。 （2）限制同时只允许4个哲学家进餐。 （3）限制拿起筷子的方法：一部分先拿左边、一部分先拿右边。,原理：规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边的筷子;而偶数号的哲学家则相反.按此规定,将是1,2号哲学家竞争1号筷子,3,4号哲学家竞争3号筷子.即五个哲学家都竞争奇数号筷子,获得后,再去竞争偶数号筷子,最后总会有一个哲学家能获得两支筷子而进餐。而申请不到的哲学家进入阻塞等待队列，根FIFO原则，则先申请的哲学家会较先可以吃饭，因此不会出现饿死的哲学家。,
