资源描述：
《北邮操作系统课件CH07-deadlock》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Chapter7DeadlocksLIWensheng,SCST,BUPTTeachinghours:4hStrongpoint:DeadlockCharacterizationMethodsforHandlingDeadlocksDeadlockPrevention,AvoidanceandDetectionChapterObjectives¢Todevelopadescriptionofdeadlocks,whichpreventsetsofconcurrentprocessesfromcompletingtheirtasks¢Topr
2、esentanumberofdifferentmethodsforpreventingoravoidingdeadlocksinacomputersystem.WenshengLiBUPT2ContentsDeadlockmodel?7.1SystemModel7.2DeadlockCharacterization7.3MethodsforHandlingDeadlocks7.4DeadlockPrevention7.5DeadlockAvoidance7.6DeadlockDetection7.7RecoveryfromDeadlockW
3、enshengLiBUPT37.1SystemModel¢ResourcetypesR,R,...,R12mCPUs,CPUcycles,memoryspace,files,I/Odevices(printers)¢Theresourcesmaybeeitherphysicalresourcesorlogicalresources.¢EachresourcetypeRhasWinstances.ii¢Eachprocessutilizesaresourceasfollows:–request–use–ReleaseWenshen¢Asyst
4、emtablerecordswhethereachresourceisfreegLiBUPorallocated,andifaresourceisallocated,towhichprocess.T47.2DeadlockCharacterization¢Mutualexclusion:onlyoneprocessatatimecanusearesource.¢Holdandwait:aprocessholdingatleastoneresourceiswaitingtoacquireadditionalresourcesheldbyoth
5、erprocesses.¢Nopreemption:aresourcecanbereleasedonlyvoluntarilybytheprocessholdingit,afterthatprocesshascompleteditstask.¢Circularwait:thereexistsaset{P,P,…,P}ofwaiting010processessuchthatPiswaitingforaresourcethatisheldby0P,PiswaitingforaresourcethatisheldbyP,…,Pis112n–1w
6、aitingforaresourcethatisheldbyP,andPiswaitingforannresourcethatisheldbyP.0Wenshen¢AdeadlocksituationcanariseiftheabovefourconditionsgLiBUPholdsimultaneously.T5Resource-AllocationGraph¢DeadlockcanbedescribedintermsofaSystemresource-allocationgraph–Directedgraph–Asetofvertic
7、esVandasetofedgesE.¢Vispartitionedintotwodifferenttypes:–P={P,P,…,P},thesetconsistingofalltheprocesses12ninthesystem.–R={R,R,…,R},thesetconsistingofallresourcetypes12minthesystem.¢Eisclassedintotwodifferenttypes:–requestedge–directededgeP→RProcessPij,irequestedaninstanceof
8、resourcetypeR,andisjWenshencurrentlywaitingforthatresource.–assignmentedge–directededgeR→
