操作系统同步互斥练习题

1、操作系统同步试题1、设公共汽车上，司机和售票员的活动分别是：司机的活动：启动车辆；正常行车；到站停车；售票员的活动：关车门；售票；开车门；在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用P、V操作实现它们的同步。设两个信号量S和C,初值为S=0;C=0;司机：L1:正常行车售票员：L2:售票到站停车P(S)V(S)开车门P(C)关车门启动开车V(C)GOTOL1GOTOL22、桌子上有一个空盘子，允许存放一只水果，爸爸可以向盘中放苹果，妈妈向盘子中放橘子，女儿专门吃盘子中的苹果，儿子专门吃盘子中的橘子。规定当盘子空的时候一次只能放一只水果，请用信号量实现他们之间的同步与互斥。S

2、,S1,S2:semaphore=1,0,0;Cobegin:ProcessFather:Begin:L1:P(S);PutApple;V(S1);GOTOL1；End;ProcessMother:Begin:L2:P(S);PutOrange;V(S2)GOTOL2EndProcessSon:Begin:L3:P(S2);GetOrange;V(S);GOTOL1;End;ProcessDaughter:Begin:L4:P(S1);GetApple;V(S)GOTOL4EndCoEnd;2、写者优先的“读者一一写者”问题：1)共享读2)互斥写、读写互斥3)写者优先于读者(一旦有写者，则后续

3、读者必须等待，唤醒时优先考虑写者)wmutex:semaphore=1S:semaphore=1/读者与写者之间、写者与写者之间互斥使用共享数据/当至少有一个写者准备访问共享数据时，它可使后续的读者等待写完成S2：semaphoa1/阻塞第二个以后的等待读者readcount,writecount:semaphore=0,0;当前读者数量、写者数量mutex1:semaphore=1多个读者互斥使用readcountmutex2:semaphore=1多个写者互斥使用writecountCobegin:Reader:beginRepeatWait(S2)；wait(S);wait(mutex1

4、)ifreadcount=0thenwait(wmutex);readcount+;signal(mutex1);signal(S);signal(S2)；readingwait(mutex1);readcount-;ifreadcount=0thensignal(wmutex);signal(mutex1);untilfalse;begin;writer:beginrepeat;wait(mutex2);ifwritecount=0thenwait(S);writecount+;signal(mutex2);wait(wmutex);writingsignal(wmutex);wait(mu

5、tex2);writecount-;ifwritecount=0thensignal(S);signal(mutex2);untilfalse;end;coend;4、有一个仓库，可以存放A、B两种产品，但要求：每次只能存入一种产品(A或B);A产品数量一B产品数量M;B产品数量一A产品数量N;其中M、N是正整数，使用P、V操作描述产品A与产品B的入库过程Mutex,Sa,Sb:Semaphore;Mutex=1;Sa=M-1;Sb=N-1;CoBegin:ProcessPA:BeginLoop:P(Sa);P(Mutex);产品A入库；V(Mutex);V(Sb);GotoLoop;End;

6、ProcessPB:BeginLoop:P(Sb);P(Mutex);产品B入库；V(Mutex);V(Sa);GotoLoop;End;CoEnd;5、进程A1、A2、An1通过m个缓冲区向进程B1、B2Bn2不断地发送消息。发送和接收工作遵循如下规则：(1)每个发送进程一次发送一个消息，写入一个缓冲区，缓冲区大小等于消息长度；(2)对每一个消息，B1,B2,，Bn都必须接收一次，读入各自的数据区内；(3) m个缓冲区都满时，发送进程等待；没有可读的消息时，接收进程等待。解答：本题是生产者一一消费者问题的一个变形，一组生产者A1,A2,.An1和一组消费者B1,B2,Bn2公用m个缓冲区，每

7、个缓冲区只要写一次，但需要读n2次，因此，我们可以把这一组缓冲区看成n2组缓冲区，每个发送者需要同时写n2组缓冲区，而每一个接收者只需读它自己对应的那组缓冲区中的对应单元。Mutex,emptyn2,fulln2:semaphore;Mutex=1;/多进程互斥使用缓冲区empty0,1,n2=m,m,m;full0,1,.n2=0,0,0;intI;Cobegin:ProcessAiBegin:Loop:IntI;For(I=0;I<n2;I+)P(emptyI);P(Mutex);将消息放入缓冲区；v(Mutex);for(I=0;I<n2;I+)v(fullI);GotoLo

8、op;End;ProcessBiBegin:Loop:P(fullI);P(Mutex);从消息缓冲区取出消息；v(Mutex);v(emptyI);GotoLoop;End;CoEnd;6、理发师问题：一个理发店有N张沙发和一张理发椅，没有顾客要理发时，理发师便去睡觉；当一个顾客走进理发店时，如果所有的沙发都已被占用，他便离开理发店；否则，如果理发师正在为其他顾客理发，则该顾客就找一张空沙发坐下等待；如果理发师因无顾客正在睡觉，则由新到的顾客唤醒理发师为其理发。在理发完成后，顾客必须付费，直到理发师收费后才能离开理发店。使用信号量实现这一同步问题。解答：为解决上述问题，需要设置一个整形变量c

9、ount用来对理发店中的顾客进行计数，再设置7个信号量：mutex用来实现顾客进程对count变量的互斥访问，其初值为1;sofa是对应于等候室中N张沙发的资源信号量，其初值为N；empty表示是否有空闲的理发椅，其初值为1;full表示理发椅上是否坐有等待理发的顾客，其初值为0;cut用来等待理发的完成，其初值为0;payment用来等待付费，其初值为0;receipt用来等待收费，其初值为0。Intcount=0;Mutex,sofa,empty,full,cut,payment,receipt:semaphore=1,N,1,0,0,0,0;CoBegin:ProcessGuest:Be

10、gin:P(mutex);If(count>N)thenv(mutex);exitshop;elsecount+;if(count>1)thenp(sofa);sitonsofa;p(empty);getupfromsofa;v(sofa);else/count=1p(empty);sitonthebaber_chair;v(full);p(cut);pay；v(payment);p(receipt);getupfromthebaber_chair;v(empty);p(mutex)count-;v(mutex);exitshop;End;ProcessBarber:BeginLo

11、op:P(full);Cuthair;V(cut);P(payment);Acceptpayment;V(receipt);GotoLoop;CoEnd;7、一个海底隧道中只有一个车道，规定同一个方向的可以连续过隧道；某方向有列车过隧道时，另一个方向的列车就要等待，现在东岸和西岸都有列车要过隧道，如果把每个过隧道的列车看作一个进程，为保证安全，使用P、V操作实现正确管理。8、如果系统中有N个进程，?运行进程最多几个，最少几个？?就绪进程最多几个，最少几个？?等待进程最多几个，最少几个？解答：运行进程最多1个，最少0个；就绪进程最多N-1个，最少0个；等待进程最多N个，最少0个；9、教材作业第2

12、5题：(1)具有忙等待的关锁和开锁原语：Lock(W):WhileW=1DoNoOperation;W=1;Unlock(W):W=0;(2)不会忙等待的关锁和开锁原语：Lock(W):W+;Block();Wakeup();IfW>1ThenUnlock(W):W-;IfW>=1Then10、教材作业第28题：第一种解法：S1,S2:Semaphore=0,0;Main()Cobegin:Collection();Computer();Collection()L1:CollectMesg;PutMesgIntoBuffer;V(S1);P(S2);GotoL1;Computer(

13、)L2:P(S1);GetMesg;V(S2);Computing;GotoL2;第二种解法：S1,S2:Semaphore=0,1;Main()Cobegin:Collection();Computer();Collection()L1:CollectMesg;P(S2);PutMesgIntoBuffer;V(S1);GotoL1;)Computer。L2:P(S1);GetMesg;V(S2);Computing;GotoL2;)11、信号量的PV操作是如何定义的？t搦兑明信号量的PV操作的物理意义。参考答案：P(S):将信号量S减1,若结果大于或等于0,则该进程继续执行；若结果小于0,

14、则该进程被阻塞，并将其插入到该信号量的等待队列中，然后转去调度另一进程。V(S):将信号量S加1,若结果大于0,则该进程继续执行；若结果小于或等于0,则从该信号量的等待队列中移出一个进程，使其从阻塞状态变为就绪状态，并插入到就绪队列中，然后返回当前进程继续执行。PV操作的物理含义：信号量S值的大小表示某类资源的数量。当S>0时，其值表示当前可供分配的资源数目；当S<0时，其绝对值表示S信号量的等待队列中的进程数目。每执行一次P操作，S值减1,表示请求分配一个资源，若S>0,表示可以为进程分配资源，即允许进程进入其临界区；若S<0,表示已没有资源可供分配，申请资源的进程被

15、阻塞，并插入S的等待队列中，S的绝对值表示等待队列中进程的数目，此时CPU将重新进行调度。每执行一次V操作，S值加1,表示释放一个资源，若S>0,表示等待队列为空；若SW0,则表示等待队列中有因申请不到相应资源而被阻塞的进程，于是唤醒其中一个进程，并将其插入就绪队列。无论以上哪种情况，执行V操作的进程都可继续运行。12、假设有三个并发进程P,Q,R,其中P负责从输入设备上读入信息并传送给Q,Q将信息加工后传送给R,R则负责将信息打印输出。写出下列条件的并发程序：(1)进程P、Q共享一个缓冲区，进程Q、R共享另一个缓冲区。(2)进程P、Q共享一个由m个缓冲区组成的缓冲池，进程Q、R共享另一

16、个由n个缓冲区组成的缓冲池。参考答案：(1)第一步：确定进程3个进程P、Q、RP进程：从输入设备上读入信息将信息放入缓冲区1Q进程：从缓冲区1取出信息将信息放入缓冲区2中R进程：从缓冲区2取出信息将信息打印输出第二步：确定进程的同步、互斥关系步步步步日同同同同口P当缓存区1无数据时，才可以向缓冲区1写入信息Q当缓存区1有数据时，才可以从缓冲区1读取信息Q当缓存区2无数据时，才可以向缓冲区2写入信息R当缓存区2有数据时，才可以从缓冲区2读取信息弟一少'：坟白/I口可厘缓存区1无数据，empty1,初值1缓存区1有数据，full1,初值0缓存区2无数据，empty2,初值1缓存区2有数据，

17、full2,初值0第四步：用伪代码描述beginempty1,empty2,full1,full2:semaphore;empty1:=1;empty2:=1;full1:=0;full2:=0;cobeginP();Q();R();coend;end;processP()beginL1:从输入设备上读入信息P(empty1);将信息放入缓冲区1;V (full1);gotoL1end;processQ()beginL2:P(full1);从缓冲区1取出信息；V (empty1);P(empty2);将信息放入缓冲区2;V (full2);gotoL2end;processR()beginL3

18、:P(full2);从缓冲区2取出信息V (empty2);将信息打印输出；V otoL3;end;2)第一步：确定进程3个进程P、Q、RP进程：从输入设备上读入信息将信息放入缓冲池1中的一个空缓冲区中Q进程：从缓冲池1中的一个非空缓冲区中取出信息将信息放入缓冲池2中的一个空缓冲区中R进程：从缓冲池2中的一个非空缓冲区中取出信息将信息打印输出第二步：确定进程的同步、互斥关系同步：P当缓冲池1中有空的缓冲区时，才可以向缓冲池1写入信息同步：Q当缓冲池1中有非空的缓冲区时，才可以从缓冲池1读取信息同步：Q当缓冲池2中有空的缓冲区时，才可以向缓冲池2写入信息同步：R当缓冲池2中有非空的缓冲区时，才可

19、以从缓冲池2读取信息第三步：设置信号量缓冲池1中的空缓冲区的数量，empty1,初值m缓冲池1中的非空缓冲区的数量，full1,初值0缓冲池2中的空缓冲区的数量，empty2,初值n缓冲池2中的非空缓冲区的数量，full2,初值0第四步：用伪代码描述beginempty1,empty2,full1,full2:semaphore;empty1:=m;empty2:=n;full1:=0;full2:=0;cobeginP();Q();R();coend;end;processP()beginL1:从输入设备上读入信息；P(emptyl);将信息放入缓冲池1中的一个空缓冲区中；V (fulll)

20、;gotoL1end;processQ()beginL2:P(full1);从缓冲池1中的一个非空缓冲区中取出信息；V (empty1);P(empty2);将信息放入缓冲池2中的一个空缓冲区中；V (full2);gotoL2end;processR()beginL3:P(full2);从缓冲池2中的一个非空缓冲区中取出信息；V (empty2);将信息打印输出；V otoL3;end;13、有四个并发进程：R1,R2,W1和W2,它们共享可以存放一个数的缓冲区。进程R1每次从磁盘读入一个数存放到缓冲区中，供进程W1打印输出；进程R2每次从键盘读一个数存放到缓冲区中，供进程W2打印输出。当缓

21、冲区满时，不允许再向缓冲区中存放数据；当缓冲区空时，不允许再从缓冲区中取出数据打印输出。试用PV操作实现四个进程的协调运行。参考答案：第一步：确定进程4个进程R1、R2、W1、W2R1进程：从磁盘上读入一个数将数存放到缓冲区中W1进程:将R1进程放进缓冲区中的数取出打印输出R2进程：从键盘读入一个数将数存放到缓冲区中W2进程：将R2进程放进缓冲区中的数取出打印输出第二步：确定进程的同步、互斥关系步步步步日同同同同口R1当缓存区无数据时，才可以向缓冲区写入数据R2当缓存区无数据时，才可以向缓冲区写入数据W1当缓存区中是R1写的数据时，才可以将数据从缓冲区中读出W2当缓存区中是R2写的数据时，才可

22、以将数据从缓冲区中读出万里缓存区无数据，empty,初值1缓存区中是R1写的数据，full1,初值0缓存区中是R2写的数据，full2,初值0第四步：用伪代码描述beginempty,full1,full2:semaphore;empty:=1;full1:=0;full2:=0;cobeginR1();R2();W1();W2();coend;end;processR1()beginL1:从磁盘上读入一个数;P(empty);将数存放到缓冲区中；V(full1);gotoL1end;processR2()beginL2:从键盘上读入一个数;P(empty);将数存放到缓冲区中;V(full2

23、);gotoL2end;processW1()beginL3:P(full1);将缓冲区中的数取出;V(empty);打印输出；gotoL3end;processW2()beginL4:P(full2);将缓冲区中的数取出;V(empty);打印输出；gotoL4end;14、请用PV操作实现他们之间的同步关系：（1）桌上一个盘子，只能放一只水果。爸爸放苹果，妈妈放桔子，儿子只吃桔子，女儿只吃苹果。（2）桌上一个盘子，只能放一只水果。爸爸放苹果，妈妈放桔子，儿子吃桔子、苹果。参考答案：第一步：确定进程4个进程Father（爸爸）、Mother（妈妈）、Son（儿子）、Daughter（女儿）Father进程：将苹果放入盘中Mother进程：将桔子放入盘中Son进程：从盘中取出桔子吃桔子Daughter进程：从盘中取出苹果吃苹果第二步：确定进程的同步、互斥关系同步：Father当盘中无水果时，才可以将苹果放入盘中同步：Mother当盘中无水果时，才可以将桔子放入盘中同步：Son当盘中