第05講_進程調度

1、1第第 五五 講講清華大學軟件學院清華大學軟件學院22.6 進程調度進程調度在多道系統(tǒng)當中，往往有多個進程同時在內存中在多道系統(tǒng)當中，往往有多個進程同時在內存中運行。在任何時刻，一個進程只可能是以下三種運行。在任何時刻，一個進程只可能是以下三種狀態(tài)之一：狀態(tài)之一：v 運行狀態(tài)：該進程正在運行狀態(tài)：該進程正在CPU上運行，每個上運行，每個CPU 上最多只能有一個進程在運行；上最多只能有一個進程在運行；v 就緒狀態(tài)：進程已經(jīng)就緒，隨時可以運行；就緒狀態(tài)：進程已經(jīng)就緒，隨時可以運行；v 阻塞狀態(tài)：如在某個信號量上被阻塞，等待阻塞狀態(tài)：如在某個信號量上被阻塞，等待I/O與此相對應，操作系統(tǒng)會維護相應的

2、狀態(tài)隊列。與此相對應，操作系統(tǒng)會維護相應的狀態(tài)隊列。3就緒隊列和各種就緒隊列和各種I/O設備隊列設備隊列（本圖摘自（本圖摘自Silberschatz, Galvin and Gagne： “Operating System Concepts”）選擇誰去運行？選擇誰去運行？4 在操作系統(tǒng)中，負責去做這個選擇的那在操作系統(tǒng)中，負責去做這個選擇的那 部分程序，稱為部分程序，稱為調度程序調度程序(scheduler)； 調度程序在決策過程中所采用的算法，調度程序在決策過程中所采用的算法， 稱為是稱為是調度算法調度算法； 調度程序是調度程序是CPU資源的管理者；資源的管理者； 調度的對象是進程，也可以是

3、線程，大調度的對象是進程，也可以是線程，大 多數(shù)的調度問題對兩者都是適用的。多數(shù)的調度問題對兩者都是適用的。52.6.1 關于調度的若干問題關于調度的若干問題1. 歷史背景q 在早期的簡單批處理系統(tǒng)當中，調度算法很簡在早期的簡單批處理系統(tǒng)當中，調度算法很簡 單：選擇磁帶上的下一個作業(yè)運行；單：選擇磁帶上的下一個作業(yè)運行；q 隨著分時系統(tǒng)的出現(xiàn)，同時有多個用戶在等待隨著分時系統(tǒng)的出現(xiàn)，同時有多個用戶在等待 服務，使得調度算法變得越來越復雜。有些大服務，使得調度算法變得越來越復雜。有些大 型機系統(tǒng)還把批處理與分時結合在一起，更增型機系統(tǒng)還把批處理與分時結合在一起，更增 大了難度。由于當時的大了難度

4、。由于當時的CPU時間是一種稀缺資時間是一種稀缺資 源，因此調度算法的好壞將直接影響到系統(tǒng)的源，因此調度算法的好壞將直接影響到系統(tǒng)的 性能和用戶的滿意度，算法的設計很受重視。性能和用戶的滿意度，算法的設計很受重視。6q 隨著個人計算機時代的到來，形勢發(fā)生了變化。隨著個人計算機時代的到來，形勢發(fā)生了變化。 首先，在首先，在PC上通常只有一個進程在活動，這樣，上通常只有一個進程在活動，這樣， 調度程序無事可做。其次，計算機變得越來越快調度程序無事可做。其次，計算機變得越來越快, CPU已不是稀缺資源了，哪個程序先運行或運行已不是稀缺資源了，哪個程序先運行或運行, 已經(jīng)不重要了。因此，調度算法的作用

5、已經(jīng)顯得已經(jīng)不重要了。因此，調度算法的作用已經(jīng)顯得 微不足道了。微不足道了。q 不過，對于那些高端聯(lián)網(wǎng)工作站和服務器而言，不過，對于那些高端聯(lián)網(wǎng)工作站和服務器而言， 多個進程需要同時競爭多個進程需要同時競爭CPU的使用權，因此調度的使用權，因此調度 問題又出現(xiàn)了。首先，調度程序要選擇合適的進問題又出現(xiàn)了。首先，調度程序要選擇合適的進 程去運行，因為對于不同的進程，用戶期望的響程去運行，因為對于不同的進程，用戶期望的響 應時間和要求是不同的；其次，調度程序要注意應時間和要求是不同的；其次，調度程序要注意 CPU的使用效率，因為進程切換的開銷很大。的使用效率，因為進程切換的開銷很大。72. 進程的

6、行為 CPU繁忙（繁忙（CPU-bound）的進程：大部分時間的進程：大部分時間 處于運行和就緒狀態(tài)；處于運行和就緒狀態(tài)； I/O繁忙（繁忙（I/O-bound）的進程：大部分時間處的進程：大部分時間處 于阻塞狀態(tài)。于阻塞狀態(tài)。8（本圖摘自（本圖摘自Andrew S. Tanenbaum： “Modern Operating Systems” ）CPU繁忙與繁忙與I/O繁忙繁忙CPU繁忙繁忙I/O繁忙繁忙9 內部因素：進程自身的功能決定了它的各種工內部因素：進程自身的功能決定了它的各種工作量。例如，矩陣相乘進程的計算量大，文件作量。例如，矩陣相乘進程的計算量大，文件管理進程的管理進程的I/O需

7、求很大；需求很大； 外部因素：計算機系統(tǒng)的運行速度決定了完成外部因素：計算機系統(tǒng)的運行速度決定了完成這些工作量所需要的時間長短。工作量和工作這些工作量所需要的時間長短。工作量和工作時間是兩回事，判斷一個進程是屬于時間是兩回事，判斷一個進程是屬于CPU繁忙繁忙還是屬于輸入輸出繁忙，主要看它的計算時間還是屬于輸入輸出繁忙，主要看它的計算時間和輸入輸出時間；和輸入輸出時間； I/O設備的運行速度較慢，設備的運行速度較慢，CPU的運行速度較的運行速度較快，而且更新?lián)Q代的速度快，將來進程都趨向快，而且更新?lián)Q代的速度快，將來進程都趨向于于I/O繁忙。繁忙。CPU繁忙還是繁忙還是I/O繁忙？繁忙？10 VC

8、D播放軟件；播放軟件； WORD文字編輯器；文字編輯器； 磁盤碎片整理工具磁盤碎片整理工具defrag。CPU繁忙還是繁忙還是I/O繁忙？（續(xù)）繁忙？（續(xù)）113. 何時調度？1. 當一個新的進程被創(chuàng)建時，是執(zhí)行新進程還當一個新的進程被創(chuàng)建時，是執(zhí)行新進程還是繼續(xù)執(zhí)行父進程？是繼續(xù)執(zhí)行父進程？2. 當一個進程運行完畢時；當一個進程運行完畢時；3. 當一個進程由于當一個進程由于I/O、信號量或其他的某個原、信號量或其他的某個原因被阻塞時；因被阻塞時；4. 當一個當一個I/O中斷發(fā)生時，表明某個中斷發(fā)生時，表明某個I/O操作已經(jīng)操作已經(jīng)完成，而等待該完成，而等待該I/O操作的進程轉入就緒狀態(tài)；操作

9、的進程轉入就緒狀態(tài)；5. 在分時系統(tǒng)中，當一個時鐘中斷發(fā)生時。在分時系統(tǒng)中，當一個時鐘中斷發(fā)生時。12不可搶占調度方式不可搶占調度方式：一個進程若被選中，就：一個進程若被選中，就一直運行下去，直到它被阻塞（一直運行下去，直到它被阻塞（I/O，或正在，或正在等待其他的進程），或主動地交出等待其他的進程），或主動地交出CPU。以。以上的情形上的情形13均可發(fā)生調度；均可發(fā)生調度；可搶占調度方式可搶占調度方式：當一個進程在運行時，調：當一個進程在運行時，調度程序可以打斷它。以上的情形度程序可以打斷它。以上的情形15均可發(fā)均可發(fā)生調度，另外，在其他的一些情形下，如就生調度，另外，在其他的一些情形下，如

10、就緒隊列中有進程的優(yōu)先級高于當前運行進程緒隊列中有進程的優(yōu)先級高于當前運行進程的優(yōu)先級，也可能立即進行調度。的優(yōu)先級，也可能立即進行調度。兩種調度方式兩種調度方式134. 調度算法的類別不同的不同的OS有不同的目標，對調度程序有不同的有不同的目標，對調度程序有不同的要求，因此需要不同類型的調度算法。要求，因此需要不同類型的調度算法。批處理系統(tǒng)：無須及時的用戶響應，采用不批處理系統(tǒng)：無須及時的用戶響應，采用不可搶占的調度方式，或時間間隔很長的可搶可搶占的調度方式，或時間間隔很長的可搶占調度方式，從而允許進程能長時間運行，占調度方式，從而允許進程能長時間運行，減少進程的切換次數(shù)，提高系統(tǒng)的性能；減

11、少進程的切換次數(shù)，提高系統(tǒng)的性能；交互式系統(tǒng)：及時的用戶響應非常重要，必交互式系統(tǒng)：及時的用戶響應非常重要，必須采用可搶占的調度方式。以防單個進程占須采用可搶占的調度方式。以防單個進程占用太多用太多CPU時間，影響到其他進程的運行。時間，影響到其他進程的運行。實時系統(tǒng)：對響應時間要求苛刻，每個進程實時系統(tǒng)：對響應時間要求苛刻，每個進程運行時間很短，可采用可搶占的調度方式。運行時間很短，可采用可搶占的調度方式。145. 調度算法的目標算法調度的目標是多元的，有些是可以共存的，算法調度的目標是多元的，有些是可以共存的，也有些是相互牽制的，對于一個實際的調度算法也有些是相互牽制的，對于一個實際的調度

12、算法來說，有一個綜合權衡的過程。來說，有一個綜合權衡的過程。所有系統(tǒng)普遍適用的目標：所有系統(tǒng)普遍適用的目標： 公平：大致相當?shù)膬蓚€進程所得到的公平：大致相當?shù)膬蓚€進程所得到的CPU時間時間 也應是大致相同的；也應是大致相同的； 對已制訂的調度策略必須能貫徹執(zhí)行；對已制訂的調度策略必須能貫徹執(zhí)行； 均衡：盡可能使整個系統(tǒng)的各部分都忙起來，均衡：盡可能使整個系統(tǒng)的各部分都忙起來， 提高系統(tǒng)資源的使用效率。提高系統(tǒng)資源的使用效率。15批處理系統(tǒng)中調度算法的評價指標：批處理系統(tǒng)中調度算法的評價指標： 吞吐量吞吐量（Throughput）：單位時間內所完成的）：單位時間內所完成的 作業(yè)數(shù)，與作業(yè)本身特性

13、和調度算法有關；作業(yè)數(shù)，與作業(yè)本身特性和調度算法有關； 周轉時間周轉時間（Turnaround time）：一個批處理作）：一個批處理作 業(yè)從提交到完成（得到結果）所經(jīng)歷的時間。業(yè)從提交到完成（得到結果）所經(jīng)歷的時間。 包括：在收容隊列中等待，包括：在收容隊列中等待，CPU上執(zhí)行，就緒上執(zhí)行，就緒 隊列和阻塞隊列中等待，結果輸出等待；隊列和阻塞隊列中等待，結果輸出等待；C 平均周轉時間：一批作業(yè)的周轉時間的平均值；平均周轉時間：一批作業(yè)的周轉時間的平均值；C 平均帶權周轉時間：權值是實際執(zhí)行時間的倒數(shù)平均帶權周轉時間：權值是實際執(zhí)行時間的倒數(shù); CPU的利用率的利用率：大中型主機的：大中型主機

14、的CPU較貴，所以較貴，所以 讓它時刻不停地轉著。讓它時刻不停地轉著。16周轉時間：周轉時間：iiiSET（Ei表示作業(yè)表示作業(yè)i完成時間，完成時間， Si表示作業(yè)表示作業(yè)i提交時間）提交時間）平均周轉時間：平均周轉時間：NiiTNT11(N表示作業(yè)的個數(shù)表示作業(yè)的個數(shù))平均帶權周轉時間：平均帶權周轉時間：NiiirTNW11(ri表示作業(yè)表示作業(yè)i的實際執(zhí)行時間的實際執(zhí)行時間)17交換式系統(tǒng)中調度算法的評價指標：交換式系統(tǒng)中調度算法的評價指標： 響應時間：用戶輸入一個請求（如擊鍵）到系統(tǒng)響應時間：用戶輸入一個請求（如擊鍵）到系統(tǒng) 給出首次響應（如屏幕顯示）的時間。響應時間給出首次響應（如屏幕

15、顯示）的時間。響應時間 越短越好，優(yōu)先考慮交互式進程；越短越好，優(yōu)先考慮交互式進程； 相稱性：滿足用戶對程序運行時間的期望值。相稱性：滿足用戶對程序運行時間的期望值。實時系統(tǒng)中調度算法的評價指標：實時系統(tǒng)中調度算法的評價指標： 實時響應：必須嚴格地遵守時間期限；實時響應：必須嚴格地遵守時間期限； 可預測性：在實時多媒體系統(tǒng)中，信號的播放必可預測性：在實時多媒體系統(tǒng)中，信號的播放必 須連貫，不能時斷時續(xù)。須連貫，不能時斷時續(xù)。182.6.2 批處理系統(tǒng)中的調度算法批處理系統(tǒng)中的調度算法1. 先來先服務 先來先服務先來先服務（First Come First Served，F(xiàn)CFS； First

16、In First Out，F(xiàn)IFO）：按照作業(yè)到達的）：按照作業(yè)到達的 先后次序進行調度；先后次序進行調度； 不可搶占方式：當前進程占用不可搶占方式：當前進程占用CPU，直到執(zhí)行，直到執(zhí)行 完或被阻塞，才讓出完或被阻塞，才讓出CPU給另外一個進程；給另外一個進程； 在進程被喚醒后（如在進程被喚醒后（如I/O完成），并不立即恢復完成），并不立即恢復 執(zhí)行，而是放在就緒隊列的末尾；執(zhí)行，而是放在就緒隊列的末尾； 優(yōu)點：簡單、公平，易于理解也易于實現(xiàn)。優(yōu)點：簡單、公平，易于理解也易于實現(xiàn)。 現(xiàn)實生活中應用廣泛：排隊。現(xiàn)實生活中應用廣泛：排隊。19問題問題1. 平均周轉時間取決于各作業(yè)到達的順序，若平

17、均周轉時間取決于各作業(yè)到達的順序，若短作業(yè)位于長作業(yè)之后，將增大平均周轉時間。短作業(yè)位于長作業(yè)之后，將增大平均周轉時間。例如，三個作業(yè)例如，三個作業(yè)A、B、C的運行時間為的運行時間為24、3、3時間時間 24 27 30ABC平均周轉時間平均周轉時間(24+27+30)/327平均等待時間平均等待時間(0+24+27)/317時間時間 3 6 30ABC平均周轉時間平均周轉時間(3+6+30)/313平均等待時間平均等待時間(0+3+6)/3320問題問題2. 無法充分利用無法充分利用CPU繁忙的作業(yè)與繁忙的作業(yè)與I/O繁忙的繁忙的作業(yè)之間的互補關系。如果作業(yè)之間的互補關系。如果CPU繁忙的作

18、業(yè)獨占很繁忙的作業(yè)獨占很長時間的長時間的CPU，使得，使得I/O設備空閑，也使得設備空閑，也使得I/O繁忙繁忙的作業(yè)無法運行。的作業(yè)無法運行。作業(yè)作業(yè)A作業(yè)作業(yè)BCPUI/O作業(yè)作業(yè)A作業(yè)作業(yè)B時間時間t0t1 t2t3t4212. 短作業(yè)優(yōu)先 短作業(yè)優(yōu)先短作業(yè)優(yōu)先（Shortest Job First，SJF），設計），設計 目標是改進目標是改進FCFS算法，減少平均周轉時間；算法，減少平均周轉時間； SJF算法要求作業(yè)在開始執(zhí)行時預計執(zhí)行時間，算法要求作業(yè)在開始執(zhí)行時預計執(zhí)行時間， 對預計執(zhí)行時間短的作業(yè)優(yōu)先分派處理器；對預計執(zhí)行時間短的作業(yè)優(yōu)先分派處理器； 兩種實現(xiàn)方案：兩種實現(xiàn)方案：Q

19、 不可搶占方式：當前作業(yè)在運行時不會被打不可搶占方式：當前作業(yè)在運行時不會被打 斷，只有運行完畢或阻塞時，才讓出斷，只有運行完畢或阻塞時，才讓出CPU；Q 可搶占方式：如果一個新的短作業(yè)到來，其可搶占方式：如果一個新的短作業(yè)到來，其 運行時間小于當前正在運行作業(yè)的剩余時間，運行時間小于當前正在運行作業(yè)的剩余時間， 則搶占則搶占CPU運行，稱為運行，稱為SRTF（Shortest Remaining Time First）。）。22 可以證明：對于一組同時到達的作業(yè)，采用可以證明：對于一組同時到達的作業(yè)，采用SJF 算法將得到一個算法將得到一個最小最小的平均周轉時間。的平均周轉時間。D時間時間A

20、Ca a+b a+b+c a+b+c+d 例如，考察例如，考察4個作業(yè)個作業(yè)A、B、C、D，其運行時間分，其運行時間分別為別為a、b、c、dBA、B、C、D的周轉時間分別為的周轉時間分別為a、a+b、a+b+c和和a+b+c+d，因此平均周轉時間為：，因此平均周轉時間為：(4a+3b+2c+d)/4顯然，當顯然，當a b c d時，平均周轉時間最小。時，平均周轉時間最小。23取得最優(yōu)解的前提之一：這組作業(yè)必須同時到達；取得最優(yōu)解的前提之一：這組作業(yè)必須同時到達；例如：例如：進程進程到達時間到達時間運行時間運行時間P1 0.0 7P2 2.0 4P3 4.0 1P4 5.0 4SJF（不可搶占）

21、：（不可搶占）：P1P3P2P403781216平均周轉時間：平均周轉時間：(7 + 10 + 4 + 11) / 4 = 8平均等待時間：平均等待時間：(0 + 6 + 3 + 7) / 4 = 4若按若按P2,P3,P4,P1順序順序, 平均周轉和等待時間平均周轉和等待時間7.75, 3.7524進程進程到達時間到達時間運行時間運行時間P1 0.0 7P2 2.0 4P3 4.0 1P4 5.0 4SJF（可搶占）：（可搶占）：P1P3P2P4P2P1027411165平均周轉時間：平均周轉時間：(16 + 5 + 1 + 6) / 4 = 7平均等待時間：平均等待時間：(9 + 1 +

22、0 + 2) / 4 = 325前提條件之二：需要事先估計作業(yè)的運行時間前提條件之二：需要事先估計作業(yè)的運行時間如何知道作業(yè)的運行時間？如何知道作業(yè)的運行時間？% 該時間只可能是一個估計值；該時間只可能是一個估計值；% 讓提交該作業(yè)的用戶來提供。不太實用；讓提交該作業(yè)的用戶來提供。不太實用；% 使用前面的使用前面的CPU運行時間來預測后面的運行時間來預測后面的CPU運運 行時間，通過過去的行為來預測將來的行為。行時間，通過過去的行為來預測將來的行為。C 如果一個作業(yè)已經(jīng)運行很長時間了，那它可能如果一個作業(yè)已經(jīng)運行很長時間了，那它可能 還會運行更長的時間；還會運行更長的時間；C 使用指數(shù)平均值函

23、數(shù)來預測下一段使用指數(shù)平均值函數(shù)來預測下一段CPU時間時間;26指數(shù)平均值函數(shù)方法指數(shù)平均值函數(shù)方法.1 1nnnt1. tn 第第n個個CPU運行時間的實際長度；運行時間的實際長度；2. n+1 下一個下一個CPU運行時間的預測長度；運行時間的預測長度；3. 定義系數(shù)定義系數(shù) ，0 14. 定義：定義：273. 三層調度模型（本圖摘自（本圖摘自Andrew S. Tanenbaum： “Modern Operating Systems” ）28 準入調度：決定哪一些作業(yè)能夠進入系統(tǒng)運行。準入調度：決定哪一些作業(yè)能夠進入系統(tǒng)運行。 在這個層次上的調度算法主要有短作業(yè)優(yōu)先進入在這個層次上的調度算

24、法主要有短作業(yè)優(yōu)先進入, 以及把以及把CPU繁忙的作業(yè)和繁忙的作業(yè)和I/O繁忙的作業(yè)混合在繁忙的作業(yè)混合在 一起提交給系統(tǒng)；一起提交給系統(tǒng)； 存儲調度：決定哪一些進程應該留在內存中，哪存儲調度：決定哪一些進程應該留在內存中，哪 一些進程應該保存在磁盤上。需要考慮的因素包一些進程應該保存在磁盤上。需要考慮的因素包 括該進程呆在內存或磁盤上的時間長短，它所用括該進程呆在內存或磁盤上的時間長短，它所用 的的CPU時間以及它的優(yōu)先級等；時間以及它的優(yōu)先級等； CPU調度：從內存當中，選擇一個已經(jīng)就緒的進調度：從內存當中，選擇一個已經(jīng)就緒的進 程去運行。程去運行。批處理系統(tǒng)中的三層調度模型批處理系統(tǒng)中的

25、三層調度模型292.6.3 交互式系統(tǒng)中的調度算法交互式系統(tǒng)中的調度算法1. 時間片輪轉法 在在時間片輪轉算法時間片輪轉算法（Round-Robin，RR）中，將）中，將 所有的就緒進程按照所有的就緒進程按照FCFS原則，排成一個隊列；原則，排成一個隊列； 每次調度時將處理器分派給隊首進程，讓其執(zhí)行每次調度時將處理器分派給隊首進程，讓其執(zhí)行 一小段一小段CPU時間（時間片）；時間（時間片）； 在一個時間片結束時，如果進程還沒有執(zhí)行完的在一個時間片結束時，如果進程還沒有執(zhí)行完的 話，將發(fā)生時鐘中斷，在時鐘中斷中，進程調度話，將發(fā)生時鐘中斷，在時鐘中斷中，進程調度 程序將暫停當前進程的執(zhí)行，并將其

26、送到就緒隊程序將暫停當前進程的執(zhí)行，并將其送到就緒隊 列的末尾，然后執(zhí)行當前的隊首進程；列的末尾，然后執(zhí)行當前的隊首進程； 如果一個進程在它的時間片用完之前就已結束或如果一個進程在它的時間片用完之前就已結束或 被阻塞，那么立即讓出被阻塞，那么立即讓出CPU。30開始時，進程開始時，進程B位于隊列之首，因此被調度執(zhí)行。當位于隊列之首，因此被調度執(zhí)行。當它的時間片用完后，就把它送到就緒隊列的末尾。它的時間片用完后，就把它送到就緒隊列的末尾。同時，進程同時，進程F成為隊首進程，被調度運行。成為隊首進程，被調度運行。（本圖摘自（本圖摘自Andrew S. Tanenbaum： “Modern Oper

27、ating Systems” ）31Round robin, too.32 優(yōu)點：優(yōu)點：e 公平性公平性：各個就緒進程平均地分配：各個就緒進程平均地分配CPU的使用的使用 時間。假設有時間。假設有n個就緒進程，時間片大小為個就緒進程，時間片大小為q， 那么每個進程將得到那么每個進程將得到1/n的的CPU時間；時間；e 活動性活動性：每個進程最多等待：每個進程最多等待(n-1)q時間就能夠時間就能夠 再次得到再次得到CPU去運行；去運行；e 一般來說，平均周轉時間較一般來說，平均周轉時間較SJF算法為長，但算法為長，但 能夠得到能夠得到較短的平均響應時間較短的平均響應時間； 缺點：缺點：q的大小

28、難以確定的大小難以確定（一般在（一般在2050ms）。）。e q太大：退化為太大：退化為FCFS算法，進程在一個時間片算法，進程在一個時間片 內都執(zhí)行完，響應時間長。如內都執(zhí)行完，響應時間長。如q=100ms；e q太?。好總€進程都需要更多的時間片才能處理太?。好總€進程都需要更多的時間片才能處理 完，進程切換次數(shù)增加，增大系統(tǒng)開銷。如完，進程切換次數(shù)增加，增大系統(tǒng)開銷。如q=4ms時間片輪轉法的特點時間片輪轉法的特點33進程進程CPU時間時間P153 P2 17 P368 P4 24一個例子：時間片長度一個例子：時間片長度q20P1P2P3P4P1P3P4P1P3P30 20 37 57 77

29、 97 117 121 134 154 162平均周轉時間：平均周轉時間：(134 + 37 + 162 + 121) / 4113.5SJF的平均周轉時間：的平均周轉時間： (94 + 17 + 162 + 41) / 478.5342. 優(yōu)先級算法1 輪轉法有一個缺省的前提，即各進程同等重要；輪轉法有一個缺省的前提，即各進程同等重要；1 “人人生而平等人人生而平等”？ 恐怕不太現(xiàn)實！同樣，并恐怕不太現(xiàn)實！同樣，并 不是每個進程都同等重要，不是每個進程都同等重要， 怎么辦？分等級！怎么辦？分等級！1 優(yōu)先級算法優(yōu)先級算法（Priority Scheduling）：給每個進）：給每個進 程設置

30、一個優(yōu)先級，然后在所有就緒進程中選擇程設置一個優(yōu)先級，然后在所有就緒進程中選擇 優(yōu)先級最高的那個進程去運行；優(yōu)先級最高的那個進程去運行；1 SJF就是一個優(yōu)先級算法，每個進程的優(yōu)先級是就是一個優(yōu)先級算法，每個進程的優(yōu)先級是 它的它的CPU運行時間（時間越短，優(yōu)先級越高）；運行時間（時間越短，優(yōu)先級越高）；1 分為分為可搶占可搶占和和不可搶占不可搶占兩種方式；各進程優(yōu)先級兩種方式；各進程優(yōu)先級 的確定方式可分為的確定方式可分為靜態(tài)靜態(tài)和和動態(tài)動態(tài)兩種。兩種。35靜態(tài)優(yōu)先級方式靜態(tài)優(yōu)先級方式 確定優(yōu)先級的依據(jù)：確定優(yōu)先級的依據(jù)： 進程類型（系統(tǒng)進程優(yōu)先級高于用戶進程，進程類型（系統(tǒng)進程優(yōu)先級高于用

31、戶進程，交互式進程高于批處理進程）；交互式進程高于批處理進程）； 對系統(tǒng)資源的需求（對對系統(tǒng)資源的需求（對CPU和內存需求較少和內存需求較少的進程，優(yōu)先級較高）；的進程，優(yōu)先級較高）； 用戶要求（用戶級別和付費情況，如軍用電用戶要求（用戶級別和付費情況，如軍用電腦、商用電腦）。腦、商用電腦）。 靜態(tài)方式的缺點：高優(yōu)先級的進程一直占用靜態(tài)方式的缺點：高優(yōu)先級的進程一直占用CPU，低優(yōu)先級的進程，低優(yōu)先級的進程“饑餓饑餓”。 靜態(tài)優(yōu)先級方式靜態(tài)優(yōu)先級方式是指在創(chuàng)建進程時確定進程優(yōu)先級，是指在創(chuàng)建進程時確定進程優(yōu)先級，并保持不變到進程結束。并保持不變到進程結束。36動態(tài)優(yōu)先級方式動態(tài)優(yōu)先級方式 為防

32、為防“饑餓饑餓”, 根據(jù)運行時間和等待時間調整優(yōu)先根據(jù)運行時間和等待時間調整優(yōu)先級級 進程每執(zhí)行一個時間片就降低其優(yōu)先級。當一進程每執(zhí)行一個時間片就降低其優(yōu)先級。當一個進程持續(xù)執(zhí)行時，其優(yōu)先級降低到讓出個進程持續(xù)執(zhí)行時，其優(yōu)先級降低到讓出CPU； 在就緒隊列中，等待時間延長則優(yōu)先級提高，在就緒隊列中，等待時間延長則優(yōu)先級提高，從而使優(yōu)先級較低的進程在等待足夠的時間后，從而使優(yōu)先級較低的進程在等待足夠的時間后，其優(yōu)先級提高到可被調度執(zhí)行。其優(yōu)先級提高到可被調度執(zhí)行。 為了讓為了讓I/O忙起來，可提高忙起來，可提高I/O繁忙進程的優(yōu)先級。繁忙進程的優(yōu)先級。但如何判定一個進程是但如何判定一個進程是I

33、/O繁忙的？可把進程優(yōu)先繁忙的？可把進程優(yōu)先級設為級設為1/f，f是在上一個時間片中所用的時間比例是在上一個時間片中所用的時間比例動態(tài)優(yōu)先級方式動態(tài)優(yōu)先級方式是指在創(chuàng)建進程時賦予給進程的優(yōu)是指在創(chuàng)建進程時賦予給進程的優(yōu)先級，在進程運行過程中可以動態(tài)改變，以便獲得先級，在進程運行過程中可以動態(tài)改變，以便獲得更好的調度性能。更好的調度性能。37優(yōu)先級類別優(yōu)先級類別（本圖摘自（本圖摘自Andrew S. Tanenbaum： “Modern Operating Systems” ）可以把進程按照不同的優(yōu)先級別分組，然后在不同可以把進程按照不同的優(yōu)先級別分組，然后在不同級別之間使用優(yōu)先級算法，而在同一

34、級別的各個進級別之間使用優(yōu)先級算法，而在同一級別的各個進程之間使用時間片輪轉法。程之間使用時間片輪轉法。383. 多級隊列算法多級隊列算法多級隊列算法（Multilevel Queue）引入多個就緒）引入多個就緒隊列，通過各個隊列的區(qū)別對待，達到一個綜合的隊列，通過各個隊列的區(qū)別對待，達到一個綜合的調度目標。調度目標。K 根據(jù)進程的性質或類型的不同，將就緒隊列再分根據(jù)進程的性質或類型的不同，將就緒隊列再分 為為若干個子隊列若干個子隊列，如系統(tǒng)進程、用戶交互進程、，如系統(tǒng)進程、用戶交互進程、 批處理進程等；批處理進程等；K 不同的隊列可以有不同的隊列可以有不同的優(yōu)先級不同的優(yōu)先級；K 不同的隊列

35、可以采用各自不同的隊列可以采用各自不同的調度算法不同的調度算法，如前，如前 臺的交互式進程可采用臺的交互式進程可采用RR算法，后臺的批處理進算法，后臺的批處理進 程可采用程可采用FCFS算法。算法。39K 在各個隊列之間也必須進行調度：在各個隊列之間也必須進行調度： 固定優(yōu)先級調度固定優(yōu)先級調度：按照各種類型的進程的優(yōu)先：按照各種類型的進程的優(yōu)先 級別從高到低地進行，先運行最高優(yōu)先級的所級別從高到低地進行，先運行最高優(yōu)先級的所 有進程，再運行次一級所有進程，依此類推。有進程，再運行次一級所有進程，依此類推。 問題：可能導致問題：可能導致“饑餓饑餓”； 時間片方法時間片方法：把：把CPU時間按比

36、例分配給不同的時間按比例分配給不同的 隊列，然后再由各個隊列的調度算法去調度，隊列，然后再由各個隊列的調度算法去調度， 如如80給前臺的交互式進程隊列（給前臺的交互式進程隊列（RR算法），算法）， 20給后臺的批處理進程隊列（給后臺的批處理進程隊列（FCFS）。）。40（本圖摘自（本圖摘自Silberschatz, Galvin and Gagne： “Operating System Concepts”）多級隊列算法的一個例子多級隊列算法的一個例子414. 多級反饋隊列算法J 多級隊列算法把每個進程按照它的類型多級隊列算法把每個進程按照它的類型固定固定在一在一 個隊列中，但問題是如何來確定進

37、程的類型？個隊列中，但問題是如何來確定進程的類型？ 而且有的進程其類型可能動態(tài)變化，怎么辦？而且有的進程其類型可能動態(tài)變化，怎么辦？ “路遙知馬力，日久見人心路遙知馬力，日久見人心”！J 多級反饋隊列算法多級反饋隊列算法 (Multilevel Feedback Queue) 即根據(jù)一個進程的運行反饋信息，即根據(jù)一個進程的運行反饋信息，動態(tài)地動態(tài)地調整它調整它 所在的隊列。所在的隊列。F 反饋反饋（Feedback）：即進程在運行當中的表）：即進程在運行當中的表 現(xiàn)，例如，它是否需要整個的時間片用于計現(xiàn)，例如，它是否需要整個的時間片用于計 算，或者它是否經(jīng)常地執(zhí)行算，或者它是否經(jīng)常地執(zhí)行I/O

38、操作？操作？42J 如何實現(xiàn)多級反饋隊列算法？需要確定以下的一如何實現(xiàn)多級反饋隊列算法？需要確定以下的一 些參數(shù)：些參數(shù)：F 隊列的個數(shù)；隊列的個數(shù)；F 每個隊列所用的調度算法；每個隊列所用的調度算法；F 用來確定何時給一個進程用來確定何時給一個進程“升級升級”的方法；的方法；F 用來確定何時給一個進程用來確定何時給一個進程“降級降級”的方法；的方法；F 用來確定一個進程的初始隊列的方法；用來確定一個進程的初始隊列的方法；43多級反饋隊列算法的一個例子多級反饋隊列算法的一個例子 三種優(yōu)先級別，三種優(yōu)先級別，3最高、最高、1最低，三個就緒隊列。時間片長度最低，三個就緒隊列。時間片長度 分別為分別

39、為N、2N和和4N； 新進程進入內存后，優(yōu)先級為新進程進入內存后，優(yōu)先級為3，加入隊列，加入隊列3的末尾，按的末尾，按FCFS 算法調度；若一個時間片內未能執(zhí)行完，則優(yōu)先級降為算法調度；若一個時間片內未能執(zhí)行完，則優(yōu)先級降為2，加，加 入到隊列入到隊列2的末尾，同樣按的末尾，同樣按FCFS算法調度；依此類推。算法調度；依此類推。 如果進程在時間片用完之前即被阻塞，則增加它的優(yōu)先級；如果進程在時間片用完之前即被阻塞，則增加它的優(yōu)先級； 僅當較高優(yōu)先級的隊列為空，才調度較低優(yōu)先級的隊列中的進僅當較高優(yōu)先級的隊列為空，才調度較低優(yōu)先級的隊列中的進 程執(zhí)行。若進程執(zhí)行時有新進程進入較高優(yōu)先級的隊列，則

40、搶程執(zhí)行。若進程執(zhí)行時有新進程進入較高優(yōu)先級的隊列，則搶 先執(zhí)行新進程。先執(zhí)行新進程。優(yōu)先級優(yōu)先級32144多級反饋隊列算法是時間片輪轉算法和優(yōu)先級算多級反饋隊列算法是時間片輪轉算法和優(yōu)先級算法法的綜合和發(fā)展。其特點是：的綜合和發(fā)展。其特點是： 為提高系統(tǒng)吞吐量和縮短平均周轉時間而照顧短為提高系統(tǒng)吞吐量和縮短平均周轉時間而照顧短進程：新進程一進來即賦予最高優(yōu)先級。進程：新進程一進來即賦予最高優(yōu)先級。 為獲得較好的為獲得較好的I/O設備利用率和縮短響應時間而設備利用率和縮短響應時間而照顧了照顧了I/O繁忙的進程：繁忙的進程： I/O繁忙進程：讓其進入最高優(yōu)先級隊列，以及時啟繁忙進程：讓其進入最高

41、優(yōu)先級隊列，以及時啟動動I/O操作。通常只需一個小時間片，即可處理完一操作。通常只需一個小時間片，即可處理完一次次I/O請求，然后轉入到阻塞隊列。請求，然后轉入到阻塞隊列。 CPU繁忙進程：每次都執(zhí)行完時間片，進入更低級隊繁忙進程：每次都執(zhí)行完時間片，進入更低級隊列。最終采用最大時間片來執(zhí)行，減少調度次數(shù)。列。最終采用最大時間片來執(zhí)行，減少調度次數(shù)。 不必估計進程的執(zhí)行時間，動態(tài)調節(jié)，能夠適應不必估計進程的執(zhí)行時間，動態(tài)調節(jié)，能夠適應一個進程在不同時間段的不同運行特點。一個進程在不同時間段的不同運行特點。452.6.4 實時系統(tǒng)中的調度算法實時系統(tǒng)中的調度算法 在實時系統(tǒng)中，對時間的要求是非常

42、嚴格的。典在實時系統(tǒng)中，對時間的要求是非常嚴格的。典 型的例子是：一個或多個外部的物理設備定期或型的例子是：一個或多個外部的物理設備定期或 不定期地生成激勵信號，而計算機必須在一定的不定期地生成激勵信號，而計算機必須在一定的 時間期限內做出恰當?shù)姆磻?。時間期限內做出恰當?shù)姆磻?硬實時硬實時：有一個絕對的時間期限，計算機的反應：有一個絕對的時間期限，計算機的反應 動作必須在此期限之前完成，如核電站的控制系動作必須在此期限之前完成，如核電站的控制系 統(tǒng)；統(tǒng)；軟實時軟實時：偶爾錯過一次期限雖然是令人不快：偶爾錯過一次期限雖然是令人不快 的，但也是可以容忍的，如的，但也是可以容忍的，如VCD的播放系統(tǒng)；的播放系統(tǒng)； 實時調度算法可以是實時調度算法可以是靜態(tài)的靜態(tài)的或或動態(tài)的動態(tài)的，前者在系，前者在系 統(tǒng)開始運行之前即已做好調度決策；而后者是在統(tǒng)開始運行之前即已做好調度決策；而后者是在 運行中做出調度決策。運行中做出調度決策。462.6.5 線程調度線程調度在進程調度中，如果每個進程都帶有多個的在進程調度中，如果每個進程都帶有多個的線程，那么我們就有了兩個層面上的并行關線程，那么我們就有了兩個層面上的并行關