进程同步与死锁习题答案

1、第4章进程同步与死锁(1) 什么是进程同步？什么是进程互斥？解：同步是进程间的直接制约关系，这种制约主要源于进程间的合作。进程同步的主要任务 就是使并发执行的各进程之间能有效地共享资源和相互合作，从而在执行时间、次序上相互 制约，按照一定的协议协调执行，使程序的执行具有可再现性。进程互斥是进程间的间接制约关系，当多个进程需要使用相同的资源，而此类资源在任 一时刻却只能供一个进程使用，获得资源的进程可以继续执行，没有获得资源的进程必须等 待，进程的运行具有时间次序的特征，谁先从系统获得共享资源，谁就先运行，这种对共享 资源的排它性使用所造成的进程间的河接制约关系称为进程互斥。互斥是一种特殊的同步

2、方 式。(2) 进程执行时为什么要设置进入区和退出区？解：为了实现多个进程对临界资源的互斥访问，必须在临界区前面增加一段用于检查欲访问 的临界资源是否正被访问的代码，如果未被访问，该进程便可进入临界区对资源进行访问， 并设置正被访问标志，如果正被访问，则本进程不能进入临界区，实现这一功能的代码成为 “进入区”代码：在退出临界区后，必须执行“退出区”代码，用于恢复未被访问标志。(3) 同步机构需要遵循的基本准则是什么？请简要说明。解：同步机制都应遵循下面的4条准则：1. 空闲让进。当无进程处于临界区时，允许进程进入临界区，并且只能在临界区运行 有限的时间。2. 忙则等待。当有一个进程在临界区时，

3、其它欲进入临界区的进程必须等待，以保证 进程互斥地访问临界资源。3. 有限等待。对要求访问临界资源的进程，应保证进程能在有限时间内进入临界区， 以免陷入“饥饿”状态。4. 让权等待。当进程不能进入临界区时，应立即放弃占用CPU,以使其它进程有机 会得到CPU的使用权，以免陷入“饥饿”状态。(4) 整型信号量是否能完全遵循同步机构的四条基本准则？为什么？解：不能。在整型信号量机制中，未遵循“让权等待”的准则。(5) 在生产者-消费者问题中，若缺少了 V(fUll)或讯empty),对进程的执行有什么影响？解：如果缺少了 V(fiill),那么表明从第一个生产者进程开始就没有对信号量純11值改变，

4、即 使缓冲池存放的产品已满了，但伍11的值还是0,这样消费者进程在执行P(fiill)时会认为缓 冲池是空的而取不到产品，那么消费者进程则会一直处于等待状态。如果缺少了 V(empty)，例如在生产者进程向n个缓冲区放满产品后消费者进程才开始 从中取产品，这时emptv=0, fiill=n,那么每当消费者进程取走一个产品时empty并没有被 改变，直到缓冲池中的产品都取走了，empty的值也一直是0,即使目前缓冲池有n个空缓 冲区，生产者进程要想再往缓冲池中投放产品会因申请不到空缓冲区而被阻塞。(6) 在生产者-消费者问题中，若将P(full)和P(empty)交换位置，或将V(fiill)

5、或V(empty)交换位置，对进程执行有什么影响？解：对仕山和empty信号量的P、V操作应分别出现在合作进程中，这样做的目的是能正确 表征各进程对临界资源的使用情况，保证正确的进程通信联络。(7) 利用信号量写出不会出现死锁的竹学家进餐问题的算法。解：对哲学家按顺序从0到4编号，哲学家1左边的筷子的编号为1,哲学家右边的筷子的 编号为(i+1) %5。semaphore chopstick5= 1;定义信号量数组chopstick5,由于信子是临街资源(互斥)，故设置初值均为1。P“/1号哲学家的进程doif(i<(i+l)%5)wait(chopsticki);wait(chopst

6、ick(i+1)% 5);elsewait(chopstick(i+1)% 5);wait(chopsticki); signal(chopsticki);signal(chopstick(i+1)%5);tliuikwlule(l);(8) 利用AND型信号量和管程解决生产者-消费者问题。解：利用AND信号屋解决生产者一消费者问题的算法描述如卞: var mutex,empty,fu止 semaphoie:=l ,n.O;buffer: arrav0,.,n-l of item;in out: integer := 0, 0;beginparbegmproducer: beginrepeat

7、 produce ail item in nextp;Swait(empty, mutex);buffer(in) := nextp;ill := (iii+1) mod n;Ssignal(mutex, full);until false;endconsumer: beginrepeatSwait(full, mutex);nextc := buffer(out);out := (out+1) mod n;Ssignal(mutex, empty);consume the item in nextc;until false;endparendend利用管程机制解决生产者-消费者问题，首先需要

8、建立一个管程ProducerConsuiner,其 中包含两个过程msen(item)和consumei(item)o生产者-消费者同步问题可以用伪代码描述如 下：monitor PioduceiConsumercondition hill,empty;mt count;void inseit(iiit item)if (count=N) wait(full);iiiseit(item);count=count+l;if (count=l) signal(empty);mt remover()if (count=0) wait(empty);remove=remove_item;count=c

9、ount-l;if (count=N-l) signal(fxill);count=0;end monitorvoid producerQwhile (tnie) item=produce_item;ProducerConsumer.iiisen(item);void consumer()while (true)item=Producei-Consumer.remove;consume(item)(9) 进程的高级通信机制有哪些？请简要说明。解：进程的高级通信机制分为三人类：共享存储系统、消息传递系统和管道通信系统。1. 共享存储器系统：在共享存储器系统中，相互通信的进程通过共享某些数据结构或

10、 共享存储区实现进程之间的通信。该系统又可进一步细分为两种方式：基于共享数 据结构的通信方式和基于共享存储区的通信方式。2. 消息传递系统：消息传递机制可以实现不同主机间多个CPU上进程的通信。这种 方式需要使用两条原语send和receive来发送和接收格式化的消息(message)o3. 管道通信系统:管道通信是一种以文件系统为基础实现的适用于在进程之间实现大 量数据传送的通信方式。(10) 什么是死锁？产生死锁的原因和必要条件是什么？解：所谓死锁是指在一个进程集合中的所有进程都在等待只能由该集合中的其它一个进程 才能引发的爭件而无限期地僵持下去的局面。产生死锁的原因可以归结为两点：1)竞

11、争资源，2)各进程之间的推进顺序不当。 产生死锁的必要条件有四个：1)互斥条件，2)不剥夺条件，3)请求和保持条件，4) 环路条件。(11) 死锁的预防策略有哪些？请简要说明。解：死锁的预防策略有三，说明如下：1. 摒弃请求和保持条件：为摒弃请求和保持条件，系统中需要使用静态资源分配法, 该方法规定每一个进程在开始运行前都必须一次性地申请其在整个运行过程中所 需的全部资源。此时，若系统有足够的资源，就把进程需要的全部资源一次性地分 配给它：若不能全部满足进程的资源请求，则一个资源也不分给它，即使有部分资 源处于空闲状态也不分配给该进程。这样，当一个进程申请某个资源时，它不能占 有其它任何资源，

12、在进程运行过程中也不会再提出资源请求。这种方法破坏了请求 和保持条件，从而避免死锁的发生。2. 摒弃不剥夺条件：要摒弃“不剥夺条件”，可以使用如下策略：进程在需要资源时 才提出请求，并且进程是逐个地申请所需资源，如果一个进程已经拥有了部分资源, 然后又申请另一个资源而不可得时，其现有资源必须全部释放。在这种方法中，进 程只能在获得其原有资源和所申请的新资源时才能继续执行。3. 摒弃坏路等待条件：为确保环路等待条件不成立，可以在系统中实行资源有序分配 策略，即系统中的所有资源按类型被赋予一个唯一的编号，每个进程只能按编号的 升序申请资源。(12) 某系统中有A、E、C、D四类资源，且其总数量都是

13、8个。某时刻系统中有5个进程, 判断下列资源状态是否安全？若进程P2申请资源(1, 1, 1, 1),能否为其分配？进程NeedA B C DAllocation A B C DP00 0 4 30 0 2 2P12 6 3 0110 0P23 2 15210 3P34 0 2 02 0 0 0P40 5 5 40 2 2 2解：现在对该时刻的状态进行安全分析：由于Available向量为(3, 4, 4, 1),所以Work向量初始化为(3, 4, 4, 1) 此时的Work小于任意的Needi向量，所以系统处于不安全状态由于 Request2( 1,1,1,l)<Available

14、(3,4,4,1)且 Request2 (1,1,1,1) <Need2 (1,1,1,2)所以先试着把P2所申请的资源分配给它，Available变为(2,3,3,0)得到系统状态如卞 表所示：AllocationNeedAvailableABCDABCDABCDP0002200432330Pl11002630P232142104P320004020P402220554然后进行安全性检测：此时Available向量为(2,3,3,0),所以Work向量初始化为(2,3,3,0),此时的Work小 于任意的Needi向量，所以系统处于不安全状态，所以不可以为P2分配资源(13) 三个进程

15、Pl、P2、P3都需要5个同类资源才能正常执行直到终止，且这些进程只有在 需要设备时才申请，则该系统中不会发生死锁的最小资源数量是多少？请说明理由。解：系统中不会发生死锁的最小资源数量是13,这样可以保证当每一个进程都占有4个资 源的时候，有一个进程可以获得最后一个资源后被运行，运行完毕后释放资源，于是其余进 程也能顺利运行完，所以不会死锁。(14) 在解决死锁问题的几个方法中，哪种方法最易于实现，哪种方法使资源的利用率最高？解：预防死锁这个方法实现简单，效果突出；避免死锁这种方法系统吞吐量和资源利用率较 咼。(15)考虑由n个进程共享的具有m个同类资源的系统，如果对于i=l,2,3,-.-A

16、WNeedi>0 并且所有进程的最大需求量之和小于m+n,试证明系统不会产生死锁。解：本题中只有一种资源，不妨设Maxi为第1个进程的资源总共需要量，Needi为第i个 进程还需要的资源数量，Allocationi表示第1个进程己经分配到的资源数量，bailable为系 统剩余的资源数，其中1=1,2,3,假设此系统可以发生死锁。系统剩余的资源数量为Available (Available>=0),由假设，因为系统处于死锁状态，所 以Available个资源无法分配出去，所以每个进程的Needi都大于Available,即NEdi>=Available+l所以L Needi&

17、gt;=n*(Available+l)=n*Available+n,因为剩下的资源数是Available,所以已经分配出去的资源数为m-Available;即L Allocationi=m 一 Available由式和式可以得到：LNeedi + E Allocationi>=n*Avrailable+n+ m -Available= (n-1) *Av*ailable+m+n 又因为 n>=L 所以(ml) >=0,又因为 Available>=0,所以(n-1) *Available>=0 由式和式可以得到 L Needi + L Allocationi &g

18、t;=O+m+n=m-rii根据题意知：L Maxi<m+n又因为:Maxi=Needi+Allocationi,所以EMaxi= LNeedi + LAllocationi 由式和式得：ENeedfi + L Allocationi<m+n由假设推出的式和由题意推出的式相矛盾，所以假设是错误的，即系统不会产生 死锁。(16)某车站售票厅，在任何时刻最多可以容纳20名购票者进入，当售票厅中少于20 名购票者时，厅外的购票者可立即进入，否则需要在外面等待。若把一个购票者看作一个进 程，请回答以下问题： 用信号量管理这些并发进程时，应该怎样定义信号量，写出信号量的初值以及信号 量的各取

19、值的含义。 根据所定义的信号量，写出相应的程序来保证进程能够正确地并发执行。 如呆购票者最多为n个人，试写出信号量取值的可能变化范闱(最人值和最小值)。 解：定义信号量S,初值为20,当s>0时，它表示可以继续进入购票厅的人数，当s = 0 时表示厅内已有20人正在购票，当s < 0时| s |表示正等待进入的人数。©semaphore S=20;beginparbeginprocedure :begmrepeatwait(s);Enter and buv ticket;signal(s); until false;endparendend最大值为20,最小值为20-n(

20、17)在测量控制系统中的数据采集任务时，把所采集的数据送往一单缓冲区：计算任务从 该单缓冲区中取出数据进行计算。试写出利用信号量机制实现两个任务共享单缓冲区的同步 算法。11解：semaphore mutex = 1; semaphore full = 0; semaphore empty = 1; beginparbegincollect:begm repeatcollect data in nextp; wait(empty); wait(mutex); buffer:=nextp; signal(mutex); signal(full);until false;endcompute: b

21、egm repeatwait(full); wait(mutex); nextc:=buffer; signal(mutex); signal(empty); compute data in nextc; until false;endparend end(18)桌上有一空盘，允许存放一只水果。爸爸可以向盘中放苹果，也可以向盘中放桔子， 儿子专等着吃盘中的桔子，女儿专等着吃盘中的苹果。规定当盘空时一次只能放一只水果供 吃者用，请用信号量实现爸爸、儿子和女儿3个并发进程的同步。解:本题中应设置三个信号量S、so. S"信号量S表示盘中是否为空，其初值为1； S。表示盘中是否有桔子，其初

22、值为0； Sd表示盘中是否有苹果，其初值为0。同步描述如下:爸爸:P(S);将水果放入盘中 if(放入的是桔子) else v(Sa)；儿子:P(SO);从盘子中取出桔子v(So):V (S)；吃桔子女儿：P(SJ； 从盘子中取出苹果V (S)；吃苹果；(19)设某系统中有3个进程Get、Process和Pxit,共用两个缓冲区bufferl和buffer2。假设buffed中最多可以放11个信息，现在己经放入了两个信息；buffer2最多可以放5个信息。Get进程负贵不断地将输入信息送入bufferl中，Process进程负贯从bufferl中取出信息进行 处理，并将处理结果送到buffer

23、2中，Put进程负责从buffer2中读取结果并输出。试用信号 量机制实现它们的同步与互斥。解：semaphore empty 1=9; /bufferl 空的数量semaphore fulll=2; /bufferl 满的数量semaphore empty2=5: /buffer2 空的数量semaphore full2=0; /buffer2 满的数量ini, in2, outl, out2: integer :二 2, 0,1,0;Get () while (1) wait(emptyl)inl=(inl+l)modllsignal(fulll)Process ( ) while(1)

24、wait(fulll)out1=(out1+1)modllsignal(emptyl)signal(empty2)in2=(in2+l)mod5signal(full2)Put () while (1) wait (full2)out2=(out2+l)mod5signal(empty2)(20) 某寺庙有大、小和尚若干，另有一水缸。由小和尚挑水入缸供人和尚饮用。水缸可以 容10桶水，水取自同一井。水井很窄，每次只能容一个水桶取水。水桶总数为3。每次入、 取缸水仅为1桶，且不可同时进行。试给出取水、入水的同步算法。解：semaphore well=l; /保证互斥地访问水井的信号屋seniap

25、lioie vat= 1; /保证互斥地访问水缸的信号量semaphore empty=10; /表示水缸中剩余的空间能容纳的水的桶数semaphore full=O: /表示水缸中水的桶数semaplioie pail=3; /保证互斥地访问临界资源水桶的信号量 /大和尚进程big_moiik()while(l)wait(full);wait(pail); wait(vat);use pail to get water from vat signal(vat);signal(empty);diuik water in the pail signal(pail);/小和尚进程little_mo

26、iik()wlule(l)wait(empty); wait(pail);wait(well);use pail to get water from wellsigiial(well); wait(vat); pour water to the vat sigiial(vat); sigiial(fiill); sigiial(pail);(21) 在银行家算法中，若出现下述资源分配情况：Process AllocationNeedAvailablePO003 200121622Pl10001750P213542 3 5 6P3003 20652P40014065 6试问： 该状态是否安全？ 若进程P2提出请求Request 1,2, 2, 2)后，系统能否将资源分配给它？ 解：现在对该时刻的状态进行安全分析：由于Available向量为(1, 6, 2, 2),所以Work向量初始化为(1, 6, 2, 2)该时刻 的安全性检查表如下：WorkNeedAllocationWork+AllocationFinishABCDABCDABcDABCDP01622001200321654TrueP31654065200321686TrueP416860656001416910TrueP216910