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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21、度算法（先來先服務調度算法（FCFSFCFS） 操作系統 第三章 處理機調度與死鎖2222例：先來先服務調度算法（單位：小時，并以十進制計）例：先來先服務調度算法（單位：小時，并以十進制計）作業作業提交時間提交時間運行時間運行時間開始時間開始時間完成時間完成時間周轉時間周轉時間帶權周轉時間帶權周轉時間 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 操作系統 第三章 處理機調度與死鎖23232. 2. 短作業優先調度算法（短作業優先調度算法（SJFSJF） 此算法總是優先調度要求運行時間最短的作業。此算法總是優先調度要求運行時間最短的作業。優點：優點：易于實現，效率比較高。易于實現，效率比較高。缺點：缺點：只照顧短作業而不考慮長作業的利益。只照顧短作業而不考慮長作業的利益。 如果系統不斷地接受新的短作業。則有可能較長作業如果系統不斷地接受新的短作業。則有可能較長作業長時間等待而不能運行。長時間等待而不能運行。 操作系統 第三章 處理機調度與死鎖2424例：短作業優先調度算法（單位：小時，并

23、以十進制計）例：短作業優先調度算法（單位：小時，并以十進制計）作業作業提交時間提交時間運行時間運行時間開始時間開始時間完成時間完成時間周轉時間周轉時間帶權周轉時間帶權周轉時間 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 操作系統 第三章 處理機調度與死鎖25253. 3. 響應比高者優先調度算法響應比高者

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

25、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例：響應比高者優先調度算法（單位：小時，并以十進制計例：響應比高者優先調度算法（單位：小時，并以十進制計) )平均周轉時間平均周轉時間T T1.6251.625， 平均帶權周轉時間平均帶權周轉時間W W5.6755.675 響應比響應比1 1作業等待時間作業等待時間/ /執行時間執行時間例如：當作業例如：當作業3 3結束時，結束時，Rp2= 1Rp2= 1作業等

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

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

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

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

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

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

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

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

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

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

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

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

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

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

40、以表示為：入系統的進程數來決定。可以表示為： N NT Tq q 其中，其中，q q是時間片的大小，是時間片的大小，T T是系統的響應時間，是系統的響應時間，N N是進入系統是進入系統的進程數。的進程數。 簡單輪轉法的優點是簡單、方便，但由于采用固定時間簡單輪轉法的優點是簡單、方便，但由于采用固定時間片的方式，調度欠靈活，服務質量不夠理想。可以通過以下片的方式，調度欠靈活，服務質量不夠理想。可以通過以下兩個方面加以改進：兩個方面加以改進：1 1）將固定時間片方式改為可變時間片方式；）將固定時間片方式改為可變時間片方式；2 2）將單就緒隊列改為多就緒隊列。）將單就緒隊列改為多就緒隊列。 操作系統

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

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

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

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

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

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

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

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

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

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

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

52、亦即發生了死鎖。二、產生死鎖的原因 產生的產生的根本原因根本原因是系統能夠提供的資源數少于需要該是系統能夠提供的資源數少于需要該資源的進程數資源的進程數( (系統資源不足系統資源不足) )。 1 1）對資源的分配策略（請求順序）不當）對資源的分配策略（請求順序）不當 ； 2 2）進程推進順序非法。）進程推進順序非法。 死鎖起因是并發進程的資源競爭。死鎖起因是并發進程的資源競爭。 可剝奪性資源可剝奪性資源 非剝奪性資源非剝奪性資源 操作系統 第三章 處理機調度與死鎖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的三種可能的進展情況：的三種可能的進展情況： 操作系統 第三章 處理機調度與死鎖4747三、死鎖存在的必要條件1 1）互斥條件。互斥條件。進程對其所要求的資源進行排它性控制，進程對其所要求的資源進行排它性控制，即一次只有一個進程可以使用一個資源。即一次只有一個進程可以使用一個資

54、源。2 2）不剝奪條件不剝奪條件。進程所獲得進程所獲得的資源在未被釋放之前，不能被的資源在未被釋放之前，不能被其它進程強行剝奪。其它進程強行剝奪。3 3）占有且等待條件占有且等待條件。進程每。進程每次申請它所需要的一部分資源，次申請它所需要的一部分資源，在進程等待分配其它資源的同時，在進程等待分配其它資源的同時，可以占有已分配的資源。可以占有已分配的資源。 P1P1P2P2 R1 R1 R2 R2被占有被占有 被占有被占有 請求請求 請求請求 4 4）環路條件。）環路條件。在發生死鎖時，必然存在一個進程資源的在發生死鎖時，必然存在一個進程資源的循環等待鏈，循環等待鏈， 操作系統 第三章 處理機

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

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

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

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

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

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