王昊翔 操作系统ch03new

《王昊翔 操作系统ch03new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter3Deadlocks3.1.Resource3.2.Introductiontodeadlocks3.3.Theostrichalgorithm3.4.Deadlockdetectionandrecovery3.5.Deadlockavoidance3.6.Deadlockprevention3.7.Otherissues1Resources•Examplesofcomputerresources–printers–tapedrives–tables•Processesneedacc

2、esstoresourcesinreasonableorder•SupposeaprocessholdsresourceA(e.g.scanner)andrequestsresourceB(e.g.CDrecorder)–atsametimeanotherprocessholdsBandrequestsA–bothareblockedandremainso2Resources•Deadlocksoccurwhen…–processesaregrantedexclusiveaccesstodevic

3、es–werefertothesedevicesgenerallyasresources•Aresourceisanythingthatcanbeusedbyasingleprocessatanyinstantoftime.•Preemptableresources–canbetakenawayfromaprocesswithnoilleffects(e.g.memory)•Nonpreemptableresources–willcausetheprocesstofailiftakenaway(e

4、.g.CDrecorder)3Resources•Sequenceofeventsrequiredtousearesource1.requesttheresource2.usetheresource3.releasetheresource•Mustwaitifrequestisdenied–requestingprocessmaybeblocked–mayfailwitherrorcode4Resources•Associateasemaphorewitheachresource(Deadlock

5、-freeCode):typedefintsemaphore;semaphoreresource_1;semaphoreresource_2;voidprocess_A(void){voidprocess_B(void){down(resource_1);down(resource_1);down(resource_2);down(resource_2);use_both_resources();use_both_resources();up(resource_2);up(resource_2);

6、up(resource_1);up(resource_1);}}5IntroductiontoDeadlocks•Formaldefinition:Asetofprocessesisdeadlockedifeachprocessinthesetiswaitingforaneventthatonlyanotherprocessinthesetcancause•Usuallytheeventisreleaseofacurrentlyheldresource•Noneoftheprocessescan…

7、–run–releaseresources–beawakened6FourConditionsforDeadlock1.Mutualexclusioncondition•eachresourceassignedto1processorisavailable2.Holdandwaitcondition•processholdingresourcescanrequestadditional3.Nopreemptioncondition•previouslygrantedresourcescannotf

8、orciblytakenaway4.Circularwaitcondition•mustbeacircularchainof2ormoreprocesses•eachiswaitingforresourceheldbynextmemberofthechain7DeadlockModeling•Modeledwithdirectedgraphs–resourceRassignedtoprocessA–processBisrequesting/waitingforresourceS–p