操作系统同步互斥练习题

操作系统同步试题1、设公共汽车上，司机和售票员的活动分别是：司机的活动：启动车辆；正常行车；到站停车；售票员的活动：关车门；售票；开车门；在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用P、V操作实现它们的同步。设两个信号量S和C，初值为S＝0；C＝0；司机：L1：正常行车售票员：L2：售票到站停车P（S）V（S）开车门P（C）关车门启动开车V（C）GOTOL1GOTOL22、桌子上有一个空盘子，允许存放一只水果，爸爸可以向盘中放苹果，妈妈向盘子中放橘子，女儿专门吃盘子中的苹果，儿子专门吃盘子中的橘子。规定当盘子空的时候一次只能放一只水果，请用信号量实现他们之间的同步与互斥。S,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)；GOTOL2；End；ProcessSon:Begin:L3:P(S2);GetOrange;V(S)；GOTOL1；End；ProcessDaughter:Begin:L4:P(S1);GetApple;V(S)；GOTOL4；End；CoEnd;2、写者优先的“读者――写者”问题：1）共享读2）互斥写、读写互斥3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）wmutex:semaphore=1//读者与写者之间、写者与写者之间互斥使用共享数据S：semaphore=1//当至少有一个写者准备访问共享数据时，它可使后续的读者等待写完成S2：semaphor＝1//阻塞第二个以后的等待读者readcount,writecount:semaphore=0,0;//当前读者数量、写者数量mutex1:semaphore=1//多个读者互斥使用readcountmutex2:semaphore=1//多个写者互斥使用writecountCobegin:Reader:beginRepeatWait（S2）；wait(S);wait(mutex1)ifreadcount=0thenwait(wmutex);readcount++;signal(mutex1);signal(S);signal（S2）；reading…wait(mutex1);readcount--;ifreadcount=0thensignal(wmutex);signal(mutex1);untilfalse;begin;writer:beginrepeat;wait(mutex2);ifwritecount=0thenwait(S);writecount++;signal（mutex2）;wait(wmutex);writing…signal(wmutex);wait(mutex2);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;ProcessPB:BeginLoop:P(Sb);P(Mutex);产品B入库；V(Mutex);V(Sa);GotoLoop;End;CoEnd;5、进程A1、A2、……An1通过m个缓冲区向进程B1、B2……Bn2不断地发送消息。发送和接收工作遵循如下规则：（1）每个发送进程一次发送一个消息，写入一个缓冲区，缓冲区大小等于消息长度；（2）对每一个消息，B1，B2，…，Bn都必须接收一次，读入各自的数据区内；（3）m个缓冲区都满时，发送进程等待；没有可读的消息时，接收进程等待。解答：本题是生产者——消费者问题的一个变形，一组生产者A1，A2，…….An1和一组消费者B1，B2，……Bn2公用m个缓冲区，每个缓冲区只要写一次，但需要读n2次，因此，我们可以把这一组缓冲区看成n2组缓冲区，每个发送者需要同时写n2组缓冲区，而每一个接收者只需读它自己对应的那组缓冲区中的对应单元。Mutex,empty[n2],full[n2]:semaphore;Mutex=1;//多进程互斥使用缓冲区empty[0,1,……n2]={m,m,……m};full[0,1,…..n2]={0,0,……0};intI;Cobegin:ProcessAiBegin:Loop:IntI;For(I=0;In2;I++)P(empty[I]);P(Mutex);将消息放入缓冲区；v(Mutex);for(I=0;In2;I++)v(full[I]);GotoLoop;End;ProcessBiBegin:Loop:P(full[I]);P(Mutex);从消息缓冲区取出消息；v(Mutex);v(empty[I]);GotoLoop;End;CoEnd;6、理发师问题：一个理发店有N张沙发和一张理发椅，没有顾客要理发时，理发师便去睡觉；当一个顾客走进理发店时，如果所有的沙发都已被占用，他便离开理发店；否则，如果理发师正在为其他顾客理发，则该顾客就找一张空沙发坐下等待；如果理发师因无顾客正在睡觉，则由新到的顾客唤醒理发师为其理发。在理发完成后，顾客必须付费，直到理发师收费后才能离开理发店。使用信号量实现这一同步问题。解答：为解决上述问题，需要设置一个整形变量count用来对理发店中的顾客进行计数，再设置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:Begin:P(mutex);If(countN)then{v(mutex);exitshop;}else{count++;if(count1)then{p(sofa);sitonsofa;p(empty);getupfromsofa;v(sofa);}else//count=1{p(empty);sitonthebaber_chair;v(full);p(cut);pay;v(payment);p(receipt);getupfromthebaber_chair;v(empty);p(mutex)count--;v(mutex);exitshop;End;ProcessBarber:BeginLoop: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、教材作业第25题:(1)具有忙等待的关锁和开锁原语:Lock(W):{WhileW=1DoNoOperation;W=1;}Unlock(W):{W=0;}(2)不会忙等待的关锁和开锁原语:Lock(W):{W++;IfW1ThenBlock();}Unlock(W):{W--;IfW=1ThenWakeup();}10、教材作业第28题:第一种解法:S1,S2:Semaphore=0,0;Main(){Cobegin:Collection();Computer();}Collection(){L1:CollectMesg;PutMesgIntoBuffer;V(S1);P(S2);GotoL1;}Computer(){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操作是如何定义的？试说明信号量的PV操作的物理意义。参考答案：P（S）：将信号量S减1，若结果大于或等于0，则该进程继续执行；若结果小于0，则该进程被阻塞，并将其插入到该信号量的等待队列中，然后转去调度另一进程。V（S）：将信号量S加1，若结果大于0，则该进程继续执行；若结果小于或等于0，则从该信号量的等待队列中移出一个进程，使其从阻塞状态变为就绪状态，并插入到就绪队列中，然后返回当前进程继续执行。PV操作的物理含义：信号量S值的大小表示某类资源的数量。当S0时，其值表示当前可供分配的资源数目；当S0时，其绝对值表示S信号量的等待队列中的进程数目。每执行一次P操作，S值减1，表示请求分配一个资源，若S≥0，表示可以为进程分配资源，即允许进程进入其临界区；若S0，表示已没有资源可供分配，申请资源的进程被阻塞，并插入S的等待队列中，S的绝对值表示等待队列中进程的数目，此时CPU将重新进行调度。每执行一次V操作，S值加1，表示释放一个资源，若S0，表示等待队列为空；若S≤0，则表示等待队列中有因申请不到相应资源而被阻塞的进程，于是唤醒其中一个进程，并将其插入就绪队列。无论以上哪种情况，执行V操作的进程都可继续运行。12、假设有三个并发进程P，Q，R，其中P负责从输入设备上读入信息并传送给Q，Q将信息加工后传送给R，R则负责将信息打印输出。写出下列条件的并发程序：（1）进程P、Q共享一个缓冲区，进程Q、R共享另一个缓冲区。（2）进程P、Q共享一个由m个缓冲区组成的缓冲池，进程Q、R共享另一个由n个缓冲区组成的缓冲池。参考答案：（1）第一步：确定进程3个进程P、Q、RP进程：从输入设备上读入信息将信息放入缓冲区1Q进程：从缓冲区1取出信息将信息放入缓冲区2中R进程：从缓冲区2取出信息将信息打印输出第二步：确定进程的同步、互斥关系同步：P当缓存区1无数据时，才可以向缓冲区1写入信息同步：Q当缓存区1有数据时，才可以从缓冲区1读取信息同步：Q当缓存区2无数据时，才可以向缓冲区2写入信息同步：R当缓存区2有数据时，才可以从缓冲区2读取信息第三步：设置信号量缓存区1无数据，empty1，初值1缓存区1有数据，full1，初值0缓存区2无数据，empty2，初值1缓存区2有数据，full2，初值0第四步：用伪代码描述beginempty1,empty2,full1,full2：semaphore;empty1:=1;empty2:=1;full1:=0;full2:=0;cobeginP();Q();R();coend;end;p