操作系统精髓与设计原理-第6章并发性_死锁和饥饿

第六章习题翻译第一部分复习题６.１给出可重用资源和可消费资源的例子。答：可重用资源：处理器，Ｉ/Ｏ通道，主存和辅存，设备以及诸如文件，数据库和信号量之类的数据结构。可消费资源：中断，信号，消息和Ｉ/Ｏ缓冲区中的信息。６.２可能发生死锁所必须的三个条件是什么？答：互斥，占有且等待，非抢占。６.３产生死锁的第４个条件是什么？答：循环等待。６.４如何防止占有且等待的条件？答：可以要求进程一次性地请求所有需要的资源，并且阻塞这个资源直到所有请求都同时满足。６.５给出防止无抢占条件的两种方法。答：第一种，如果占有某些资源的一个进程进行进一步资源请求被拒绝，则该进程必须释放它最初占用的资源，如果有必要，可再次请求这些资源和另外的资源。第二种，如果一个进程请求当前被另一个进程占有的一个资源，则操作系统可以抢占另一个进程，要求它释放资源。６.６如何防止循环等待条件？答：可以通过定义资源类型的线性顺序来预防。如果一个进程已经分配到了Ｒ类型的资源，那么它接下来请求的资源只能是那些排在Ｒ类型之后的资源类型。６.７死锁避免，检测和预防之间的区别是什么？答：死锁预防是通过间接地限制三种死锁必要条件的至少一个或是直接地限制循环等待的发生来避免死锁的出现。死锁避免允许可能出现的必要条件发生，但是采取措施确保不会出现死锁的情况。而死锁检测允许资源的自由分配，采取周期性的措施来发现并处理可能存在的死锁情况。第二部分习题６.１写出图６.１（a）中死锁的四个条件。解：互斥：同一时刻只有一辆车可以占有一个十字路口象限。占有且等待：没有车可以倒退；在十字路口的每辆车都要等待直到它前面的象限是空的。非抢占:没有汽车被允许挤开其他车辆。循环等待:每辆汽车都在等待一个此时已经被其他车占领的十字路口象限。６.２按照６.１节中对图６.２中路径的描述，给出对图６.３中６种路径的简单描述。解：１.Q获得B和Ａ,然后释放B和A.当P重新开始执行的时候,它将会能够获得两个资源。2.Q获得B和Ａ，P执行而且阻塞在对A的请求上.Q释放B和Ａ。当P重新开始执行的时候，它将会能够获得两个资源。3.Q获得B，然后P获得和释放A.Q获得Ａ然后释放B和A.当P重新开始行的时候，它将会能够获得B。4.P获得Ａ然后Q获得B.P释放A.Q获得Ａ然后释放B.P获得B然后释放B。5.P获得，然后释放A.P获得B.Q执行而且阻塞在对Ｂ的请求上。Ｐ释放Ｂ。当Q重新开始执行的时候，,它将会能够获得两个资源。6.P获得Ａ而且释放Ａ然后获得并且释放B.当Q重新开始实行,它将会能够获得两个资源。６.３图６.３反映的情况不会发生死锁，请证明。证明：如果Q获得B和Ａ（在P之前请求Ａ）,那么Q能使用这些两类资源然后释放他们,允许Ａ进行。如果P在Q之前请求Ａ获得Ａ,然后Q最多能执行到请求Ａ然后被阻塞。然而,一旦P释放A，Q能进行。一旦Q释放B,Ａ能进行。６.４考虑下面的一个系统，当前不存在未满足的请求。可用r1r2r3r4当前分配最大需求仍然需求a计算每个进程仍然可能需要的资源，并填入标为“仍然需要”的列中。b系统当前是处于安全状态还是不安全状态，为什么。c系统当前是否死锁？为什么？d哪个进程（如果存在）是死锁的或可能变成死锁的？e如果Ｐ３的请求（0，1，0，0）到达，是否可以立即安全地同意该请求？在什么状态（死锁，安全，不安全）下可以立即同意系统剩下的全部请求？如果立即同意全部请求，哪个进程（如果有）是死锁的或可能变成死锁的？解：a.00000750662220020320b.系统当前处于安全状态，因为至少有一个进程执行序列，不会导致死锁，运行顺序是p1,p4,p5,p2,p3.c.系统当前并没有死锁，因为P1进程当前分配与最大需求正好相等，P1进2100r1r2r3r4r1r2r3r4r1r2r3r40012001220002750003466562354435603320652程可以运行直至结束，接下来运行其他进程d.P2,P3,P4,P5可能死锁e.不可以，当进程P1,P4,P5执行完可用资源为（4，6，9，8），P2,P3将死锁，所以不安全，完全不可以立即同意系统剩下的全部请求。６.５请把６.４中的死锁检测算法应用于下面的数据，并给出结果。Available=(2100)20010010Request=1010Allocation=200121000120解：1.W=(2100)2.MarkP3;W=(2100)+(0120)=(2220)3.MarkP2;W=(2220)+(2001)=(4221)4.MarkP1;nodeadlockdetected没有死锁６.６一个假脱机系统包含一个输入进程Ｉ，用户进程进程Ｐ和一个输出进程Ｏ，它们之间用两个缓冲区连接。进程以相等大小的块为单位交换数据，这些块利用输入缓冲区和输出缓冲区之间的移动边界缓存在磁盘上，并取决于进程的速度。所使用的通信原语确保满足下面的资源约束：i+o≤max其中，max表示磁盘中的最大块数，i表示磁盘中的输入块数目，o表示磁盘中的输出块数目。以下是关于进程的知识：１.只要环境提供数据，进程Ｉ最终把它输入到磁盘上（只要磁盘空间可用）。２.只要磁盘可以得到输入，进程Ｐ最终消耗掉它，并在磁盘上为每个输入块输出有限量的数据（只要磁盘空间可用）。３.只要磁盘可以得到输出，进程Ｏ最终消耗掉它。说明这个系统可能死锁。解：当I的速度远大于P的速度，有可能使磁盘上都是输入数据而此时P进程要处理输入数据，即要将处理数据放入输出数据区。于是P进程等待磁盘空间输出，I进程等待磁盘空间输入，二者死锁。６.７给出在习题６.６中预防死锁的附加资源约束，仍然通话输入和输出缓冲区之间的边界可以根据进程的要求变化。I输入缓冲区P输出缓冲区o解：为输出缓冲区保留一个最小数目(称为reso)块,但是当磁盘空间足够大时允许输出块的数目超过这一个界限。资源限制现在变成Ｉ+Ｏ≤maxＩ≤max–reso当0resomax如果程序P正在等候递送输出给磁盘,程序O最后处理所有的早先输出而且产生至少reso页,然后让P继续执行。因此P不会因为O而延迟。如果磁盘充满I/O，Ｉ能被延迟;但是迟早,所有的早先的输入可以被Ｐ处理完，而且对应的输出将会被O处理,因而可以让Ｉ继续执行。６.８在ＴＨＥ多道程序设计系统中，一个磁鼓（磁盘的先驱，用做辅存）被划分为输入缓冲区，处理和输出缓冲区，它们的边界可以移动，这取决于所涉及的进程速度。磁鼓的当前状态可以用以下参数描述：max表示磁鼓中的最大页数，i示磁鼓中的输入页数，p示磁鼓中的处理页数，o示磁鼓中的输出页数，reso出保留的最小页数，resp理保留的最小页数。解：Ｉ+Ｏ+Ｐ≤max–Ｉ+Ｏ≤max–respＩ+Ｐ≤max–resoＩ≤max–(reso+resp)６．９在ＴＨＥ多道程序设计系统中，一页可以进行下列状态转换：１.空→输入缓冲区（输入生产）２.输入缓冲区→处理区域（输入消耗）３.处理区域→输出缓冲区（输出生产）４.输出缓冲区→空（输出生产）５.空→处理区域（输出消耗）６.处理区域→空（过程调用）a根据Ｉ，Ｏ和Ｐ的量定义这些转换的结果。b如果维持习题６.６中关于输入进程，用户进程和输出进程的假设，它们中的任何一个转换是否会导致死锁。解：1.i←i+12.i←i–1;p←p+13.p←p–1;o←o+14.o←o–15.p←p+16.p←p–1b.结合在对问题6.7的解决办法被列出的资源限制,我们能总结下列各项:6.过程返回能立刻发生因为他们只释放资源。5.程序调用可能用尽磁盘片(p=max–reso)导致死锁。4.当有输出时输出消耗能立刻发生。3.输出生产能暂时被延迟直到所有的早先输出被消耗而且为下一步的输出至少可以产生reso页。2.只要有输入，输入消耗能立刻发生。1.输入生产被延迟直到所有先前输入和对应的输出已经被消耗。此时,当i=o=0,如果消费进程还没有占用完磁盘空间(pmax–reso)，可以产生输入。结论:分配给消费进程的不受控制的存储空间是唯一可能引发死锁的因素。６.１０考虑一个共有１５０个存储器单元的系统，其单元如下分配三个进程：进程最大占用170452604036015使用银行家算法，以确定同意下面的任何一个请求是否安全。如果安全，说明能保证的终止序列；如果不安全，给出结果分配简表。a．第４个进程到达，最多需要６０个存储单元，最初需要２５个单元。b第４个进程到达，最多需要６０个存储单元，最初需要３５个单元。解：a.若同意第4个进程请求，则储存器单元共用去25＋15＋40＋45=125个单元，还有25个存储单元，则可以安全执行全部进程。安全顺序是1－2－3－4b.若同意第4个进程请求，则还有15个资源可以用，此时处于不安全状态，结果分配见表进程最大占有需要空闲170452515260402036015454603525６.１１评价独家算法在实际应用中是否有用。解：不切实际的:不能总是预先知道最大要求,进程数目和资源数目可能随着时间改变。大多数的操作系统忽视死锁。６.１２有一个已经实现了的管道算法，使得进程Ｐ０产生的Ｔ类型的数据元素经进程序列Ｐ1Ｐ2…Ｐn-1,并且按该顺序在元素上操作。a.定义一个一般的消息缓冲区，包含所有部分消耗的数据元素，并按下面的格式为进程Ｐi(0≤i≤n-1)写一个算法。Repeat从前驱接收消耗给后续发送Forever假设Ｐ0收到Ｐn-1发送的空元素。该算法能够使进程直接在缓冲区中保存的消息上操作，而无需复制。b.说明关于普通的缓冲区进程不会死锁。解：arbuffer:array0..max-1ofsharedT;available:sharedarray0..n-1of0..max;InitializationvarK:1..n-1;regionavailabledobeginavailable(0):=max;foreverykdoavailable(k):=0;endProcessivarj:0..max-1;succ:0..n-1;beginj:=0;succ:=(i+1)modn;repeatregionavailabledoawaitavailable(i)0;regionbuffer(j)doconsumeelement;regionavailabledobeginavailable(i):=available(i)–1;available(succ):=available(succ)+1;endj:=(j+1)modmax;foreverendb.死锁可以被解决通过P0waitsforPn-1ANDP1waitsforP0AND.....Pn-1waitsforPn-2因为(available(0)=0)AND(available(1)=0)AND.....(available(n-1)=0)但是如果max0,这个条件不成立，因为临界域满足claim(1)+claim(2)+…+claim(n)available(1)+available(2)+…+available(n)=max６.１３a.３个进程共享４个资源单元，一次只能保留或释放一个单元。每个进程最大需要２个单元。说明不会死锁。b.Ｎ个进程共享Ｍ个资源单元，一次只能保留或释放一个单元。每个进程最大需要单元数不超过Ｍ，并且所有最大需求的总和小于Ｍ+Ｎ。说明不会发生死锁。解：a.说明由于每个进程最多需要2个资源，最坏情况下，每个进程需要获得一个，系统还剩1个，这一个资源，无论分给谁都能完成。完成进程释放资源后，使剩余进程也完成，故系统不会死锁。b.假定每个进程最多申请X个资源，最坏情况下，每个进程都得到X-1个资源都在申请最后一个资源，这时系统剩余资源数量为M-N(X－1)，只要系统还有一个剩余资源，就可以使其中的一个进程获得所需要的全部资源，该进程运行结束以后释放资源，就可以使其他进程得到全部资源的满足，因此，当M-N(X-1)》1时系统不会发生死锁，解这个不等式X《（M+N-1）,系