2012級講義第1-8章5cpu調(diào)度

1、操作系統(tǒng)北京大學(xué)計算中心 付中南 第5章 CPU調(diào)度5.1 基本概念5.2 調(diào)度準(zhǔn)則5.3 調(diào)度算法5.4 算法評估第5章 CPU調(diào)度CPU調(diào)度是多道程序操作系統(tǒng)的基礎(chǔ)。通過在進(jìn)程間切換CPU，操作系統(tǒng)可以提高計算機(jī)的吞吐率。本章介紹基本調(diào)度概念和多個不同的CPU調(diào)度算法。本章目標(biāo)介紹CPU調(diào)度描述各種CPU調(diào)度算法。討論為特定系統(tǒng)選擇CPU調(diào)度算法的評估標(biāo)準(zhǔn)。第5章 CPU調(diào)度5.1 基本概念單處理器系統(tǒng)任何時刻只允許一個進(jìn)程運(yùn)行多道程序的目標(biāo)多道程序設(shè)計思想第5章 CPU調(diào)度5.1 基本概念5.1.1 CPU-I/O區(qū)間周期進(jìn)程在CPU和I/O間切換每個進(jìn)程從CPU區(qū)間開始，然后進(jìn)入I/O

2、區(qū)間。如此反復(fù)，最后的CPU區(qū)間通過系統(tǒng)調(diào)用終止進(jìn)程的執(zhí)行。CPU區(qū)間的長度已被大量測試過。雖然它們的長度隨進(jìn)程和計算機(jī)系統(tǒng)的不同變化很大，但是呈現(xiàn)出如下圖的頻率曲線。第5章 CPU調(diào)度5.1 基本概念5.1.1 CPU-I/O區(qū)間周期第5章 CPU調(diào)度5.1 基本概念5.1.2 CPU調(diào)度程序短期調(diào)度程序 VS 長期調(diào)度程序就緒隊列FIFO隊列、優(yōu)先隊列或無序鏈表第5章 CPU調(diào)度5.1 基本概念5.1.3 搶占調(diào)度CPU調(diào)度策略發(fā)生在下面4種情況：1、進(jìn)程從運(yùn)行態(tài)切換到等待態(tài)2、進(jìn)程從運(yùn)行態(tài)切換到就緒態(tài)3、進(jìn)程從等待態(tài)切換到就緒態(tài)4、進(jìn)程終止在1和4兩種情況下，CPU必須進(jìn)行調(diào)度；但在2和

3、3兩種情況下，CPU調(diào)度會因策略不同而不同。第5章 CPU調(diào)度5.1 基本概念5.1.3 搶占調(diào)度如果調(diào)度僅發(fā)生在1、4兩種情況下，我們稱這種調(diào)度為非搶占調(diào)度。否則，我們稱之為搶占調(diào)度。搶占調(diào)度提高了系統(tǒng)的并發(fā)，但實現(xiàn)更為復(fù)雜。并發(fā)數(shù)據(jù)的訪問對操作系統(tǒng)內(nèi)核的影響解決方式：禁止中斷第5章 CPU調(diào)度5.2 調(diào)度準(zhǔn)則為了比較各種CPU調(diào)度算法，人們提出了許多準(zhǔn)則，如下：CPU使用率：要使CPU盡可能忙。從概念上講，CPU使用率從0%100%。對于真實系統(tǒng)，它應(yīng)從40%90%。吞吐量：指一個時間單元內(nèi)完成進(jìn)程的數(shù)量。對于長進(jìn)程，吞吐量可能為每小時一個進(jìn)程；對于短進(jìn)程，吞吐量可能為每秒10個進(jìn)程。第5

4、章 CPU調(diào)度5.2 調(diào)度準(zhǔn)則為了比較各種CPU調(diào)度算法，人們提出了許多準(zhǔn)則，如下：周轉(zhuǎn)時間：從進(jìn)程提交到進(jìn)程完成的時間段稱為周轉(zhuǎn)時間。包括進(jìn)程等待進(jìn)入內(nèi)存、在就緒隊列中等待、在CPU上執(zhí)行和I/O執(zhí)行。等待時間：進(jìn)程在就緒隊列中等待所花費(fèi)時間之和。CPU調(diào)度算法并不影響進(jìn)程運(yùn)行和執(zhí)行I/O的時間，它只影響進(jìn)程在就緒隊列中等待所花的時間。第5章 CPU調(diào)度5.2 調(diào)度準(zhǔn)則為了比較各種CPU調(diào)度算法，人們提出了許多準(zhǔn)則，如下：響應(yīng)時間：對于交互系統(tǒng)，周轉(zhuǎn)時間并不是最佳準(zhǔn)則。響應(yīng)時間是指從提交請求到產(chǎn)生第一次響應(yīng)的時間。是開始響應(yīng)的時間，而不是輸出結(jié)果的時間。好的調(diào)度算法應(yīng)使CPU使用率和吞吐量最

5、大化，而使周轉(zhuǎn)時間、等待時間和響應(yīng)時間最小化。第5章 CPU調(diào)度5.3 調(diào)度算法5.3.1 先到先服務(wù)算法( e, first-served)FCFS最簡單的調(diào)度算法先請求CPU的進(jìn)程先分配到CPU。FCFS策略可以用FIFO隊列來實現(xiàn)。非搶占算法第5章 CPU調(diào)度5.3 調(diào)度算法5.3.2 最短作業(yè)優(yōu)先調(diào)度(shortest-job-first)SJF將每個進(jìn)程與其下一個CPU區(qū)間相關(guān)聯(lián)。當(dāng)CPU空閑是，選擇最短CPU區(qū)間的進(jìn)程運(yùn)行。如果兩個或多個進(jìn)程具有同樣長度，采用FCFS調(diào)度來處理。第5章 CPU調(diào)度5.3 調(diào)度算法5.3.2 最短作業(yè)優(yōu)先調(diào)度(shortest-job-first)S

6、JF將每個進(jìn)程與其下一個CPU區(qū)間相關(guān)聯(lián)。當(dāng)CPU空閑是，選擇最短CPU區(qū)間的進(jìn)程運(yùn)行。如果兩個或多個進(jìn)程具有同樣長度，采用FCFS調(diào)度來處理。搶占的SJF稱為最短剩余時間優(yōu)先調(diào)度(shortest-remaining-time-first scheduling)。第5章 CPU調(diào)度5.3 調(diào)度算法5.3.3 優(yōu)先級調(diào)度每個進(jìn)程都有一個優(yōu)先級與其關(guān)聯(lián)，具有最高優(yōu)先級的進(jìn)程會分配到CPU。具有相同優(yōu)先級的進(jìn)程按FCFS順序調(diào)度。SJF可以理解為優(yōu)先級調(diào)度算法的一個特例。進(jìn)程的優(yōu)先級為下一個CPU區(qū)間的倒數(shù)。優(yōu)先級通常為固定區(qū)間的數(shù)字，如09或0255。第5章 CPU調(diào)度5.3 調(diào)度算法5.3.3 優(yōu)先級調(diào)度優(yōu)先級調(diào)度算法的一個主要問題無窮阻塞或叫做饑餓解決方法之一是老化。第5章 CPU調(diào)度5.3 調(diào)度算法5.3.4 輪轉(zhuǎn)法調(diào)度(round-robin)RR專為分時系統(tǒng)設(shè)計類似FCFS調(diào)度，但是增加了搶占以切換進(jìn)程。定義一個較小時間單元，稱為時間片。CPU調(diào)度程序循環(huán)就緒隊列，為每個進(jìn)程分配不超過一個時間片的CPU。第5章 CPU調(diào)度5.3 調(diào)度算法5.3.5 多級隊列調(diào)度在進(jìn)程可容易地分成不同組的情況下，可以建立多級隊列調(diào)度。將就緒隊列分成多個獨(dú)立隊列。根據(jù)進(jìn)程的屬性，如內(nèi)存大小、進(jìn)程優(yōu)先級、進(jìn)程類型，一個進(jìn)程被永久地分配到一個隊列。每個隊列有自己的調(diào)度算法。