太原理工大學操作系統(tǒng)-第三章處理機調度與死鎖

1、 操作系統(tǒng) 第三章 處理機調度與死鎖1 1第三章 處理機調度與死鎖3.1 處理機調度的基本概念3.2 作業(yè)調度3.3 進程調度3.4 死鎖 操作系統(tǒng) 第三章 處理機調度與死鎖2 23.1 處理機調度的基本概念 處理機資源是計算機系統(tǒng)中最重要的資源，它的調度處理機資源是計算機系統(tǒng)中最重要的資源，它的調度策略，常常表示操作系統(tǒng)的某種特征，其算法的優(yōu)劣直接策略，常常表示操作系統(tǒng)的某種特征，其算法的優(yōu)劣直接影響整個系統(tǒng)的性能。影響整個系統(tǒng)的性能。 處理機調度需要解決三個問題：處理機調度需要解決三個問題：(1) (1) 處理機分配的策略，即需要確定處理機的調度算法；處理機分配的策略，即需要確定處理機的調

2、度算法；(2) (2) 什么時候分配處理機，即需要確定處理機的調度時機；什么時候分配處理機，即需要確定處理機的調度時機；(3) (3) 如何分配處理機，即需要給出處理機的調度過程。如何分配處理機，即需要給出處理機的調度過程。 操作系統(tǒng) 第三章 處理機調度與死鎖3 3一、處理機的分級調度：一、處理機的分級調度：1 1、作業(yè)調度（高級調度）：、作業(yè)調度（高級調度）： 按一定原則選擇按一定原則選擇若干個后備作業(yè)若干個后備作業(yè)調入主存調入主存，分配資，分配資源，并建立相應的進程，投入運行。當該作業(yè)執(zhí)行完畢源，并建立相應的進程，投入運行。當該作業(yè)執(zhí)行完畢時，還負責回收資源。時，還負責回收資源。 在每次執(zhí)

3、行作業(yè)調度時，都須做出以下兩個決定。在每次執(zhí)行作業(yè)調度時，都須做出以下兩個決定。 1) 1) 接納多少個作業(yè)接納多少個作業(yè) 2) 2) 接納哪些作業(yè)接納哪些作業(yè) 操作系統(tǒng) 第三章 處理機調度與死鎖4 42 2、進程調度（低級調度）：、進程調度（低級調度）： （線程調度）（線程調度） 按照某種策略從進程就緒隊列中選擇按照某種策略從進程就緒隊列中選擇一個就緒進程一個就緒進程，使，使其其占有處理機占有處理機運行。運行。進程調度方式：進程調度方式： 1 1）非搶占式調度方式非搶占式調度方式 當有重要或緊迫的進程進入就緒隊列時，仍然讓正在執(zhí)當有重要或緊迫的進程進入就緒隊列時，仍然讓正在執(zhí)行的進程繼續(xù)執(zhí)行

4、，直到該進程完成任務終止運行或發(fā)生某行的進程繼續(xù)執(zhí)行，直到該進程完成任務終止運行或發(fā)生某種等待事件而進入阻塞狀態(tài)時，才主動放棄占有的處理機，種等待事件而進入阻塞狀態(tài)時，才主動放棄占有的處理機，把處理機分配給重要或緊迫的就緒進程，以使其運行。把處理機分配給重要或緊迫的就緒進程，以使其運行。優(yōu)點：優(yōu)點：實現簡單、系統(tǒng)開銷小。實現簡單、系統(tǒng)開銷小。 適用于大多數的批處理系統(tǒng)環(huán)境。適用于大多數的批處理系統(tǒng)環(huán)境。 缺點：缺點：難以滿足緊急任務的要求難以滿足緊急任務的要求立即執(zhí)行，因而可能造立即執(zhí)行，因而可能造成難以預料的后果。顯然，在要求比較嚴格的實時系統(tǒng)中，成難以預料的后果。顯然，在要求比較嚴格的實時

5、系統(tǒng)中，不宜采用這種調度方式。不宜采用這種調度方式。 操作系統(tǒng) 第三章 處理機調度與死鎖5 5 2 2）搶占式調度方式搶占式調度方式 當重要或緊迫的進程一到，便把正在執(zhí)行的進程占當重要或緊迫的進程一到，便把正在執(zhí)行的進程占有的處理機強行剝奪下來，并轉給這個優(yōu)先級比它更高有的處理機強行剝奪下來，并轉給這個優(yōu)先級比它更高的重要或緊迫的就緒進程，使其運行。的重要或緊迫的就緒進程，使其運行。 搶占的原則：搶占的原則： (1) (1) 優(yōu)先權原則優(yōu)先權原則 (2) (2) 短作業(yè)短作業(yè)( (進程進程) )優(yōu)先原則優(yōu)先原則 (3) (3) 時間片原則時間片原則 操作系統(tǒng) 第三章 處理機調度與死鎖6 63

6、3）交換調度（中級調度）（均衡調度）：）交換調度（中級調度）（均衡調度）： 按照給定的原則實現按照給定的原則實現進程進程在主存和外存交換區(qū)之間的在主存和外存交換區(qū)之間的換進換出換進換出，以解決內存緊張問題，特別是具有虛擬存儲器，以解決內存緊張問題，特別是具有虛擬存儲器的系統(tǒng)中。的系統(tǒng)中。 引入中級調度的主要目的引入中級調度的主要目的: : 是為了提高內存利用率和系統(tǒng)吞吐量。是為了提高內存利用率和系統(tǒng)吞吐量。 為此，應使那為此，應使那些暫時不能運行的進程不再占用寶貴的內存資源，而將它些暫時不能運行的進程不再占用寶貴的內存資源，而將它們調至外存上去等待。們調至外存上去等待。 操作系統(tǒng) 第三章 處理

7、機調度與死鎖7 7二、調度隊列模型二、調度隊列模型 1. 1. 僅有進程調度的調度隊列模型僅有進程調度的調度隊列模型 僅具有進程調度的調度隊列模型僅具有進程調度的調度隊列模型 就 緒 隊 列阻 塞 隊 列進程調度CPU進程完成等待事件交互用戶事件出現時間片完 操作系統(tǒng) 第三章 處理機調度與死鎖8 82. 具有高級和低級調度的調度隊列模型具有高級和低級調度的調度隊列模型 具有高、低兩級調度的調度隊列模型具有高、低兩級調度的調度隊列模型 就 緒 隊 列進程調度CPU進程完成等待事件 1作業(yè)調度事件1出現時間片完等待事件 2事件2出現等待事件 n事件n出現后 備 隊 列 操作系統(tǒng) 第三章 處理機調度

8、與死鎖9 93. 3. 同時具有三級調度的調度隊列模型同時具有三級調度的調度隊列模型 具有三級調度時的調度隊列模型具有三級調度時的調度隊列模型 就緒隊列進程調度CPU就緒，掛起隊列中級調度阻塞，掛起隊列阻塞隊列等待事件進程完成時間片完作業(yè)調度交互型作業(yè)后備隊列批量作業(yè)掛起事件出現事件出現 操作系統(tǒng) 第三章 處理機調度與死鎖1010三、三、 選擇調度方式和調度算法的若干準則選擇調度方式和調度算法的若干準則 面向用戶的準則面向用戶的準則 (1) (1) 作業(yè)周轉時間短。作業(yè)周轉時間短。 (2) (2) 響應時間快。響應時間快。 (3) (3) 截止時間的保證。截止時間的保證。 (4) (4) 優(yōu)先

9、權準則。優(yōu)先權準則。2.2.面向系統(tǒng)的準則面向系統(tǒng)的準則 (1) (1) 系統(tǒng)吞吐量高。系統(tǒng)吞吐量高。 (2) (2) 處理機利用率好。處理機利用率好。 (3) (3) 各類資源的平衡利用。各類資源的平衡利用。 操作系統(tǒng) 第三章 處理機調度與死鎖11113.2 作業(yè)調度一、作業(yè)的組織 程序程序 作業(yè)由三部分組成作業(yè)由三部分組成 數據數據 作業(yè)說明書作業(yè)說明書 （說明用戶的控制意圖）（說明用戶的控制意圖） 操作系統(tǒng) 第三章 處理機調度與死鎖1212作業(yè)控制塊作業(yè)控制塊（JCBJCB）：為了管理和調度已進入系統(tǒng)的各個作為了管理和調度已進入系統(tǒng)的各個作業(yè)業(yè)，系統(tǒng)設置的用于記錄作業(yè)的基本情況的數據結構

10、系統(tǒng)設置的用于記錄作業(yè)的基本情況的數據結構。作業(yè)控制塊作業(yè)控制塊（JCBJCB）的主要內容的主要內容：(1)(1)作業(yè)的基本情況作業(yè)的基本情況 用戶名、作業(yè)名、作業(yè)的狀態(tài)和使用的語言等。用戶名、作業(yè)名、作業(yè)的狀態(tài)和使用的語言等。(2)(2)作業(yè)的控制要求作業(yè)的控制要求 控制方式、類型、優(yōu)先數、操作順序和出錯處理等。控制方式、類型、優(yōu)先數、操作順序和出錯處理等。(3)(3)作業(yè)的資源要求作業(yè)的資源要求 作業(yè)建立的時間、要求運行的時間、最遲完成的時間、作業(yè)建立的時間、要求運行的時間、最遲完成的時間、需要的主存容量、外設的種類及數量和資源使用情況。需要的主存容量、外設的種類及數量和資源使用情況。二、

11、作業(yè)控制塊二、作業(yè)控制塊 操作系統(tǒng) 第三章 處理機調度與死鎖1313作業(yè)名作業(yè)名資源要求資源要求估計執(zhí)行時間估計執(zhí)行時間最遲完成時間最遲完成時間要求的主存量要求的主存量要求外設的類型及臺數要求外設的類型及臺數要求文件量和輸出量要求文件量和輸出量資源使用情況資源使用情況進入系統(tǒng)時間進入系統(tǒng)時間開始執(zhí)行時間開始執(zhí)行時間已執(zhí)行時間已執(zhí)行時間主存地址主存地址外設臺號外設臺號類型類型控制方式控制方式作業(yè)類型作業(yè)類型優(yōu)先級優(yōu)先級狀態(tài)狀態(tài)作業(yè)控制塊作業(yè)控制塊聯(lián)機和脫機聯(lián)機和脫機 操作系統(tǒng) 第三章 處理機調度與死鎖1414 一個作業(yè)從提交給計算機系統(tǒng)到執(zhí)行結束退出系統(tǒng)，一一個作業(yè)從提交給計算機系統(tǒng)到執(zhí)行結束退

12、出系統(tǒng)，一般都要經歷般都要經歷4 4個狀態(tài)：個狀態(tài)：提交、后備（收容）、執(zhí)行和完成。提交、后備（收容）、執(zhí)行和完成。1 1）提交狀態(tài)：）提交狀態(tài)：通過終端設備向計算機的磁盤輸入作業(yè)信息通過終端設備向計算機的磁盤輸入作業(yè)信息時所處的狀態(tài)。時所處的狀態(tài)。2 2）后備狀態(tài)：）后備狀態(tài)：作業(yè)的全部信息已輸入到磁盤的一個專用區(qū)作業(yè)的全部信息已輸入到磁盤的一個專用區(qū)( (輸入井輸入井) )中等待作業(yè)調度時所處的狀態(tài)。中等待作業(yè)調度時所處的狀態(tài)。3 3）執(zhí)行狀態(tài)：）執(zhí)行狀態(tài)：在后備作業(yè)隊列中的作業(yè)一旦被作業(yè)調度程在后備作業(yè)隊列中的作業(yè)一旦被作業(yè)調度程序選中，為它分配了必要的資源，并且建立了進程序選中，為它分

13、配了必要的資源，并且建立了進程, , 開始開始處理時所處的狀態(tài)。處理時所處的狀態(tài)。4 4）完成狀態(tài)：）完成狀態(tài)：作業(yè)完成其全部任務后，進程撤消作業(yè)完成其全部任務后，進程撤消, , 做善后做善后處理時的作業(yè)狀態(tài)稱為完成狀態(tài)。處理時的作業(yè)狀態(tài)稱為完成狀態(tài)。三、作業(yè)的狀態(tài) 操作系統(tǒng) 第三章 處理機調度與死鎖1515四、作業(yè)狀態(tài)的轉換 作業(yè)的狀態(tài)及其轉換作業(yè)的狀態(tài)及其轉換 執(zhí)執(zhí)行行 進程調度進程調度 內存內存 線程調度線程調度運運行行等等待待就就緒緒外存外存 就就緒緒等等待待提提交交后后備備完完成成作業(yè)輸入作業(yè)輸入 作業(yè)調度作業(yè)調度 交換調度交換調度 作業(yè)調度作業(yè)調度 執(zhí)執(zhí)行行 操作系統(tǒng) 第三章 處理

14、機調度與死鎖1616五、作業(yè)調度的功能 作業(yè)調度的主要任務：作業(yè)調度的主要任務：完成作業(yè)從后備狀態(tài)到運行狀態(tài)和完成作業(yè)從后備狀態(tài)到運行狀態(tài)和從運行狀態(tài)到完成狀態(tài)的轉變。從運行狀態(tài)到完成狀態(tài)的轉變。1 1）記錄系統(tǒng)中各作業(yè)的狀況）記錄系統(tǒng)中各作業(yè)的狀況。 作業(yè)調度程序應包括以下功能：作業(yè)調度程序應包括以下功能： 作業(yè)調度程序為了挑選一個作業(yè)投入運行，并且在運作業(yè)調度程序為了挑選一個作業(yè)投入運行，并且在運行中對它實施管理，它必須掌握該作業(yè)進入系統(tǒng)時的有關行中對它實施管理，它必須掌握該作業(yè)進入系統(tǒng)時的有關情況并隨時記錄該作業(yè)在各運行階段的變化。為此，系統(tǒng)情況并隨時記錄該作業(yè)在各運行階段的變化。為此，

15、系統(tǒng)為每一個已進入系統(tǒng)的作業(yè)分配一個為每一個已進入系統(tǒng)的作業(yè)分配一個作業(yè)控制塊作業(yè)控制塊JCBJCB(Job (Job Contrl block)Contrl block)。每個作業(yè)的。每個作業(yè)的JCBJCB在該作業(yè)進入后備狀態(tài)時在該作業(yè)進入后備狀態(tài)時由系統(tǒng)建立在該作業(yè)退出系統(tǒng)時由系統(tǒng)撤消。每個作業(yè)由系統(tǒng)建立在該作業(yè)退出系統(tǒng)時由系統(tǒng)撤消。每個作業(yè)在各階段的情況在各階段的情況( (包括分配的資源和作業(yè)狀態(tài)等包括分配的資源和作業(yè)狀態(tài)等) )都記錄在都記錄在它的它的JCBJCB中。中。 操作系統(tǒng) 第三章 處理機調度與死鎖17172) 2) 按一定的調度算法，從后備作業(yè)中挑選出一個或幾個作按一定的調度

16、算法，從后備作業(yè)中挑選出一個或幾個作業(yè)運行。業(yè)運行。 系統(tǒng)中處于后備狀態(tài)的作業(yè)較多，幾十個甚至幾百個，系統(tǒng)中處于后備狀態(tài)的作業(yè)較多，幾十個甚至幾百個，處于運行狀態(tài)的作業(yè)只是有限的幾個如最多不超過處于運行狀態(tài)的作業(yè)只是有限的幾個如最多不超過4 4個或個或8 8個。個。作業(yè)調度程序的一個重要職能就是在適當的時候按一定的調作業(yè)調度程序的一個重要職能就是在適當的時候按一定的調度原則從后備作業(yè)中挑選出若干個作業(yè)投入運行。度原則從后備作業(yè)中挑選出若干個作業(yè)投入運行。3) 3) 為被選中的作業(yè)做好執(zhí)行前的準備工作。為被選中的作業(yè)做好執(zhí)行前的準備工作。 為該作業(yè)建立相應的進程，并且為這些進程提供所需的為該作業(yè)

17、建立相應的進程，并且為這些進程提供所需的資源，如內存和外部設備等。資源，如內存和外部設備等。4) 4) 在作業(yè)執(zhí)行結束時做善后處理工作。在作業(yè)執(zhí)行結束時做善后處理工作。 輸出如運行時間、作業(yè)執(zhí)行情況等必要信息，回收該作輸出如運行時間、作業(yè)執(zhí)行情況等必要信息，回收該作業(yè)所占用的全部資源，撤消與該作業(yè)有關的全部進程和該作業(yè)所占用的全部資源，撤消與該作業(yè)有關的全部進程和該作業(yè)的作業(yè)控制塊。業(yè)的作業(yè)控制塊。 操作系統(tǒng) 第三章 處理機調度與死鎖1818六、作業(yè)調度目標與性能衡量 （1 1）公平性）公平性（2 2）均衡使用資源）均衡使用資源（3 3）較高的吞吐量）較高的吞吐量（4 4）較快的響應時間）較快

18、的響應時間1.1.調度目標調度目標 操作系統(tǒng) 第三章 處理機調度與死鎖1919（1 1）周轉時間）周轉時間T Ti i = = 完成時刻完成時刻TcTci i 提交時刻提交時刻TsTsi i = = 等待時間等待時間TwTwi i + + 運行時間運行時間 TrTri i對于進入系統(tǒng)的對于進入系統(tǒng)的n n個作業(yè)而言，個作業(yè)而言，平均周轉時間平均周轉時間T T為為用于衡量不同調度算法對同一作業(yè)流的調度性能用于衡量不同調度算法對同一作業(yè)流的調度性能:平均周轉時間越小，該作業(yè)調度算法的性能越好。平均周轉時間越小，該作業(yè)調度算法的性能越好。 2.2.調度性能衡量指標調度性能衡量指標iiiTnT11n

19、操作系統(tǒng) 第三章 處理機調度與死鎖2020(2)(2)帶權周轉時間帶權周轉時間Wi = TiWi = TiTriTri它能說明作業(yè)它能說明作業(yè)i i的相對等待時間。的相對等待時間。 平均帶權周轉時間平均帶權周轉時間 用于衡量同一調度算法對不同作業(yè)流的調度性能：用于衡量同一調度算法對不同作業(yè)流的調度性能：平均帶權周轉時間越小，作業(yè)調度算法對該作業(yè)流的調度平均帶權周轉時間越小，作業(yè)調度算法對該作業(yè)流的調度性能越好。性能越好。 對于批處理系統(tǒng)，主要依據平均周轉時間和平均帶對于批處理系統(tǒng)，主要依據平均周轉時間和平均帶權周轉時間來作為衡量調度算法性能的指標；而對于分權周轉時間來作為衡量調度算法性能的指標

20、；而對于分時系統(tǒng)和實時系統(tǒng)，外加平均響應時間作為衡量調度算時系統(tǒng)和實時系統(tǒng)，外加平均響應時間作為衡量調度算法性能的指標。法性能的指標。 niSiiTTnW11Wi 操作系統(tǒng) 第三章 處理機調度與死鎖2121七、作業(yè)調度算法 按作業(yè)來到的先后次序進行調度。這種算法優(yōu)先考慮按作業(yè)來到的先后次序進行調度。這種算法優(yōu)先考慮在系統(tǒng)中等待時間最長的作業(yè)，而不管它要求運行時間的在系統(tǒng)中等待時間最長的作業(yè)，而不管它要求運行時間的長短。長短。優(yōu)點：優(yōu)點：容易實現；容易實現；缺點：缺點：沒有考慮各個作業(yè)運行特征和資源要求的差異，系沒有考慮各個作業(yè)運行特征和資源要求的差異，系統(tǒng)效率較低。統(tǒng)效率較低。1.1.先來先服

21、務調度算法（先來先服務調度算法（FCFSFCFS） 操作系統(tǒng) 第三章 處理機調度與死鎖2222例：先來先服務調度算法（單位：小時，并以十進制計）例：先來先服務調度算法（單位：小時，并以十進制計）作業(yè)作業(yè)提交時間提交時間運行時間運行時間開始時間開始時間完成時間完成時間周轉時間周轉時間帶權周轉時間帶權周轉時間 1 8.00 2.00 8.0010.00 2.00 1 2 8.50 0.5010.0010.50 2.00 4 3 9.00 0.1010.5010.60 1.60 16 4 9.50 0.2010.6010.80 1.30 6.5平均周轉時間平均周轉時間T T1.7251.725平均帶

22、權周轉時間平均帶權周轉時間W W6.8756.875 操作系統(tǒng) 第三章 處理機調度與死鎖23232. 2. 短作業(yè)優(yōu)先調度算法（短作業(yè)優(yōu)先調度算法（SJFSJF） 此算法總是優(yōu)先調度要求運行時間最短的作業(yè)。此算法總是優(yōu)先調度要求運行時間最短的作業(yè)。優(yōu)點：優(yōu)點：易于實現，效率比較高。易于實現，效率比較高。缺點：缺點：只照顧短作業(yè)而不考慮長作業(yè)的利益。只照顧短作業(yè)而不考慮長作業(yè)的利益。 如果系統(tǒng)不斷地接受新的短作業(yè)。則有可能較長作業(yè)如果系統(tǒng)不斷地接受新的短作業(yè)。則有可能較長作業(yè)長時間等待而不能運行。長時間等待而不能運行。 操作系統(tǒng) 第三章 處理機調度與死鎖2424例：短作業(yè)優(yōu)先調度算法（單位：小時

23、，并以十進制計）例：短作業(yè)優(yōu)先調度算法（單位：小時，并以十進制計）作業(yè)作業(yè)提交時間提交時間運行時間運行時間開始時間開始時間完成時間完成時間周轉時間周轉時間帶權周轉時間帶權周轉時間 1 8.00 2.00 8.0010.00 2.00 1 2 8.50 0.5010.3010.80 2.30 4.6 3 9.00 0.1010.0010.10 1.10 11 4 9.50 0.2010.1010.30 0.80 4平均周轉時間平均周轉時間T T1.551.55平均帶權周轉時間平均帶權周轉時間W W5.155.15 操作系統(tǒng) 第三章 處理機調度與死鎖25253. 3. 響應比高者優(yōu)先調度算法響應比

24、高者優(yōu)先調度算法 響應比是指作業(yè)的響應時間與作業(yè)估計運行時間的比響應比是指作業(yè)的響應時間與作業(yè)估計運行時間的比值。值。執(zhí)執(zhí)行行時時間間響響應應時時間間響響應應比比 選擇原則是優(yōu)先選取響應比值最大的作業(yè)。即兼顧等選擇原則是優(yōu)先選取響應比值最大的作業(yè)。即兼顧等待時間長和運行時間短的作業(yè)，它是待時間長和運行時間短的作業(yè)，它是FCFSFCFS和和SJFSJF算法的結合。算法的結合。響應比響應比1 1作業(yè)等待時間作業(yè)等待時間/ /執(zhí)行時間執(zhí)行時間 操作系統(tǒng) 第三章 處理機調度與死鎖2626 作業(yè)作業(yè)提交時間提交時間運行時間運行時間開始時間開始時間完成時間完成時間周轉時間周轉時間帶權周轉時間帶權周轉時間

25、1 8.00 2.00 8.0010.00 2.00 1 2 8.50 0.5010.1010.60 2.10 4.2 3 9.00 0.1010.0010.10 1.10 11 4 9.50 0.2010.6010.80 1.30 6.5例：響應比高者優(yōu)先調度算法（單位：小時，并以十進制計例：響應比高者優(yōu)先調度算法（單位：小時，并以十進制計) )平均周轉時間平均周轉時間T T1.6251.625， 平均帶權周轉時間平均帶權周轉時間W W5.6755.675 響應比響應比1 1作業(yè)等待時間作業(yè)等待時間/ /執(zhí)行時間執(zhí)行時間例如：當作業(yè)例如：當作業(yè)3 3結束時，結束時，Rp2= 1Rp2= 1作

26、業(yè)等待時間作業(yè)等待時間/ /可執(zhí)行時間可執(zhí)行時間=1+(10.10-8.50)/0.5=1+3.2=1+(10.10-8.50)/0.5=1+3.2Rp4= 1Rp4= 1作業(yè)等待時間作業(yè)等待時間/ /可執(zhí)行時間可執(zhí)行時間=1+(10.10-9.50)/0.2=1+3=1+(10.10-9.50)/0.2=1+3 操作系統(tǒng) 第三章 處理機調度與死鎖2727 這種算法是根據確定的優(yōu)先數來選取作業(yè)，每次總是選這種算法是根據確定的優(yōu)先數來選取作業(yè)，每次總是選擇優(yōu)先級最高的作業(yè)。擇優(yōu)先級最高的作業(yè)。 4.4.最高優(yōu)先級優(yōu)先調度算法最高優(yōu)先級優(yōu)先調度算法規(guī)定用戶作業(yè)優(yōu)先數的方法規(guī)定用戶作業(yè)優(yōu)先數的方法:

27、 :1 1）由用戶自己提出作業(yè)的優(yōu)先數。）由用戶自己提出作業(yè)的優(yōu)先數。有的用戶為了自己的作業(yè)有的用戶為了自己的作業(yè)盡快被系統(tǒng)選中就設法提高自己作業(yè)的優(yōu)先數，這時系統(tǒng)可以盡快被系統(tǒng)選中就設法提高自己作業(yè)的優(yōu)先數，這時系統(tǒng)可以規(guī)定優(yōu)先數越高則需付出的計算機使用費就越多，以作限制。規(guī)定優(yōu)先數越高則需付出的計算機使用費就越多，以作限制。2 2）由系統(tǒng)綜合有關因素來確定用戶作業(yè)的優(yōu)先數。）由系統(tǒng)綜合有關因素來確定用戶作業(yè)的優(yōu)先數。 例如，根據作業(yè)的緩急程度、作業(yè)計算時間的長短、等待例如，根據作業(yè)的緩急程度、作業(yè)計算時間的長短、等待時間的多少、資源申請情況等來確定優(yōu)先數。確定優(yōu)先數時，時間的多少、資源申請

28、情況等來確定優(yōu)先數。確定優(yōu)先數時，各因素的比例應根據系統(tǒng)設計目標來分析這些因素在系統(tǒng)中的各因素的比例應根據系統(tǒng)設計目標來分析這些因素在系統(tǒng)中的地位而決定。地位而決定。 操作系統(tǒng) 第三章 處理機調度與死鎖28283.3 進程調度進程調度：進程調度：就是系統(tǒng)按照某種算法把就是系統(tǒng)按照某種算法把CPUCPU動態(tài)地分配給某一就動態(tài)地分配給某一就緒進程。進程調度工作是通過進程調度程序來完成的。緒進程。進程調度工作是通過進程調度程序來完成的。一、調度/分派結構調度程序：調度程序：將進程插入就緒隊列，按一定原則保持隊列結構；將進程插入就緒隊列，按一定原則保持隊列結構；分派程序：分派程序：將進程從就緒隊列中移

29、出，建立它執(zhí)行的機器狀態(tài)。將進程從就緒隊列中移出，建立它執(zhí)行的機器狀態(tài)。進程切換進程切換：把一個進程讓出處理機，由另一個進程占用處理機把一個進程讓出處理機，由另一個進程占用處理機的調度過程稱為的調度過程稱為“進程切換進程切換”。 分派程序首先將正在執(zhí)行的進程的分派程序首先將正在執(zhí)行的進程的CPUCPU現場信息保存在該進現場信息保存在該進程程PCBPCB的現場保護區(qū)中，再從被調度選中的進程的現場保護區(qū)中，再從被調度選中的進程PCBPCB的現場保護的現場保護區(qū)中取出它的區(qū)中取出它的CPUCPU現場信息恢復?，F場信息恢復。CPUCPU現場信息由程序狀態(tài)寄存現場信息由程序狀態(tài)寄存器、程序計數器以及若干

30、通用寄存器的內容組成。器、程序計數器以及若干通用寄存器的內容組成。 操作系統(tǒng) 第三章 處理機調度與死鎖29291.1.記錄系統(tǒng)中所有進程的執(zhí)行情況。記錄系統(tǒng)中所有進程的執(zhí)行情況。 二、進程調度功能 記錄系統(tǒng)中所有進程的有關情況，對進程控制塊記錄系統(tǒng)中所有進程的有關情況，對進程控制塊PCBPCB的內的內容作相應的登記、修改，記錄進程的狀態(tài)特征。容作相應的登記、修改，記錄進程的狀態(tài)特征。2.2.按照一定調度策略選擇一個占有處理機的就緒進程。按照一定調度策略選擇一個占有處理機的就緒進程。 在處理機空閑時根據一定的原則選擇一個進程去運行，在處理機空閑時根據一定的原則選擇一個進程去運行，同時確定獲得處理

31、機的時間。同時確定獲得處理機的時間。3.3.實施處理機的分配和回收實施處理機的分配和回收( (進行進程上下文切換進行進程上下文切換)?；厥栈厥? :正在運行的進程由于某種原因讓出處理機，該進程的狀正在運行的進程由于某種原因讓出處理機，該進程的狀態(tài)改為態(tài)改為“阻塞阻塞”，插入到相應隊列中，保留該進程的，插入到相應隊列中，保留該進程的CPUCPU現場?，F場。分配分配: :根據調度原則選擇進程去運行，把選中進程從就緒隊列中根據調度原則選擇進程去運行，把選中進程從就緒隊列中移出移出, ,改狀態(tài)為改狀態(tài)為“運行運行”，把，把CPUCPU控制權交給被選中的進程，將控制權交給被選中的進程，將選中進程的有關選

32、中進程的有關PCBPCB現場信息，分別送到相應的寄存器中?，F場信息，分別送到相應的寄存器中。 操作系統(tǒng) 第三章 處理機調度與死鎖3030三、進程調度時機 1 1）正在執(zhí)行的進程完成其任務而正在執(zhí)行的進程完成其任務而運行完畢運行完畢。 2 2）執(zhí)行中的進程由于執(zhí)行中的進程由于請求某個事件的發(fā)生請求某個事件的發(fā)生，比如，比如I/OI/O請求，請求，等待所需要的信號、信件的到來等而自己調用等待所需要的信號、信件的到來等而自己調用阻塞阻塞原語將自原語將自己阻塞起來，進入相應的等待隊列。己阻塞起來，進入相應的等待隊列。 3 3）在分時系統(tǒng)中，當進程使在分時系統(tǒng)中，當進程使用完規(guī)定的時間片用完規(guī)定的時間片

33、。 4 4）在在采用可搶占采用可搶占調度方式的系統(tǒng)中，當具有更高優(yōu)先級的調度方式的系統(tǒng)中，當具有更高優(yōu)先級的進程要求使用處理機。進程要求使用處理機。 操作系統(tǒng) 第三章 處理機調度與死鎖3131四、進程調度算法 采用最高優(yōu)先級優(yōu)先調度算法時，系統(tǒng)對每個進程確采用最高優(yōu)先級優(yōu)先調度算法時，系統(tǒng)對每個進程確定一個優(yōu)先數，進程的優(yōu)先數用于表示進程的重要性及運定一個優(yōu)先數，進程的優(yōu)先數用于表示進程的重要性及運行的優(yōu)先性。調度時，系統(tǒng)把處理機分配給優(yōu)先級最高的行的優(yōu)先性。調度時，系統(tǒng)把處理機分配給優(yōu)先級最高的就緒進程。如果就緒進程具有相同的優(yōu)先數，則再按先來就緒進程。如果就緒進程具有相同的優(yōu)先數，則再按先

34、來先服務的次序分配處理機。先服務的次序分配處理機。 先來先服務調度算法是按照進程進入就緒隊列的先后先來先服務調度算法是按照進程進入就緒隊列的先后次序來選擇進程分配處理機。次序來選擇進程分配處理機。（一）最高優(yōu)先級優(yōu)先調度算法 操作系統(tǒng) 第三章 處理機調度與死鎖3232系統(tǒng)確定優(yōu)先數的方法： 1.1.靜態(tài)優(yōu)先數法：靜態(tài)優(yōu)先數法：靜態(tài)優(yōu)先數是在創(chuàng)建進程時系統(tǒng)為其確靜態(tài)優(yōu)先數是在創(chuàng)建進程時系統(tǒng)為其確定的，并且在進程的生命期內不再改變。定的，并且在進程的生命期內不再改變。 確定靜態(tài)優(yōu)先數的原則：確定靜態(tài)優(yōu)先數的原則：1 1）按進程類型。）按進程類型。系統(tǒng)進程的優(yōu)先級高于用戶進程的優(yōu)先級。系統(tǒng)進程的優(yōu)先

35、級高于用戶進程的優(yōu)先級。 2 2）按進程使用的資源。）按進程使用的資源。進程所使用的資源越多，進程的優(yōu)進程所使用的資源越多，進程的優(yōu)先級越低；反之，則進程的優(yōu)先級越高。先級越低；反之，則進程的優(yōu)先級越高。 3 3）按進程的估計運行時間。）按進程的估計運行時間。進程的估計運行時間越長，進進程的估計運行時間越長，進程的優(yōu)先級越低；反之，則進程的優(yōu)先級越高。程的優(yōu)先級越低；反之，則進程的優(yōu)先級越高。 4 4）由用戶指定。）由用戶指定。有些系統(tǒng)可以按收費標準不同，設置不同的有些系統(tǒng)可以按收費標準不同，設置不同的優(yōu)先級別，可以由用戶指定。優(yōu)先級別，可以由用戶指定。 靜態(tài)優(yōu)先級法實現起來比較簡單，但不能反

36、映系統(tǒng)以及進程靜態(tài)優(yōu)先級法實現起來比較簡單，但不能反映系統(tǒng)以及進程在運行過程中的動態(tài)變化情況，系統(tǒng)管理效果顯然不佳。在運行過程中的動態(tài)變化情況，系統(tǒng)管理效果顯然不佳。 操作系統(tǒng) 第三章 處理機調度與死鎖33332. 2. 動態(tài)優(yōu)先數法。動態(tài)優(yōu)先數法。動態(tài)優(yōu)先數是指在系統(tǒng)創(chuàng)建進程時，根動態(tài)優(yōu)先數是指在系統(tǒng)創(chuàng)建進程時，根據系統(tǒng)資源的使用情況和進程的當前特點確定一個優(yōu)先數，據系統(tǒng)資源的使用情況和進程的當前特點確定一個優(yōu)先數，然后，在進程運行過程中再根據情況的變化動態(tài)調整進程的然后，在進程運行過程中再根據情況的變化動態(tài)調整進程的優(yōu)先數。優(yōu)先數。 調整進程優(yōu)先數的原調整進程優(yōu)先數的原則：則： 1 1）進

37、程占有處理機的時間越長，則進程的優(yōu)先級越低；進程）進程占有處理機的時間越長，則進程的優(yōu)先級越低；進程的等待時間越長，則進程的優(yōu)先級越高。的等待時間越長，則進程的優(yōu)先級越高。 2 2）根據進程所執(zhí)行的程序的輕重緩急程度，調整進程的優(yōu)先）根據進程所執(zhí)行的程序的輕重緩急程度，調整進程的優(yōu)先數。數。 操作系統(tǒng) 第三章 處理機調度與死鎖3434優(yōu)先權的變化規(guī)律：優(yōu)先權的變化規(guī)律： (1) (1) 如果進程（作業(yè)）的等待時間相同，則要求服如果進程（作業(yè)）的等待時間相同，則要求服務的時間愈短，其優(yōu)先權愈高，因而該算法有利于短進務的時間愈短，其優(yōu)先權愈高，因而該算法有利于短進程（作業(yè)）。程（作業(yè)）。 (2)

38、(2) 當要求服務的時間相同時，進程（作業(yè)）的優(yōu)當要求服務的時間相同時，進程（作業(yè)）的優(yōu)先權決定于其等待時間，等待時間愈長，其優(yōu)先權愈高，先權決定于其等待時間，等待時間愈長，其優(yōu)先權愈高，因而它實現的是先來先服務。因而它實現的是先來先服務。 (3) (3) 對于長進程（作業(yè)），進程（作業(yè)）的優(yōu)先級對于長進程（作業(yè)），進程（作業(yè)）的優(yōu)先級可以隨等待時間的增加而提高，當其等待時間足夠長時，可以隨等待時間的增加而提高，當其等待時間足夠長時，其優(yōu)先級便可升到很高，其優(yōu)先級便可升到很高， 從而也可獲得處理機（進入主從而也可獲得處理機（進入主存）。存）。 操作系統(tǒng) 第三章 處理機調度與死鎖3535（二）時

39、間片輪轉調度算法 在分時系統(tǒng)中，為了滿足系統(tǒng)對響應時間的要求，通在分時系統(tǒng)中，為了滿足系統(tǒng)對響應時間的要求，通常采用時間片輪轉調度算法。常采用時間片輪轉調度算法。 1. 簡單輪轉法(固定時間片輪轉法） 在這種調度算法中，系統(tǒng)把所有就緒進程按到達的先在這種調度算法中，系統(tǒng)把所有就緒進程按到達的先后順序形成一個就緒隊列，就緒隊列中的所有進程按時間后順序形成一個就緒隊列，就緒隊列中的所有進程按時間片依次輪流獲得處理機。片依次輪流獲得處理機。 操作系統(tǒng) 第三章 處理機調度與死鎖3636 時間片的大小應根據進程要求系統(tǒng)給出應答的時間和進時間片的大小應根據進程要求系統(tǒng)給出應答的時間和進入系統(tǒng)的進程數來決定

40、?？梢员硎緸椋喝胂到y(tǒng)的進程數來決定。可以表示為： N NT Tq q 其中，其中，q q是時間片的大小，是時間片的大小，T T是系統(tǒng)的響應時間，是系統(tǒng)的響應時間，N N是進入系統(tǒng)是進入系統(tǒng)的進程數。的進程數。 簡單輪轉法的優(yōu)點是簡單、方便，但由于采用固定時間簡單輪轉法的優(yōu)點是簡單、方便，但由于采用固定時間片的方式，調度欠靈活，服務質量不夠理想?？梢酝ㄟ^以下片的方式，調度欠靈活，服務質量不夠理想?？梢酝ㄟ^以下兩個方面加以改進：兩個方面加以改進：1 1）將固定時間片方式改為可變時間片方式；）將固定時間片方式改為可變時間片方式；2 2）將單就緒隊列改為多就緒隊列。）將單就緒隊列改為多就緒隊列。 操作

41、系統(tǒng) 第三章 處理機調度與死鎖37372. 可變時間片輪轉法 時間片可變會給系統(tǒng)帶來好處。如果要求系統(tǒng)快速應時間片可變會給系統(tǒng)帶來好處。如果要求系統(tǒng)快速應答，則時間片小一些，這樣可使輪轉一遍的總時間減少而答，則時間片小一些，這樣可使輪轉一遍的總時間減少而可對進程盡快應答。如果進程數少，則時間片可以大一些，可對進程盡快應答。如果進程數少，則時間片可以大一些，這樣可減少進程調度的次數，提高系統(tǒng)效率。這樣可減少進程調度的次數，提高系統(tǒng)效率。 操作系統(tǒng) 第三章 處理機調度與死鎖3838可變時間片輪轉法中，可采取如下措施調整時間片：可變時間片輪轉法中，可采取如下措施調整時間片： 1) 1) 固定周期輪轉

42、法。固定周期輪轉法。 在這種方法中，每一輪調度中所得的時間片在這種方法中，每一輪調度中所得的時間片q q值的大值的大小僅在這一輪調度中有效。系統(tǒng)的響應時間小僅在這一輪調度中有效。系統(tǒng)的響應時間T T固定，在每一固定，在每一輪調度中，根據當前就緒隊列中的進程數輪調度中，根據當前就緒隊列中的進程數n n計算這一輪調度計算這一輪調度的時間片：的時間片：q qT/ n T/ n ， 然后進行輪轉，每個進程可獲得然后進行輪轉，每個進程可獲得這一輪的一個時間片這一輪的一個時間片q q。在此期間所到達的進程暫不進入。在此期間所到達的進程暫不進入就緒隊列，等此次輪轉完畢再一并進入。系統(tǒng)根據此時就緒就緒隊列，等

43、此次輪轉完畢再一并進入。系統(tǒng)根據此時就緒隊列的進程數重新計算時間片隊列的進程數重新計算時間片q q，然后開始下一輪循環(huán)。，然后開始下一輪循環(huán)。 2) 2) 時間片的大小取決于優(yōu)先級的高低時間片的大小取決于優(yōu)先級的高低，優(yōu)先級高的進程分，優(yōu)先級高的進程分得的時間片較大，優(yōu)先級低的進程分得的時間片較小。得的時間片較大，優(yōu)先級低的進程分得的時間片較小。 3) 3) 短作業(yè)的時間片較小，短作業(yè)的時間片較小，長作業(yè)的時間片較大。長作業(yè)的時間片較大。 操作系統(tǒng) 第三章 處理機調度與死鎖39393.多級反饋輪轉法（多重時間片輪轉調度算法） 調度算法的實施過程如下：調度算法的實施過程如下： 1. 1. 設置多

44、個就緒隊列，設置多個就緒隊列，并為各個就緒隊列賦予不同的優(yōu)先并為各個就緒隊列賦予不同的優(yōu)先級。第一個就緒隊列的優(yōu)先級最高，第二個就緒隊列的優(yōu)先級。第一個就緒隊列的優(yōu)先級最高，第二個就緒隊列的優(yōu)先級次之，其余各個就緒隊列的優(yōu)先級逐個降低。級次之，其余各個就緒隊列的優(yōu)先級逐個降低。2.2.賦予各個就緒隊列中進程賦予各個就緒隊列中進程的時間片也各不相同，優(yōu)先級越的時間片也各不相同，優(yōu)先級越高的就緒隊列中的進程的時間片越小，反之，優(yōu)先級越低的高的就緒隊列中的進程的時間片越小，反之，優(yōu)先級越低的就緒隊列中的進程的時間片越大。就緒隊列中的進程的時間片越大。 3.3.當一個新被創(chuàng)建的進程當一個新被創(chuàng)建的進程

45、進入就緒隊列后，首先將它加入第進入就緒隊列后，首先將它加入第一個就緒隊列的隊尾，按先來先服務的原則排隊等待調度。一個就緒隊列的隊尾，按先來先服務的原則排隊等待調度。 操作系統(tǒng) 第三章 處理機調度與死鎖4040 當輪到該進程執(zhí)行時，如能在該時間片內完成，則該進當輪到該進程執(zhí)行時，如能在該時間片內完成，則該進程將被撤消；如果在一個時間片結束時該進程尚未完成，調程將被撤消；如果在一個時間片結束時該進程尚未完成，調度程序則將該進程轉入第二個就緒隊列的隊尾，按先來先服度程序則將該進程轉入第二個就緒隊列的隊尾，按先來先服務的原則排隊等待調度；如果它在第二個就緒隊列中運行一務的原則排隊等待調度；如果它在第二

46、個就緒隊列中運行一個時間片后仍未完成，再以同樣的方法將它轉入第三個就緒個時間片后仍未完成，再以同樣的方法將它轉入第三個就緒隊列的隊尾，隊列的隊尾， 如此下去。如此下去。4.4.僅當第一個就緒隊列空閑時，僅當第一個就緒隊列空閑時，調度程序才調度第二個就緒調度程序才調度第二個就緒隊列中的進程運行；僅當第隊列中的進程運行；僅當第1 1至第至第i i1 1個就緒隊列均為空時，個就緒隊列均為空時，才會調度第才會調度第i i個就緒隊列中的進程運行。個就緒隊列中的進程運行。如果處理機正在第如果處理機正在第i i個就緒隊列中為某進程服務時，又有新進程進入優(yōu)先級較高個就緒隊列中為某進程服務時，又有新進程進入優(yōu)先

47、級較高的就緒隊列時，則此時新進程將搶占正在運行進程的處理機，的就緒隊列時，則此時新進程將搶占正在運行進程的處理機，即由調度程序把正在運行的進程放回到第即由調度程序把正在運行的進程放回到第i i個就緒隊列的隊個就緒隊列的隊尾，然后將處理機重新分配給新進程。尾，然后將處理機重新分配給新進程。 操作系統(tǒng) 第三章 處理機調度與死鎖4141多級反饋隊列調度算法多級反饋隊列調度算法 就緒隊列 1就緒隊列 2就緒隊列 3就緒隊列 nS1S2S3至CPU至CPU至CPU至CPU(時間片： S1 S2 S3) 操作系統(tǒng) 第三章 處理機調度與死鎖42423.4 死鎖 一、死鎖的概念死鎖：死鎖：各并發(fā)進程彼此互相等

48、待對方所擁有的資源，且這各并發(fā)進程彼此互相等待對方所擁有的資源，且這些并發(fā)進程在得到對方的資源之前不會釋放自己所擁有的些并發(fā)進程在得到對方的資源之前不會釋放自己所擁有的資源。從而造成系統(tǒng)中一些進程處于無休止的等待狀態(tài)，資源。從而造成系統(tǒng)中一些進程處于無休止的等待狀態(tài)，在無外力作用的情況下，這些進程永遠也不能繼續(xù)前進。在無外力作用的情況下，這些進程永遠也不能繼續(xù)前進。我們稱這種現象為我們稱這種現象為死鎖死鎖。例：例：系統(tǒng)中只有一臺輸入機系統(tǒng)中只有一臺輸入機R1R1和一臺打印機和一臺打印機R2R2可供進程可供進程P1P1和和P2P2共享。共享。 操作系統(tǒng) 第三章 處理機調度與死鎖4343進程進程P

49、1 P1 進程進程P2P2 請求資源請求資源R1 R1 請求資源請求資源R2R2 請求資源請求資源R2 R2 請求資源請求資源R1R1 釋放資源釋放資源R1 R1 釋放資源釋放資源R2 R2 釋放資源釋放資源R2 R2 釋放資源釋放資源R1R1 R1R1R2R2 兩個進程死鎖的典型情況兩個進程死鎖的典型情況 死鎖死鎖R1R2 操作系統(tǒng) 第三章 處理機調度與死鎖4444 進程在同步和通信的過程進程在同步和通信的過程當中也會產生死鎖。當中也會產生死鎖。 例如，在生產者例如，在生產者消費者消費者問題中，若把生產者進程中兩問題中，若把生產者進程中兩個個P P操作的順序顛倒如下圖所示：操作的順序顛倒如下

50、圖所示： 生產者進程生產者進程Pi Pi 生產一個產品生產一個產品 產品送入緩沖區(qū)產品送入緩沖區(qū) P(avail) P(avail) P(mutex)P(mutex) V(mutex) V(mutex) V(full)V(full) 在這種情況下，當緩沖區(qū)在這種情況下，當緩沖區(qū)都已放滿了產品時，生產者仍都已放滿了產品時，生產者仍可執(zhí)行可執(zhí)行P(mutex)操作，于是操作，于是該生產者掌握了對緩沖區(qū)的存該生產者掌握了對緩沖區(qū)的存取 控 制 權 ， 當 它 繼 續(xù) 執(zhí) 行取 控 制 權 ， 當 它 繼 續(xù) 執(zhí) 行P(avail)P(avail)操作時，由于沒有空操作時，由于沒有空緩沖區(qū)，該生產者被

51、阻塞，并緩沖區(qū)，該生產者被阻塞，并在在avail上等待。上等待。 操作系統(tǒng) 第三章 處理機調度與死鎖4545若此時有一個消費者到達，盡管緩沖區(qū)中有產品，消費者在若此時有一個消費者到達，盡管緩沖區(qū)中有產品，消費者在執(zhí)行執(zhí)行P(full)P(full)操作時通過，但緊接著執(zhí)行操作時通過，但緊接著執(zhí)行P(mutex)P(mutex)操作時，將操作時，將因緩沖區(qū)已被阻塞的生產者所占有，而使消費者無法獲得緩因緩沖區(qū)已被阻塞的生產者所占有，而使消費者無法獲得緩沖區(qū)的存取控制權而被阻塞。此時，出現了生產者和消費者沖區(qū)的存取控制權而被阻塞。此時，出現了生產者和消費者之間僵死的局面，亦即發(fā)生了死鎖。之間僵死的局

52、面，亦即發(fā)生了死鎖。二、產生死鎖的原因 產生的產生的根本原因根本原因是系統(tǒng)能夠提供的資源數少于需要該是系統(tǒng)能夠提供的資源數少于需要該資源的進程數資源的進程數( (系統(tǒng)資源不足系統(tǒng)資源不足) )。 1 1）對資源的分配策略（請求順序）不當）對資源的分配策略（請求順序）不當 ； 2 2）進程推進順序非法。）進程推進順序非法。 死鎖起因是并發(fā)進程的資源競爭。死鎖起因是并發(fā)進程的資源競爭。 可剝奪性資源可剝奪性資源 非剝奪性資源非剝奪性資源 操作系統(tǒng) 第三章 處理機調度與死鎖4646 P1P1和和P2P2都占用都占用R1R1 P1 P1和和P2P2都占用都占用R2R2 P2P2的進展的進展 P1P1的

53、進展的進展 占用占用R1 R1 占用占用R2 R2 釋放釋放R1 R1 釋放釋放R2 R2 請求請求R1 R1 請求請求R2 R2 請求請求R1R1 請求請求R2 R2 釋放釋放R1R1 釋放釋放R2R2 占用占用R1 R1 1 1 2 2 3 3 占用占用R2R2下面用圖示來說明進程下面用圖示來說明進程P1P1和和P2P2的三種可能的進展情況：的三種可能的進展情況： 操作系統(tǒng) 第三章 處理機調度與死鎖4747三、死鎖存在的必要條件1 1）互斥條件。）互斥條件。進程對其所要求的資源進行排它性控制，進程對其所要求的資源進行排它性控制，即一次只有一個進程可以使用一個資源。即一次只有一個進程可以使用

54、一個資源。2 2）不剝奪條件。）不剝奪條件。進程所獲得進程所獲得的資源在未被釋放之前，不能被的資源在未被釋放之前，不能被其它進程強行剝奪。其它進程強行剝奪。3 3）占有且等待條件）占有且等待條件。進程每。進程每次申請它所需要的一部分資源，次申請它所需要的一部分資源，在進程等待分配其它資源的同時，在進程等待分配其它資源的同時，可以占有已分配的資源?？梢哉加幸逊峙涞馁Y源。 P1P1P2P2 R1 R1 R2 R2被占有被占有 被占有被占有 請求請求 請求請求 4 4）環(huán)路條件。）環(huán)路條件。在發(fā)生死鎖時，必然存在一個進程資源的在發(fā)生死鎖時，必然存在一個進程資源的循環(huán)等待鏈，循環(huán)等待鏈， 操作系統(tǒng) 第

55、三章 處理機調度與死鎖4848四、解決死鎖的方法（一）死鎖的防止（一）死鎖的防止( (預防預防) ) 1 1破壞互斥條件破壞互斥條件 為了破壞資源使用的互斥條件，就要允許多個進程同為了破壞資源使用的互斥條件，就要允許多個進程同時訪問共享資源。但是這種方法受到資源本身固有特性的時訪問共享資源。但是這種方法受到資源本身固有特性的限制，對某些資源是行不通的。例如打印機，就不允許多限制，對某些資源是行不通的。例如打印機，就不允許多個進程在其運行期間交替打印數據，打印機只能互斥使用。個進程在其運行期間交替打印數據，打印機只能互斥使用。而文件，可能允許多個進程對其進行讀訪問，但只允許互而文件，可能允許多個

56、進程對其進行讀訪問，但只允許互斥地寫訪問。因此，互斥條件難以破壞。斥地寫訪問。因此，互斥條件難以破壞。 死鎖的防止是通過設置某些嚴格的限制條件，以破壞死鎖的防止是通過設置某些嚴格的限制條件，以破壞產生死鎖的必要條件來防止死鎖的發(fā)生。產生死鎖的必要條件來防止死鎖的發(fā)生。 操作系統(tǒng) 第三章 處理機調度與死鎖4949 2 2破壞不剝奪條件破壞不剝奪條件 該策略規(guī)定，一個已保持了某些資源的進程，若新的資該策略規(guī)定，一個已保持了某些資源的進程，若新的資源要求不能立即得到滿足，它必須釋放已保持的所有資源。源要求不能立即得到滿足，它必須釋放已保持的所有資源。以后再需要時重新申請。這意味著，一個進程已占有的資

57、源，以后再需要時重新申請。這意味著，一個進程已占有的資源，在運行過程中可能暫時地釋放，或說被剝奪。在運行過程中可能暫時地釋放，或說被剝奪。問題：問題：1 1）這種防止死鎖的策略實現起來比較復雜；）這種防止死鎖的策略實現起來比較復雜；2 2）一個資源在使用一段時間后被釋放，可能會造成前階段）一個資源在使用一段時間后被釋放，可能會造成前階段工作的失效，即使采取某些防范措施，也還會使前后兩次運工作的失效，即使采取某些防范措施，也還會使前后兩次運行的信息不連續(xù)。行的信息不連續(xù)。3 3）該策略還可能由于反復地申請和釋放資源，使進程的執(zhí)）該策略還可能由于反復地申請和釋放資源，使進程的執(zhí)行無限推遲。這不僅延

58、長了進程的周轉時間，還增加了系統(tǒng)行無限推遲。這不僅延長了進程的周轉時間，還增加了系統(tǒng)開銷，又降低了系統(tǒng)吞吐量。開銷，又降低了系統(tǒng)吞吐量。 操作系統(tǒng) 第三章 處理機調度與死鎖5050 3 3破壞占有且等待條件破壞占有且等待條件-資源的靜態(tài)分配策略資源的靜態(tài)分配策略 系統(tǒng)要求所有進程一次性地申請其所需的全部資源。若系統(tǒng)要求所有進程一次性地申請其所需的全部資源。若系統(tǒng)有足夠的資源分配給該進程時，便一次把所有其所需的系統(tǒng)有足夠的資源分配給該進程時，便一次把所有其所需的資源分配給該進程。這樣，該進程在整個運行期間，便不會資源分配給該進程。這樣，該進程在整個運行期間，便不會再提出任何資源要求，從而使請求條

59、件不成立。但在分配時再提出任何資源要求，從而使請求條件不成立。但在分配時只要有一種資源要求不能滿足，則已有的其它資源也全部不只要有一種資源要求不能滿足，則已有的其它資源也全部不分配給該進程，該進程只能等待。由于等待期間的進程不占分配給該進程，該進程只能等待。由于等待期間的進程不占有任何資源，因此，破壞了必要條件之有任何資源，因此，破壞了必要條件之3 3，防止了死鎖發(fā)生。，防止了死鎖發(fā)生。 破壞占有且等待條件破壞占有且等待條件-資單請求方式分配資源資單請求方式分配資源優(yōu)點：優(yōu)點：簡單、易于實現，且很安全。簡單、易于實現，且很安全。 操作系統(tǒng) 第三章 處理機調度與死鎖5151缺點：缺點：1 1）資

60、源嚴重浪費。）資源嚴重浪費。 一個進程一次獲得其所需的全部資源且獨占，其中可一個進程一次獲得其所需的全部資源且獨占，其中可能有些資源很少使用，甚至在整個運行期間都未使用，這能有些資源很少使用，甚至在整個運行期間都未使用，這就嚴重地惡化了系統(tǒng)資源利用率：就嚴重地惡化了系統(tǒng)資源利用率：2 2）進程延遲運行。）進程延遲運行。 僅當進程獲得其所需全部資源后，方能開始運行，但僅當進程獲得其所需全部資源后，方能開始運行，但可能有許多資源長期被其它進程占用，致使進程推遲運行，可能有許多資源長期被其它進程占用，致使進程推遲運行，這往往要經過很長的時延。這往往要經過很長的時延。 操作系統(tǒng) 第三章 處理機調度與死