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

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

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

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

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

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

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

8、0ms）的平均等待時(shí)間綜合計(jì)算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進(jìn)程調(diào)度例題分析以下哪些算法與作業(yè)的執(zhí)行時(shí)間有關(guān)A)優(yōu)先級調(diào)度B)RRC)SJFD)HRNE)FCFS進(jìn)程調(diào)度例題分析作業(yè)調(diào)度是高級調(diào)度，進(jìn)程調(diào)度是低級調(diào)度（）在各種作業(yè)調(diào)度算法中，SJF會使每個(gè)作業(yè)的等待時(shí)間最短（）作業(yè)一旦被作業(yè)調(diào)度選中，即占有CPU（）在一個(gè)兼顧分時(shí)系統(tǒng)和批處理系統(tǒng)中，通常把終端作業(yè)稱為前臺作業(yè)，把批量作業(yè)稱為后臺作業(yè)（）總結(jié)CPU調(diào)度的時(shí)機(jī)與處理方式？調(diào)度算法FCFSSJFRRHRNSRR作業(yè)作業(yè)調(diào)度和進(jìn)程調(diào)度的區(qū)別以下調(diào)度算法的區(qū)別FC