进程同步习题全.pptx
《进程同步习题全.pptx》由会员分享,可在线阅读,更多相关《进程同步习题全.pptx(95页珍藏版)》请在咨信网上搜索。
1、进程管理进程管理设有设有n n个进程共享一个程序段,对如下两种情况:个进程共享一个程序段,对如下两种情况:(1)1)如果每次只允许一个进程进入该程序段;如果每次只允许一个进程进入该程序段;(2)(2)如果每次最多允许如果每次最多允许m m个进程个进程(M(Mn)n)同时进入该同时进入该程序段。程序段。试问:所采用的信号量初值是否相同试问:所采用的信号量初值是否相同?信号量值的变信号量值的变化范围如何化范围如何?所采用信号量的初值不相同。所采用信号量的初值不相同。在情况在情况(1)(1)中,信号量的初值为中,信号量的初值为1 1,信号量值的变化范围是信号量值的变化范围是l l,0 0,-1-1-
2、(n-1)-(n-1)。在情况在情况(2)(2)中,信号量的初值为中,信号量的初值为M M,信号量值的变化范围是信号量值的变化范围是M M,m-1m-1,m-2m-2(m-n)(m-n)。进程同步习题进程同步习题进程管理进程管理【例】一个buffer,一个生产者,一个消费者,生产者只生产一个东西,消费者只进行一次消费,即:生产者只进行一次putdata操作,消费者只进行一次getdata操作。进程管理进程管理【解答】设置信号量full,表示buffer是否有数据,初值为0生产者消费者putdataP(full)V(full)getdata进程管理进程管理【例】一个buffer,一个生产者,一个
3、消费者,生产者不断进行putdata操作,消费者不断进行getdata操作,即生产者不断生产,消费者不断消费。【解答】buffer为空时,才能进行putdata操作,只有buffer有数据时,才能进行getdata操作信号量full:是否有数据初值为0empty:是否为空,初值为1进程管理进程管理生产者:repeatP(empty)putdataV(full)消费者:repeat P(full)getdata V(empty)进程管理进程管理【例】一个buffer,多个生产者,多个消费者,多个生产者和消费者都在不断地存取buffer,即生产者不断地进行putdata操作,消费者不断进行getd
4、ata操作。【解答】只有buffer为空时能进行putdata操作,只有buffer有数据时能进行putdata操作。不允许多个进程同时操作buffer,即不允许多个消费者同时进行getdata,不允许多个生产者进行putdata操作信号量full:buffer是否有数据,初值为0empty:buffer是否为空,初值为1mutex:buffer是否可操作,初值为1进程管理进程管理生产者irepeatP(empty)P(mutex)putdataV(mutex)V(full)消费者irepeat P(full)P(mutex)getdata V(mutex)V(empty)进程管理进程管理【例
5、】多个生产者,多个消费者,N个buffer,多次循环存取buffer,即多个生产者不断进行putdata操作,多个消费者不断进行getdata操作【解答】只有buffer有空间时才能进行putdata操作只有buffer有数据时才能进行getdata操作不允许多个消费者和多个生产者同时操作信号量full:表示buffer是否有数据,初值为0empty:表示buffer是否为空,初值为nmutex:表示buffer是否可操作,初值为1进程管理进程管理生产者irepeatP(empty)P(mutex)putdataV(mutex)V(full)消费者j repeat P(full)P(mutex
6、)putdata V(mutex)V(empty)进程管理进程管理【改进】putdata和getdata操作都在临界区中,因此多个进程对多个buffer的操作不能并行进行的,进程间并行操作的程度很低。实际上只要保证多个进程同时操作不同buffer就可以实现对整个buffer的并行操作。getEBuffer()返回空的buffer号getEBuffer()return(pbuffer+1)modngetDBuffer()返回有数据的buffer号getDBuffer()return(pdata+1)modn进程管理进程管理semaphoremutex,empty,full=1,n,0intege
7、rpbuff,pdata=0,0生产者i消费者jrepeatrepeatP(empty)P(full)P(mutex)P(mutex)in=getEBuffer()out=getDBuffer()V(mutex)V(mutex)putdata(in)getdata(out)V(full)V(empty)进程管理进程管理【练习】如图,有多个PUT操作同时向Buff1放数据,有一个MOVE操作不断地将Buff1的数据移到Buff2,有多个GET操作不断地从Buff2中将数据取走。Buff1的容量是m,Buff2的容量是n,PUT,MOVE,GET每次操作一个数据,在操作的过程中要保证数据不丢失。试
8、用P,V原语协调PUT,MOVE操作,并说明每个信号量的含义和初值。进程管理进程管理Buff1Buff2MOVEPUTGET进程管理进程管理【解答】三类进程:多个PUT类进程,一个MOVE类进程,多个GET类进程操作规则1只有buff1有空间才能进行PUT操作2只有buff1有数据,buff2有空间才能进行MOVE操作3只有buff2有数据才能进行GET操作4不允许多个进程同时操作buff15不允许多个进程同时操作buff2进程管理进程管理操作流程repeat判断buff1是否有空间,没有则等待是否可操作buff1PUT设置buff1可操作标志设置buff1有数据的标志untilfalse进程
9、管理进程管理repeat判断buff1是否有数据,没有则等待判断buff2是否有空间,没有则等待是否可操作buff1是否可操作buff2MOVE设置buff1可操作标志设置buff2可操作标志设置buff1有空间标志设置buff2有空间标志进程管理进程管理repeat判断buff2是否有数据,没有则等待是否可操作buff2GET设置buff1可操作标志设置buff1有空间标志进程管理进程管理4信号量设置6个信号量full1:buff1是否有数据,初值为0empty1:buff1有空间,初值为mmutex1:buff1是否可操作,初值为1full2:buff2是否有数据,初值为0empty2:b
10、uff2有空间,初值为nmutex2:buff2是否可操作,初值为1进程管理进程管理5PV操作实现repeatp(empty1);/判断buff1是否有空间,没有则等待p(mutex1);/是否可操作buff1PUT;v(mutex1);/设置buff1可操作标志v(full);/设置buff1有数据标志进程管理进程管理repeatP(full1);判断buff1是否有数据,没有则等待P(empty2);/判断buff2是否有空间,没有则等待P(mutex1);/是否可操作buff1P(mutex2);/是否可操作buff2MOVE;V(mutex1);/设置buff1可操作标志V(mutex
11、2);/设置buff2可操作标志V(empty1);/设置buff1有空间标志V(full2);/设置buff2有数据标志进程管理进程管理repeatP(empty2);/判断buff2是否有空间,没有则等待P(mutex2);/是否可操作buff2GETV(mutex2);/设置buff2可操作标记V(full2);/设置buff2有数据标记进程管理进程管理【例】现有4个进程R1,R2,W1,W2。它们共享可以存放一个数据的缓冲器B。进程R1每次把磁盘上读出的一个数据存到缓冲器B中,供进程W1打印输出;进程R2每次从键盘上读一个数据存放到缓冲器B,供W2打印输出。当一个进程把数据存放到缓冲器
12、后,在该数据还没有打印输出之前不准任何进程再想缓冲器中存数据。当一个进程已把缓冲器中的数据打印输出后,在缓冲器中还没有存如新数据之前不准任何进程再从缓冲器中取数打印。问怎样用PV操作使这4个进程并发执行时能相互协作地工作?进程管理进程管理R1R2W1W2进程管理进程管理【解答】4个进程互斥,R1,W1同步,R2,W2同步mutex:表示能否把数据存如缓冲器,初始化时缓冲器为空,故初值为1S1:进程R1是否已向缓冲器存入一个数据,初值为0S2:进程R2是否已向缓冲器存入一个数据,初值为0进程管理进程管理beginmutex,s1,s2:semaphore;s:=1;s2:=0;s2:=0;cob
13、eginprocessR1beginL1:从磁盘上读数据送x1;P(mutex);B:=x1;V(s1);gotoL1end;processW1beginL3:P(s1);y:=B;V(mutex);打印ygotoL3end;进程管理进程管理processR2beginL2:从键盘上读数据送x2;P(mutex);B:=x2;V(s2);gotoL2end;processW2beginL4:P(s2);z:=B;V(mutex);打印z;gotoL4end;进程管理进程管理【例】假定有3个进程R,W1,W2共享一个缓冲器,而B中每次只能存放一个数,当缓冲器中无数时,进程R可将M输入设备上读入的
14、数存放到缓存器B中,若存放到缓存器中的是奇数,则允许进程W1将其取出打印;若存放到缓冲器中的是偶数,则允许进程W2将取出打印。同时规定:进程R必须等缓冲器中的数被取出打印后才能再存放一个数;进程W1或W2对每次存入缓冲器中的数只能打印一次;W1和W2都不能从空的缓冲器中取数。写出这3个并发进程能正确工作的程序。进程管理进程管理【分析】把进程R看作是生产者,把进程W1和W2看作是消费者。现在有一个生产者(进程R)能生产不同的产品(读入奇数或偶数),把生产的产品存放在缓冲器B中,供不同的消费者(进程W1和进程W2)取用。可以看出,当进程R读入的是整数,则要把有奇数的消息发送给进程W1;当进程R读入
15、的是偶数,则要把有偶数的消息发送给W2,在进程W1或进程W2从缓冲器中取出数后,应把缓冲器中又可有一个数的消息告诉进程R,于是,可以定义如下3个信号量:S表示是否可以把数存入缓冲器,由于缓冲器中每次只能放一个数,所以其初值取为”1“SO:表示缓冲器中是否有奇数,初值为”0“,表示无奇数SE:表示缓冲器是否偶数,初值为0,表示无偶数进程管理进程管理【解答】integerB;semaphoreS,SO,SESO=0;SE=0:integerxL1:从输入设备读入一个数X=读入的数P(S);B=Xif(B=偶数)V(SO)elseV(SE)gotoL1进程管理进程管理进程管理进程管理【例】设有一个具
16、有N个信息元素的环形缓冲区,A进程顺序地把信息写入缓冲区,B进程依次从缓冲区读出信息。回答下列问题:1叙述A,B两进程的相互制约关系2判别下列用PV操作表示的同步算法是否正确?如不正确,试说明理由,并修改成正确的算法。设置信号量初值:S10,S2N;设置变量初值:in=out=0;进程管理进程管理【例】进程P1使用缓冲区buffer向进程P2,P3,P4发送消息,要求每当P1向buffer中发消息时,只有当P2,P3,P4进程都读取这条消息后才可再向buffer中发送消息。利用PV原语描述进程的动作序列P1bufferP2P3P4进程管理进程管理【解答】设置信号量初值S1=S2=S3=0,S=
17、3进程P1进程P2进程P3进程P4P(S)P(S1)P(S2)P(S3)P(S)读消息读消息读消息P(S)V(S)V(S)V(S)发送消息到BufferV(S1)V(S2)V(S3)进程管理进程管理【例】设A,B为两个并发进程,它们共享一个临界区,其执行临界区的算法框图如下。试判断该算法是否有错?请说明理由。如果有错,请改正。S1,S2的初值为0,CSA,CSB为临界区。CSAV(S1)P(S2)A进程P(S1)CSBV(S2)B进程进程管理进程管理【分析】系统启动时,S1,S2为0,则B执行P(S1)被阻塞,而A进程可直接访问临界资源。故A,B两个并发进程不可能同时操作临界资源,该算法是可以
18、保证互斥的。按题目要求,两个进程对临界资源的操作是没有先后顺序的,但是,在上面的实现中,只有A进程先操作完资源后,B资源才能操作。进程管理进程管理【解答】该算法错误若A进程用不要求访问临界资源,则不会折行V(S1),意味着B进程的申请永远得不到操作临界资源的机会;同理,若B不要求访问临界资源,则不会执行V(S2),意味着进程A下次也得不到操作临界资源的机会。所以,问题在于本应该互斥控制而使用的却是同步控制。实现改正:进程管理进程管理信号量mutex=1A进程B进程repeatrepeatP(mutex);P(mutex);CSA;CSB;V(mutex);V(mutex);进程管理进程管理【例
19、】当进程X和进程Y共享某个资源r,进程并发执行时的程序如下:semaphore=1ProcessXProcessYL1:P(S)L2:P(S)使用资源r使用资源rV(S)V(S)gotoL1gotoL2进程管理进程管理请回答:1两个进程并发执行时,能否保证互斥使用资源?为什么?2若要使两个进程交替使用资源,仍使用PV操作来进行管理,写出应定义的信号量机器初值3修改上述程序,使两个进程能交替使用资源r进程管理进程管理【解答】1能保证互斥使用资源。因为在两个进程中,“使用资源r”都是作为临界区,由P(S)和V(S)操作保证互斥执行,S的初值定义为1,符合要求。2要使两个进程交替使用资源,仅仅保证互
20、斥使用是不够的,必须要两个进程相互等待互相通知。为此,必须定义新的信号量。定义两个私有信号量S1和S2。假定进程X先使用资源,那么进程X的私有信号量S1的初值定义为1,进程Y的私有信号量S2的初值为0.轮流使用可以保证互斥,因此信号量S可以不要。进程管理进程管理3两个进程可以改为semaphoreS1=1semaphoreS2=0ProcessXProcessYL1:P(s1)L2:P(S2)使用资源r使用资源rV(S2)V(S1)gotoL1gotoL2进程管理进程管理【例】桌上有一空盘,只允许存放一个水果。爸爸可向盘中放苹果,也可向盘中放橘子。儿子专等吃盘中的橘子,女儿专等吃盘中的苹果。规
21、定当盘中空时一次只能放一只水果供吃者取用,请用PV原语实现爸爸,儿子,女儿三个并发进程的同步进程管理进程管理【解答】信号量mutex:盘子是否为空信号量So:盘中是否有橘子信号量Sa:盘中是否有苹果Sempahoremutex=1,So=0,Sa=0进程管理进程管理fatherP(mutex);将水果放入盘中if(放入的是橘子)V(So)elseV(Sa)儿子 P(So);从盘中取橘子 V(mutex)吃橘子女儿 P(Sa);从盘中取苹果 V(mutex)吃苹果进程管理进程管理读者写者介绍读者写者介绍读者写者(readerwriter),共享文件要求:1允许多个读者同时对文件执行读操作2只允许
22、一个写者对文件执行写操作3任何写者在完成写操作前不允许其他读者或写者工作4写者在执行写操作前,应让已有的写者和读者全部退出进程管理进程管理单纯使用信号量不能解决问题,引入计数器readcount对读进程计算,mutex是用于对计数器readcount操作的互斥信号量,writeblock表示是否允许写的信号量进程管理进程管理intreadcount=0semaphorewriteblock,mutex;writeblock=1;mutex=1进程管理进程管理读者iP(mutex)readcount+if(readcount=1)P(writeblock)V(mutex)读文件P(mutex);
23、readcountif(readcount=0)V(writeblock)V(mutex)写者j P(writeblock)写文件 V(writeblock)进程管理进程管理进程同步习题进程同步习题1.1.一条小河上有一座独木桥,规定每次只允许一一条小河上有一座独木桥,规定每次只允许一人过桥。如果把每个过桥这看作一个进程,为人过桥。如果把每个过桥这看作一个进程,为保证安全,请用信号量操作实现正确管理。保证安全,请用信号量操作实现正确管理。进程管理进程管理进程同步习题进程同步习题begins:semaphore;s:=1;cobeginbeginwait(s);过桥;signal(s);endC
24、oendend进程管理进程管理v桌子上有一只盘子,最多可容纳两个水果,每次桌子上有一只盘子,最多可容纳两个水果,每次只能放入或取出一个水果。爸爸专向盘子中放苹只能放入或取出一个水果。爸爸专向盘子中放苹果,妈妈专向盘子中放橘子,两个儿子专等吃盘果,妈妈专向盘子中放橘子,两个儿子专等吃盘子中的橘子,两个女儿专等吃盘子中的苹果。请子中的橘子,两个女儿专等吃盘子中的苹果。请用信号量操作来实现爸爸、妈妈、儿子、女儿之用信号量操作来实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系。间的同步与互斥关系。进程管理进程管理ParbeginFather:begin L1:p(empty);p(mutex);放苹果;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 进程 同步 习题
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【快乐****生活】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【快乐****生活】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。