【正文】 合理的 批處理作業(yè)的調(diào)度（續(xù) 1） 要設(shè)計一個理想的調(diào)度算法是一件十分困難的事 在實際系統(tǒng)中，調(diào)度算法往往折衷考慮 設(shè)計調(diào)度算法時應(yīng)考慮的因素： ? 調(diào)度算法應(yīng)與系統(tǒng)設(shè)計目標(biāo)保持一致 ? 注意系統(tǒng)資源均衡使用 ? 保證提交的作業(yè)在截止時間內(nèi)完成 ? 設(shè)法縮短作業(yè)平均周轉(zhuǎn)時間 大多數(shù)操作系統(tǒng)都采用比較簡單的調(diào)度算法 批處理作業(yè)的調(diào)度（續(xù) 2） 作業(yè)平均周轉(zhuǎn)時間 假定某一作業(yè)進(jìn)入 “ 輸入井 ” 的時間為 Si， 它被選中執(zhí)行，得到計算結(jié)果的時間為 Ei 它的周轉(zhuǎn)時間為 Ti ＝ Ei – Si 則作業(yè)平均周轉(zhuǎn)時間為： T＝（ ） n為被測定作業(yè)流中的作業(yè)數(shù) ??niTi1 n1（ 2）調(diào)度算法性能的衡量 批處理作業(yè)的調(diào)度（續(xù) 3） 平均帶權(quán)周轉(zhuǎn)時間 W＝（ ） ri 為某作業(yè) i的實際執(zhí)行時間 ??ni riTi1n1? T：衡量不同調(diào)度算法對同一個作業(yè)流的性能 ? W：同一調(diào)度算法對不同作業(yè)流的性能衡量 批處理作業(yè)的調(diào)度（續(xù) 4） （ 3）系統(tǒng)進(jìn)行作業(yè)調(diào)度的決策因素 ? 作業(yè)到達(dá)時間 ? 預(yù)先為作業(yè)確定的優(yōu)先級 系統(tǒng)可測定的其他因素： ? 作業(yè)所需的 CPU時間 C ? 存儲要求 M ? 打印輸出的行數(shù) L ? 其他的資源要求 批處理作業(yè)的調(diào)度（續(xù) 5） （ 4）常見的批處理作業(yè)調(diào)度算法 ? 先來先服務(wù)算法（ FCFS： First Come First Serve） ? 最短作業(yè)優(yōu)先算法（ SJF： Shortest Job First） ? 最高響應(yīng)比優(yōu)先算法 （ HRN： Highest Response Ratio Next） 響應(yīng)比 R = 作業(yè)周轉(zhuǎn)時間 / 作業(yè)處理時間 =（作業(yè)處理時間 +作業(yè)等待時間） / 作業(yè)處理時間 = 1 +（作業(yè)等待時間 / 作業(yè)處理時間） 批處理作業(yè)的調(diào)度（續(xù) 6） ? 基于優(yōu)先數(shù)調(diào)度算法 （ HPF： Highest Priority First） （ a）由用戶規(guī)定優(yōu)先數(shù)（外部優(yōu)先數(shù)） 用戶提交作業(yè)時，根據(jù)急迫程度規(guī)定適當(dāng)?shù)膬?yōu)先數(shù) 作業(yè)調(diào)度程序根據(jù) JCB優(yōu)先數(shù)決定進(jìn)入內(nèi)存的次序 （ b）由系統(tǒng)計算優(yōu)先數(shù)（內(nèi)部優(yōu)先數(shù)） 例：可按如下公式計算作業(yè)的優(yōu)先數(shù)： 優(yōu)先數(shù) = 用戶規(guī)定優(yōu)先數(shù) – 作業(yè)處理時間 + 作業(yè)等待時間 – 輸出量 批處理作業(yè)的調(diào)度（續(xù) 7） ? 均衡調(diào)度算法 (分類排隊算法 ) 基本思想： ? 根據(jù)系統(tǒng)運行情況和作業(yè)屬性將作業(yè)分類 ? 輪流從不同的作業(yè)類中挑選作業(yè) 目標(biāo)： ? 力求均衡地利用各種系統(tǒng)資源，發(fā)揮資源使用效率 ? 力求使用戶滿意 批處理作業(yè)的調(diào)度（續(xù) 8） 例 1：將待處理作業(yè)分成如下隊列： 隊列 1：計算量大的作業(yè) 隊列 2： I/O量大的作業(yè) 隊列 3：計算量與 I/O量均衡的作業(yè) ? 調(diào)度時，在三個隊列中各取一些作業(yè) 在內(nèi)存中的作業(yè)有的使用處理機(jī) 有的使用外部設(shè)備 ? 使得系統(tǒng)的各種資源能得到充分利用 批處理作業(yè)的調(diào)度（續(xù) 9） 例 2：將待處理作業(yè)分成如下三個隊列： 隊列 1：長作業(yè) 隊列 2：中等長度作業(yè) 隊列 3：短作業(yè) ? 調(diào)度時 取隊列 1一作業(yè)，隊列 2一作業(yè)，隊列 3一作業(yè) ? 長作業(yè)用戶和短作業(yè)用戶均比較滿意 批處理作業(yè)的調(diào)度（續(xù) 10） （ 5）作業(yè)調(diào)度算法應(yīng)用例子 1 ? 假設(shè)在單道批處理環(huán)境下有四個作業(yè)，已知它們進(jìn)入系統(tǒng)的時間、估計運行時間 應(yīng)用先來先服務(wù)、最短作業(yè)優(yōu)先和最高響應(yīng)比優(yōu)先作業(yè)調(diào)度算法，分別計算出作業(yè)的平均周轉(zhuǎn)時間和帶權(quán)的平均周轉(zhuǎn)時間 批處理作業(yè)的調(diào)度（續(xù) 11） 先來先服務(wù)調(diào)度算法計算結(jié)果 作業(yè) 進(jìn)入時間 估計運行時間（分鐘）開始時間 結(jié)束時間 周轉(zhuǎn)時間（分鐘）帶權(quán)周轉(zhuǎn)時間J O B1 8 ： 00 120 8 ： 00 10 ： 00 120 1J O B2 8 ： 50 50 10 ： 00 10 ： 50 120 2 .4J O B3 9 ： 00 10 10 ： 50 11 ： 00 120 12J O B4 9 ： 50 20 11 ： 00 11 ： 20 90 4 .5作業(yè)平均周轉(zhuǎn)時間 T = 1 1 2 .5作業(yè)帶權(quán)平均周轉(zhuǎn)時間 W = 4 .9 7 5450 1 9 .9批處理作業(yè)的調(diào)度（續(xù) 12） 最短作業(yè)優(yōu)先作業(yè)算法計算結(jié)果 作業(yè) 進(jìn)入時間 估計運行時間（分鐘）開始時間 結(jié)束時間 周轉(zhuǎn)時間（分鐘）帶權(quán)周轉(zhuǎn)時間J O B1 8 ： 00 120 8 ： 00 10 ： 00 120 1J O B2 8 ： 50 50 10 ： 30 11 ： 20 150 3J O B3 9 ： 00 10 10 ： 00 10 ： 10 70 7J O B4 9 ： 50 20 10 ： 10 10 ： 30 40 2作業(yè)平均周轉(zhuǎn)時間 T = 9 5作業(yè)帶權(quán)平均周轉(zhuǎn)時間 W = 3 .2 5380 13批處理作業(yè)的調(diào)度（續(xù) 13） 最高響應(yīng)比優(yōu)先作業(yè)算法計算結(jié)果 作業(yè) 進(jìn)入時間 估計運行時間（分鐘）開始時間 結(jié)束時間 周轉(zhuǎn)時間（分鐘）帶權(quán)周轉(zhuǎn)時間J O B1 8 ： 00 120 8 ： 00 10 ： 00 120 1J O B2 8 ： 50 30 10 ： 10 11 ： 00 70 1 .4J O B3 9 ： 00 10 10 ： 00 10 ： 10 70 7J O B4 9 ： 50 20 11 ： 00 11 ： 20 90 4 .5作業(yè)平均周轉(zhuǎn)時間 T = 8 7 .5作業(yè)帶權(quán)平均周轉(zhuǎn)時間 W = 4 .0 7 5350 1 6 .3批處理作業(yè)的調(diào)度