操作系统第4章习题带答案

1、第四章一、问答题1、同步机制应遵循的准那么是什么？2、死锁产生的4个必要条件是什么？它们是彼此独立的吗？3、简述死锁的定义和死锁产生的原因。4、简述死锁定理和解除死锁的方法。5、什么是平安状态？怎么推断系统是否处于平安状态？6、同步机制应遵循的准那么是什么？7、死锁产生的4个必要条件是什么？它们是彼此独立的吗？二、计算题共20分1、当前系统中出现下述资源分配状况：allocationneedavailablep0003200121622p110001750p213542356p303320652p400140656利用银行家算法，试问假设进程p2提出资源恳求request1，2，2，2后，系统

2、能否将资源分配给它？ 答：request1，2，2，2<=(2,3,5,6)申请合法 request1，2，2，2<=available，开始试探性分配，available=(0,4,0,0) 测试系统是否平安：work= available,finish=1 没有进程的need满足<=work 系统处于不平安状态，系统回绝此次资源分配。 2、当前某系统有同类资源7个，进程p，q所必必需资源总数分别为5，4。它们向系统申请资源的次序和数量如表所示。答复：次序进程申请量123456qpqppq211321问：采纳死锁防止的方法进展资源分配，请你写出系统完成第3次分配后各进程占有

3、资源量，在以后各次的申请中，哪次的申请要求可先得到满足? 答：第1次申请，q申请资源2，系统平安，分配 第2次申请，p申请资源1，系统平安，分配第3次申请，q申请资源1，系统平安，分配 资源剩余3个，p占有1个资源，q占有3个资源，第4次分配不平安，回绝，第5分配系统平安，满足。3、一个计算机系统有6个磁带驱动器和4个进程。每个进程最多必必需要n个磁带驱动器。问当n为什么值时，系统不会发生死锁？并说明理由 答：n=2理由同第4题(进程资源最大必必需求1)×进程数量1系统资源数量4、 假设系统有某类资源m×n+1个，同意进程执行过程中动态申请该类资源，但在该系统上运行的每一个

4、进程对该资源的占有量任何随时都不会超过m+1个。当进程申请资源时只要有资源尚未分配完那么满足它的申请，但用限制系统中可同时执行的进程数来防止发生死锁，你认为进程调度同意同时执行的最大进程数应该是多少？并说明原因。 答；假设系统中有x个进程的进程，那么资源至少要有m×x+1个才不会产生死锁，由于系统资源有m×n+1个，那么可列出不等式：m×x+1m×n+1解不等式，得到xn，所以系统同意同时执行的最大进程数为n。证实：假设在系统同意同时执行的最大进程数为n时，仍然出现了死锁，此时应该存在一组进程都在等待资源，而且系统已无资源可用。那么此时该组进程最多n个，

5、每个进程没有执行完时最多占用m个资源，所以如今系统分配出去的资源最多m×n，少于系统资源m×n+1，所以不可能有死锁出现。 假设系统进程数量为n+1，每个进程占有最大资源数量为m+1，那么会出现死锁。例如，当其中n个进程均占有m个资源，剩下的一个进程占有了最后一个资源，所有进程都都还必必需要资源才可运行完，而此时系统已经无资源可用，产生死锁。因此，系统同意同时执行的最大进程数为n时系统不会有死锁发生5、设系统中有3种类型的资源a、b、c和5个进程p0、p1、p2、p3、p4，a资源的数量为10，b资源的数量为5，c资源的数量为7。在t0随时系统状态如下表所示。系统采纳银行家

6、算法施行死锁防止策略。12分maxallocationneedavailableabcabcabcabcp0p1p2p3p4753010743332322200122902302600222211011433002431. t0随时是否为平安状态？假设是，请给出平安序列。 在t0随时假设进程p1发出资源恳求request1，0，2，是否可以施行资源分配？ 在的根底上p4发出资源恳求request3，3，0，是否可以施行资源分配？ 在的根底上p0发出资源恳求request0，2，0，是否可以施行资源分配? 见课本五、应用题 1、假设有三个进程r、w1、w2共享一个缓冲器b，而b中每次只能存放一个

7、数。当缓冲器中无数时，进程r可以将从输入设备上读入的数存放到缓冲器中。假设存放到缓冲器中的是奇数，那么同意进程w1将其取出打印；假设存放到缓冲器中的是偶数，那么同意进程w2将其取出打印。同时规定：进程r必必需等缓冲区中的数被取出打印后才干再存放一个数；进程w1或w2对每次存入缓冲器的数只能打印一次；w1和w2都不能从空缓冲中取数。写出这三个并发进程能正确工作的程序。 semaphore s=1,so=se=0;buffer b;void r1int x;while(1)从输入设备上读一个数;x=接收的数;wait(s);b=x;if b=奇数 then signal(so);else sign

8、al(se); void w1()int y;while(1) wait(so);y=b;signal(s);打印y中数; void w2()int z;while(1) wait(se);z=b;signal(s);打印z中数 ; main() cobegin r(); w1(); w2();2、制定一种可以防止死锁的资源分配算法，要求写明数据构造和相应方案或算法。 参照课本上方案3、复印室里有一个操作员为顾客复印资料，有5把椅子供顾客休息等待复印。假设没有顾客，那么操作员休息。当顾客来到复印室时，假设有空椅子那么坐下来，并唤醒复印操作员；假设没有空椅子那么必必需分开复印室。利用信号量机制解

9、决该同步互斥问题。 设置3个信号量：customers表示正在等待复印的顾客数量不包括正在复印的顾客；operator记录正在等候顾客的操作员数，只有1和0；mutex用于对变量waiting的互斥访问。1个变量：waiting表示等待的顾客数量。semaphore customers=0,operator=0,mutex=1;waiting=0；process operator( )/操作员进程 while(1) wait(customers); /等待顾客到来 复印； signal(operator); /通知顾客已经完成复印process cusotmeri( )/顾客进程i wait(

10、mutex); if(waiting<5) waiting+;signal(customers);signal(mutex);wait(operator);wait(mutex);waiting-;signal(mutex); elsesignal(mutex); 分开复印室； main( )cobegin operator( ); customeri( ); 4、a，b两点之间是一段东西向的单行车道，现要制定一个自动管理系统，管理规那么如下：当ab之间有车辆在行驶时同方向的车可以同时驶入ab段，但另一方向的车必必需在ab段外等待；当ab之间无车辆在行驶时，到达a点(或b点)的车辆可以进

11、入ab段，但不能从a点和b点同时驶入，当某方向在ab段行驶的车辆驶出了ab段且暂无车辆进入ab段时，应让另一方向等待的车辆进入ab段行驶。请用信号量机制为工具，对ab段实现正确管理以确保行驶平安。 semaphore s1=1,s2=1,sab=1; int ab=ba=0; void pab ()while(1) wait(s1);if(ab=0)wait(sab);ab=ab+1;signal(s1); 车辆从a点驶向b点; wait(s1); ab=ab-1; if(ab=0)signal(sab); signal(s1); void pba ()while(1) wait(s2); i

12、f(ba=0)wait(sab); ba=ba+1; signal(s2); 车辆从b点驶向a点; wait(s2); ba=ba-1; if(ba=0)signal(sab); signal(s2); main()cobeginpab ();pba ();5、某系统五个合作的进程前驱图如下，请用信号量方法控制它们的执行，以确保它们的执行顺序，请写出类c算法。p1p5p3p2p4参照解题方案 5、一条河上架设了由假设干个桥墩组成的一座桥。假设一个桥墩只能站一个人，过河的人只能沿着桥向前走而不能向后退。过河时，只要对岸无人过，就可以过。但不同意河对岸的两个人同时过，以防止出现死锁。请给出两个方向

13、的人顺利过河的同步算法。 假设桥墩数量为ksemaphore s, scounteast, scountwest, scount;s=1, scounteast=1, scountwest=1, scount=k;int counteast=0, countwest=0;void east(int i) wait(scounteast); if(counteast=0) wait(s); counteast+; signal(scounteast); wait(scount4); 上桥，过桥，下桥； signal(scount4); wait(scounteast); counteast-;

14、if(counteast=0) signal(s); signal(scounteast);void west(int i) wait(scountwest); if(countwest=0) wait(s); countwest+; signal(scountwest); wait(scount4); 上桥，过桥，下桥； signal(scount4); wait(scountwest); countwest-; if(countwest=0) signal(s); signal(scountwest);main()cobegin east(1); . east(n); west(1); .

15、 west(m);6、现有四个进程r1、r2、w1、w2，它们共享可以存放一个数的缓冲器b。进程r1每次把来自键盘的一个数存入缓冲器b中，供进程w1打印输出；进程r2每次从磁盘上读一个数存放到缓冲器b中，供进程w2打印输出。为防止数据的丧失和重复打印，问怎样用wait,signal操作来协调这四个进程的并发执行。semaphore s=1,s1=s2=0;buffer b;void r1int x;while(1)接收来自键盘的数;x=接收的数;wait(s);b=x;signal(s1); void r2()int y;while(1) 从磁盘上读一个数;y=接收的数;wait(s);b=y

16、;signal(s2); void w1()int k;while(1) wait(sl);k=b;signal(s);打印k中数; void w2()int j;while(1)wait(s2);j=b;signal(s);打印j中数; main() cobegin r1(); r2(); w1(); w2(); 7、系统中有4种类型的资源a、b、c、d和5个进程p0、p1、p2、p3、p4，当前系统出现下表所示资源分配状况：allocationneedavailableabcdabcdabcdp0003200121622p110001750p213542356p303320652p4001

17、40656试问： 该状态是否平安？分析说明。假设进程p2提出资源恳求request1，2，2，2后，系统能否将资源分配给它？ 1利用银行家算法对此随时的资源分配状况进展分析，可得此随时的平安性分析状况，如表1-4-7所示。表1-4-7workneedallocationwork+allocationfinishp01622001200321654truep31654065203321986truep419860656001419910truep1199101750100029910truep229910235613543121414true从上述分析中可以看出，此时存在一个平安序列p0，p3，

18、p4，p1，p2，故该状态是平安的。2p2提出恳求request1，2，2，2，按银行家算法进展检查：request(1,2,2,2)need(2,3,5,6)request(1,2,2,2)available(1,6,2,2)试探分配并修改相应的数据构造，资源分配状况如表1-4-8所示。表1-4-8allocationneedavailablep0003200120400p110001750p225761134p303320652p400140656再利用平安性算法检查系统状态是否平安，资源向量available0，4，0，0已不能满足任何进程的必必需要，故系统进入不平安状态，所以系统不能将

19、资源分配给进程p2。8、某寺庙有小和尚和老和尚各假设干人，水缸一只，由小和尚提水入缸给老和尚饮用。水缸可容水10桶，水取自同一口水井中。水井径窄，每次仅能容一只水桶取水，水桶总数为3个。假设每次入、取水仅为1桶，而且不可同时进展。试用记录型信号量机制写出小和尚和老和尚的活动过程。 互斥资源有水缸和水井，分别用mutex1和mutex2来互斥。水桶总数仅3只，由信号量count控制，信号量empty和full控制入水和出水量。semaphore mutex1,mutex2,empty,full,count;mutex1=1;mutex2=1;count=3;empty=10; full=0;pr

20、ocess young_monkint i(i=1、2、) while(1) wait(empty); wait(count); wait(mutex1); 从井中取水; signal(mutex1); wait(mutex2); 倒水入缸; signal(mutex2); signal(count); signal(full); process old_monk(int j)j(j=1、2) while(1) wait(full); wait(count); wait(mutex2); 从缸中取水; signal(mutex2); signal(count); signal(empty);

21、main()cobeginyoung_monk(i);old_monk(j);9、合计三个吸烟者进程和一个经销商进程的系统。每个吸烟者连绵不断地做烟卷并抽他做好的烟卷，做一支烟卷必必需要烟草、纸和火柴三种原料。这三个吸烟者分别掌握有烟草、纸和火柴。经销商源源不断地提供上述三种原料，但他只将其中的两种原料放在桌上，具有另一种原料的吸烟者就可以做烟卷并抽烟，且在做完后给经销商发信号，然后经销商再拿出两种原料放在桌上，如此反复。试制定一个同步算法来描述他们的活动。 semaphore sa=sb=sc=0,sd=1;i:integer;void smokera()while (1)wait(sa);

22、制烟;signal(sd);吸烟； void smokerb()while (1)wait(sb);制烟;signal(sd);吸烟； void smokerc()while (1)wait(sc);制烟;signal(sd);吸烟； void provider( ) while(1) i=random(2);/0代表纸和火柴的组合，1代表烟草和火柴的组合，2代表烟草和纸的组合wait(sd);把i放到桌子上；switch(i)case 0: signal(sa);case 1: signal (sb);case 2: signal (sc); main()cobeginsomkera();s

23、omkerb();somkerc();provider();10、假定有一个信箱可存放n封信，当信箱不满时发信者可把信件送入信箱；当信箱中有信时收信者可从信箱中取信。用指针r，k分别表示可存信和取信的位置， 请用信号量来管理这个信箱，使发信者和收信者能正确工作。 参照课本消费者消费者问题11、n个进程共享某种资源r，该资源共有m个，每个进程一次一个地申请或释放资源。假设每个进程对该资源的最大必必需求量均小于m，且各进程最大必必需求量之和小于mn，试证实在这个系统中不可能发生死锁。 答：设max(i)表示第i个进程的最大资源必必需求量，needi表示第i个进程还必必需要的资源量，alloc(i)

24、表示第i个进程已分配的资源量。由题中所给条件可知：max(1)+max(n)=need(1)+need(n)+alloc(1)+alloc(n)<m+n 假设在这个系统中发生了死锁，那么一方面m个资源应该全部分配出去，即alloc(1)+alloc(n)=m 另一方面所有的进程将陷入无限等待状态，need(1)+need(n)>=n 两式相加， max(1)+max(n)=need(1)+need(n)+alloc(1)+alloc(n)=m+n 这与前面的假设矛盾，从而证实了在这个系统中不会发生死锁。12、一个数据文件或记录统称数据对象，可被多个进程共享。有些读进程要求读，而另一

25、些写进程对数据对象进展写或修改。同意多个写进程同时读一个共享对象，决不同意一个写进程和其他读进程或写进程同时访问共享对象。请用信号量或管程为工具，实现读写进程并发的正确管理。 参照课本，题目中没有具体尤其哦球，所以读者优先和写者优先均可13、有一个仓库，可以存放a和b两种产品，但要求：1每次只能存入一种产品a或b；2-na产品数量b产品数量m。其中，n和m是正整数。试用同步算法描述产品a与产品b的入库过程。 【分析】a产品的数量不能比b产品的数量少n个以上，a产品的数量不能比b产品的数量多m个以上。设置2个信号量来控制a、b产品的存放数量，sa表示当前同意a产品比b产品多入库的数量，即在当前库

26、存量和b产品不入库的状况下，还可以同意sa个a产品入库；sb表示当前同意b产品比a产品多入库的数量，即在当前库存量和a产品不入库的状况下，还可以同意sb个b产品入库。初始时，sa为m一1，sb为n一1。当往库中存放入一个a产品时，那么同意存入b产品的数量也增加1;当往库中存放入一个b产品时，那么同意存入a产品的数量也增加1。semaphore mutex=1，sa=m-1， sb=n-1;process puta() while(1) 准备一个产品； wait(sa); wait(mutex); 将产品入库； signal(mutex); signal(sb); process puta()

27、while(1) 准备一个产品； wait(sb); wait(mutex); 将产品入库； signal(mutex); signal(sa); main()cobegin puta(); putb();14在一个系统中，不采纳死锁防止和预防措施，但当死锁发生后必必需要可以检测出来，请制定一个可行的死锁检测方案。 参照课本课本方案15、一个理发店由一个有n张沙发的等候室和一个放有一张理发椅的理发室组成。没有顾客要理发时，理发师便去睡觉。当一个顾客走进理发店时，假设等候室的所有沙发都已经占用，便分开理发店；否那么，假设理发师正在为其他顾客理发，那么该顾客就找一张空沙发坐下等待。假设理发师因无顾

28、客正在睡觉，那么由新到的顾客唤醒理发师为其理发。请用信号量机制解决该问题 参照课本嗜睡理发师问题16、有一个可以存放n整数的循环缓冲，今有m个输入进程，每个输入进程每次读入一个数据放入缓冲中；还有k个输出进程，每个输出进程每次可以从缓冲中读出一个数据输出；不同意有两个或两个以上的输入进程或输出进程同时去存数据或取数据,但同意有一个输入进程在存数据时有一个输出进程可以取数据。试用请用信号量为工具协调它们的工作，写出算法。 参照课本消费者消费者问题17、某系统中由5种资源，数量为5，6，8，6，4，某个随时进程和资源的使用状况如下： 进程名 占有资源(向量) 运行完还必必需资源数量向量 p1 0，

29、2，1，1，1 1，0，2，1，1 p2 2，0，1，1，1 0，3，2，1，0 p3 0，1，0，1，1 0，3，3，2，2 p4 0，3，1，2，0 1，0，1，2，1如此时进程p1提出申请资源1,0,0,0,1，如系统满足其要求，系统是否平安？请制定一平安检测方案。 18、司机与售票员问题： 司机与售票员之间的同步关系如下所示，当司机停车后售票员才干开门，售票员关门后司机才干开车，请用信号量给出同步算法。司机与售票员的活动程序如下： 司机： 售票员：l：车在行进中； m：买票； 停车； 开门； 开车； 关门；goto l； goto m。在汽车行驶过程中，司机活动与售票员活动之间的同步关

30、系为：售票员在关车门之后，向司机发开车信号，司机接到开车信号后启动车辆，在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开车门让乘客下车。因此司机启动车辆的动作必必需与售票员关车门的动作获得同步；售票员开车门的动作也必必需与司机停车获得同步。在此题中，设置两个信号量：s1、s2，s1表示是否同意司机启动汽车，其初值为0；s2表示是否同意售票员开门，其初值为0。【答案】那么该问题描述如下：semaphoere s1=s2=0;void driver() while(1) wait(s1); 启动车辆； 正常行车； 到站停车； signal(s2); void busman() wh

31、ile(1) 关车门； signal(s1)； 售票； wait(s2)； 开车门； main() cobegin driver(); busman(); 19、写一个管程，用于实现读者写者问题，要求写者优先。参照课本读者写者问题写者优先20、用信号量机制解决读者写者问题，要求写者优先。此题是第二类读者-写者问题，即写者优先，与读者优先有一定差异。为了使写者优先，可在原来的读者优先算法的根底上增加一个互斥信号量s，初值为1，使得当至少有一个写者准备访问共享对象时，它可以使后续的读者进程等待完成；整型变量writecount，初值为0，用来对写者进展计数；互斥信号量mutex，初值为1，用来实现多个读者对写者writecount进展互斥访问。【答案】semaphore s,rmutex,wmutex,mutex;int readcount,writecount;s=1;rmutex=1;wmutex=1;mutex=1;readcount=0;writecount=0;void reader(int i) while(1) wai