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

操作系統(tǒng)概念

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

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

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