您好,欢迎访问三一刀客
1.有一个盒子,混装了数量相等的围棋白子和黑子。现在要用自动分拣系统把白子和黑子分开。设系统有两个进程P1和P2,其中P1拣白子,P2拣黑子。当一个进程在拣子时,不允许另一进程去拣。试写出这两个并发进程能正确执行的程序。beginmutex:=1;cobeginP1:beginrepeatP(mutex);拣白子;V(mutex);untilfalseendP2:beginrepeatP(mutex);拣黑子;V(mutex);untilfalseendcoendend加上“当以一进程拣了一子时,必须让另一个进程去拣”条件:设置两个信号量S1和S2来协调进程P1和P2之间的同步。假定先让P1拣白子,则信号量S1和S2的初值分别为1和0。两个并发进程相应的程序如下:beginS1:=1;S2:=0;cobeginP1:beginrepeatP(S1);拣白子;V(S2);untilfalseendP2:beginrepeatP(S2);拣黑子;V(S1);untilfalseendcoendend2.用P、V操作实现下述问题的解。桌上有一个盘子,可以存放一个水果,父亲总是放苹果到盘子中,而母亲则总是放香蕉到盘子中;一个儿子专等吃盘中的香蕉,而一个女儿专等吃盘中的苹果。由于父亲和母亲可以同时向盘子放水果,所以盘子是临界资源,应设置一个互斥信号量mutex来实现放水果的互斥,其初值为1.此外父亲和女儿,母亲和儿子之间存在同步关系,及分别设置信号量apple和banana来分别实现这种同步关系,其初值均为0。4个进程的并发程序如下:beginmutex:=1;apple:=0;banana:=0;cobeginfather:beginrepeatP(mutex);向盘中放苹果;V(apple);untilfalse;end;mother:beginrepeatP(mutex);向盘中放香蕉;V(banana);untilfalseend;daughter:beginrepeatP(apple);取盘中的苹果;V(mutex);untilfalse;end;son:beginrepeatP(banana);取盘中的香蕉;V(mutex);untilfalse;end;coend;end;升级版桌上有一空盘,允许存放一只水果。爸爸可向盘中放苹果,可向盘中放桔子;儿子专等吃盘中的桔子,女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用,请用P、V原语实现爸爸、儿子、女儿3个并发进程的同步。beginmutex:=1;apple:=0;banana:=0;cobeginfather:beginrepeatP(mutex);将水果放入盘中;if放入的是桔子thenV(orange)elseV(apple);untilfalse;end;daughter:beginrepeatP(apple);取盘中的苹果;V(mutex);untilfalse;end;son:beginrepeatP(orange);取盘中的香蕉;V(mutex);untilfalse;end;coend;end;桌上有一只盘子,最多可容纳两个水果,每次只能放入或取出一个水果。爸爸专向盘子放苹果,妈妈专向盘子中放桔子;两个儿子专等吃盘子中的桔子,两个女儿专等吃盘子中的苹果。请用P、V操作来实现爸爸、妈妈、儿子和女儿之间的同步与互斥关系。与上一例不同的是,现在盘子可以放入两个水果,因此除了互斥信号量mutex之外,还应对允许向盘中放入水果的个数进行计数,即再设置一个信号量empty,其初值为2.此外由于盘子中可以放两个水果,即当盘中有一个水果时,存在着既可以放有可以取得情况,因此,除了对放水果进行互斥外,对取水果也应进行互斥。此时,4个进程的并发程序如下:beginmutex:=1;empty:=2;apple:=0;orange:=0;cobeginfather:beginrepeatP(empty);P(mutex);向盘中放苹果;V(mutex);V(apple);untilfalseendmother:beginrepeatP(empty);P(mutex);向盘中放桔子;V(mutex);V(orange);untilfalseenddaughteri(i=1,2;):beginrepeatP(apple);P(mutex);取盘中苹果;V(mutex);V(empty);untilfalseendsoni(i=1,2):beginrepeatP(orange);P(mutex);取盘中桔子;V(mutex);V(empty);untilfalseendcoendend;3.有一个理发师,一把理发椅和n-1把供等候理发的顾客坐的椅子。(1)如果没有顾客,则理发师便在理发椅子上睡觉;(2)当一个顾客到来时,必须唤醒理发师进行理发;(3)如果理发师正在理发时又有顾客来到,则如果有空椅子可坐,他就坐下来等,如果没有空椅子,他就离开。为理发师和顾客各编写一段程序描述他们的行为,要求不能带有竞争条件。本题可看作是n个生产者和一个消费者问题。顾客作为生产者,每到来一个就使计数器rc加1,以便让理发师理发(消费)至最后一个顾客(产品)。并且,第一个到来的顾客应负责唤醒理发师;如果不是第一个到达的顾客,则在有空椅子的情况下坐下等待,否则离开理发厅(该信息可由计数器rc获得)。理发师与顾客的并发程序描述如下:beignmutex:=1;wakeup:=0;wait:=n;cobegincustomeri(i=1;…):beginP(mutex);rc=rc+1;if(rc=1)thenV(wakeup)elseifrc≤nthenP(wait)/*顾客人数≤n时在椅子上等待*/elsebeginrc:=rc-1;/*是第n+1个顾客时则离开理发厅*/该顾客离开end;V(mutex)end;barber:beginP(wakeup);/*没有顾客时,理发师睡觉(阻塞),直到第一个顾客来时唤醒*/repeat理发;P(mutex);rc:=rc-1;if(rc≠0)thenV(wait);/*让等待中的一个顾客准备理发*/V(mutex)untilrc=0/*理发重复到没有顾客为止*/endconend;end;扩展版:一个理发店由一个有N个沙发的等候室和一个放有一张理发椅的理发室组成。没有顾客要理发时,理发师便去睡觉。当一个顾客走进理发店时,如果所有的沙发都已被占用,他便离开理发店;否则,如果理发师正在为其他顾客理发,则该顾客就找一张空沙发坐下等待;如果理发师因无顾客正在睡觉,则由新到的顾客唤醒理发师为其理发。在理发完成后,顾客必须付费,直到理发师收费后才能离开理发店。试用信号量实现这一同步问题。本题中,顾客进程和理发师进程之间存在着多种同步关系:(1)只有在理发椅空闲时,顾客才能坐到理发椅上等待理发师理发,否则顾客必须等待;只有当理发椅上有顾客时,理发师才可以开始理发,否则他也必须等待。这种同步关系类似于单缓冲(对应于理发椅)的生产者-消费者问题中的同步关系,故可通过信号量empty和full来控制。(2)理发师为顾客理发时,顾客必须等待理发的完成,并在理发完成后由理发师唤醒他,这可单独使用一个信号量cut来控制。(3)顾客理完发后必须向理发师付费,并等理发师收费后顾客才能离开;而理发师则必须等待顾客付费,并在收费后唤醒顾客以允许他离开,这可分别通过两个信号量payment和receipt来控制。(4)等候室中的N张沙发是顾客进程竞争的资源,故还需为他们设置一个信号量sofa。(5)为了控制顾客的人数,使顾客能在所有的沙发都被占用时离开理发店,还必须设置一个整型变量count来对理发店中的顾客进行计数,该变量将被多个顾客进程互斥地访问并修改,这可通过一个互斥信号量mutex来实现。为了解决上述问题,需设置一个整型变量count用来对理发店中的顾客进行计数,并需设置7个信号量,其中:mutex用来实现顾客进程对count变量的互斥访问,其初值为1;sofa是对应于等候室中N张沙发的资源信号量,其初值为N;empty表示有是否空闲的理发椅,其初值为1;full表示理发椅上是否坐有等待理发的顾客,其初值为0;cut用来等待理发的完成,其初值为0;payment用来等待付费,其初值为0;receipt用来等待收费,其初值为0。具体算法描述如下:Varcount:integer:=0;mutex,sofaempty,full:semaphore:=1,N,1,0;cut,pament,receipt:semaphore:=0,0,0;beiginparbeginguest:beginwait(mutex);if(countN)thenbeginsignal(mutex);exitshop;endelsebegincount:=count+1;if(count1)thenbeginwait(sofa);sitonsofa;wait(empty);getupfromsofa;signal(sofa)endelse/*count=1*/wait(empty);sitonthebaber_chair;signal(full);wait(cut);pay;signal(payment);wait(receipt);getupfromthebaber_chair;signal(empty);wait(mutex);count:=count–1;signal(mutex);exitshop;endendbaber:beginrepeatwait(full);cuthair;signal(cut);wait(payment);acceptpayment;signal(receipt);untilfalse;endparendend4.设有P1,P2,P3进程共享某一文件F,P1对F只读不写,P2对F只写不读,P3对F先读后写。当一个进程写F时,其他进程对F不能进行读写,但多个进程同时读F是允许的。试用P、V实现P1,P2,P3的同步与互斥。beginrmutex:=1;wmutex:=1;count:=0;cobeginP1:beginrepeatP(rmutex);count:=count+1;ifcount=1thenP(mutex);V(rmutex);读文件F;P(rmutex);count:=count–1;ifcount=0thenV(wmutex);V(rmutex)untilfalseend;P2:beginrepeatP(wmutex);写文件F;V(wmutex);untilfalseend;P3beginrepeatP(rmutex);count:=count+1;ifcount=1thenP(wmutex);V(rmutex);读文件F;P(rmutex);count:=count–1;ifcount=0thenV(wmutex);V(rmutex);P(wmutex);写文件F;V(wmutex);untilfalseend;coendend5.吸烟者问题:假设系统有3个吸烟者(smoker)进程和1个供货商进程(Agent)进程。每个吸烟者连续不断地制造香烟并吸掉它。但是,制造一支香烟需要3种材料—烟、纸、火柴。一个吸烟者进程有纸,另一个有烟,第三个有火柴。供货商进程可以无限地提供这三种材料。供货商将两种材料一起放在桌子上,持有另一种材料的吸烟者即可制造一支香烟并吸掉它。当此吸烟者抽香烟时,他发出一个信号通知供货商进程,供货商马上给出另外两种材料,如此循环往复。试编写一个程序使供货商与吸烟者同步执行。beginsale:=1;S1:=0;S2:=0;S3:=0;a:=1;cobeginAgent:beginrepeatP(sale);ifa=1thenbegin将烟和火柴放在桌子上;V(S1)end;ifa=2thenbegin将纸和火柴放在桌子上
本文标题:典型问题
链接地址:https://www.111doc.com/doc-4592487 .html