操作系統(tǒng)第3章處理機調(diào)度與死鎖(3)

1、Operating SystemOperating SystemPage 12022-3-22Operating SystemOperating SystemPage 22022-3-22q處理機調(diào)度的基本概念處理機調(diào)度的基本概念 q調(diào)度算法調(diào)度算法 q實時調(diào)度實時調(diào)度 q多處理機系統(tǒng)中的調(diào)度多處理機系統(tǒng)中的調(diào)度q產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件 q預防死鎖的方法預防死鎖的方法 q死鎖的檢測與解除死鎖的檢測與解除Operating SystemOperating SystemPage 32022-3-22q死鎖的基本概念死鎖的基本概念q產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因q產(chǎn)生死鎖的必

2、要條件產(chǎn)生死鎖的必要條件q處理死鎖的基本方法處理死鎖的基本方法Operating SystemOperating SystemPage 42022-3-22q 死鎖例子死鎖例子v一個由于申請不同類型資源而產(chǎn)生死一個由于申請不同類型資源而產(chǎn)生死鎖的例子鎖的例子v設系統(tǒng)有一臺打印機設系統(tǒng)有一臺打印機(R1)(R1)一臺掃描儀一臺掃描儀(R2)(R2)，兩進程共享這兩臺設備。，兩進程共享這兩臺設備。v用信號量用信號量S1S1表示表示R1R1是否可用，用信號是否可用，用信號量量S2S2表示表示R2R2是否可用，是否可用，S1S1、S2S2初值為初值為1 1。Operating SystemOperat

3、ing SystemPage 52022-3-22這兩個進程在并發(fā)執(zhí)行過程中，可能會發(fā)生死鎖。這兩個進程在并發(fā)執(zhí)行過程中，可能會發(fā)生死鎖。大家可以思考一下，如何修改，進程才不會發(fā)生大家可以思考一下，如何修改，進程才不會發(fā)生死鎖？死鎖？Operating SystemOperating SystemPage 62022-3-22q 死鎖的概念死鎖的概念v指指多個進程多個進程因因競爭共享資源競爭共享資源而造成的而造成的一種一種僵局僵局，若無外力作用，這些進程，若無外力作用，這些進程都將永遠不能再向前推進。都將永遠不能再向前推進。v即：一組進程中，每個進程都即：一組進程中，每個進程都無限等無限等待待

4、被該組進程中被該組進程中另一進程所占有的資另一進程所占有的資源源，因而永遠無法得到的資源，這種，因而永遠無法得到的資源，這種現(xiàn)象稱為進程死鎖，這一組進程就稱現(xiàn)象稱為進程死鎖，這一組進程就稱為死鎖進程。為死鎖進程。Operating SystemOperating SystemPage 72022-3-22q 關于死鎖的一些結(jié)論關于死鎖的一些結(jié)論v參與死鎖的進程參與死鎖的進程最少是兩個最少是兩個 v參與死鎖的進程參與死鎖的進程至少有兩個已經(jīng)占有至少有兩個已經(jīng)占有資源資源v參與死鎖的所有進程參與死鎖的所有進程都在等待資源都在等待資源v參與死鎖的進程是當前系統(tǒng)中所有參與死鎖的進程是當前系統(tǒng)中所有進進

5、程的子集程的子集注：注：如果死鎖發(fā)生，會浪費大量系統(tǒng)資源，如果死鎖發(fā)生，會浪費大量系統(tǒng)資源，甚至導致系統(tǒng)崩潰。甚至導致系統(tǒng)崩潰。Operating SystemOperating SystemPage 82022-3-22q 永久性資源和臨時性資源永久性資源和臨時性資源v永久性資源：可以被多個進程多次使用（可永久性資源：可以被多個進程多次使用（可再用資源）再用資源）可搶占資源：可搶占資源：CPUCPU不可搶占資源：打印機不可搶占資源：打印機v臨時性資源：只可使用一次的資源；即由一臨時性資源：只可使用一次的資源；即由一個進程產(chǎn)生，被另一進程使用后就再也無用個進程產(chǎn)生，被另一進程使用后就再也無用的

6、資源，也稱為的資源，也稱為消耗性資源消耗性資源 如信號量如信號量, ,中斷信號，同步信號等（可消耗中斷信號，同步信號等（可消耗性資源）性資源）“申請申請-分配分配-使用使用-釋放釋放”模式模式Operating SystemOperating SystemPage 92022-3-22q死鎖的基本概念死鎖的基本概念q產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因q產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件q處理死鎖的基本方法處理死鎖的基本方法Operating SystemOperating SystemPage 102022-3-223.5 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件3.5.1 產(chǎn)生死鎖的原因

7、產(chǎn)生死鎖的原因 競爭資源。競爭資源。當系統(tǒng)中供多個進程所共享的資源，不足以同時滿足它們的需要時，引起它們對資源的競爭而產(chǎn)生死鎖。 (2) 進程間推進順序非法。進程間推進順序非法。 進程在運行過程中，請求和釋放資源的順序不當，導致了進程死鎖。 所謂死鎖（Deadlock），是指多個進程因競爭資源而造成的一種僵局，若無外力作用，這些進程都將永遠不能再向前推進。 Operating SystemOperating SystemPage 112022-3-22q 競爭資源引起進程死鎖競爭資源引起進程死鎖v可剝奪和非剝奪性資源可剝奪和非剝奪性資源 可剝奪性資源可剝奪性資源是指進程在獲得這類資源后，是指進

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

9、源 Operating SystemOperating SystemPage 122022-3-22I/O設設備備共共享享時時的的死死鎖鎖情情況況 若系統(tǒng)中只有一臺打印機若系統(tǒng)中只有一臺打印機R1R1和一臺讀卡機和一臺讀卡機R2R2，可，可供進程供進程P1P1和和P2P2共享。若共享。若形成環(huán)路形成環(huán)路，這樣會產(chǎn)生死鎖。，這樣會產(chǎn)生死鎖。R1R2P1P2分配分配分配分配請求請求請求請求Operating SystemOperating SystemPage 132022-3-22 進程之間通信時的死鎖進程之間通信時的死鎖 S2P1S3P3S1P2產(chǎn)生產(chǎn)生P2P2產(chǎn)生產(chǎn)生P3P3產(chǎn)生產(chǎn)生要求接收

10、要求接收要求接收要求接收要求接收要求接收Operating SystemOperating SystemPage 142022-3-22q進程推進順序不當引起死鎖進程推進順序不當引起死鎖P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2) P1Rel(R1) P1Rel(R2)D不安全區(qū)Operating SystemOperating SystemPage 152022-3-22q若并發(fā)進程若并發(fā)進程P P1 1和和P P2 2按曲線按曲線所示的順序推所示的順序推進，它們將進入不安全區(qū)進，它們將進入不安全區(qū)D D內(nèi)。此時內(nèi)。此時P P1

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

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

13、資源又已被其他進程占有有q 不剝奪條件不剝奪條件 v進程已獲得的資源在未使用完之前不能被剝進程已獲得的資源在未使用完之前不能被剝奪奪q 環(huán)路等待條件環(huán)路等待條件v在發(fā)生死鎖時，必然存在一個進程在發(fā)生死鎖時，必然存在一個進程-資源循資源循環(huán)等待的環(huán)形鏈環(huán)等待的環(huán)形鏈Operating SystemOperating SystemPage 182022-3-22q死鎖的基本概念死鎖的基本概念q產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因q產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件q處理死鎖的基本方法處理死鎖的基本方法Operating SystemOperating SystemPage 192022-3-22q 預防

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

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

16、；進程初始化效率低；進程初始化時間延長時間延長剝奪次數(shù)過多；多次剝奪次數(shù)過多；多次對資源重新起動對資源重新起動不便靈活申請新資源不便靈活申請新資源資源剝奪資源剝奪適用于狀態(tài)可以保存和適用于狀態(tài)可以保存和恢復的資源恢復的資源資源資源按序申請按序申請避免避免Avoidance是是“預防預防”和和“檢測檢測”的折衷的折衷（在運行時判斷（在運行時判斷是否可能死鎖）是否可能死鎖）尋找可能的安尋找可能的安全的運行順序全的運行順序 不必進行剝奪不必進行剝奪使用條件：必須知道使用條件：必須知道將來的資源需求；進將來的資源需求；進程可能會長時間阻塞程可能會長時間阻塞檢測檢測Detection寬松的；只要允寬松的

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

18、鎖的方法 q死鎖的檢測與解除死鎖的檢測與解除Operating SystemOperating SystemPage 232022-3-22q預防死鎖預防死鎖q系統(tǒng)安全狀態(tài)系統(tǒng)安全狀態(tài)q利用銀行家算法避免死鎖利用銀行家算法避免死鎖Operating SystemOperating SystemPage 242022-3-22q 互斥條件互斥條件 v進程對所分配到的資源進行進程對所分配到的資源進行排它性的使用排它性的使用q 請求和保持條件請求和保持條件 v進程已經(jīng)至少進程已經(jīng)至少保持了一個保持了一個資源，但又提出了資源，但又提出了新的資源新的資源請求請求，而該資源又已被其他進程占，而該資源又已被

19、其他進程占有有q 不剝奪條件不剝奪條件 v進程已獲得的資源在未使用完之前不能被剝進程已獲得的資源在未使用完之前不能被剝奪奪q 環(huán)路等待條件環(huán)路等待條件v在發(fā)生死鎖時，必然存在一個進程在發(fā)生死鎖時，必然存在一個進程-資源循資源循環(huán)等待的環(huán)形鏈環(huán)等待的環(huán)形鏈Operating SystemOperating SystemPage 252022-3-22q 摒棄摒棄“請求和保持請求和保持”條件條件 v所有進程在開始運行之前必須所有進程在開始運行之前必須一次性的一次性的申請申請整個運行過程所需的全部資源整個運行過程所需的全部資源v簡單、易于實現(xiàn)、安全簡單、易于實現(xiàn)、安全v資源浪費嚴重資源浪費嚴重v進程

20、延遲運行進程延遲運行Operating SystemOperating SystemPage 262022-3-22q摒棄摒棄“不剝奪不剝奪”條件條件 v進程逐個地申請所需資源進程逐個地申請所需資源v當一個已經(jīng)保持了某些資源的進程當一個已經(jīng)保持了某些資源的進程申請申請新資源而不能得到滿足時，必須放棄新資源而不能得到滿足時，必須放棄所所有已保持的資源有已保持的資源v實現(xiàn)復雜、代價高昂實現(xiàn)復雜、代價高昂v延長了進程的周轉(zhuǎn)時間，還增加了系統(tǒng)延長了進程的周轉(zhuǎn)時間，還增加了系統(tǒng)開銷，降低了系統(tǒng)的吞吐量開銷，降低了系統(tǒng)的吞吐量Operating SystemOperating SystemPage 272

21、022-3-22q摒棄摒棄“環(huán)路等待環(huán)路等待”條件條件v系統(tǒng)將所有資源按類型分配序號并排隊系統(tǒng)將所有資源按類型分配序號并排隊v所有進程所有進程申請申請資源必須資源必須按序號按序號遞增的順遞增的順序序v資源利用率和系統(tǒng)吞吐量較高資源利用率和系統(tǒng)吞吐量較高v但在資源管理和資源申請方面仍有問題但在資源管理和資源申請方面仍有問題Operating SystemOperating SystemPage 282022-3-22序號序號資源資源1輸入機輸入機2打印機打印機3磁帶機磁帶機進程進程需求資源需求資源P1打印機打印機磁帶機磁帶機P2磁帶機磁帶機打印機打印機存在問題：資源的需求順序不等于存在問題：資源

22、的需求順序不等于序號，仍存在資源浪費。序號，仍存在資源浪費。Operating SystemOperating SystemPage 292022-3-22q摒棄摒棄“環(huán)路等待環(huán)路等待”條件條件q其資源利用率和系統(tǒng)吞吐量，都有較明顯其資源利用率和系統(tǒng)吞吐量，都有較明顯的改善，但也存在下述嚴重問題：的改善，但也存在下述嚴重問題：v（1）資源所分配的序號，必須相對穩(wěn)定，這）資源所分配的序號，必須相對穩(wěn)定，這就限制了新設備類型的增加。就限制了新設備類型的增加。v（2）進程使用各資源的順序，與系統(tǒng)規(guī)定的）進程使用各資源的順序，與系統(tǒng)規(guī)定的順序不同，造成對資源的浪費。順序不同，造成對資源的浪費。v（3）

23、按規(guī)定次序申請資源的方法，必然會限）按規(guī)定次序申請資源的方法，必然會限制了用戶簡單、自主地編程。制了用戶簡單、自主地編程。 Operating SystemOperating SystemPage 302022-3-22方法方法資源分配策略資源分配策略各種可能模式各種可能模式 主要優(yōu)點主要優(yōu)點主要缺點主要缺點預防預防Prevention保守的；寧可資保守的；寧可資源閑置（從機制源閑置（從機制上使死鎖條件不上使死鎖條件不成立，即摒棄三成立，即摒棄三個必要條件）個必要條件）一次請求所有一次請求所有資源資源適用于作突發(fā)式處理的適用于作突發(fā)式處理的進程；不必剝奪進程；不必剝奪效率低；進程初始化效率低；

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

25、源許，就分配資源定期檢查死鎖定期檢查死鎖是否已經(jīng)發(fā)生是否已經(jīng)發(fā)生不延長進程初始化時間；不延長進程初始化時間；允許對死鎖進行現(xiàn)場處允許對死鎖進行現(xiàn)場處理理通過剝奪解除死鎖，通過剝奪解除死鎖，造成損失造成損失可以在編譯時（而不必可以在編譯時（而不必在運行時）就進行檢查在運行時）就進行檢查Operating SystemOperating SystemPage 312022-3-22q預防死鎖預防死鎖q系統(tǒng)安全狀態(tài)系統(tǒng)安全狀態(tài)q利用銀行家算法避免死鎖利用銀行家算法避免死鎖Operating SystemOperating SystemPage 322022-3-22q進程推進順序不當引起死鎖進程推進

26、順序不當引起死鎖P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2) P1Rel(R1) P1Rel(R2)DOperating SystemOperating SystemPage 332022-3-22q安全狀態(tài)安全狀態(tài)v在避免死鎖的方法中，允許進程在避免死鎖的方法中，允許進程動態(tài)地動態(tài)地申請申請資源，但系統(tǒng)在進行資源分配之前，應先計資源，但系統(tǒng)在進行資源分配之前，應先計算此次資源分配的安全性。若此次分配不會算此次資源分配的安全性。若此次分配不會導致系統(tǒng)進入導致系統(tǒng)進入不安全狀態(tài)不安全狀態(tài)，則將資源分配給，則將資源分配給進程；進程；

27、否則，令進程等待否則，令進程等待v所謂所謂安全狀態(tài)安全狀態(tài)，是指系統(tǒng)能按某種進程順序，是指系統(tǒng)能按某種進程順序(P1, P2, (P1, P2, ，Pn)(Pn)(稱稱P1, P2, , PnP1, P2, , Pn序序列為安全序列列為安全序列) )，來為每個進程，來為每個進程PiPi分配其所需分配其所需資源，直至滿足每個進程對資源的最大需求，資源，直至滿足每個進程對資源的最大需求，使每個進程都可順利地完成。如果系統(tǒng)無法使每個進程都可順利地完成。如果系統(tǒng)無法找到這樣一個安全序列，則稱系統(tǒng)處于找到這樣一個安全序列，則稱系統(tǒng)處于不安不安全狀態(tài)全狀態(tài)Operating SystemOperating

28、 SystemPage 342022-3-22 2. 安全狀態(tài)之例安全狀態(tài)之例 我們通過一個例子來說明安全性。假定系統(tǒng)中有三個進程P1、 P2和P3，共有12臺磁帶機。進程P1總共要求10臺磁帶機，P2和P3分別要求4臺和9臺。假設在T0時刻，進程P1、P2和P3已分別獲得5臺、2臺和2臺磁帶機，尚有3臺空閑未分配，如下表所示： 29P324P23510P1可 用 已 分 配 最 大 需 求 進 程 41 5100109312存在安全序列：存在安全序列：P2-P1-P3，系統(tǒng)處于安全狀態(tài)。，系統(tǒng)處于安全狀態(tài)。Operating SystemOperating SystemPage 352022

29、-3-22 3. 由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換 如果不按照安全序列分配資源，則系統(tǒng)可能會由安全狀態(tài)進入不安全狀態(tài)。例如，在T0時刻以后，P3又請求1臺磁帶機， 若此時系統(tǒng)把剩余3臺中的1臺分配給P3，則系統(tǒng)便進入不安全狀態(tài)。進 程 最 大 需 求 已 分 配 可 用 P11053P242P3923240 4不安全狀態(tài)Operating SystemOperating SystemPage 362022-3-22q預防死鎖預防死鎖q系統(tǒng)安全狀態(tài)系統(tǒng)安全狀態(tài)q利用銀行家算法避免死鎖利用銀行家算法避免死鎖Operating SystemOperating SystemPa

30、ge 372022-3-223.6.3 利用銀行家算法避免死鎖利用銀行家算法避免死鎖 1. 銀行家算法中的數(shù)據(jù)結(jié)構(gòu)銀行家算法中的數(shù)據(jù)結(jié)構(gòu) (1) 可利用資源向量可利用資源向量Available。這是一個含有m個元素的數(shù)組，其中的每一個元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動態(tài)地改變。如果Availablej = K，則表示系統(tǒng)中現(xiàn)有，則表示系統(tǒng)中現(xiàn)有Rj類資源類資源K個。個。 Operating SystemOperating SystemPage 382022-3-22 (2) 最大需求矩陣最大需求矩陣Max。這是一個nm

31、的矩陣，它定義了系統(tǒng)中n個進程中的每一個進程對m類資源的最大需求。如果Maxi,j = K，則表示進程，則表示進程i需要需要Rj類資源的最大數(shù)目為類資源的最大數(shù)目為K。 (3) 分配矩陣分配矩陣Allocation。這也是一個nm的矩陣，它定義了系統(tǒng)中每一類資源當前已分配給每一進程的資源數(shù)。如果Allocationi,j=K，表示進程，表示進程i當前已分得當前已分得Rj類資源的數(shù)目為類資源的數(shù)目為K。 (4) 需求矩陣需求矩陣Need。這也是一個nm的矩陣，用以表示每一個進程尚需的各類資源數(shù)。如果Needi,j = K，則表示進程，則表示進程i還需要還需要Rj類資源類資源K個，個，方能完成其任

32、務。 Needi,j = Maxi,j Allocationi,j Operating SystemOperating SystemPage 392022-3-22 2. 銀行家算法銀行家算法 設Requesti是進程Pi的請求向量，如果Requestij = K，表示進程Pi需要K個Rj類型的資源。當Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進行檢查： (1) 如果Requestij Needi,j，便轉(zhuǎn)向步驟(2)；否則認為出錯，因為它所需要的資源數(shù)已超過它所宣布的最大值。 (2) 如果Requestij Availablej，便轉(zhuǎn)向步驟(3)；否則， 表示尚無足夠資源，Pi須等待。 Operat

33、ing SystemOperating SystemPage 402022-3-22 (3) 系統(tǒng)試探著把資源分配給進程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： Availablej := Availablej - Requestij; Allocationi,j := Allocationi,j + Requestij; Needi,j := Needi,j - Requestij; (4) 系統(tǒng)執(zhí)行安全性算法安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復原來的資源分配狀態(tài)，讓進程Pi等待。 Operati

34、ng SystemOperating SystemPage 412022-3-223. 安全性算法安全性算法 (1) 設置兩個向量： 工作向量Work: 它表示系統(tǒng)可提供給進程繼續(xù)運行所需的各類資源數(shù)目，它含有m個元素，在執(zhí)行安全算法開始時，Work := Available; Finish: 它表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成。開始時先做Finishi := false; 當有足夠資源分配給進程時， 再令Finishi := true。 Operating SystemOperating SystemPage 422022-3-22 (2) 從進程集合中找到一個能滿足下述條件

35、的進程： Finishi = false; Needi,j Workj； 若找到， 執(zhí)行步驟(3)， 否則，執(zhí)行步驟(4)。 (3) 當進程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應執(zhí)行： Workj := Worki + Allocationi,j; Finishi := true; go to step 2; (4) 如果所有進程的Finishi = true都滿足， 則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。 Operating SystemOperating SystemPage 432022-3-224. 銀行家算法之例銀行家算法之例 假定系統(tǒng)中有五個

36、進程P0, P1, P2, P3, P4和三類資源A, B, C，各種資源的數(shù)量分別為10、5、7，在T0時刻的資源分配情況如圖 3-15 所示。 圖 3-15 T0時刻的資源分配表 2C3B11023C31024B21200C01001B32223C32025B404P4639P23707P0022P3123P1AAAAAvailableNeedAllocationMaxNeedi,j = Maxi,j Allocationi,j Operating SystemOperating SystemPage 442022-3-22(1) T0時刻的安全性： 圖 3-16 T0時刻的安全序列 tr

37、uetruetruetruetrueFinish77532C54443B02210C10010B30112C40312B75322C44433B100710P07047P45213P110367P27205P3AAAAWork + AllocationAllocationNeedWork存在安全序列：存在安全序列：P1-P3-P4-P2-P0，系統(tǒng)在系統(tǒng)在T0時刻處于安全狀態(tài)。時刻處于安全狀態(tài)。Operating SystemOperating SystemPage 452022-3-22 (2) P1請求資源：P1發(fā)出請求向量Request1(1，0，2)，系統(tǒng)按銀行家算法進行檢查： Req

38、uest1(1, 0, 2)Need1(1, 2, 2) Request1(1, 0, 2)Available1(3, 3, 2)MaxAllocationNeedAvailableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P4433002431Operating SystemOperating SystemPage 462022-3-22 系統(tǒng)先假定可為P1分配資源，并修改Available, Allocation1和Need1向量，由此形成的資源變化情況如圖 3-15 中的圓括號所示。 Request1(1，0，2

39、) 2C3B11023C31024B21200C01001B32223C32025B404P4639P23707P0022P3123P1AAAAAvailableNeedAllocationMax322000032Operating SystemOperating SystemPage 472022-3-22 再利用安全性算法檢查此時系統(tǒng)是否安全。 truetruetruetruetrueFinish75532C55443B20212C01010B03110C04312B55320C54433B10367P27047P45302P17077P07205P3AAAAWork + Allocati

40、onAllocationNeedWork圖 3-17 P1申請資源時的安全性檢查 存在安全序列：存在安全序列：P1-P3-P4-P0-P2，系統(tǒng)處于安全狀態(tài)，可以滿足系統(tǒng)處于安全狀態(tài)，可以滿足P1資源分配請求。資源分配請求。Operating SystemOperating SystemPage 482022-3-22 (3) P4請求資源：P4發(fā)出請求向量Request4(3，3，0)，系統(tǒng)按銀行家算法進行檢查： Request4(3, 3, 0)Need4(4, 3, 1); Request4(3, 3, 0)Available(2, 3, 0)，讓P4等待。MaxAllocationNe

41、edAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431/Operating SystemOperating SystemPage 492022-3-22 (4) P0請求資源：P0發(fā)出請求向量Request0(0，2，0)，系統(tǒng)按銀行家算法進行檢查： Request0(0, 2, 0)Need0(7, 4, 3); Request0(0, 2, 0)Available(2, 3, 0);MaxAllocationNeedAvailableABCABCABCABCP075301074323

42、0P1322302020P2902302600P3222211011P4433002431Operating SystemOperating SystemPage 502022-3-22 系統(tǒng)暫時先假定可為P0分配資源，并修改有關數(shù)據(jù)，如圖 3-18 所示。 Request0(0，2，0)MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431723210030圖 3-18 為P0分配資源后的有關資源數(shù)據(jù) 不安全狀態(tài)Operating SystemOperat

43、ing SystemPage 512022-3-22 (5) P0請求資源：P0發(fā)出請求向量改為Request0(0, 1, 0)，系統(tǒng)按銀行家算法進行檢查： Request0(0, 1, 0)Need0(7, 4, 3); Request0(0, 1, 0)Available(2, 3, 0);MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431Operating SystemOperating SystemPage 522022-3-22 系統(tǒng)先假定可

44、為P0分配資源，并修改Available, Allocation0和Need0向量，由此形成的資源變化情況如圖所示。 Request0(0, 1, 0) 0C3B11003C31024B21220C01001B32223C32025B404P4639P22707P0022P3033P1AAAAAvailableNeedAllocationMax733220020Operating SystemOperating SystemPage 532022-3-22 再利用安全性算法檢查此時系統(tǒng)是否安全。 truetruetruetruetrueFinish75532C55332B20212C02010

45、B03110C03312B55320C53322B10367P27047P45302P17077P07205P3AAAAWork + AllocationAllocationNeedWork圖 3-17 P1申請資源時的安全性檢查 存在安全序列：存在安全序列：P1-P3-P4-P0-P2，系統(tǒng)處于安全狀態(tài)，可以滿足系統(tǒng)處于安全狀態(tài)，可以滿足P0資源分配請求。資源分配請求。Operating SystemOperating SystemPage 542022-3-22q處理機調(diào)度的基本概念處理機調(diào)度的基本概念 q調(diào)度算法調(diào)度算法 q實時調(diào)度實時調(diào)度 q多處理機系統(tǒng)中的調(diào)度多處理機系統(tǒng)中的調(diào)度q產(chǎn)

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

47、作系統(tǒng)運行Operating SystemOperating SystemPage 572022-3-22q檢測時機檢測時機v 當進程等待時檢測死鎖當進程等待時檢測死鎖 其缺點是系統(tǒng)的開銷大其缺點是系統(tǒng)的開銷大v 定時檢測定時檢測 系統(tǒng)資源利用率下降時檢測死鎖系統(tǒng)資源利用率下降時檢測死鎖Operating SystemOperating SystemPage 582022-3-223.7 死鎖的檢測與解除死鎖的檢測與解除 3.7.1 死鎖的檢測死鎖的檢測 當系統(tǒng)為進程分配資源時，若未采取任何限制性措施，則系統(tǒng)必須提供檢測和解除死鎖的手段，為此，系統(tǒng)必須：（1）保存有關資源的請求和分配信息；（2

48、）提供一種算法，以利用這些信息來檢測系統(tǒng)是否進入死鎖狀態(tài)。 Operating SystemOperating SystemPage 592022-3-22q資源分配圖資源分配圖(Resource Allocation Graph)(Resource Allocation Graph) 用有向圖描述進程的死鎖用有向圖描述進程的死鎖v優(yōu)點：準確、形象優(yōu)點：準確、形象 系統(tǒng)由若干類資源構(gòu)成，一類資源稱系統(tǒng)由若干類資源構(gòu)成，一類資源稱為一個為一個資源類資源類；每個資源類中包含若干個；每個資源類中包含若干個同種資源，稱為同種資源，稱為資源實例資源實例Operating SystemOperating

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

50、. 資源分配圖資源分配圖(Resource Allocation Graph) 圖 3-19 每類資源有多個時的情況 P=p1，p2，R=r1，r2，N=r1，r2 p1，p2 P1P2r1r2Operating SystemOperating SystemPage 622022-3-22q資源分配圖資源分配圖v表示法表示法: :資源類資源類: :用方框表示用方框表示（資源的不同類型）（資源的不同類型）資源實例資源實例: :用方框中的用方框中的圓點表示（存在于每圓點表示（存在于每個資源中）個資源中） 進程進程 : :用圓圈中加進程用圓圈中加進程名表示名表示分配邊：分配邊：資源實例資源實例進進程

51、的一條有向邊程的一條有向邊申請邊：申請邊：進程進程資源類資源類的一條有向邊的一條有向邊P1P2r1r2獲得獲得申請申請Operating SystemOperating SystemPage 632022-3-22q死鎖定理死鎖定理 如果資源分配圖中沒有環(huán)路，則系統(tǒng)如果資源分配圖中沒有環(huán)路，則系統(tǒng)中沒有死鎖，如果圖中存在環(huán)路則系統(tǒng)中中沒有死鎖，如果圖中存在環(huán)路則系統(tǒng)中可能存在死鎖?？赡艽嬖谒梨i。 如果如果每個資源類中只包含一個資源實每個資源類中只包含一個資源實例例，則環(huán)路是死鎖存在的充分必要條件。，則環(huán)路是死鎖存在的充分必要條件。Operating SystemOperating System

52、Page 642022-3-22q死鎖定理死鎖定理有環(huán)有死鎖有環(huán)有死鎖Operating SystemOperating SystemPage 652022-3-22q死鎖定理死鎖定理有環(huán)無死鎖有環(huán)無死鎖Operating SystemOperating SystemPage 662022-3-22q死鎖定理死鎖定理資源分配圖化簡資源分配圖化簡v找出一個既不阻塞又非獨立的進程結(jié)點找出一個既不阻塞又非獨立的進程結(jié)點pipi，在順，在順利的情況下利的情況下pipi可獲得資源而繼續(xù)運行，再釋放所可獲得資源而繼續(xù)運行，再釋放所有資源。消去有資源。消去pipi所有的請求邊和分配邊，將其變所有的請求邊和分

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

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