os经典问题.doc

第二章 Typical Excises一 生产者-消费者问题扩展1.扩展一（北大1991）设有一个可以装A、B两种物品的仓库,其容量无限大，但要求仓库中A、B两种物品的数量满足下述不等式：-M（A物品数量B物品数量）N其中M和N为正整数。试用信号量和PV操作描述A、B两种物品的入库过程。问题分析：若只放入A，而不放入B，则A产品最多可放入N次便被阻塞；若只放入B，而不放入A，则B产品最多可放入M次便被阻塞；每放入一次A，放入产品B的机会也多一次；同理，每放入一次B，放入产品A的机会也多一次。The P,V code Using Pascal Semaphore mutex=1，sa=N，sb=M; cobegin procedure A: procedure B: while(TURE) while(TURE) begin begin p(sa); p(sb); p(mutex); p(mutex); A产品入库； B产品入库； V(mutex); V(mutex); V(sb); V(sa); end end coend 2.扩展二（北大1995）设有一个可以装A、B两种物品的仓库，其容量有限（分别为N），但要求仓库中A、B两种物品的数量满足下述不等式:-MA物品数量B物品数量N其中M和N为正整数。另外，还有一个进程消费A,B，一次取一个A，B组装成C。试用信号量和PV操作描述A、B两种物品的入库过程。问题分析：已知条件-MA物品数量B物品数量N可以拆成两个不等式，即A物品数量B物品数量NB物品数量A物品数量M这两个不等式的含义是：仓库中A物品可以比B物品多，但不能超过N个；物品可以比A物品多，但不能超过M个。The P,V code Using Pascalsemaphore mutex=1,a,b=m,empty1,empty2=N,full1,full2=0;cobegin process(A); process(B); process(C)coend A物品入库：process A begin while(TRUE) begin p(empty1); P(a); p(mutex); 2.扩展二（北大1995）设有一个可以装A、B两种物品的仓库，其容量有限（分别为N），但要求仓库中A、B两种物品的数量满足下述不等式:-MA物品数量B物品数量N其中M和N为正整数。另外，还有一个进程消费A,B，一次取一个A，B组装成C。试用信号量和PV操作描述A、B两种物品的入库过程。问题分析：已知条件-MA物品数量B物品数量N可以拆成两个不等式，即A物品数量B物品数量NB物品数量A物品数量M这两个不等式的含义是：仓库中A物品可以比B物品多，但不能超过N个；物品可以比A物品多，但不能超过M个。The P,V code Using Pascalsemaphore mutex=1,a,b=m,empty1,empty2=N,full1,full2=0;cobegin process(A); process(B); process(C)coend A物品入库：process A begin while(TRUE) begin p(empty1); P(a); p(mutex);    3.扩展三设P,Q,R共享一个缓冲区，P，Q构成一对生产者-消费者，R既为生产者又为消费者。使用P,V实现其同步。问题分析：略。The P,V code Using Pascalvar mutex,full,empty:semaphore;full:=1;empty:=0;mutex:=1;cobegin Procedure P Procedure Q Procedure R begin begin begin while true while true if empty:=1 then p(empty); p(full); begin P(mutex); P(mutex); p(empty); Product one； consume one； P(mutex); v(mutex); v(mutex); product； v(full); v(empty); v(mutex); end end v(full); endif full:=1 then begin p(full); p(mutex);消费一个产品； v(mutex); v(empty); endcoend 2.读者一写者问题(Readers-Writers Problem)问题描述：有一个许多进程共享的数据区，这个数据区的一块空间；有一些只读取这个数据区的进程（Reader）和一程(Writer)，此外还需要满足以下条件：（1）任意多个读进程可以同时读这个文件；（2）一次只有一个写进程可以往文件中写；（3）如果一个写进程正在进行操作，禁止任何读进程度文件。实验要求用信号量来实现读者写者问题的调度算法。实验类通过P()、V()两个方法实现了P、V原语的功能。实验的任务法以及Writer类的Write方法。我们需要分两种情况实现该问题：读优先：要求指一个读者试图进行读操作时，如果这时正有其直接开始读操作，而不需要等待。写优先：一个读者试图进行读操作时，如果有其他写者在等写操作，他要等待该写者完成写操作后才开始读操作。The P,V code Using Pascal读者优先算法：rwmutex 用于写者与其他读者/写者互斥的访问共享数据rmutex 用于读者互斥的访问readcount 读者计数器var rwmutex,rmutex：semaphore:=1,1；int readcount=0;cobeginprocedure reader_ibegin /i=1,2,.P(rmutex);Readcount+;if(readcount=1) P(rwmutex);V(rmutex);读数据； P(rmutex);Readcount-;if(readcount=0) V(rwmutex);V(rmutex);endprocedure Writer_jbegin /j=1,2,.P(rwmutex);写更新；V(rwmutex);endCoend写者优先：1）多个读者可以同时进行读2）写者必须互斥（只允许一个写者写，也不能读者写者同时进3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒如果读者数是固定的，我们可采用下面的算法：rwmutex： 用于写者与其他读者/写者互斥的访问共享数据rmutex： 该信号量初始值设为10，表示最多允许10个读者var rwmutex,rmutex：semaphore:=1,10；cobeginprocedure reader_ibegin /i=1,2,.P(rwmutex); /读者、写者互斥P(rmutex);V(rwmutex); /释放读写互斥信号量，允许其它读、写进程访问资源读数据；V(rmutex);endprocedure Writer_jbegin /j=1,2,.P(rwmutex);for(i=1;i<=10;i+) P(rmutex); /禁止新读者，并等待已进入的读者退出写更新；for(i=1;i<=10;i+)V(rmutex);/恢复允许rmutex值为10V(rwmutex);endCoend问题扩展如果读者写者均是平等的即二者都不优先，如何实现？ 3.哲学家进餐问题问题描述：(由Dijkstra首先提出并解决)5个哲学家围绕一张圆桌而坐，桌子上放着5支筷子，每两个哲学家之间放一支；哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两支筷子，思考时则同时将两支筷子放回原处。如何保证哲学家们的动作有序进行？如：不出现相邻者同时要求进餐；不出现有人永远拿不到筷子；The P,V code Using Pascal解法一：semaphore Forki:=1(i=0,1,2,3,4)begin Thiking; Being hangery; P(Forki mod 5); p(Fork(i+1)mod 5); Eating; v(Forki mod 5); v(Fork(i+1)mod 5);end 解法二：semaphore c0?c4,初值均为1；Integer i=0,1,.,4;procedure philosopher_ibegin if i mod 2=0 then begin p(ci); p(ci+1mod 5); Eating; v(ci); v(ci+1mod 5); end else begin p(ci+1mod 5); p(ci); Eating; v(ci+1mod 5); v(ci); endend4.理发师问题作者：pz整理来源：希赛教育2009年11月13日发表评论进入社区 4.理发师问题(Barber Problem)问题描述：理发店理有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子如果没有顾客，理发师便在理发椅上睡觉一个顾客到来时，它必须叫醒理发师如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开。The P,V code Using Pascal1)控制变量waiting用来记录等候理发的顾客数，初值均为0；2)信号量customers用来记录等候理发的顾客数，并用作阻塞理发师进程，初值为0；3)信号量barbers用来记录正在等候顾客的理发师数，并用作阻塞顾客进程，初值为0；4)信号量mutex用于互斥，初值为1int waiting=0；/等候理发的顾客数int chairs=n；/为顾客准备的椅子数semaphore customers=0,barbers=0,mutex=1;cobegin barber() begin while(TRUE);/理完一人,还有顾客吗? P(cutomers);/若无顾客,理发师睡眠 P(mutex);/进程互斥 waiting:=waiting1;/等候顾客数少一个 V(barbers);/理发师去为一个顾客理发 V(mutex);/开放临界区 cut-hair();/正在理发 end customer() begin P(mutex);/进程互斥 if(waiting) begin waiting:=waiting+1;/等候顾客数加1 V(customers);/必要的话唤醒理发师 V(mutex);/开放临界区 P(barbers);/无理发师,顾客坐着养神 get-haircut();/一个顾客坐下等理/ end else V(mutex);/人满了,走吧! endcoend 5.吸烟者问题问题描述：三个吸烟者在一间房间内，还有一个香烟供应者。为了制造并抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴。供应者有丰富的货物提供。三个吸烟者中，第一个有自己的烟草，第二个有自己的纸，第三个有自己的火柴。供应者将两样东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再放两样东西（随机地）在桌面上，然后唤醒另一个吸烟者。试为吸烟者和供应者编写程序解决问题。问题分析：k供应者seller随即产生两样东西，提供它们，这里用普通变量来表示k吸烟者进程smoker根据其排号不同，拥有不同的一件东西。假设1号吸烟者拥有烟草tobacco，2号吸烟者拥有纸paper，3号吸烟者拥有火柴match。其他号码错误返回。k吸烟者的序号代表他们拥有的东西，用他们的序号和供应者产生的两样东西比较，如果都不相等，则说明他拥有的东西和供应者产生的东西匹配，它可以吸烟。如果其中一个相等，则推出，继续排队。k mutex信号量代表一个只能进入的门，每次只有一个吸烟者可以进入进行比较和吸烟。k每个吸烟者在吸烟完毕之后出门之前要叫醒供应者，调用seller进程。The P,V code Using Pascalvar s, S1, S2, S3; semaphore;S:=1; S1:=S2:=S3:=0;fiag1,flag2,fiag3:Boolean;fiag1:=flag2:=flag3:=true;cobegin process 供应者 begin repeat P(S); 取两样香烟原料放桌上，由flagi标记； /nago1、nage2、nage3 代表烟草、纸、火柴 5.吸烟者问题1作者：pz整理来源：希赛教育2009年11月13日发表评论进入社区 5.吸烟者问题(Smoker Problem)问题描述：三个吸烟者在一间房间内，还有一个香烟供应者。为了制造并抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴。供应者有丰富的货物提供。三个吸烟者中，第一个有自己的烟草，第二个有自己的纸，第三个有自己的火柴。供应者将两样东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再放两样东西（随机地）在桌面上，然后唤醒另一个吸烟者。试为吸烟者和供应者编写程序解决问题。问题分析：k供应者seller随即产生两样东西，提供它们，这里用普通变量来表示k吸烟者进程smoker根据其排号不同，拥有不同的一件东西。假设1号吸烟者拥有烟草tobacco，2号吸烟者拥有纸paper，3号吸烟者拥有火柴match。其他号码错误返回。k吸烟者的序号代表他们拥有的东西，用他们的序号和供应者产生的两样东西比较，如果都不相等，则说明他拥有的东西和供应者产生的东西匹配，它可以吸烟。如果其中一个相等，则推出，继续排队。k mutex信号量代表一个只能进入的门，每次只有一个吸烟者可以进入进行比较和吸烟。k每个吸烟者在吸烟完毕之后出门之前要叫醒供应者，调用seller进程。The P,V code Using Pascalvar s, S1, S2, S3; semaphore;S:=1; S1:=S2:=S3:=0;fiag1,flag2,fiag3:Boolean;fiag1:=flag2:=flag3:=true;cobegin process 供应者 begin repeat P(S); 取两样香烟原料放桌上，由flagi标记； /nago1、nage2、nage3 代表烟草、纸、火柴 if flag2&flag3 then V(S1); /供纸和火柴 else if flag1&fiag3 then V(S2); /供烟草和火柴 else V(S3); /供烟草和纸 untile false; end process吸烟者1 begin repeat P(S1); 取原料； 做香烟； V(S); 吸香烟； untile false; end process吸烟者2 begin repeat P(S2); 取原料； 做香烟； V(S); 吸香烟； untile false; end process吸烟者3 begin repeat P(S3); 取原料； 做香烟； V(S); 吸香烟； untile false; endcoend 16 烟香 ) 烟做 料取 ) 者吸 烟吸 ) 烟做 料料 ) 者吸 烟烟 ) 烟做 料取 ) 者者 和烟/;) 火草烟 )( & 火纸/ 火纸、代 、 记标 由桌原两取)( 应 : =: 0= =;= 程进 者供前出之吸者吸烟和较进可个有，入进表代 队排出则相其。以，匹生者和的他则不如比东的应供们，的有表序烟回返码。 拥烟号 纸有吸， 烟烟 。件同有同排 进表量通用，供西两 析析题题程者供者。吸个醒，桌机西样放应应后吸者。烟康行烟一允子西两应。的有，纸自第烟自第者个供物的有。纸草西样烟每香并了者供一还间间吸述描 (题区" _ " % % %0 = . / " 表 "% % % 0%& % % % % ? . / " 育：来整 " "% ?. / / 者作. / 者火、草表 记 放烟两 ) 应 = : , 0= ;: ; 程进 用者供前出之烟烟个烟吸比进者烟有，入只一量 队续出推个其如以可匹生应和有他，相都较西生者号们，的们代的烟回误错他 拥烟， 纸者号 有烟 假东一有同其根 程烟表量变这它，东产 者供析析题决序者和吸试烟另后然桌）西样者，应后成烟。的康行者一允子放样将柴的自，纸自第草自第，吸供货富应。和、东三烟每烟掉了为应个，内在烟述描问烟 吧,人;) 理理顾个/ 养着顾理/ 界临/ 发理话/) 加加等; = 互进; ( 理正/ 界放/ 理客为师/) 一一候/ 互程/ 睡发理顾/ 吗客还完/ ( 0 = 子椅备/ 客的理等0 为值互于 号)0为程客塞并师客候在用 号0为程师阻用客发等来 0均初数的录用 变制 ,开就否来坐坐椅如，客时在师果理须它来客睡发在理顾没子客发等把椅把师位店发述题 (师发 _ % . ./ 论表 "% % % % % %= % % 0 _ . : 育源 " " ? _ / / / 作 . /问师 ) ) + ) ) ) + ) ) +( ) ( = _ .0 为,? 二 ) ( ) ( ) () ( ,(: 一一 子到远永出进时同现不行作动哲保处放筷将则，支两右起同需，进括包家支间家两，支着桌而圆家哲决并首 由述述问进学现实先都即平者读扩题 ) ( 复/) +0=; 新更退者入已者读禁 ) <= ) (,=/ _ ) 据据源" _ " % / 进读其，号写放/ () (互者读/ ) = _ 0,: , 读0允示0设始信 数数的者者读写用 ： 法的用可我是读醒，须续则写（者者）时同读也者个只（者行进以个先优 ) 新更写) ( ,/ _ ) ) )= ) 据数读) () = ( + ) ,=/ _ 0 : 数计 访斥互用 数共的斥者其者 法算 , 作操始作写该等作等者他，操进图一先待待而操开接时这作读试读求要题该现两要法方 类 以任。的原、实两 ( 类算的问写现量求件件读任禁进在写如）写写以程一只）件文时可读多）件条足需， ） 进区这只一间一数个区享多一：题 (者者 ) ( ; ( ；个) ( ; ) ( ) ;) ( ; ) ) ; ; ) ( ( : 0: : , 略析题步其实用。消产生者-生一，缓共, 展.) ) ) ( ( 库品物 ) ) 0 = 个个超，品可物个能，多以物库是的等数 量物数 数品，两以品品 件条析题程库的两 作 量试。组 一 费进一，另正和量 量品式式下数物 、仓，）（限，仓种、以一 北二) )( ) ( ( 库品 ( )( ) 0= , , = 个个能多 比物个超，物以品中仓的不两数品量数物数，等个拆 数品 知析题程库品两 作 量试成组个次一费进一，另正 数物式不足数品两中求，为分量其的种、装一 展扩 )( ;) ) ; 库入 库品 ) ; ) ; : ， 次多也 放次放，次一的品，一入阻被放可 不 只；被入多品，放而放析题程库的种 述操号试数 数物物：等足量种 库要大无其仓种、以可 北一扩题消产