【文章內(nèi)容簡介】 程的先來先服務(wù)調(diào)度算法作用在就緒隊列上。進(jìn)程就緒時，將 PCB插入到就緒隊列尾部；調(diào)度時，總是把 CPU分配給就緒隊列之首的進(jìn)程使用。它一直占用 CPU，除非運行結(jié)束自愿釋放，或因等待某事件的發(fā)生交出 CPU。這是一種非搶占式的調(diào)度算法。 . ? 輪轉(zhuǎn)調(diào)度算法 系統(tǒng)時鐘周期性地產(chǎn)生中斷。中斷發(fā)生時，迫使當(dāng)前正在運行的進(jìn)程中止運行，到就緒隊列里排隊，調(diào)度程序按 FCFS從就緒隊列里選擇就緒進(jìn)程投入運行。因此每個運行進(jìn)程在被搶占前，最多運行一個規(guī)定的時間長度，這個時間長度被稱為“時間片”。 . 分配給進(jìn)程 A 的一個時間片 q 分配給進(jìn)程 B 的一個時間片 q 分配給進(jìn)程 A 的另一個時間片 q 時鐘中斷 時鐘中斷 時鐘中斷 用戶 A一次 交互結(jié)束 . RR調(diào)度算法的關(guān)鍵是時間片設(shè)置的大小。若時間片 q設(shè)置得小，那么長作業(yè)可能需要經(jīng)若干個時間片才能完成一次交互活動，從而增加了系統(tǒng)在進(jìn)程間切換時的開銷；若時間片 q設(shè)置得長，長到每個交互只需要一個時間片就能夠完成時， 那么 RR就成 FCFS了。 所以，時間片的尺寸最 好是略大于一次典型交 互活動所需的時間。 q=4 時，五 個進(jìn)程的調(diào)度順 序是：A→B→C→D→B →E→D q=1 時，五 個進(jìn)程的調(diào)度順序是： A→A→A→B→B →C→B→D→C →B→E→D→C →B→E→D→C →B→D→D 五個作業(yè) A~E的情況如右所示，對進(jìn)程實施兩次 RR調(diào)度算法，時間片分別為 1個 CPU時間單位和 4個 CPU時間單位。求各進(jìn)程的開始運行時間、完成時間、周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間、平均周轉(zhuǎn)時間以及帶權(quán)平均周轉(zhuǎn)時間。 . RR進(jìn)程調(diào)度是個多路開關(guān)，通過它把一個 CPU分配給多個進(jìn)程使用，產(chǎn)生出有多個邏輯 CPU的空幻印象，只是每個邏輯 CPU的運行速度要比真正的物理 CPU來得慢罷了。 0 20 5 10 15 A B C D E 輪轉(zhuǎn) q=1 (RR) A B C D E 輪轉(zhuǎn) q=4 (RR) 0 20 5 10 15 進(jìn)程 B 到達(dá) 進(jìn)程 A到達(dá) 進(jìn)程 C 到達(dá) 進(jìn)程 D 到達(dá) 進(jìn)程 E 到達(dá) 例 37 ： 作業(yè) 所需 CPU時間 A B C D E 0 2 4 6 8 到達(dá)時間 3 6 4 5 2 ..解 ：返回目錄 就緒隊列里有如右所示五個進(jìn)程 P1~P5 ，實施HPF調(diào)度算法，試計算平均等待時間。 ? 優(yōu)先級調(diào)度算法 . 優(yōu)先級調(diào)度（ HPF）算法，是基于進(jìn)程優(yōu)先級進(jìn)行的調(diào)度算法。在需要調(diào)度時， HPF算法總是從就緒隊列里挑選優(yōu)先級最高者投入運行。 進(jìn)程的 PCB里，都會記錄進(jìn)程的優(yōu)先級。優(yōu)先級常用數(shù)字表示，比如0～ 7，或 0～ 4095。不過，數(shù)字 0到底表示最高還是最低，各個操作系統(tǒng)不盡相同。有的系統(tǒng)以數(shù)字越小表示優(yōu)先級越高，有的則以數(shù)字越大表示優(yōu)先級越高。本書規(guī)定數(shù)字越小優(yōu)先級越高。 . 例 38 ： 進(jìn)程 所需 CPU時間 P1 P2 P3 P4 P5 10 1 2 1 5 優(yōu)先級 3 1 4 5 2 它們的調(diào)度順序是： P2→P5→P1→P3→P4 。 . 解 ： . 相應(yīng)的 gantt圖如下所示。 P2 P5 P1 P3 P4 0 1 6 16 18 19 搶占式優(yōu)先級調(diào)度算法：一個新進(jìn)程抵達(dá)就緒隊列時，若優(yōu)先級高于當(dāng)前運行進(jìn)程，那就讓當(dāng)前進(jìn)程暫停運行進(jìn)入就緒隊列，把 CPU分配給新進(jìn)程使用，實現(xiàn)搶占。 . 非搶占式優(yōu)先級調(diào)度算法：就緒隊列基于進(jìn)程優(yōu)先級進(jìn)行排隊，優(yōu)先級高的排在前面，優(yōu)先級低的排在后面。調(diào)度時，總是把就緒隊列的首進(jìn)程作為分配 CPU的對象。 .. 確定進(jìn)程優(yōu)先級的因素 根據(jù)進(jìn)程的類型。比如由于系統(tǒng)進(jìn)程完成的任務(wù)是提供系統(tǒng)服務(wù)，分配系統(tǒng)資源，因此給予系統(tǒng)進(jìn)程較高的優(yōu)先級，不僅合乎情理，而且也能夠提高系統(tǒng)的工作效率。 (1) (2) 根據(jù)進(jìn)程執(zhí)行任務(wù)的重要性。每個進(jìn)程所完成的任務(wù)，其重要性和緊迫性肯定是不一樣的。比如，賦予報警進(jìn)程高的優(yōu)先級，一旦緊急事件發(fā)生時，讓它立即搶占 CPU投入運行，這是理所當(dāng)然的事情。 (3) 根據(jù)進(jìn)程程序的性質(zhì)。一個“處理機限制”進(jìn)程，由于需占用較長的運行時間，影響系統(tǒng)整體效率的發(fā)揮，因此只能給予較低的優(yōu)先級；一個“ I/O限制”進(jìn)程，給予它較高的優(yōu)先級后，就能充分發(fā)揮 CPU和外部設(shè)備之間的并行工作能力。 (4) 根據(jù)對資源的要求。系統(tǒng)資源有處理機、內(nèi)存儲器、外部設(shè)備等?？砂凑找粋€進(jìn)程所需資源的類型和數(shù)量，確定它的優(yōu)先級。比如給予占用 CPU時間短或內(nèi)存容量少的進(jìn)程以較高的優(yōu)先級，這樣可以提高系統(tǒng)的吞吐量。 (5) 根據(jù)用戶的請求。系統(tǒng)可以根據(jù)用戶的請求，給予它的作業(yè)及其相應(yīng)進(jìn)程很高的優(yōu)先級，作“加急”處理。 . 進(jìn)程優(yōu)先級的分類：所謂“靜態(tài)”優(yōu)先級，即指在進(jìn)程的整個生命期內(nèi)優(yōu)先數(shù)保持不變；所謂“動態(tài)”優(yōu)先級，是指在進(jìn)程的整個生命期內(nèi)可隨時修正它的優(yōu)先級別，以適應(yīng)系統(tǒng)環(huán)境和條件的變化。 返回目錄 ? 多級隊列調(diào)度算法 . 多級隊列（ MQ）調(diào)度算法，是把就緒進(jìn)程按不同的性質(zhì)組合成若干個就緒隊列，每個隊列實行不同的進(jìn)程調(diào)度算法。 系統(tǒng)進(jìn)程就緒隊列 實時進(jìn)程就緒隊列 交互進(jìn)程就緒隊列 批處理進(jìn)程就緒隊列 優(yōu)先級 高 低 . 可按進(jìn)程的類型組建各種就緒隊列：系統(tǒng)進(jìn)程就緒隊列、實時進(jìn)程就緒隊列、交互進(jìn)程就緒隊列、批處理進(jìn)程就緒隊列等。每個隊列都執(zhí)行自己的調(diào)度算法。 . 兩個隊列間獲得 CPU的權(quán)利要有先后次序。比如，根據(jù)每個隊列的優(yōu)先級不同，越往上的隊列，獲得 CPU的優(yōu)先級越高；越往下的隊列，獲得 CPU的優(yōu)先級越低。這樣，只有在系統(tǒng)進(jìn)程就緒隊列和實時進(jìn)程就緒隊列為空的前提下，才能夠去調(diào)度交互進(jìn)程就緒隊列里的進(jìn)程；當(dāng)一個批處理進(jìn)程執(zhí)行時，若有一個交互進(jìn)程抵達(dá)了就緒隊列，那么批處理進(jìn)程就將被搶占，把 CPU讓給交互進(jìn)程使用。 返回目錄 系統(tǒng)從第 1個隊列開始調(diào)度；只有在前 i1個隊列都空時，才調(diào)度第 i個隊列里的進(jìn)程。當(dāng)更高級別的隊列到達(dá)進(jìn)程時，系統(tǒng)將立即轉(zhuǎn)去運行級別高的那個進(jìn)程。 系統(tǒng)設(shè)多個就緒隊列，有自己的優(yōu)先級，第 1個隊列的優(yōu)先級最高，越往下隊列的優(yōu)先級依次降低。 多級反饋隊列（ MFQ）調(diào)度算法，是在多級隊列調(diào)度算法基礎(chǔ)上加入隊列間的反饋措施構(gòu)成的，它允許進(jìn)程在不同的就緒隊列里移動?！胺答仭保且罁?jù)進(jìn)程使用 CPU的時間長短進(jìn)行的。 . ? 多級反饋隊列調(diào)度算法 CPU 調(diào)度 阻塞，就緒 時間片到 CPU 調(diào)度 阻塞，就緒 完成 完成 時間片到 CPU 調(diào)度 阻塞，就緒 時間片到 完成 到達(dá) 級 1 (先來先服務(wù) ) 級 2 (先來先服務(wù) ) 級 n (輪轉(zhuǎn)或先來先服務(wù) ) . 多級反饋隊列的做法 (1)(2)