《中斷與處理機(jī)調(diào)度》PPT課件

《《中斷與處理機(jī)調(diào)度》PPT課件》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、3.2處理機(jī)調(diào)度3.2.1處理機(jī)調(diào)度算法按什么原則分配3.2.2處理機(jī)調(diào)度時(shí)機(jī)何時(shí)重新分配3.2.3處理機(jī)調(diào)度過程如何完成分配scheduling3.2.1處理機(jī)調(diào)度算法考慮因素（schedulingcriteria）CPU利用率;(max)吞吐量;(max)周轉(zhuǎn)時(shí)間;(min)響應(yīng)時(shí)間;(min)系統(tǒng)開銷;(min)調(diào)度參數(shù)周轉(zhuǎn)時(shí)間：完成時(shí)間-進(jìn)入時(shí)間平均周轉(zhuǎn)時(shí)間：周轉(zhuǎn)時(shí)間的平均值帶權(quán)周轉(zhuǎn)時(shí)間：周轉(zhuǎn)時(shí)間/運(yùn)行時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間：帶權(quán)周轉(zhuǎn)時(shí)間的平均值CPUburstvs.I/Oburst陣發(fā)期:CPUburstcycle:進(jìn)程(線程)使用CPU計(jì)算；I/Oburstcycle

2、:進(jìn)程(線程)使用設(shè)備I/O。進(jìn)程運(yùn)行行為：CPUburst,I/Oburst,CPUburst,I/Oburst,……CPU調(diào)度：考慮處于CPUburst進(jìn)程集合CPUburst時(shí)間根據(jù)以前行為推定。CPUburstvs.I/Oburst下一個(gè)CPUburst的長(zhǎng)度估算令τn是估計(jì)的第n個(gè)CPU陣發(fā)期的長(zhǎng)度，tn的值是進(jìn)程最近一次CPU陣發(fā)期長(zhǎng)度，則有如下估算公式：τn+1=αtn+(1-α)τn參數(shù)α(0≤α≤1)控制tn和τn在公式中起的作用：當(dāng)α=0時(shí)，τn+1=τn；當(dāng)α=1時(shí)，τn+1=tn。通常α取0.5。剝奪式調(diào)度與非剝奪式調(diào)度剝奪式(preemptive)就緒

3、進(jìn)程可以從運(yùn)行進(jìn)程手中搶占CPU。進(jìn)程運(yùn)行,直到結(jié)束、等待或被搶先非剝奪式(non-preemptive)就緒進(jìn)程不可從運(yùn)行進(jìn)程手中搶占CPU。進(jìn)程運(yùn)行,直到結(jié)束或等待3.2.1.1先到先服務(wù)算法FCFS（FirstComeFirstServe)按進(jìn)程申請(qǐng)CPU（就緒）的次序。ProcessArrivaltimeBursttimeP1027P213P325CPU調(diào)度狀況可用Gantt圖表示．0273035P1P2P33.2.1.1先到先服務(wù)算法(Cont.)進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間P1027027271P2132730299.67P3253035

4、336.6平均周轉(zhuǎn)時(shí)間=(27+29+33)/3=29.67平均帶權(quán)周轉(zhuǎn)時(shí)間=(1+9.67+6.6)/3=5.760273035P1P2P33.2.1.1先到先服務(wù)算法(Cont.)優(yōu)點(diǎn)：“公平”；缺點(diǎn):短作業(yè)等待時(shí)間長(zhǎng)。3.2.1.2短作業(yè)優(yōu)先SJF（ShortestJobFirst)按CPUburst長(zhǎng)度ProcessArrivaltimeBursttimeP1012P205P307P403GanttChart0381527P1P2P3P43.2.1.2短作業(yè)優(yōu)先0381527P1P2P3P4進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間P10121527272

5、.25P2053881.6P307815152.14P4030331平均周轉(zhuǎn)時(shí)間=(27+8+15+3)/4=13.25平均帶權(quán)周轉(zhuǎn)時(shí)間=(2.25+1.6+2.14+1)/4=1.753.2.1.2短作業(yè)優(yōu)先特點(diǎn)：假定所有任務(wù)同時(shí)到達(dá)，平均等待時(shí)間最短。長(zhǎng)作業(yè)可能被餓死。3.2.1.3最短剩余時(shí)間優(yōu)先算法(SRTN)ShortestRemainingTimeNext可剝奪SJFProcessArrivaltimeBursttimeP1012P219P336P453Gantt圖P1P2P3P4P3P2P1013581219303.2.1.3最短剩余時(shí)間優(yōu)先算法(Cont.)進(jìn)程

6、到達(dá)時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間P1012030302.5P219119182P33631291.5P4535831平均周轉(zhuǎn)時(shí)間=(30+18+9+3)/4=15平均帶權(quán)周轉(zhuǎn)時(shí)間=(2.5+2+1.5+1)/4=1.75平均等待時(shí)間＝(18+9+3+0)/4＝7.5(ms)P1P2P3P4P3P2P1013581219303.2.1.4最高響應(yīng)比優(yōu)先(HRN)HighestResponseRatioNextRR=(BT+WT)/BT=1+WT/BT其中:BT=bursttimeWT=waittime優(yōu)點(diǎn):同時(shí)到達(dá)任務(wù),短者優(yōu)先長(zhǎng)作業(yè)隨等待時(shí)間增加響應(yīng)比增加3

7、.2.1.5最高優(yōu)先數(shù)算法(HPF)靜態(tài)優(yōu)先數(shù)(static)優(yōu)先數(shù)在進(jìn)程創(chuàng)建時(shí)分配，生存期內(nèi)不變。響應(yīng)速度慢，開銷小。適合批處理進(jìn)程動(dòng)態(tài)優(yōu)先數(shù)(dynamic)進(jìn)程創(chuàng)建時(shí)繼承優(yōu)先數(shù)，生存期內(nèi)可以修改。響應(yīng)速度快，開銷大。適用于實(shí)時(shí)系統(tǒng)3.2.1.5最高優(yōu)先數(shù)算法(Cont.)非剝奪式優(yōu)先數(shù)獲得處理機(jī)的進(jìn)程運(yùn)行，直至終止等待剝奪式優(yōu)先數(shù)獲得處理機(jī)的進(jìn)程運(yùn)行，直至終止等待出現(xiàn)高優(yōu)先級(jí)的進(jìn)程3.2.1.5最高優(yōu)先數(shù)算法(Cont.)可搶占CPUProcessArrivaltimePriority