1、第四章 處理機(jī)調(diào)度,一、分級(jí)調(diào)度,處理機(jī)調(diào)度可分為四級(jí)： 作業(yè)調(diào)度（宏觀調(diào)度或高級(jí)調(diào)度）：負(fù)責(zé)從后備作業(yè)中選擇若干作業(yè)調(diào)到內(nèi)存，并為它們分配相應(yīng)的資源，當(dāng)作業(yè)運(yùn)行完畢時(shí)，負(fù)責(zé)回收資源。 交換調(diào)度（中級(jí)調(diào)度）：負(fù)責(zé)外存交換區(qū)域內(nèi)存中的就緒狀態(tài)或等待狀態(tài)的進(jìn)程進(jìn)行交換。 進(jìn)程調(diào)度（微觀調(diào)度或低級(jí)調(diào)度）負(fù)責(zé)選取適當(dāng)?shù)倪M(jìn)程占有處理機(jī) 線程調(diào)度,二、作業(yè)調(diào)度,1、主要功能 審查系統(tǒng)能否滿足用戶作業(yè)的資源要求，較容易，只要通過(guò)調(diào)用相應(yīng)的資源管理程序的有關(guān)部分，審核其表中是否能滿足作業(yè)說(shuō)明書(shū)中的要求即可。 按照一定的算法叢輸入井中的后備作業(yè)中選取作業(yè)。,調(diào)度的關(guān)鍵在選擇恰當(dāng)?shù)乃惴?2、調(diào)度算法的評(píng)價(jià) 調(diào)度實(shí)

2、質(zhì)上是一個(gè)策略問(wèn)題，設(shè)定的目標(biāo)往往是相互沖突的。 目標(biāo)： 單位時(shí)間內(nèi)運(yùn)行盡可能多的作業(yè) 是處理機(jī)盡可能保持“忙碌” 使各種I/O設(shè)備得以充分利用 對(duì)所有的作業(yè)都是公平合理的 要設(shè)計(jì)一個(gè)理想的調(diào)度算法是一件十分困難的事，在實(shí)際系統(tǒng)中，調(diào)度算法往往折衷考慮,設(shè)計(jì)調(diào)度算法時(shí)應(yīng)考慮的因素： 調(diào)度算法應(yīng)與系統(tǒng)設(shè)計(jì)目標(biāo)保持一致 注意系統(tǒng)資源均衡使用 保證提交的作業(yè)在截止時(shí)間內(nèi)完成 設(shè)法縮短作業(yè)平均周轉(zhuǎn)時(shí)間 大多數(shù)操作系統(tǒng)都采用比較簡(jiǎn)單的調(diào)度算法,3、調(diào)度算法性能的衡量 （1）作業(yè)平均周轉(zhuǎn)時(shí)間：假定某一作業(yè)進(jìn)入“輸入井”的時(shí)間為Si，它被選中執(zhí)行，得到計(jì)算結(jié)果的時(shí)間為Ei，它的周轉(zhuǎn)時(shí)間為Ti=Ei-Si 則

3、作業(yè)平均周轉(zhuǎn)時(shí)間為：T=（ ）1/n 其中，n為被測(cè)定作業(yè)流中的作業(yè)數(shù),（2）平均帶權(quán)某周轉(zhuǎn)時(shí)間 W=（ ）1/n 其中，ri為作業(yè)i的實(shí)際執(zhí)行時(shí)間 T：衡量不同調(diào)度算法對(duì)同一個(gè)作業(yè)流的性能 W：同一調(diào)度算法對(duì)不同作業(yè)流的性能衡量,4、系統(tǒng)進(jìn)行作業(yè)調(diào)度的決策因素 作業(yè)到達(dá)時(shí)間 預(yù)先為作業(yè)確定的優(yōu)先級(jí),三、常見(jiàn)的批處理作業(yè)調(diào)度算法,1、先來(lái)先服務(wù)（FCFS:First Come First Serve) 2、最短作業(yè)優(yōu)先算法（SJF: Shortest Job First) 3、最高響應(yīng)比優(yōu)先算法（HRN:Highest Response Ratio Next) 響應(yīng)比R=作業(yè)周轉(zhuǎn)時(shí)間/作業(yè)處理

4、時(shí)間 =（作業(yè)處理時(shí)間+作業(yè)等待時(shí)間）/作業(yè)處理時(shí)間 =1+作業(yè)等待時(shí)間/作業(yè)處理時(shí)間,4、基于優(yōu)先數(shù)調(diào)度算法（HPF：Heghest Priority First） （1）由用戶規(guī)定優(yōu)先數(shù)（外部?jī)?yōu)先數(shù)） 用戶提交作業(yè)時(shí)，根據(jù)急迫程度規(guī)定適當(dāng)?shù)膬?yōu)先數(shù)。 作業(yè)調(diào)度程序根據(jù)JCB優(yōu)先數(shù)決定適當(dāng)?shù)膬?yōu)先數(shù) （2）由系統(tǒng)計(jì)算優(yōu)先數(shù)（內(nèi)部?jī)?yōu)先數(shù)） 例：可按如下公式計(jì)算作業(yè)的優(yōu)先數(shù)： 優(yōu)先數(shù)=用戶規(guī)定優(yōu)先數(shù)-作業(yè)處理時(shí)間+作業(yè)等待時(shí)間-輸出量,5、輪轉(zhuǎn)法 基本思路：讓每個(gè)進(jìn)程在就緒隊(duì)列中的等待時(shí)間與享受服務(wù)的時(shí)間成正比。 時(shí)間片的選擇是根據(jù)系統(tǒng)對(duì)響應(yīng)時(shí)間的要求R和就緒隊(duì)列中所允許的最大進(jìn)程數(shù)Nmax確定的。

5、表示為：q=R/ Nmax 只能用來(lái)調(diào)度那些可以搶占的資源。 該方法不用于作業(yè)調(diào)度,6、均衡調(diào)度算法（分類排隊(duì)算法） 基本思想： 根據(jù)系統(tǒng)運(yùn)行情況和作業(yè)屬性將作業(yè)分類 輪流從不同的作業(yè)類中挑選作業(yè) 目標(biāo)： 力求均衡地利用各種系統(tǒng)資源，發(fā)揮資源使用效率 力求使用戶滿意,例1：將待處理作業(yè)分成如下隊(duì)列： 隊(duì)列1：計(jì)算量大的作業(yè) 隊(duì)列2：I/O量大的作業(yè) 隊(duì)列3：計(jì)算量與I/O量均衡的作業(yè) 調(diào)度時(shí)，在三個(gè)隊(duì)列中各取一些作業(yè) 在內(nèi)存中的作業(yè)有的使用處理機(jī) 有的使用外部設(shè)備 使得系統(tǒng)的各種資源能得到充分利用,例2：將待處理作業(yè)分成如下三個(gè)隊(duì)列： 隊(duì)列1：長(zhǎng)作業(yè) 隊(duì)列2：中等長(zhǎng)度作業(yè) 隊(duì)列3：短作業(yè) 調(diào)度

6、時(shí) 取隊(duì)列1一作業(yè)，隊(duì)列2一作業(yè)，隊(duì)列3一作業(yè) 長(zhǎng)作業(yè)用戶和短作業(yè)用戶均比較滿意,四、調(diào)度算法舉例,例1：假設(shè)在單道批處理環(huán)境下有四個(gè)作業(yè)，已知它們進(jìn)入系統(tǒng)的時(shí)間、估計(jì)運(yùn)行時(shí)間 應(yīng)用先來(lái)先服務(wù)、最短作業(yè)優(yōu)先和最高響應(yīng)比優(yōu)先作業(yè)調(diào)度算法，分別計(jì)算出作業(yè)的平均周轉(zhuǎn)時(shí)間和帶權(quán)的平均周轉(zhuǎn)時(shí)間,先來(lái)先服務(wù)：,短作業(yè)優(yōu)先：,最高響應(yīng)比優(yōu)先：,例2：在兩道環(huán)境下有四個(gè)作業(yè) 已知它們進(jìn)入系統(tǒng)的時(shí)間、估計(jì)運(yùn)行時(shí)間 系統(tǒng)采用短作業(yè)優(yōu)先作業(yè)調(diào)度算法，作業(yè)被調(diào)度運(yùn)行后不再退出 當(dāng)一新作業(yè)投入運(yùn)行后，可按照作業(yè)運(yùn)行時(shí)間長(zhǎng)短調(diào)整作業(yè)執(zhí)行的次序 請(qǐng)給出這四個(gè)作業(yè)的執(zhí)行時(shí)間序列，并計(jì)算出平均周轉(zhuǎn)時(shí)間及帶權(quán)平均周轉(zhuǎn)時(shí)間,短作業(yè)

7、優(yōu)先：,四個(gè)作業(yè)的執(zhí)行時(shí)間序列為： JOB1：10：0010：05，10：4011：05 JOB2：10：0510：25 JOB3：10：2510：30 JOB4：10：3010：40,在兩道批處理系統(tǒng)中，短作業(yè)優(yōu)先算法的分析： 10：00，JOB1進(jìn)入，只有一作業(yè)，JOB1被調(diào)入執(zhí)行 10：05，JOB2到達(dá)，最多允許兩作業(yè)同時(shí)進(jìn)入 所以JOB2也被調(diào)入 內(nèi)存中有兩作業(yè)，哪一個(gè)執(zhí)行？題目規(guī)定當(dāng)一新作業(yè)運(yùn)行后，可按作業(yè)運(yùn)行時(shí)間長(zhǎng)短調(diào)整執(zhí)行次序 即基于優(yōu)先數(shù)可搶占式調(diào)度策略 優(yōu)先數(shù)是根據(jù)作業(yè)估計(jì)運(yùn)行時(shí)間大小來(lái)決定的 由于JOB2運(yùn)行時(shí)間（20分）比JOB1少 （到10：05，JOB1還需25分鐘） 所以JOB2運(yùn)行