1、1,第3章 處理機調(diào)度,本章知識點： 3.1 調(diào)度類型 3.2 調(diào)度算法,2,3.1 調(diào)度類型,處理機調(diào)度問題就是處理器的分配問題，它的目的是使處理機在滿足系統(tǒng)要求的響應(yīng)時間、吞吐量和處理機利用率的前提下及時地運行進程。在許多系統(tǒng)中，調(diào)度被分成3種：長程、中程和短程調(diào)度。 由于調(diào)度決定了哪些進程將等待、哪些進程被執(zhí)行，所以直接影響到系統(tǒng)的執(zhí)行效率。從根本上講，調(diào)度就是要使隊列延遲最小，并優(yōu)化系統(tǒng)的執(zhí)行效率。,3,3.1.1 長程調(diào)度,長程調(diào)度又稱為作業(yè)調(diào)度或高級調(diào)度。長程調(diào)度決定哪些作業(yè)可參與競爭CPU和其他資源，即決定給哪個作業(yè)分配一臺虛擬處理機，它是處理機的宏觀調(diào)度。 長程調(diào)度的一般功能是

2、：從后備作業(yè)中挑選一個或多個作業(yè)，為它(它們)分配基本的內(nèi)存和外設(shè)資源并建立相應(yīng)的進程。不同類型的操作系統(tǒng)關(guān)于長程調(diào)度的功能、調(diào)度時機以及工作形式是有差異的。,4,3.1.2 中程調(diào)度,中程調(diào)度也稱中級調(diào)度。中級調(diào)度決定哪些進程可參與競爭CPU，用以實現(xiàn)進程的活動狀態(tài)與靜止的掛起態(tài)之間的轉(zhuǎn)換。引入中程調(diào)度的主要目的，是為了提高內(nèi)存的利用率和系統(tǒng)吞吐量。中程調(diào)度實際上就是存儲器管理中的置換功能。,5,3.1.3 短程調(diào)度,短程調(diào)度又稱為進程調(diào)度或低級調(diào)度。短程調(diào)度決定哪個進程可獲得物理CPU，它是處理機的終結(jié)調(diào)度，即微觀調(diào)度。短程調(diào)度的功能是：從就緒進程隊列中挑選一個進程并啟動執(zhí)行該進程。 短程

3、調(diào)度是最基本的一種調(diào)度，它可以采用非搶占方式或搶占方式。,6,3.2 調(diào)度算法,如何選擇和設(shè)計調(diào)度算法是實現(xiàn)調(diào)度的關(guān)鍵。對調(diào)度算法進行評價的常用量度標(biāo)準是：平均周轉(zhuǎn)時間、平均帶權(quán)周轉(zhuǎn)時間及平均等待時間。,7,調(diào)度策略是指根據(jù)系統(tǒng)的資源分配策略所設(shè)計的資源分配算法。 1. 先來先服務(wù)(FCFS)策略 FCFS策略遵循先來者優(yōu)先服務(wù)的原則，故它本質(zhì)上是非搶占式的。它簡單易行，但調(diào)度性能較差，有可能使短的、重要的或緊迫的作業(yè)及進程長期等待。FCFS策略的另一個問題是它有利于偏重CPU的進程，不利于偏重I/O的進程。,8,2. 時間片輪轉(zhuǎn)(Round-Robin，RR)策略 RR策略是一種搶占式的進程

4、調(diào)度法，是以就緒隊列中的所有進程均以相等的速度向前進展為特征的。它對每個作業(yè)給予一個運行時間片，若一個作業(yè)在規(guī)定的時間片內(nèi)未運行完，則掛起該作業(yè)并調(diào)度另一作業(yè)(繼續(xù))運行。當(dāng)所有的作業(yè)都運行完分配的一個時間片后，第一個作業(yè)才再次得到運行的機會。,9,時間片值的設(shè)置是RR算法的關(guān)鍵問題。時間片過大則退化為FCFS算法，時間片過小時則稱為“處理機共享”。此片值的設(shè)置可以是固定的，也可以是可變的。 RR算法主要用于分時系統(tǒng)或事務(wù)處理系統(tǒng)，可保證對各終端用戶的及時響應(yīng)。但它對偏重CPU的進程和偏重I/O的進程有不同的處理結(jié)果，可以采用虛擬時間片輪轉(zhuǎn)(VRR)策略來避免這個問題。新加入的特性是附加一個F

5、CFS策略隊列來收集從I/O等待中釋放的進程。,10,3. 最短作業(yè)優(yōu)先(Shortest Process Next，SPN)策略 SPN策略是一種非搶占式的方式，它偏袒短者，對短作業(yè)或短進程最為有利，它導(dǎo)致最短的平均周轉(zhuǎn)時間。但它忽略等待時間的長短，對長作業(yè)不利，特別是在搶占方式下，可能會使長作業(yè)無限延遲。對于搶占式SPN進程調(diào)度，還需要考慮是按最短原則還是按剩余最短原則搶占。理論上該方法在等待時間方面是最優(yōu)的，但實際上無法預(yù)測下一CPU瞬時段的長度。,11,4. 最短剩余時間優(yōu)先(Shortest Remaining Time，SRT)策略 SRT策略是搶占式的SPN策略，它將較高的優(yōu)先級給予具有最短剩余CPU瞬時段的作業(yè)。和SPN策略一樣，根據(jù)執(zhí)行時間來選擇進程執(zhí)行可能會引起長進程的饑餓，但SRT策略輪轉(zhuǎn)時間性能比SPN策略好。,12,某個單CPU系統(tǒng)有一批處于就緒狀態(tài)的進