操作系統(tǒng)第7講

1、操作系統(tǒng)概念第七講 CPU調(diào)度(2)上章回顧周轉時間與響應時間的區(qū)別SJF的優(yōu)點和遇到的問題是什么？，如何解決問題？輪轉法調(diào)度中的時間片是如何設定的？本課總體綱要調(diào)度算法多級隊列調(diào)度多級反饋輪轉調(diào)度（round robin with multiple feedback)線性優(yōu)先級調(diào)度（selfish round robin)最高響應比優(yōu)先法(Highest response_ratio next)實時調(diào)度算法評估進程調(diào)度例題分析多級隊列調(diào)度就緒隊列分為：前臺與后臺每個隊列有自己的調(diào)度方法：前臺：RR 80后臺：FCFS 20調(diào)度必須在隊列之間完成按優(yōu)先權進行調(diào)度按時間片進行調(diào)度多級隊列調(diào)度多級

2、反饋輪轉調(diào)度（RRMF)在輪轉法中加入到就緒隊列的進程有三種情況：時間片用完I/O請求或進程互斥導致阻塞新創(chuàng)建進程進入就緒隊列對這些進程區(qū)別對待，采用不同的時間片或優(yōu)先權。多級反饋隊列調(diào)度本課總體綱要調(diào)度算法多級隊列調(diào)度多級反饋輪轉調(diào)度（round robin with multiple feedback)線性優(yōu)先級調(diào)度（selfish round robin)最高響應比優(yōu)先法(Highest response_ratio next)實時調(diào)度算法評估進程調(diào)度例題分析線性優(yōu)先級調(diào)度(SRR)輪轉法調(diào)度時，新創(chuàng)建的進程放入就緒隊列末尾享受平等的處理機時間片。是否可以采用兩種隊列進行服務享受服務隊列

3、CPU新創(chuàng)建進程隊列完成線性優(yōu)先級調(diào)度(SRR)新進程在就緒隊列中的優(yōu)先級：P=a*t (a0)享受服務進程在就緒隊列中的優(yōu)先級：P=b*t(ab0)某進程在t1時刻被創(chuàng)建，在t時刻的優(yōu)先級：P(t)=a(t-t1)(t1ta0-FCFS如果ab=0RRSRR是對FCFS和RR調(diào)度算法的折衷算法本課總體綱要調(diào)度算法多級隊列調(diào)度多級反饋輪轉調(diào)度（round robin with multiple feedback)線性優(yōu)先級調(diào)度（selfish round robin)最高響應比優(yōu)先法(Highest response_ratio next)實時調(diào)度算法評估進程調(diào)度例題分析最高響應比優(yōu)先法(HR

4、N)最高響應優(yōu)先法是對FCFS方式和SJF方式的綜合平衡響應比定義：R=(W+T)/T=1+W/TT為該作業(yè)估計需要的執(zhí)行時間，W為等待時間本課總體綱要調(diào)度算法多級隊列調(diào)度多級反饋輪轉調(diào)度（round robin with multiple feedback)線性優(yōu)先級調(diào)度（selfish round robin)最高響應比優(yōu)先法(Highest response_ratio next)實時調(diào)度算法評估進程調(diào)度例題分析實時調(diào)度操作系統(tǒng)是實時系統(tǒng)中的重要組成部分之一其處理和控制的正確性不僅僅取決于計算的邏輯結果，而且取決于計算和處理結果產(chǎn)生的時間。實時操作系統(tǒng)具有以下特點：有限等待時間（決定性）

5、有限響應時間用戶控制可靠性高系統(tǒng)出錯處理能力強實時調(diào)度硬件實時（hard real-time）系統(tǒng)需要在保證的時間內(nèi)完成任務軟件實時(soft real-time)系統(tǒng)要求關鍵進程比其他進程擁有更高的優(yōu)先權。實時操作系統(tǒng)具有以下功能：進程或線程切換速度快快速的外部中斷響應能力基于優(yōu)先級的隨時搶占性調(diào)度策略實時調(diào)度基于優(yōu)先級的調(diào)度策略有4種：優(yōu)先級+輪轉調(diào)度基于優(yōu)先級的非搶占調(diào)度基于優(yōu)先級的固定點搶占式調(diào)度基于優(yōu)先級的隨時搶占式調(diào)度本課總體綱要調(diào)度算法多級隊列調(diào)度多級反饋輪轉調(diào)度（round robin with multiple feedback)線性優(yōu)先級調(diào)度（selfish round r

6、obin)最高響應比優(yōu)先法(Highest response_ratio next)實時調(diào)度算法評估進程調(diào)度例題分析算法評估（1）如何選擇適合的CPU調(diào)度算法用于特定的系統(tǒng)定義選擇算法的準則：最大化CPU使用率，同時要求最大響應時間為1S最大化吞吐量，要求平均周轉時間與總的時間成正比算法評估（2）Cpu和IO區(qū)間是可以確定的可以用數(shù)學公式來描述特定的CPU區(qū)間的概率分布對于系統(tǒng)模型只有一個服務器S： ：進程到達率 ：進程服務率 = / :系統(tǒng)內(nèi)存在的進程的概率n= /(1- ) :系統(tǒng)內(nèi)進程的算術平均值算法評估（3）Little 公式 n=*R n平均隊列長度（進程數(shù)） R隊列平均響應時間 新

7、進程到達隊列的平均到達率e算法評估（4）對于FCFS:短作業(yè)和長作業(yè)的平均等待時間一樣長。Rfc=1/( )對于RR:R(k)=k*q/(1- )對于SRRRsr= 1/( )(1kq )/ ( )本課總體綱要調(diào)度算法多級隊列調(diào)度多級反饋輪轉調(diào)度（round robin with multiple feedback)線性優(yōu)先級調(diào)度（selfish round robin)最高響應比優(yōu)先法(Highest response_ratio next)實時調(diào)度算法評估進程調(diào)度例題分析綜合計算例題進程到達時間區(qū)間時間P10 10P2529P383P4107P51212研究FCFS、SJF和RR（時間片1

8、0ms）的平均等待時間綜合計算FCFS=(0+5+31+32+37)/5=21msSJF(非搶占)（0（13-10）（10-8）（20-12）(32-5）/5=8msSJF(搶占）=(0+2+3+8+27)/5=8msRR=(0+27+12+13+28)/5=16ms進程調(diào)度例題分析以下哪些算法與作業(yè)的執(zhí)行時間有關A)優(yōu)先級調(diào)度B)RRC)SJFD)HRNE)FCFS進程調(diào)度例題分析作業(yè)調(diào)度是高級調(diào)度，進程調(diào)度是低級調(diào)度（）在各種作業(yè)調(diào)度算法中，SJF會使每個作業(yè)的等待時間最短（）作業(yè)一旦被作業(yè)調(diào)度選中，即占有CPU（）在一個兼顧分時系統(tǒng)和批處理系統(tǒng)中，通常把終端作業(yè)稱為前臺作業(yè)，把批量作業(yè)稱為后臺作業(yè)（）總結CPU調(diào)度的時機與處理方式？調(diào)度算法FCFSSJFRRHRNSRR作業(yè)作業(yè)調(diào)度和進程調(diào)度的區(qū)別以下調(diào)度算法的區(qū)別FC