操作系统pv操作

令p［1：n］为1到n(n1)的整数置换，设i=1，2，3，4，5，6，7；p［i］=4，7，3，2，1，5，6；描述p［i］的巡回置换算法。（巡回置换指k∈［1：n］时，k=p［...p［k］...］的置换。）p［i］=4，7，3，2，1，5，6；巡回置换算法的执行结果Beginlocalx,k;k1;whilek=7doxk;repeatprint(x);xp[x];untilx=k;kk+1;odEnd1427652765143427651514276651427765142有两个程序，A程序按顺序使用CPUl0s，使用设备甲5s，使用CPU5s，使用设备乙10s，最后使用CPUl0s。B程序按顺序使用设备甲10s，他用CPU10s，使用设备乙5s，使用CPU5s，使用设备乙10s。在顺序环境下先执行A程序再执行B程序，CPU的利用率是多少?解：根据题意，A程序的运行时间为：10+5+5+10+10＝40s，其中cpu的运行时间为：10+5+10=25s。B程序的运行时间为：10+10+5+5十10=40s，其中cpu的运行时间为；10+5＝15s。cpu的利用率为：（15+25）/（40+40）=50%设有n个进程共享一个程序段，对如下两种情况：（1)如果每次只允许一个进程进入该程序段；(2)如果每次最多允许m个进程(M＜＝n)同时进入该程序段。试问：所采用的信号量初值是否相同?信号量值的变化范围如何?所采用信号量的初值不相同。在情况(1)中，信号量的初值为1，信号量值的变化范围是l，0，-1…-(n-1)。在情况(2)中，信号量的初值为M，信号量值的变化范围是M，m-1，m-2…(m-n)。有一个售票厅只能容纳200人，当少于200人时，可以进入；否则需在外等侯。若将每一个购票者作为一个进程，请用P、v操作描写其互斥关系。设公有信号量mutex=200购票者进程：cobeginp(mutex)进入购票厅；购票；v(mutex)coend习题1.一条小河上有一座独木桥，规定每次只允许一人过桥。如果把每个过桥这看作一个进程，为保证安全，请用PV操作实现正确管理。begins:semaphore;s：=1;cobeginbeginP(s);过桥；V(s)endCoendend两个并发进程的程序如下：beginN；Integer;N:=3；cobeginPROCESSAbeginL1：N：＝N+5；gotoLlend；PROCESSBbeginL2：print(N)；N：＝0gotoL2end;coend；end；若PROCESSA先执行了三个循环后，PROCESSA和PROCESSB又并发执行了一个循环，写出可能出现的打印值。请用PV操作进行管理，使它们并发执行时不出现与时间有关的错误。[解答]若PR0CESSA先执行了三个循环后，N值变为3+5+5+5＝18；这时PROCESSA和PROCESSB并发执行了一个循环,这时可能出现的情况有以下几种：(1)print(N)；N：=0;N：＝N+5；(2)print(N)；N：＝N+5；N:=0；(3)N:=N十5；print(N);N:=0；当出现情况(1)时，出现的打印值为18;当出现情况(2)时，出现的打印值为18;当出现情况(3)时，出现的打印值为23。为了使它们并发执行时不出现与时间有关的错误，我们采用了PV操作进行管理，其管理的程序如下：begins:semaphore;N:integer;N:=3;S:=1;cobeginPROCESSAbeginL1:P(S);N:=N+5;V(S);gotoL1end;PROCESSBbeginL2：P(S)；print(N);N：＝0；V(S);gotoL2end；coend；end南京大学2000年试题桌子上有一只盘子，最多可容纳两个水果，每次只能放入或取出一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，两个儿子专等吃盘子中的橘子，两个女儿专等吃盘子中的苹果。请用PV操作来实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系。ParbeginFather:beginL1:p(empty);p(mutex);放苹果；v(mutex);v(apple);gotol1;end;Mather:beginL2:p(empty)；p(mutex);放橘子；v(mutex);v(orange);gotol2;end;Daughter:beginL3:p(apple);p(mutex);取苹果；v(mutex);v(empty);gotol3;end;L4:p(orange);p(mutex);取橘子；v(mutex);v(empty);Gotol4;end;桌上有一个空的水果盘，盘中一次只能放一个水果，服务员、男顾客和女顾客共用这个盘子。服务员向盘中放草莓和香蕉，男顾客专等吃盘中的草莓，女顾客专等吃盘中的香蕉。规定每次当盘子空时只能放一个水果供顾客食用。请用信号量机制实现服务员、男顾客和女顾客三个进程的同步。题解：盘子是三个人的公有信号量，设为mutex,初值为1，服务员的私有信号量设为empty初值为1，男顾客的私有信号量为ba，初值为0，女顾客的私有信号量为cm，初值为0。waiter:beginL1:p(empty);p(mutex);放香蕉或草莓；v(mutex);如果放香蕉则v(ba);否则v(cm);gotoL1;end;Woman:beginL3:p(cm);p(mutex);取草莓；v(mutex);v(empty);gotoL2;end;Man:beginL2:p(ba);p(mutex);取香蕉；v(mutex);v(empty);gotoL2;end;汽车司机与售票员之间必须协同工作，一方面只有售票员把车门关好了司机才能开车，因此，售票员关好车门应通知司机开车。另一方面，只有当汽车已经停下，售票员才能开门上下客，故司机停车后应通知售票员，汽车当前正在始发站停车上客，试设必要的信号灯及赋初值，写出他们的同步过程。解答：可以用两个信号量s1、s2，分别表示可以开门和可以开车，其初始值都为0，用PV操作实现为：司机售票员正常行车售票到站停车P(S1)V(S1)开车门P(S2)关车门启动开车V(S2)和尚挑水问题：寺庙里有多个小、老和尚，一水缸。小和尚取水，老和尚饮水。水缸容积10桶水，水取自同一水井，水井每次只容一个桶取水，桶总数3个，每次入、取水缸水仅为一桶。试用P、V操作描述和尚取水、饮水的互斥与同步过程。Mutex1=mutex2=1;分别代表水井和水缸Empty=10;水缸的入水量Full=0;水缸的取水量Count=3;水桶个数打水：beginp(empty)p(count)p(mutex1)从水井打水；v(mutex1)p(mutex2)往缸中放水v(mutex2)v(full)v(count)end取水：beginp(full)p(count)p(mutex2)从水缸取水v(mutex2)v(count)v(empty)end哲学家进餐问题设有5个哲学家，共享一张放有五把椅子的桌子，每人分得一把椅子。但是，桌子上总共只有5支筷子，在每人两边分开各放一支。哲学家们在肚子饥饿时才试图分两次从两边拾起筷子就餐。条件：(1)只有拿到两支筷子时，哲学家才能吃饭。(2)如果筷子已在他人手上，则该哲学家必须等待到他人吃完之后才能拿到筷子。(3)任一哲学家在自己未拿到两支筷子吃饭之前，决不放下自己手中的筷子。试:(1)描述一个保证不会出现两个邻座同时要求吃饭的通信算法。(2)描述一个既没有两邻座同时吃饭，又没有人饿死（永远拿不到筷子）的算法。(3)在什么情况下，5个哲学家全部吃不上饭？1.begin2.begin3.begin4.begin5.beginP(s1)；p(s2)；p(s3)；p(s4)；p(s5)；P(s2)；p(s3)；p(s4)；p(s5)；p(s1)；吃饭；吃饭；吃饭；吃饭；吃饭；V(s1)；v(s2)；v(s3)；v(s4)；v(s1)；V(s2)；v(s3)；v(s4)；v(s5)；v(s5)；EndendendendendPi:RepeatThinkforwhilep(mutex);p(s[i]);p(s[(i+1)mod5]);v(mutex);eatforwhile;v(s[i])v(s[(i+1)mod5]);untilfalse利用AND型信号量机制实现:semaphorechopstick[5]={1，1，1，1，1};while(true){think();Swait(chopstick[(I+1)]%5,chopstick[I]);eat();Ssignal(chopstick[(I+1)]%5,chopstick[I]);}限制人数semaphorechopstick[5]={1，1，1，1，1};semaphoremutex=4;{Repeatthink();wait(mutex);//请求进餐wait(chopstick[i]);//请求左手边的筷子wait(chopstick[(i+1)%5]);//请求右手边的筷子eat();signal(chopstick[(i+1)%5]);//释放右手边的筷子signal(chopstick[i]);//释放左手边的筷子signal(mutex);//释放信号量mutexuntilfalse}原理：规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边的筷子;而偶数号的哲学家则相反.按此规定,将是1,2号哲学家竞争1号筷子,3,4号哲学家竞争3号筷子.即五个哲学家都竞争奇数号筷子,获得后,再去竞争偶数号筷子,最后总会有一个哲学家能获得两支筷子而进餐。而申请不到的哲学家进入阻塞等待队列，根FIFO原则，则先申请的哲学家会较先可以吃饭，因此不会出现饿死的哲学家。semaphorechopstick[5]={1，1，1，1，1};voidphilosopher(inti){while(true){think();if(i%2==0)//偶数哲学家，先右后左。{wait(chopstick[i+1]mod5);wait(chopstick[i]);eat();signal(chopstick[i+1]mod5);signal(chopstick[i]);}Else//奇数哲学家，先左后右。{wait(chopstick[i]);wait(chopstick[i+1]mod5);eat();signal(chopstick[i]);signal(chopstick[i+1]mod5);}}（经典理发师问题）•假设后街有家理发店，店里有一个理发师、一把理发椅和n把等候理发的顾客椅子。（1）.如果没有顾客则理发师便在理发椅上看报纸；（2）.当有一个顾客到达时，首先查看理发师在干什么，如果在看报纸则告诉理发师理发，然后坐到理发椅上开始理发；如果理发师正在理发，则查看是否有空的椅子可坐，如果有，他就坐下等待，如果没有，则离开；（3）.理发师为一位顾客理完发后，查看是否有人等待，如有则唤醒一位为其理发，如没有则在理发椅上看报纸；（4）.顾客不分优先级•二问题分析题目中要求描述理发师和顾客的行为，因此需要两类进程Barber()和Customer()分别描述理发师和顾客的行为。当理发师看报时顾客近来需要唤醒理发师为其理发，当有顾客时理发师为其理发，没有的时候理发师看报，因此理发师和顾客之间是同步的关系，由于每次理发师只能为一个人理发，且可供等侯的椅子有限只有n个，即理发师和椅子是临界资源，所以顾客之间是互斥的关系。故引入3个信号量和一个控制变量：1)控制变量waiting用来记录等候理发的顾客数，初值均为0；2)信号量customers用来记录等候理发的顾客数，并用作阻塞理发师进程，初值为0；3)信号量barbers用来记录正在等候顾客的理发师数，并用作阻塞顾客进程，初值为0；4)信号量mutex用于互斥，初值为1三问题实现•