os经典问题(25页).doc
《os经典问题(25页).doc》由会员分享,可在线阅读,更多相关《os经典问题(25页).doc(25页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、-第二章 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
2、=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 coend2.扩展二(北大1995)设有一个可以装A、B两种物品的仓库,其容量有限(分别为N),但要求仓库中A、B两种物品的数量满足下述不等式:-MA物品数量B物品数量N其中M和N为正整数。另外,还有一个进程消费A,B,一次取一个A,B组装成C。试用信号量和PV操作描述A
3、、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)
4、; 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
5、=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;c
6、obegin 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 beginp(full); p
7、(mutex);消费一个产品; v(mutex); v(empty); endcoend2.读者一写者问题(Readers-Writers Problem)问题描述:有一个许多进程共享的数据区,这个数据区的一块空间;有一些只读取这个数据区的进程(Reader)和一程(Writer),此外还需要满足以下条件:(1)任意多个读进程可以同时读这个文件;(2)一次只有一个写进程可以往文件中写;(3)如果一个写进程正在进行操作,禁止任何读进程度文件。实验要求用信号量来实现读者写者问题的调度算法。实验类通过P()、V()两个方法实现了P、V原语的功能。实验的任务法以及Writer类的Write方法。我们需
8、要分两种情况实现该问题:读优先:要求指一个读者试图进行读操作时,如果这时正有其直接开始读操作,而不需要等待。写优先:一个读者试图进行读操作时,如果有其他写者在等写操作,他要等待该写者完成写操作后才开始读操作。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);Readc
9、ount+;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: 用于写者与其他读者/写者互斥的访问共享数据r
10、mutex: 该信号量初始值设为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(rmut
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- os 经典 问题 25
限制150内