操作系統(tǒng)概念

第七講 CPU調(diào)度(2)OperatingSystemConceptionDavidfu上章回顧周轉(zhuǎn)時間與響應(yīng)時間的區(qū)別SJF的優(yōu)點(diǎn)和遇到的問題是什么？，如何解決問題？輪轉(zhuǎn)法調(diào)度中的時間片是如何設(shè)定的？OperatingSystemConceptionDavidfu本課總體綱要調(diào)度算法多級隊(duì)列調(diào)度多級反饋輪轉(zhuǎn)調(diào)度（roundrobinwithmultiplefeedback)線性優(yōu)先級調(diào)度（selfishroundrobin)最高響應(yīng)比優(yōu)先法(Highestresponse_rationext)實(shí)時調(diào)度算法評估進(jìn)程調(diào)度例題分析OperatingSystemConceptionDavidfu多級隊(duì)列調(diào)度OperatingSystemConceptionDavidfu多級反饋輪轉(zhuǎn)調(diào)度（RRMF)在輪轉(zhuǎn)法中加入到就緒隊(duì)列的進(jìn)程有三種情況：時間片用完I/O請求或進(jìn)程互斥導(dǎo)致阻塞新創(chuàng)建進(jìn)程進(jìn)入就緒隊(duì)列對這些進(jìn)程區(qū)別對待，采用不同的時間片或優(yōu)先權(quán)。OperatingSystemConceptionDavidfu多級反饋隊(duì)列調(diào)度OperatingSystemConceptionDavidfu線性優(yōu)先級調(diào)度(SRR)輪轉(zhuǎn)法調(diào)度時，新創(chuàng)建的進(jìn)程放入就緒隊(duì)列末尾享受平等的處理機(jī)時間片。是否可以采用兩種隊(duì)列進(jìn)行服務(wù)享受服務(wù)隊(duì)列CPU新創(chuàng)建進(jìn)程隊(duì)列完成OperatingSystemConceptionDavidfu線性優(yōu)先級調(diào)度(SRR)新進(jìn)程在就緒隊(duì)列中的優(yōu)先級：P=a*t(a>0)享受服務(wù)進(jìn)程在就緒隊(duì)列中的優(yōu)先級：P=b*t(a>b>0)某進(jìn)程在t1時刻被創(chuàng)建，在t時刻的優(yōu)先級：P(t)=a(t-t1)(t1<t<t1’)在t1’時刻進(jìn)入享受服務(wù)隊(duì)列，在時刻t，進(jìn)程的優(yōu)先級：P(t)=a*(t1’-t1)+b(t-t1’)OperatingSystemConceptionDavidfu線性優(yōu)先級調(diào)度(SRR)何時進(jìn)行隊(duì)列間的調(diào)度：新創(chuàng)建進(jìn)程隊(duì)列的頭一個進(jìn)程的優(yōu)先權(quán)與享受服務(wù)隊(duì)列中最后一個進(jìn)程的優(yōu)先權(quán)相等時享受隊(duì)列為空如果b>a>0-FCFS如果a>b=0RRSRR是對FCFS和RR調(diào)度算法的折衷算法OperatingSystemConceptionDavidfu最高響應(yīng)比優(yōu)先法(HRN)

最高響應(yīng)優(yōu)先法是對FCFS方式和SJF方式的綜合平衡響應(yīng)比定義：R=(W+T)/T=1+W/TT為該作業(yè)估計需要的執(zhí)行時間，W為等待時間OperatingSystemConceptionDavidfu本課總體綱要調(diào)度算法多級隊(duì)列調(diào)度多級反饋輪轉(zhuǎn)調(diào)度（roundrobinwithmultiplefeedback)線性優(yōu)先級調(diào)度（selfishroundrobin)最高響應(yīng)比優(yōu)先法(Highestresponse_rationext)實(shí)時調(diào)度算法評估進(jìn)程調(diào)度例題分析OperatingSystemConceptionDavidfu實(shí)時調(diào)度操作系統(tǒng)是實(shí)時系統(tǒng)中的重要組成部分之一其處理和控制的正確性不僅僅取決于計算的邏輯結(jié)果，而且取決于計算和處理結(jié)果產(chǎn)生的時間。實(shí)時操作系統(tǒng)具有以下特點(diǎn)：有限等待時間（決定性）有限響應(yīng)時間用戶控制可靠性高系統(tǒng)出錯處理能力強(qiáng)OperatingSystemConceptionDavidfu實(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)先級的隨時搶占式調(diào)度OperatingSystemConceptionDavidfu本課總體綱要調(diào)度算法多級隊(duì)列調(diào)度多級反饋輪轉(zhuǎn)調(diào)度（roundrobinwithmultiplefeedback)線性優(yōu)先級調(diào)度（selfishroundrobin)最高響應(yīng)比優(yōu)先法(Highestresponse_rationext)實(shí)時調(diào)度算法評估進(jìn)程調(diào)度例題分析OperatingSystemConceptionDavidfu算法評估（1）如何選擇適合的CPU調(diào)度算法用于特定的系統(tǒng)定義選擇算法的準(zhǔn)則：最大化CPU使用率，同時要求最大響應(yīng)時間為1S?最大化吞吐量，要求平均周轉(zhuǎn)時間與總的時間成正比OperatingSystemConceptionDavidfu算法評估（3）Little公式n=λ*Rn－平均隊(duì)列長度（進(jìn)程數(shù)）R－隊(duì)列平均響應(yīng)時間

λ－新進(jìn)程到達(dá)隊(duì)列的平均到達(dá)率OperatingSystemConceptionDavidfue算法評估（4）對于FCFS:短作業(yè)和長作業(yè)的平均等待時間一樣長。Rfc=1/(μ–λ)對于RR:R(k)=k*q/(1-ρ)對于SRRRsr=1/(μ–λ)－(1－kqμ)/(μ–λ)OperatingSystemConceptionDavidfu本課總體綱要調(diào)度算法多級隊(duì)列調(diào)度多級反饋輪轉(zhuǎn)調(diào)度（roundrobinwithmultiplefeedback)線性優(yōu)先級調(diào)度（selfishroundrobin)最高響應(yīng)比優(yōu)先法(Highestresponse_rationext)實(shí)時調(diào)度算法評估進(jìn)程調(diào)度例題分析OperatingSystemConceptionDavidfu綜合計算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=16msOperatingSystemConceptionDavidfu進(jìn)程調(diào)度例題分析以下哪些算法與作業(yè)的執(zhí)行時間有關(guān)A)優(yōu)先級調(diào)度B)RRC)SJFD)HRNE)FCFSOperatingSystemConceptionDavidfu作業(yè)作業(yè)調(diào)度和進(jìn)程調(diào)度的區(qū)別以下調(diào)度算法的區(qū)別FCFSSJFRRHRNSRROperatingSystemConceptionDavidfu作業(yè)分別計算以下兩種算法的平均周轉(zhuǎn)時間T和響應(yīng)比R(1)FCFS