操作系統(tǒng)課件第三章2

1、Operating SystemOperating SystemPage 12022-4-29Operating SystemOperating Systemq處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 q調(diào)度算法調(diào)度算法 q實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度 q多處理機(jī)系統(tǒng)中的調(diào)度多處理機(jī)系統(tǒng)中的調(diào)度q產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件 q預(yù)防死鎖的方法預(yù)防死鎖的方法 q死鎖的檢測(cè)與解除死鎖的檢測(cè)與解除Page 22022-4-29Operating SystemOperating Systemq死鎖的基本概念死鎖的基本概念q產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因q產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件q處理

2、死鎖的基本方法處理死鎖的基本方法Page 32022-4-29Operating SystemOperating Systemq 死鎖例子死鎖例子v一個(gè)由于申請(qǐng)不同類型資源而產(chǎn)生死一個(gè)由于申請(qǐng)不同類型資源而產(chǎn)生死鎖的例子鎖的例子v設(shè)系統(tǒng)有一臺(tái)打印機(jī)設(shè)系統(tǒng)有一臺(tái)打印機(jī)(R1)(R1)一臺(tái)掃描儀一臺(tái)掃描儀(R2)(R2)，兩進(jìn)程共享這兩臺(tái)設(shè)備。，兩進(jìn)程共享這兩臺(tái)設(shè)備。v用信號(hào)量用信號(hào)量S1S1表示表示R1R1是否可用，用信號(hào)是否可用，用信號(hào)量量S2S2表示表示R2R2是否可用，是否可用，S1S1、S2S2初值為初值為1 1。Page 42022-4-29Operating SystemOperat

3、ing System這兩個(gè)進(jìn)程在并發(fā)執(zhí)行過程中，可能會(huì)發(fā)生死鎖。這兩個(gè)進(jìn)程在并發(fā)執(zhí)行過程中，可能會(huì)發(fā)生死鎖。大家可以思考一下，如何修改，進(jìn)程才不會(huì)發(fā)生大家可以思考一下，如何修改，進(jìn)程才不會(huì)發(fā)生死鎖？死鎖？Page 52022-4-29Operating SystemOperating Systemq 死鎖的概念死鎖的概念v指指多個(gè)進(jìn)程多個(gè)進(jìn)程因因競(jìng)爭(zhēng)共享資源競(jìng)爭(zhēng)共享資源而造成的而造成的一種一種僵局僵局，若無(wú)外力作用，這些進(jìn)程，若無(wú)外力作用，這些進(jìn)程都將永遠(yuǎn)不能再向前推進(jìn)。都將永遠(yuǎn)不能再向前推進(jìn)。v即：一組進(jìn)程中，每個(gè)進(jìn)程都即：一組進(jìn)程中，每個(gè)進(jìn)程都無(wú)限等無(wú)限等待待被該組進(jìn)程中被該組進(jìn)程中另一進(jìn)

4、程所占有的資另一進(jìn)程所占有的資源源，因而永遠(yuǎn)無(wú)法得到的資源，這種，因而永遠(yuǎn)無(wú)法得到的資源，這種現(xiàn)象稱為進(jìn)程死鎖，這一組進(jìn)程就稱現(xiàn)象稱為進(jìn)程死鎖，這一組進(jìn)程就稱為死鎖進(jìn)程。為死鎖進(jìn)程。Page 62022-4-29Operating SystemOperating Systemq 關(guān)于死鎖的一些結(jié)論關(guān)于死鎖的一些結(jié)論v參與死鎖的進(jìn)程參與死鎖的進(jìn)程最少是兩個(gè)最少是兩個(gè) v參與死鎖的進(jìn)程參與死鎖的進(jìn)程至少有兩個(gè)已經(jīng)占有至少有兩個(gè)已經(jīng)占有資源資源v參與死鎖的所有進(jìn)程參與死鎖的所有進(jìn)程都在等待資源都在等待資源v參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)進(jìn)程的子集程的子集注：注：如果死

5、鎖發(fā)生，會(huì)浪費(fèi)大量系統(tǒng)資源，如果死鎖發(fā)生，會(huì)浪費(fèi)大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰。甚至導(dǎo)致系統(tǒng)崩潰。Page 72022-4-29Operating SystemOperating Systemq 永久性資源和臨時(shí)性資源永久性資源和臨時(shí)性資源v永久性資源：可以被多個(gè)進(jìn)程多次使用（可永久性資源：可以被多個(gè)進(jìn)程多次使用（可再用資源）再用資源）可搶占資源：可搶占資源：CPUCPU不可搶占資源：打印機(jī)不可搶占資源：打印機(jī)v臨時(shí)性資源：只可使用一次的資源；即由一臨時(shí)性資源：只可使用一次的資源；即由一個(gè)進(jìn)程產(chǎn)生，被另一進(jìn)程使用后就再也無(wú)用個(gè)進(jìn)程產(chǎn)生，被另一進(jìn)程使用后就再也無(wú)用的資源，也稱為的資源，也稱為消耗

6、性資源消耗性資源 如信號(hào)量如信號(hào)量, ,中斷信號(hào)，同步信號(hào)等（可消耗中斷信號(hào)，同步信號(hào)等（可消耗性資源）性資源）“申請(qǐng)申請(qǐng)-分配分配-使用使用-釋放釋放”模式模式Page 82022-4-29Operating SystemOperating Systemq死鎖的基本概念死鎖的基本概念q產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因q產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件q處理死鎖的基本方法處理死鎖的基本方法Page 92022-4-29Operating SystemOperating System3.5 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件3.5.1 產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因 競(jìng)爭(zhēng)資源。競(jìng)爭(zhēng)資

7、源。當(dāng)系統(tǒng)中供多個(gè)進(jìn)程所共享的資源，不足以同時(shí)滿足它們的需要時(shí)，引起它們對(duì)資源的競(jìng)爭(zhēng)而產(chǎn)生死鎖。 (2) 進(jìn)程間推進(jìn)順序非法。進(jìn)程間推進(jìn)順序非法。 進(jìn)程在運(yùn)行過程中，請(qǐng)求和釋放資源的順序不當(dāng)，導(dǎo)致了進(jìn)程死鎖。 所謂死鎖（Deadlock），是指多個(gè)進(jìn)程因競(jìng)爭(zhēng)資源而造成的一種僵局，若無(wú)外力作用，這些進(jìn)程都將永遠(yuǎn)不能再向前推進(jìn)。 Page 102022-4-29Operating SystemOperating Systemq 競(jìng)爭(zhēng)資源引起進(jìn)程死鎖競(jìng)爭(zhēng)資源引起進(jìn)程死鎖v可剝奪和非剝奪性資源可剝奪和非剝奪性資源 可剝奪性資源可剝奪性資源是指進(jìn)程在獲得這類資源后，是指進(jìn)程在獲得這類資源后，該資源該資源

8、可以再被可以再被其他進(jìn)程或系統(tǒng)其他進(jìn)程或系統(tǒng)剝奪剝奪，如，如處處理機(jī)、內(nèi)存理機(jī)、內(nèi)存等等非剝奪性資源非剝奪性資源是指當(dāng)系統(tǒng)把這類資源分配給是指當(dāng)系統(tǒng)把這類資源分配給某個(gè)進(jìn)程后，某個(gè)進(jìn)程后，再不能強(qiáng)行收回再不能強(qiáng)行收回，只能在進(jìn)程，只能在進(jìn)程用完后自行釋放，如磁帶機(jī)、打印機(jī)等用完后自行釋放，如磁帶機(jī)、打印機(jī)等v競(jìng)爭(zhēng)非剝奪性資源競(jìng)爭(zhēng)非剝奪性資源 系統(tǒng)中的系統(tǒng)中的非剝奪性資源非剝奪性資源由于數(shù)量有限而不能由于數(shù)量有限而不能滿足進(jìn)程運(yùn)行的需要，進(jìn)程在運(yùn)行過程中因滿足進(jìn)程運(yùn)行的需要，進(jìn)程在運(yùn)行過程中因爭(zhēng)奪這些資源而限入僵局爭(zhēng)奪這些資源而限入僵局v競(jìng)爭(zhēng)臨時(shí)性資源競(jìng)爭(zhēng)臨時(shí)性資源 Page 112022-4-

9、29Operating SystemOperating SystemI/O設(shè)設(shè)備備共共享享時(shí)時(shí)的的死死鎖鎖情情況況 若系統(tǒng)中只有一臺(tái)打印機(jī)若系統(tǒng)中只有一臺(tái)打印機(jī)R1R1和一臺(tái)讀卡機(jī)和一臺(tái)讀卡機(jī)R2R2，可，可供進(jìn)程供進(jìn)程P1P1和和P2P2共享。若共享。若形成環(huán)路形成環(huán)路，這樣會(huì)產(chǎn)生死鎖。，這樣會(huì)產(chǎn)生死鎖。R1R2P1P2分配分配分配分配請(qǐng)求請(qǐng)求請(qǐng)求請(qǐng)求Page 122022-4-29Operating SystemOperating System 進(jìn)程之間通信時(shí)的死鎖進(jìn)程之間通信時(shí)的死鎖 S2P1S3P3S1P2產(chǎn)生產(chǎn)生P2P2產(chǎn)生產(chǎn)生P3P3產(chǎn)生產(chǎn)生要求接收要求接收要求接收要求接收要求接收

10、要求接收Page 132022-4-29Operating SystemOperating Systemq進(jìn)程推進(jìn)順序不當(dāng)引起死鎖進(jìn)程推進(jìn)順序不當(dāng)引起死鎖P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2) P1Rel(R1) P1Rel(R2)D不安全區(qū)Page 142022-4-29Operating SystemOperating Systemq若并發(fā)進(jìn)程若并發(fā)進(jìn)程P P1 1和和P P2 2按曲線按曲線所示的順序推所示的順序推進(jìn)，它們將進(jìn)入不安全區(qū)進(jìn)，它們將進(jìn)入不安全區(qū)D D內(nèi)。此時(shí)內(nèi)。此時(shí)P P1 1保保持了資源持了資源R R1

11、 1, P, P2 2保持了資源保持了資源R R2 2, , 系統(tǒng)處于系統(tǒng)處于不安全狀態(tài)。因?yàn)?，這時(shí)兩進(jìn)程再向前不安全狀態(tài)。因?yàn)?，這時(shí)兩進(jìn)程再向前推進(jìn)，便可能發(fā)生死鎖。推進(jìn)，便可能發(fā)生死鎖。q例如，當(dāng)例如，當(dāng)P P1 1運(yùn)行到運(yùn)行到P P1 1:Request(R:Request(R2 2) )時(shí)，將時(shí)，將因因R R2 2已被已被P P2 2占用而阻塞；當(dāng)占用而阻塞；當(dāng)P P2 2運(yùn)行到運(yùn)行到P P2 2: : Request(RRequest(R1 1) )時(shí)，也將因時(shí)，也將因R R1 1已被已被P P1 1占用而占用而阻塞，于是發(fā)生了進(jìn)程死鎖阻塞，于是發(fā)生了進(jìn)程死鎖Page 152022-

12、4-29Operating SystemOperating Systemq死鎖的基本概念死鎖的基本概念q產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因q產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件q處理死鎖的基本方法處理死鎖的基本方法Page 162022-4-29Operating SystemOperating Systemq 互斥條件互斥條件 v進(jìn)程對(duì)所分配到的資源進(jìn)行進(jìn)程對(duì)所分配到的資源進(jìn)行排它性的使用排它性的使用q 請(qǐng)求和保持條件請(qǐng)求和保持條件 v進(jìn)程已經(jīng)至少進(jìn)程已經(jīng)至少保持了一個(gè)保持了一個(gè)資源，但又提出了資源，但又提出了新的資源新的資源請(qǐng)求請(qǐng)求，而該資源又已被其他進(jìn)程占，而該資源又已被其他進(jìn)程占有有q 不剝

13、奪條件不剝奪條件 v進(jìn)程已獲得的資源在未使用完之前不能被剝進(jìn)程已獲得的資源在未使用完之前不能被剝奪奪q 環(huán)路等待條件環(huán)路等待條件v在發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程在發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程-資源循資源循環(huán)等待的環(huán)形鏈環(huán)等待的環(huán)形鏈Page 172022-4-29Operating SystemOperating Systemq死鎖的基本概念死鎖的基本概念q產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因q產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件q處理死鎖的基本方法處理死鎖的基本方法Page 182022-4-29Operating SystemOperating Systemq 預(yù)防死鎖預(yù)防死鎖q 避免死鎖避免死鎖

14、q 檢測(cè)死鎖檢測(cè)死鎖q 解除死鎖解除死鎖Page 192022-4-29Operating SystemOperating System3.5.3 處理死鎖的基本方法處理死鎖的基本方法 目前用于處理死鎖的方法可歸結(jié)為以下四種：1、預(yù)防死鎖、預(yù)防死鎖 通過設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或幾個(gè)條件，來(lái)防止發(fā)生死鎖。2、避免死鎖、避免死鎖 不須采用各種限制措施去破壞產(chǎn)生死鎖的必要條件，防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免發(fā)生死鎖，只需在事先加以較弱的限制條件。3、檢測(cè)死鎖、檢測(cè)死鎖 不須檢查系統(tǒng)是否已進(jìn)入不安全區(qū)，允許系統(tǒng)在運(yùn)行過程中發(fā)生死鎖。4、 解除死鎖解除死鎖 常用的實(shí)施方

15、法是撤消或掛起一些進(jìn)程，以便回收一些資源，再將這些資源分配給已處于阻塞狀態(tài)的進(jìn)程，使之轉(zhuǎn)為就緒狀態(tài)，以繼續(xù)運(yùn)行。Page 202022-4-29Operating SystemOperating System方法方法資源分配策略資源分配策略各種可能模式各種可能模式 主要優(yōu)點(diǎn)主要優(yōu)點(diǎn)主要缺點(diǎn)主要缺點(diǎn)預(yù)防預(yù)防Prevention保守的；寧可資保守的；寧可資源閑置（從機(jī)制源閑置（從機(jī)制上使死鎖條件不上使死鎖條件不成立，即摒棄三成立，即摒棄三個(gè)必要條件）個(gè)必要條件）一次請(qǐng)求所有一次請(qǐng)求所有資源資源適用于作突發(fā)式處理的適用于作突發(fā)式處理的進(jìn)程；不必剝奪進(jìn)程；不必剝奪效率低；進(jìn)程初始化效率低；進(jìn)程初始化時(shí)

16、間延長(zhǎng)時(shí)間延長(zhǎng)剝奪次數(shù)過多；多次剝奪次數(shù)過多；多次對(duì)資源重新起動(dòng)對(duì)資源重新起動(dòng)不便靈活申請(qǐng)新資源不便靈活申請(qǐng)新資源資源剝奪資源剝奪適用于狀態(tài)可以保存和適用于狀態(tài)可以保存和恢復(fù)的資源恢復(fù)的資源資源資源按序申請(qǐng)按序申請(qǐng)避免避免Avoidance是是“預(yù)防預(yù)防”和和“檢測(cè)檢測(cè)”的折衷的折衷（在運(yùn)行時(shí)判斷（在運(yùn)行時(shí)判斷是否可能死鎖）是否可能死鎖）尋找可能的安尋找可能的安全的運(yùn)行順序全的運(yùn)行順序 不必進(jìn)行剝奪不必進(jìn)行剝奪使用條件：必須知道使用條件：必須知道將來(lái)的資源需求；進(jìn)將來(lái)的資源需求；進(jìn)程可能會(huì)長(zhǎng)時(shí)間阻塞程可能會(huì)長(zhǎng)時(shí)間阻塞檢測(cè)檢測(cè)Detection寬松的；只要允寬松的；只要允許，就分配資源許，就分配

17、資源定期檢查死鎖定期檢查死鎖是否已經(jīng)發(fā)生是否已經(jīng)發(fā)生不延長(zhǎng)進(jìn)程初始化時(shí)間；不延長(zhǎng)進(jìn)程初始化時(shí)間；允許對(duì)死鎖進(jìn)行現(xiàn)場(chǎng)處允許對(duì)死鎖進(jìn)行現(xiàn)場(chǎng)處理理通過剝奪解除死鎖，通過剝奪解除死鎖，造成損失造成損失可以在編譯時(shí)（而不必可以在編譯時(shí)（而不必在運(yùn)行時(shí)）就進(jìn)行檢查在運(yùn)行時(shí)）就進(jìn)行檢查Page 212022-4-29Operating SystemOperating Systemq處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 q調(diào)度算法調(diào)度算法 q實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度 q多處理機(jī)系統(tǒng)中的調(diào)度多處理機(jī)系統(tǒng)中的調(diào)度q產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件 q預(yù)防死鎖的方法預(yù)防死鎖的方法 q死鎖的檢測(cè)與解除死鎖

18、的檢測(cè)與解除Page 222022-4-29Operating SystemOperating Systemq預(yù)防死鎖預(yù)防死鎖q系統(tǒng)安全狀態(tài)系統(tǒng)安全狀態(tài)q利用銀行家算法避免死鎖利用銀行家算法避免死鎖Page 232022-4-29Operating SystemOperating Systemq 互斥條件互斥條件 v進(jìn)程對(duì)所分配到的資源進(jìn)行進(jìn)程對(duì)所分配到的資源進(jìn)行排它性的使用排它性的使用q 請(qǐng)求和保持條件請(qǐng)求和保持條件 v進(jìn)程已經(jīng)至少進(jìn)程已經(jīng)至少保持了一個(gè)保持了一個(gè)資源，但又提出了資源，但又提出了新的資源新的資源請(qǐng)求請(qǐng)求，而該資源又已被其他進(jìn)程占，而該資源又已被其他進(jìn)程占有有q 不剝奪條件不剝

19、奪條件 v進(jìn)程已獲得的資源在未使用完之前不能被剝進(jìn)程已獲得的資源在未使用完之前不能被剝奪奪q 環(huán)路等待條件環(huán)路等待條件v在發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程在發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程-資源循資源循環(huán)等待的環(huán)形鏈環(huán)等待的環(huán)形鏈Page 242022-4-29Operating SystemOperating Systemq 摒棄摒棄“請(qǐng)求和保持請(qǐng)求和保持”條件條件 v所有進(jìn)程在開始運(yùn)行之前必須所有進(jìn)程在開始運(yùn)行之前必須一次性的一次性的申請(qǐng)申請(qǐng)整個(gè)運(yùn)行過程所需的全部資源整個(gè)運(yùn)行過程所需的全部資源v簡(jiǎn)單、易于實(shí)現(xiàn)、安全簡(jiǎn)單、易于實(shí)現(xiàn)、安全v資源浪費(fèi)嚴(yán)重資源浪費(fèi)嚴(yán)重v進(jìn)程延遲運(yùn)行進(jìn)程延遲運(yùn)行Page 2

20、52022-4-29Operating SystemOperating Systemq摒棄摒棄“不剝奪不剝奪”條件條件 v進(jìn)程逐個(gè)地申請(qǐng)所需資源進(jìn)程逐個(gè)地申請(qǐng)所需資源v當(dāng)一個(gè)已經(jīng)保持了某些資源的進(jìn)程當(dāng)一個(gè)已經(jīng)保持了某些資源的進(jìn)程申請(qǐng)申請(qǐng)新資源而不能得到滿足時(shí)，必須放棄新資源而不能得到滿足時(shí)，必須放棄所所有已保持的資源有已保持的資源v實(shí)現(xiàn)復(fù)雜、代價(jià)高昂實(shí)現(xiàn)復(fù)雜、代價(jià)高昂v延長(zhǎng)了進(jìn)程的周轉(zhuǎn)時(shí)間，還增加了系統(tǒng)延長(zhǎng)了進(jìn)程的周轉(zhuǎn)時(shí)間，還增加了系統(tǒng)開銷，降低了系統(tǒng)的吞吐量開銷，降低了系統(tǒng)的吞吐量Page 262022-4-29Operating SystemOperating Systemq摒棄摒棄“環(huán)路

21、等待環(huán)路等待”條件條件v系統(tǒng)將所有資源按類型分配序號(hào)并排隊(duì)系統(tǒng)將所有資源按類型分配序號(hào)并排隊(duì)v所有進(jìn)程所有進(jìn)程申請(qǐng)申請(qǐng)資源必須資源必須按序號(hào)按序號(hào)遞增的順遞增的順序序v資源利用率和系統(tǒng)吞吐量較高資源利用率和系統(tǒng)吞吐量較高v但在資源管理和資源申請(qǐng)方面仍有問題但在資源管理和資源申請(qǐng)方面仍有問題Page 272022-4-29Operating SystemOperating System存在問題：資源的需求順序不等于存在問題：資源的需求順序不等于序號(hào)，仍存在資源浪費(fèi)。序號(hào)，仍存在資源浪費(fèi)。Page 282022-4-29Operating SystemOperating Systemq摒棄摒棄“環(huán)

22、路等待環(huán)路等待”條件條件q其資源利用率和系統(tǒng)吞吐量，都有較明顯其資源利用率和系統(tǒng)吞吐量，都有較明顯的改善，但也存在下述嚴(yán)重問題：的改善，但也存在下述嚴(yán)重問題：v（1）資源所分配的序號(hào)，必須相對(duì)穩(wěn)定，這）資源所分配的序號(hào)，必須相對(duì)穩(wěn)定，這就限制了新設(shè)備類型的增加。就限制了新設(shè)備類型的增加。v（2）進(jìn)程使用各資源的順序，與系統(tǒng)規(guī)定的）進(jìn)程使用各資源的順序，與系統(tǒng)規(guī)定的順序不同，造成對(duì)資源的浪費(fèi)。順序不同，造成對(duì)資源的浪費(fèi)。v（3）按規(guī)定次序申請(qǐng)資源的方法，必然會(huì)限）按規(guī)定次序申請(qǐng)資源的方法，必然會(huì)限制了用戶簡(jiǎn)單、自主地編程。制了用戶簡(jiǎn)單、自主地編程。 Page 292022-4-29Operati

23、ng SystemOperating System方法方法資源分配策略資源分配策略各種可能模式各種可能模式 主要優(yōu)點(diǎn)主要優(yōu)點(diǎn)主要缺點(diǎn)主要缺點(diǎn)預(yù)防預(yù)防Prevention保守的；寧可資保守的；寧可資源閑置（從機(jī)制源閑置（從機(jī)制上使死鎖條件不上使死鎖條件不成立，即摒棄三成立，即摒棄三個(gè)必要條件）個(gè)必要條件）一次請(qǐng)求所有一次請(qǐng)求所有資源資源適用于作突發(fā)式處理的適用于作突發(fā)式處理的進(jìn)程；不必剝奪進(jìn)程；不必剝奪效率低；進(jìn)程初始化效率低；進(jìn)程初始化時(shí)間延長(zhǎng)時(shí)間延長(zhǎng)剝奪次數(shù)過多；多次剝奪次數(shù)過多；多次對(duì)資源重新起動(dòng)對(duì)資源重新起動(dòng)不便靈活申請(qǐng)新資源不便靈活申請(qǐng)新資源資源剝奪資源剝奪適用于狀態(tài)可以保存和適用于狀

24、態(tài)可以保存和恢復(fù)的資源恢復(fù)的資源資源資源按序申請(qǐng)按序申請(qǐng)避免避免Avoidance是是“預(yù)防預(yù)防”和和“檢測(cè)檢測(cè)”的折衷的折衷（在運(yùn)行時(shí)判斷（在運(yùn)行時(shí)判斷是否可能死鎖）是否可能死鎖）尋找可能的安尋找可能的安全的運(yùn)行順序全的運(yùn)行順序 不必進(jìn)行剝奪不必進(jìn)行剝奪使用條件：必須知道使用條件：必須知道將來(lái)的資源需求；進(jìn)將來(lái)的資源需求；進(jìn)程可能會(huì)長(zhǎng)時(shí)間阻塞程可能會(huì)長(zhǎng)時(shí)間阻塞檢測(cè)檢測(cè)Detection寬松的；只要允寬松的；只要允許，就分配資源許，就分配資源定期檢查死鎖定期檢查死鎖是否已經(jīng)發(fā)生是否已經(jīng)發(fā)生不延長(zhǎng)進(jìn)程初始化時(shí)間；不延長(zhǎng)進(jìn)程初始化時(shí)間；允許對(duì)死鎖進(jìn)行現(xiàn)場(chǎng)處允許對(duì)死鎖進(jìn)行現(xiàn)場(chǎng)處理理通過剝奪解除死鎖，

25、通過剝奪解除死鎖，造成損失造成損失可以在編譯時(shí)（而不必可以在編譯時(shí)（而不必在運(yùn)行時(shí)）就進(jìn)行檢查在運(yùn)行時(shí)）就進(jìn)行檢查Page 302022-4-29Operating SystemOperating Systemq預(yù)防死鎖預(yù)防死鎖q系統(tǒng)安全狀態(tài)系統(tǒng)安全狀態(tài)q利用銀行家算法避免死鎖利用銀行家算法避免死鎖Page 312022-4-29Operating SystemOperating Systemq進(jìn)程推進(jìn)順序不當(dāng)引起死鎖進(jìn)程推進(jìn)順序不當(dāng)引起死鎖P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2) P1Rel(R1) P1Rel(R2)DPa

26、ge 322022-4-29Operating SystemOperating Systemq安全狀態(tài)安全狀態(tài)v在避免死鎖的方法中，允許進(jìn)程在避免死鎖的方法中，允許進(jìn)程動(dòng)態(tài)地動(dòng)態(tài)地申請(qǐng)申請(qǐng)資源，但系統(tǒng)在進(jìn)行資源分配之前，應(yīng)先計(jì)資源，但系統(tǒng)在進(jìn)行資源分配之前，應(yīng)先計(jì)算此次資源分配的安全性。若此次分配不會(huì)算此次資源分配的安全性。若此次分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)不安全狀態(tài)，則將資源分配給，則將資源分配給進(jìn)程；進(jìn)程； 否則，令進(jìn)程等待否則，令進(jìn)程等待v所謂所謂安全狀態(tài)安全狀態(tài)，是指系統(tǒng)能按某種進(jìn)程順序，是指系統(tǒng)能按某種進(jìn)程順序(P1, P2, (P1, P2, ，Pn)(Pn)(稱稱P

27、1, P2, , PnP1, P2, , Pn序序列為安全序列列為安全序列) )，來(lái)為每個(gè)進(jìn)程，來(lái)為每個(gè)進(jìn)程PiPi分配其所需分配其所需資源，直至滿足每個(gè)進(jìn)程對(duì)資源的最大需求，資源，直至滿足每個(gè)進(jìn)程對(duì)資源的最大需求，使每個(gè)進(jìn)程都可順利地完成。如果系統(tǒng)無(wú)法使每個(gè)進(jìn)程都可順利地完成。如果系統(tǒng)無(wú)法找到這樣一個(gè)安全序列，則稱系統(tǒng)處于找到這樣一個(gè)安全序列，則稱系統(tǒng)處于不安不安全狀態(tài)全狀態(tài)Page 332022-4-29Operating SystemOperating System 2. 安全狀態(tài)之例安全狀態(tài)之例 我們通過一個(gè)例子來(lái)說明安全性。假定系統(tǒng)中有三個(gè)進(jìn)程P1、 P2和P3，共有12臺(tái)磁帶機(jī)。進(jìn)

28、程P1總共要求10臺(tái)磁帶機(jī)，P2和P3分別要求4臺(tái)和9臺(tái)。假設(shè)在T0時(shí)刻，進(jìn)程P1、P2和P3已分別獲得5臺(tái)、2臺(tái)和2臺(tái)磁帶機(jī)，尚有3臺(tái)空閑未分配，如下表所示： 29P324P23510P1可 用 已 分 配 最 大 需 求 進(jìn) 程 41 5100109312存在安全序列：存在安全序列：P2-P1-P3，系統(tǒng)處于安全狀態(tài)。，系統(tǒng)處于安全狀態(tài)。Page 342022-4-29Operating SystemOperating System 3. 由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換 如果不按照安全序列分配資源，則系統(tǒng)可能會(huì)由安全狀態(tài)進(jìn)入不安全狀態(tài)。例如，在T0時(shí)刻以后，P3又

29、請(qǐng)求1臺(tái)磁帶機(jī)， 若此時(shí)系統(tǒng)把剩余3臺(tái)中的1臺(tái)分配給P3，則系統(tǒng)便進(jìn)入不安全狀態(tài)。3240 4不安全狀態(tài)Page 352022-4-29Operating SystemOperating Systemq預(yù)防死鎖預(yù)防死鎖q系統(tǒng)安全狀態(tài)系統(tǒng)安全狀態(tài)q利用銀行家算法避免死鎖利用銀行家算法避免死鎖Page 362022-4-29Operating SystemOperating System3.6.3 利用銀行家算法避免死鎖利用銀行家算法避免死鎖 1. 銀行家算法中的數(shù)據(jù)結(jié)構(gòu)銀行家算法中的數(shù)據(jù)結(jié)構(gòu) (1) 可利用資源向量可利用資源向量Available。這是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表

30、一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。如果Availablej = K，則表示系統(tǒng)中現(xiàn)有，則表示系統(tǒng)中現(xiàn)有Rj類資源類資源K個(gè)。個(gè)。 Page 372022-4-29Operating SystemOperating System (2) 最大需求矩陣最大需求矩陣Max。這是一個(gè)nm的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果Maxi,j = K，則表示進(jìn)程，則表示進(jìn)程i需要需要Rj類資源的最大數(shù)目為類資源的最大數(shù)目為K。 (3) 分配矩陣分配矩陣Allocation。這也是一個(gè)nm的矩陣，它定

31、義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocationi,j=K，表示進(jìn)程，表示進(jìn)程i當(dāng)前已分得當(dāng)前已分得Rj類資源的數(shù)目為類資源的數(shù)目為K。 (4) 需求矩陣需求矩陣Need。這也是一個(gè)nm的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果Needi,j = K，則表示進(jìn)程，則表示進(jìn)程i還需要還需要Rj類資源類資源K個(gè)，個(gè)，方能完成其任務(wù)。 Needi,j = Maxi,j Allocationi,j Page 382022-4-29Operating SystemOperating System 2. 銀行家算法銀行家算法 設(shè)Requesti是進(jìn)程Pi的請(qǐng)求向量，如果Re

32、questij = K，表示進(jìn)程Pi需要K個(gè)Rj類型的資源。當(dāng)Pi發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查： (1) 如果Requestij Needi,j，便轉(zhuǎn)向步驟(2)；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。 (2) 如果Requestij Availablej，便轉(zhuǎn)向步驟(3)；否則， 表示尚無(wú)足夠資源，Pi須等待。 Page 392022-4-29Operating SystemOperating System (3) 系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： Availablej := Availablej - Requestij; Alloc

33、ationi,j := Allocationi,j + Requestij; Needi,j := Needi,j - Requestij; (4) 系統(tǒng)執(zhí)行安全性算法安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來(lái)的資源分配狀態(tài)，讓進(jìn)程Pi等待。 Page 402022-4-29Operating SystemOperating System3. 安全性算法安全性算法 (1) 設(shè)置兩個(gè)向量： 工作向量Work: 它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有m個(gè)元素，在執(zhí)行安全算法開始時(shí)，

34、Work := Available; Finish: 它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)先做Finishi := false; 當(dāng)有足夠資源分配給進(jìn)程時(shí)， 再令Finishi := true。 Page 412022-4-29Operating SystemOperating System (2) 從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程： Finishi = false; Needi,j Workj； 若找到， 執(zhí)行步驟(3)， 否則，執(zhí)行步驟(4)。 (3) 當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行： Workj := Worki

35、 + Allocationi,j; Finishi := true; go to step 2; (4) 如果所有進(jìn)程的Finishi = true都滿足， 則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。 Page 422022-4-29Operating SystemOperating System4. 銀行家算法之例銀行家算法之例 假定系統(tǒng)中有五個(gè)進(jìn)程P0, P1, P2, P3, P4和三類資源A, B, C，各種資源的數(shù)量分別為10、5、7，在T0時(shí)刻的資源分配情況如圖 3-15 所示。 圖 3-15 T0時(shí)刻的資源分配表 2C3B11023C31024B21200C01001B3

36、2223C32025B404P4639P23707P0022P3123P1AAAAAvailableNeedAllocationMaxNeedi,j = Maxi,j Allocationi,j Page 432022-4-29Operating SystemOperating System(1) T0時(shí)刻的安全性： 圖 3-16 T0時(shí)刻的安全序列 truetruetruetruetrueFinish77532C54443B02210C10010B30112C40312B75322C44433B100710P07047P45213P110367P27205P3AAAAWork + Alloc

37、ationAllocationNeedWork存在安全序列：存在安全序列：P1-P3-P4-P2-P0，系統(tǒng)在系統(tǒng)在T0時(shí)刻處于安全狀態(tài)。時(shí)刻處于安全狀態(tài)。Page 442022-4-29Operating SystemOperating System (2) P1請(qǐng)求資源：P1發(fā)出請(qǐng)求向量Request1(1，0，2)，系統(tǒng)按銀行家算法進(jìn)行檢查： Request1(1, 0, 2)Need1(1, 2, 2) Request1(1, 0, 2)Available1(3, 3, 2)Page 452022-4-29Operating SystemOperating System 系統(tǒng)先假定可為

38、P1分配資源，并修改Available, Allocation1和Need1向量，由此形成的資源變化情況如圖 3-15 中的圓括號(hào)所示。 Request1(1，0，2) 2C3B11023C31024B21200C01001B32223C32025B404P4639P23707P0022P3123P1AAAAAvailableNeedAllocationMax322000032Page 462022-4-29Operating SystemOperating System 再利用安全性算法檢查此時(shí)系統(tǒng)是否安全。 truetruetruetruetrueFinish75532C55443B202

39、12C01010B03110C04312B55320C54433B10367P27047P45302P17077P07205P3AAAAWork + AllocationAllocationNeedWork圖 3-17 P1申請(qǐng)資源時(shí)的安全性檢查 存在安全序列：存在安全序列：P1-P3-P4-P0-P2，系統(tǒng)處于安全狀態(tài)，可以滿足系統(tǒng)處于安全狀態(tài)，可以滿足P1資源分配請(qǐng)求。資源分配請(qǐng)求。Page 472022-4-29Operating SystemOperating System (3) P4請(qǐng)求資源：P4發(fā)出請(qǐng)求向量Request4(3，3，0)，系統(tǒng)按銀行家算法進(jìn)行檢查： Request

40、4(3, 3, 0)Need4(4, 3, 1); Request4(3, 3, 0)Available(2, 3, 0)，讓P4等待。/Page 482022-4-29Operating SystemOperating System (4) P0請(qǐng)求資源：P0發(fā)出請(qǐng)求向量Request0(0，2，0)，系統(tǒng)按銀行家算法進(jìn)行檢查： Request0(0, 2, 0)Need0(7, 4, 3); Request0(0, 2, 0)Available(2, 3, 0);Page 492022-4-29Operating SystemOperating System 系統(tǒng)暫時(shí)先假定可為P0分配資源

41、，并修改有關(guān)數(shù)據(jù)，如圖 3-18 所示。 Request0(0，2，0)723210030圖 3-18 為P0分配資源后的有關(guān)資源數(shù)據(jù) 不安全狀態(tài)Page 502022-4-29Operating SystemOperating System (5) P0請(qǐng)求資源：P0發(fā)出請(qǐng)求向量改為Request0(0, 1, 0)，系統(tǒng)按銀行家算法進(jìn)行檢查： Request0(0, 1, 0)Need0(7, 4, 3); Request0(0, 1, 0)Available(2, 3, 0);Page 512022-4-29Operating SystemOperating System 系統(tǒng)先假定可為

42、P0分配資源，并修改Available, Allocation0和Need0向量，由此形成的資源變化情況如圖所示。 Request0(0, 1, 0) 0C3B11003C31024B21220C01001B32223C32025B404P4639P22707P0022P3033P1AAAAAvailableNeedAllocationMax733220020Page 522022-4-29Operating SystemOperating System 再利用安全性算法檢查此時(shí)系統(tǒng)是否安全。 truetruetruetruetrueFinish75532C55332B20212C02010B

43、03110C03312B55320C53322B10367P27047P45302P17077P07205P3AAAAWork + AllocationAllocationNeedWork圖 3-17 P1申請(qǐng)資源時(shí)的安全性檢查 存在安全序列：存在安全序列：P1-P3-P4-P0-P2，系統(tǒng)處于安全狀態(tài)，可以滿足系統(tǒng)處于安全狀態(tài)，可以滿足P0資源分配請(qǐng)求。資源分配請(qǐng)求。Page 532022-4-29Operating SystemOperating Systemq處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 q調(diào)度算法調(diào)度算法 q實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度 q多處理機(jī)系統(tǒng)中的調(diào)度多處理機(jī)系統(tǒng)中的調(diào)度q產(chǎn)生

44、死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件 q預(yù)防死鎖的方法預(yù)防死鎖的方法 q死鎖的檢測(cè)與解除死鎖的檢測(cè)與解除Page 542022-4-29Operating SystemOperating Systemq死鎖的檢測(cè)死鎖的檢測(cè)q死鎖的解除死鎖的解除Page 552022-4-29Operating SystemOperating System 允許死鎖發(fā)生，操作系統(tǒng)不斷監(jiān)視系統(tǒng)允許死鎖發(fā)生，操作系統(tǒng)不斷監(jiān)視系統(tǒng)進(jìn)展情況，判斷死鎖是否發(fā)生進(jìn)展情況，判斷死鎖是否發(fā)生 一旦死鎖發(fā)生則采取專門的措施，解除一旦死鎖發(fā)生則采取專門的措施，解除死鎖并以最小的代價(jià)恢復(fù)操作系統(tǒng)運(yùn)行死鎖并以最小的代價(jià)恢復(fù)操作

45、系統(tǒng)運(yùn)行Page 562022-4-29Operating SystemOperating Systemq檢測(cè)時(shí)機(jī)檢測(cè)時(shí)機(jī)v 當(dāng)進(jìn)程等待時(shí)檢測(cè)死鎖當(dāng)進(jìn)程等待時(shí)檢測(cè)死鎖 其缺點(diǎn)是系統(tǒng)的開銷大其缺點(diǎn)是系統(tǒng)的開銷大v 定時(shí)檢測(cè)定時(shí)檢測(cè) 系統(tǒng)資源利用率下降時(shí)檢測(cè)死鎖系統(tǒng)資源利用率下降時(shí)檢測(cè)死鎖Page 572022-4-29Operating SystemOperating System3.7 死鎖的檢測(cè)與解除死鎖的檢測(cè)與解除 3.7.1 死鎖的檢測(cè)死鎖的檢測(cè) 當(dāng)系統(tǒng)為進(jìn)程分配資源時(shí)，若未采取任何限制性措施，則系統(tǒng)必須提供檢測(cè)和解除死鎖的手段，為此，系統(tǒng)必須：（1）保存有關(guān)資源的請(qǐng)求和分配信息；（2）

46、提供一種算法，以利用這些信息來(lái)檢測(cè)系統(tǒng)是否進(jìn)入死鎖狀態(tài)。 Page 582022-4-29Operating SystemOperating Systemq資源分配圖資源分配圖(Resource Allocation Graph)(Resource Allocation Graph) 用有向圖描述進(jìn)程的死鎖用有向圖描述進(jìn)程的死鎖v優(yōu)點(diǎn)：準(zhǔn)確、形象優(yōu)點(diǎn)：準(zhǔn)確、形象 系統(tǒng)由若干類資源構(gòu)成，一類資源稱系統(tǒng)由若干類資源構(gòu)成，一類資源稱為一個(gè)為一個(gè)資源類資源類；每個(gè)資源類中包含若干個(gè)；每個(gè)資源類中包含若干個(gè)同種資源，稱為同種資源，稱為資源實(shí)例資源實(shí)例Page 592022-4-29Operating S

47、ystemOperating System3.7 死鎖的檢測(cè)與解除死鎖的檢測(cè)與解除 系統(tǒng)死鎖可利用資源分配圖來(lái)描述。該圖是由一組結(jié)點(diǎn)N和一組邊E所組成的一個(gè)對(duì)偶G =（N，E），具有下述形成的定義和限制：（1）N被分為兩個(gè)互斥的子集，一組進(jìn)程結(jié)點(diǎn)P=（p1，p2，pn），一組資源結(jié)點(diǎn)R=r1，r2，rn，N=PR。在圖3-19所示的例子中：1. 資源分配圖資源分配圖(Resource Allocation Graph) Page 602022-4-29Operating SystemOperating System3.7 死鎖的檢測(cè)與解除死鎖的檢測(cè)與解除 3.7.1 死鎖的檢測(cè)死鎖的檢測(cè) 1.

48、 資源分配圖資源分配圖(Resource Allocation Graph) 圖 3-19 每類資源有多個(gè)時(shí)的情況 P=p1，p2，R=r1，r2，N=r1，r2 p1，p2 P1P2r1r2Page 612022-4-29Operating SystemOperating Systemq資源分配圖資源分配圖v表示法表示法: :資源類資源類: :用方框表示用方框表示（資源的不同類型）（資源的不同類型）資源實(shí)例資源實(shí)例: :用方框中的用方框中的圓點(diǎn)表示（存在于每圓點(diǎn)表示（存在于每個(gè)資源中）個(gè)資源中） 進(jìn)程進(jìn)程 : :用圓圈中加進(jìn)程用圓圈中加進(jìn)程名表示名表示分配邊：分配邊：資源實(shí)例資源實(shí)例進(jìn)進(jìn)程的

49、一條有向邊程的一條有向邊申請(qǐng)邊：申請(qǐng)邊：進(jìn)程進(jìn)程資源類資源類的一條有向邊的一條有向邊P1P2r1r2獲得獲得申請(qǐng)申請(qǐng)Page 622022-4-29Operating SystemOperating Systemq死鎖定理死鎖定理 如果資源分配圖中沒有環(huán)路，則系統(tǒng)如果資源分配圖中沒有環(huán)路，則系統(tǒng)中沒有死鎖，如果圖中存在環(huán)路則系統(tǒng)中中沒有死鎖，如果圖中存在環(huán)路則系統(tǒng)中可能存在死鎖?？赡艽嬖谒梨i。 如果如果每個(gè)資源類中只包含一個(gè)資源實(shí)每個(gè)資源類中只包含一個(gè)資源實(shí)例例，則環(huán)路是死鎖存在的充分必要條件。，則環(huán)路是死鎖存在的充分必要條件。Page 632022-4-29Operating SystemO

50、perating Systemq死鎖定理死鎖定理有環(huán)有死鎖有環(huán)有死鎖Page 642022-4-29Operating SystemOperating Systemq死鎖定理死鎖定理有環(huán)無(wú)死鎖有環(huán)無(wú)死鎖Page 652022-4-29Operating SystemOperating Systemq死鎖定理死鎖定理資源分配圖化簡(jiǎn)資源分配圖化簡(jiǎn)v找出一個(gè)既不阻塞又非獨(dú)立的進(jìn)程結(jié)點(diǎn)找出一個(gè)既不阻塞又非獨(dú)立的進(jìn)程結(jié)點(diǎn)pipi，在順，在順利的情況下利的情況下pipi可獲得資源而繼續(xù)運(yùn)行，再釋放所可獲得資源而繼續(xù)運(yùn)行，再釋放所有資源。消去有資源。消去pipi所有的請(qǐng)求邊和分配邊，將其變所有的請(qǐng)求邊和分配

51、邊，將其變?yōu)楣铝⒔Y(jié)點(diǎn)為孤立結(jié)點(diǎn)v再把相應(yīng)的資源分配給一個(gè)等待該資源的進(jìn)程，再把相應(yīng)的資源分配給一個(gè)等待該資源的進(jìn)程，即將某進(jìn)程的申請(qǐng)邊變?yōu)榉峙溥吋磳⒛尺M(jìn)程的申請(qǐng)邊變?yōu)榉峙溥卾在進(jìn)行一系列化簡(jiǎn)后若能消去圖中所有的邊，使在進(jìn)行一系列化簡(jiǎn)后若能消去圖中所有的邊，使所有進(jìn)程結(jié)點(diǎn)成為孤立結(jié)點(diǎn)，則稱該圖是所有進(jìn)程結(jié)點(diǎn)成為孤立結(jié)點(diǎn)，則稱該圖是可完全可完全簡(jiǎn)化的簡(jiǎn)化的；否則是；否則是不可完全簡(jiǎn)化的不可完全簡(jiǎn)化的v已經(jīng)證明：所有的化簡(jiǎn)順序都得到相同的不可簡(jiǎn)已經(jīng)證明：所有的化簡(jiǎn)順序都得到相同的不可簡(jiǎn)化圖。同樣可以證明，化圖。同樣可以證明，S S為死鎖的充分條件是：為死鎖的充分條件是：當(dāng)當(dāng)且僅當(dāng)且僅當(dāng)S S狀態(tài)的資

52、源分配圖是不可完全簡(jiǎn)化的狀態(tài)的資源分配圖是不可完全簡(jiǎn)化的。該。該充分條件稱為充分條件稱為死鎖定理死鎖定理Page 662022-4-29Operating SystemOperating Systemq死鎖定理死鎖定理資源分配圖的簡(jiǎn)化資源分配圖的簡(jiǎn)化 Page 672022-4-29Operating SystemOperating Systemq死鎖檢測(cè)中的數(shù)據(jù)結(jié)構(gòu)死鎖檢測(cè)中的數(shù)據(jù)結(jié)構(gòu) v可利用資源向量可利用資源向量AvailableAvailable它表示了它表示了m m類資源中每一類資源的可用類資源中每一類資源的可用數(shù)目數(shù)目v把不占用資源的進(jìn)程把不占用資源的進(jìn)程( (向量向量Allocation:=0Allocation:=0) )記入記入L L表中，表中， 即即LiLLiLv從進(jìn)程集合中找到一個(gè)從進(jìn)程集合中找到一個(gè)RequestRequesti iWorkWork的的進(jìn)程，做如下處理：進(jìn)程，做如下處理： 將其資源分配圖簡(jiǎn)化，釋放出資源，將其資源分配圖簡(jiǎn)化，釋放出資源，增加工作向量增加工作向量Work=Work+AllocationWork=Work+Allocationi i 將它記入將它記入L L表中表中Page 682022-4-29Operating SystemOperating Systemv若不能把所有進(jìn)程都記入若不能把所有進(jìn)程都記入L表