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

操作系統(tǒng)概念

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

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

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