操作系统第七章翻译

第七章翻译第七组黄常君周妮7.1Listthreeexamplesofdeadlocksthatarenotrelatedtoacomputersystemenvironment.列出三个与一个计算机系统环境不相关的死锁的例子。Answer:•Twocarscrossingasingle-lanebridgefromoppositedirections.两辆车从相反的方向跨越单线桥.•Apersongoingdownaladderwhileanotherpersonisclimbinguptheladder.当一个人下梯子时另一个人在爬上梯子。•Twotrainstravelingtowardeachotheronthesametrack.两列火车朝向对方同样的赛道驶来。•Twocarpenterswhomustpoundnails.Thereisasinglehammerandasinglebucketofnails.Deadlockoccursifonecarpenterhasthehammerandtheothercarpenterhasthenails.有两位木匠必须钉钉子。现在有一个单一的锤子和一桶钉子。如果一个木匠只分得一把锤子,而另一个木匠只能得钉子。那么就发生了死锁。7.2Supposethatasystemisinanunsafestate.Showthatitispossiblefortheprocessestocompletetheirexecutionwithoutenteringadeadlockstate.假设一个系统是在一个不安全的状态。说明这可能是一个进程完成地执行而没有进入一个死锁状态。Answer:Anunsafestatemaynotnecessarilyleadtodeadlock,itjustmeansthatwecannotguaranteethatdeadlockwillnotoccur.Thus,itispossiblethatasysteminanunsafestatemaystillallowallprocessestocompletewithoutdeadlockoccurring.Considerthesituationwhereasystemhas12resourcesallocatedamongprocessesP0,P1,andP2.Theresourcesareallocatedaccordingtothefollowingpolicy:答案：一个不安全的状态不一定导致死锁,它仅仅意味着我们不能保证死锁不会再次发生。因此,可能是一个系统在一个不安全的状态还可以让所有的进程完成而没有死锁发生。考虑到这样的情况，一个系统有12个资源要分配给进程P0，P1和P2。资源按照以下政策分配:MaxCurrentNeed当前的最大的需求P01055P1422P293622Chapter7Deadlocks第七章死锁for(inti=0;in;i++){//firstfindathreadthatcanfinishfor(intj=0;jn;j++){if(!finish[j]){booleantemp=true;for(intk=0;km;k++){if(need[j][k]work[k])temp=false;}if(temp){//ifthisthreadcanfinishfinish[j]=true;for(intx=0;xm;x++)work[x]+=work[j][x];}}}}Figure7.1Banker’salgorithmsafetyalgorithm.银行家算法的安全算法Currentlytherearetworesourcesavailable.ThissystemisinanunsafestateasprocessP1couldcomplete,therebyfreeingatotaloffourresources.ButwecannotguaranteethatprocessesP0andP2cancomplete.However,itispossiblethataprocessmayreleaseresourcesbeforerequestinganyfurther.Forexample,processP2couldreleasearesource,therebyincreasingthetotalnumberofresourcestofive.ThisallowsprocessP0tocomplete,whichwouldfreeatotalofnineresources,therebyallowingprocessP2tocompleteaswell.目前有两种资源。该系统是在一个不安全的状态，从而进程P1会完成然后释放一共有四个资源。但我们不能保证进程P0和P2可以完成。然而一个进程可能可以释放资源在其他进程请求更多资源之前。例如,进程P2可能释放一个资源,从而增加资源的总数量到五个。这允许进程P0完成,并将释放资源共计9项,从而允许P2也可以完成7.3ProvethatthesafetyalgorithmpresentedinSection7.5.3requiresanorderofm×n2operation.在7.5.3部分，证明安全算法，要求用一个米×n2的顺序操作Answer:Figure7.1providesJavacodethatimplementthesafetyalgorithmofthebanker’salgorithm(thecompleteimplementationofthebanker’salgorithmisavailablewiththesourcecodedownload).Ascanbeseen,thenestedouterloops—bothofwhichloopthroughntimes—providethen2performance.Withintheseouterloopsaretwosequentialinnerloopswhichloopmtimes.Thebig-ohofthisalgorithmisthereforeO(m×n2).答案：图7.1提供Java代码的安全算法,实现的银行家的算法(银行的完全实现算法可提供源代码下载)。可以看出,嵌套的外部loops-both循环n次——提高n2的性能。在这些外环是两个内部循环,连续循环m次。这种算法是big-oh的，因此,O(m×n2)。7.4Consideracomputersystemthatruns5,000jobspermonthwithnodeadlock-preventionordeadlock-avoidancescheme.Deadlocksoccurabouttwiceperamonth,andtheoperatormustterminateandrerunabout10jobsperdeadlock.Eachjobisworthabout$2(inCPUtime),andthejobsterminatedtendtobeabouthalf-donewhentheyareaborted.Asystemsprogrammerhasestimatedthatadeadlock-avoidancealgorithm(likethebanker’salgorithm)couldbeinstalledinthesystemwithanincreaseintheaverageexecutiontimeperjobofabout10percent.Sincethemachinecurrentlyhas30-percentidletime,all5,000jobspermonthcouldstillberun,althoughturnaroundtimewouldincreasebyabout20percentonaverage.考虑一个电脑系统运行5000个作业,每月没有死锁预防或死锁避免方案。死锁每月就会发生两次,操作人员一定要终止和重新运行10作业的死锁。每个作业值约$2(CPU时间)，当运行到一半失败时作业往往会终止。一个系统程序员估计,有一个死锁避免算法(如银行家的算法)可以在系统上安装，增加平均每工作执行时间的10%左右。由于这台机器目前有30%的空闲时间,全部的5000个作业每个月仍然可以运行,尽管转机时间将会增加大约20%的平均水平。PracticeExercises23练习活动23a.Whataretheargumentsforinstalling安装thedeadlock-avoidancealgorithm?a.安装死锁避免算法的理由是什么?b.Whataretheargumentsagainstinstallingthedeadlock-avoidancealgorithm?b.有什么理由反对安装死锁避免算法?Answer:Anargumentforinstallingdeadlockavoidanceinthesystemisthatwecouldensuredeadlockwouldneveroccur.Inaddition,despitetheincreaseinturnaroundtime,all5,000jobscouldstillrun.Anargumentagainstinstallingdeadlockavoidancesoftwareisthatdeadlocksoccurinfrequentlyandtheycostlittlewhentheydooccur.答案：一个观点,针对该系统安装的死锁是,我们可以确保死锁不会发生。此外,尽管周转时间增加,但所有的5000个作业仍能运行。安装死锁避免软件的理由是,避免死锁发生频繁,和消耗的资源会少些。7.5Canasystemdetectthatsomeofitsprocessesarestarving?Ifyouanswer“yes,”explainhowitcan.Ifyouanswer“no,”explainhowthesystemcandealwiththestarvationproblem.Answer:Starvationisadifficulttopictodefineasitmaymeandifferentthingsfordifferentsystems.Forthepurposesofthisquestion,wewilldefinestarvationasthesituationwherebyaprocessmustwaitbeyondareasonableperiodoftime—perhapsindefinitely—beforereceivingarequestedresource.Onewayofdetectingstarvationwouldbetofirstidentifyaperiodoftime—T—thatisconsideredunreasonable.Whenaprocessrequestsaresource,atimerisstarted.IftheelapsedtimeexceedsT,thentheprocessisconsideredtobestarved.Onestrategyfordealingwithstarvationwouldbetoadoptapolicywhereresourcesareassignedonlytotheprocessthathasbeenwaitingthelongest.Forexample,ifprocessPahasbeenwaitinglongerforresourceXthanprocessPb,therequestfromprocessPbw