第3章處理機調(diào)度與死鎖part3ppt課件

1、第三章 處理機調(diào)度與死鎖 第三章第三章 處理機調(diào)度與死鎖處理機調(diào)度與死鎖 3.1 3.1 處理機調(diào)度的層次處理機調(diào)度的層次 3.2 3.2 調(diào)度隊列模型和調(diào)度準(zhǔn)則調(diào)度隊列模型和調(diào)度準(zhǔn)則 3.3 3.3 調(diào)度算法調(diào)度算法 3.4 3.4 實時調(diào)度實時調(diào)度 3.5 3.5 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件 3.6 3.6 預(yù)防死鎖的方法預(yù)防死鎖的方法 3.7 3.7 死鎖的檢測與解除死鎖的檢測與解除 第三章 處理機調(diào)度與死鎖 3.5 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件3.5.1 產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因 競爭資源。競爭資源。 (2) 進程間推進順序非法。進程間推進

2、順序非法。 第三章 處理機調(diào)度與死鎖 1. 競爭資源引起進程死鎖競爭資源引起進程死鎖 可剝奪和非剝奪性資源可剝奪和非剝奪性資源 2) 競爭非剝奪性資源競爭非剝奪性資源 3) 競爭臨時性資源競爭臨時性資源 第三章 處理機調(diào)度與死鎖 圖 3-12 I/O設(shè)備共享時的死鎖情況 R1R2P1P2第三章 處理機調(diào)度與死鎖 圖 3-13 進程之間通信時的死鎖 S2P1S3P3S1P2第三章 處理機調(diào)度與死鎖 2. 進程推進順序不當(dāng)引起死鎖進程推進順序不當(dāng)引起死鎖 1) 進程推進順序合法 圖 3-14 進程推進順序?qū)λ梨i的影響 P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Re

3、q(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)D第三章 處理機調(diào)度與死鎖 2) 進程推進順序非法 若并發(fā)進程P1和P2按曲線所示的順序推進，它們將進入不安全區(qū)D內(nèi)。此時P1保持了資源R1, P2保持了資源R2, 系統(tǒng)處于不安全狀態(tài)。因為，這時兩進程再向前推進，便可能發(fā)生死鎖。例如，當(dāng)P1運行到P1:Request(R2)時，將因R2已被P2占用而阻塞；當(dāng)P2運行到P2: Request(R1)時，也將因R1已被P1占用而阻塞，于是發(fā)生了進程死鎖。 第三章 處理機調(diào)度與死鎖 3.5.2 產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件 互斥條件 (2) 請求和保持條件 (3) 不剝奪條件

4、(4) 環(huán)路等待條件 第三章 處理機調(diào)度與死鎖 3.5.3 處理死鎖的基本方法處理死鎖的基本方法預(yù)防死鎖。 (2) 避免死鎖。 (3) 檢測死鎖。 (4) 解除死鎖。 第三章 處理機調(diào)度與死鎖 3.6 預(yù)防死鎖的方法預(yù)防死鎖的方法 3.6.1 預(yù)防死鎖預(yù)防死鎖 摒棄“請求和保持條件 2. 摒棄“不剝奪條件 3. 摒棄“環(huán)路等待條件 第三章 處理機調(diào)度與死鎖 3.6.2 系統(tǒng)安全狀態(tài)系統(tǒng)安全狀態(tài) 1. 安全狀態(tài) 在避免死鎖的方法中，允許進程動態(tài)地申請資源，但系統(tǒng)在進行資源分配之前，應(yīng)先計算此次資源分配的安全性。若此次分配不會導(dǎo)致系統(tǒng)進入不安全狀態(tài)，則將資源分配給進程； 否則，令進程等待。 所謂安

5、全狀態(tài)，是指系統(tǒng)能按某種進程順序(P1, P2, ，Pn)(稱P1, P2, , Pn序列為安全序列)，來為每個進程Pi分配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程都可順利地完成。如果系統(tǒng)無法找到這樣一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)。 第三章 處理機調(diào)度與死鎖 2. 安全狀態(tài)之例安全狀態(tài)之例 我們通過一個例子來說明安全性。假定系統(tǒng)中有三個我們通過一個例子來說明安全性。假定系統(tǒng)中有三個進程進程P1、 P2和和P3，共有，共有12臺磁帶機。進程臺磁帶機。進程P1總共要求總共要求10臺臺磁帶機，磁帶機，P2和和P3分別要求分別要求4臺和臺和9臺。假設(shè)在臺。假設(shè)在T0時刻，進程時刻

6、，進程P1、P2和和P3已分別獲得已分別獲得5臺、臺、2臺和臺和2臺磁帶機，尚有臺磁帶機，尚有3臺空臺空閑未分配，如下表所示：閑未分配，如下表所示： 進 程 最 大 需 求 已 分 配 可 用 P1P2P310495223第三章 處理機調(diào)度與死鎖 【例】用銀行家算法判斷下述每個狀態(tài)是否安全。如果一個【例】用銀行家算法判斷下述每個狀態(tài)是否安全。如果一個狀態(tài)是安全的，說明所有進程是如何能夠運行完畢的。如果狀態(tài)是安全的，說明所有進程是如何能夠運行完畢的。如果一個狀態(tài)是不安全的，說明為什么可能出現(xiàn)死鎖。一個狀態(tài)是不安全的，說明為什么可能出現(xiàn)死鎖。狀態(tài)狀態(tài)A A占有臺數(shù)占有臺數(shù)最大需求最大需求用戶用戶1

7、 1用戶用戶2 2用戶用戶3 3用戶用戶4 42 26 64 47 75 56 60 02 2可供分配的臺數(shù)可供分配的臺數(shù)1 1平安平安第三章 處理機調(diào)度與死鎖 狀態(tài)狀態(tài)B B占有臺數(shù)占有臺數(shù)最大需求最大需求用戶用戶1 1用戶用戶2 2用戶用戶3 3用戶用戶4 44 48 83 39 95 58 80 02 2可供分配的臺數(shù)可供分配的臺數(shù)2 2找不到序列，不安全找不到序列，不安全第三章 處理機調(diào)度與死鎖 3. 由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換 如果不按照安全序列分配資源，則系統(tǒng)可能會由安全如果不按照安全序列分配資源，則系統(tǒng)可能會由安全狀態(tài)進入不安全狀態(tài)。例如，在狀態(tài)進入

8、不安全狀態(tài)。例如，在T0時刻以后，時刻以后，P3又請求又請求1臺磁帶機，若此時系統(tǒng)把剩余臺磁帶機，若此時系統(tǒng)把剩余3臺中的臺中的1臺分配給臺分配給P3，則系，則系統(tǒng)便進入不安全狀態(tài)。統(tǒng)便進入不安全狀態(tài)。 因為，此時也無法再找到一個安全因為，此時也無法再找到一個安全序列，序列， 例如，把其余的例如，把其余的2臺分配給臺分配給P2，這樣，在，這樣，在P2完成后完成后只能釋放出只能釋放出4臺，既不能滿足臺，既不能滿足P1尚需尚需5臺的要求，也不能滿臺的要求，也不能滿足足P3尚需尚需6臺的要求，致使它們都無法推進到完成，彼此臺的要求，致使它們都無法推進到完成，彼此都在等待對方釋放資源，即陷入僵局，結(jié)果

9、導(dǎo)致死鎖。都在等待對方釋放資源，即陷入僵局，結(jié)果導(dǎo)致死鎖。 第三章 處理機調(diào)度與死鎖 * 安全性算法安全性算法 (1) 設(shè)置兩個向量：設(shè)置兩個向量： 工作向量工作向量Work: 它表示系統(tǒng)可提供給進程繼續(xù)運行它表示系統(tǒng)可提供給進程繼續(xù)運行所需的各類資源數(shù)目，它含有所需的各類資源數(shù)目，它含有m個元素，在執(zhí)行安全算法個元素，在執(zhí)行安全算法開始時，開始時，Work =Available; Finish: 它表示系統(tǒng)是否有足夠的資源分配給進程，它表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成。開始時先做使之運行完成。開始時先做Finishi =false; 當(dāng)有足夠當(dāng)有足夠資源分配給進程時，資源分配

10、給進程時， 再令再令Finishi =true。 第三章 處理機調(diào)度與死鎖 (2) 從進程集合中找到一個能滿足下述條件的進程：從進程集合中找到一個能滿足下述條件的進程： Finishi=false; Needi,jWorkj； 若若找到，找到， 執(zhí)行步驟執(zhí)行步驟(3)， 否則，執(zhí)行步驟否則，執(zhí)行步驟(4)。 (3) 當(dāng)進程當(dāng)進程Pi獲得資源后，可順利執(zhí)行，直至完成，并獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：釋放出分配給它的資源，故應(yīng)執(zhí)行： Workj =Workj+Allocationi,j; Finishi =true; go to step 2; (4) 如果所

11、有進程的如果所有進程的Finishi=true都滿足，都滿足， 則表示系則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。 第三章 處理機調(diào)度與死鎖 之前安全狀態(tài)例題之前安全狀態(tài)例題 我們通過一個例子來說明安全性。假定系統(tǒng)中有三個我們通過一個例子來說明安全性。假定系統(tǒng)中有三個進程進程P1、 P2和和P3，共有，共有12臺磁帶機。進程臺磁帶機。進程P1總共要求總共要求10臺臺磁帶機，磁帶機，P2和和P3分別要求分別要求4臺和臺和9臺。假設(shè)在臺。假設(shè)在T0時刻，進程時刻，進程P1、P2和和P3已分別獲得已分別獲得5臺、臺、2臺和臺和2臺磁帶機，尚有臺磁帶機，尚有3臺空臺空閑未分配，如下表所示：閑未分配，如下表所示： 進 程 最 大 需 求 已 分 配 可 用 P1P2P310495223第三章 處理機調(diào)度與死鎖 WorkNeedAllo