單處理器調(diào)度課件

單處理器調(diào)度

調(diào)度的類型長程調(diào)度決定哪個(gè)進(jìn)程進(jìn)入系統(tǒng)中程調(diào)度決定哪個(gè)進(jìn)程回到內(nèi)存短程調(diào)度決定哪個(gè)進(jìn)程獲得CPUI/O調(diào)度決定哪個(gè)進(jìn)程使用I/O設(shè)備調(diào)度和進(jìn)程狀態(tài)轉(zhuǎn)換新建就緒/掛起阻塞/掛起就緒阻塞運(yùn)行退出長程長程中程中程短程調(diào)度的層次新建退出就緒阻塞運(yùn)行就緒/掛起阻塞/掛起長程調(diào)度中程調(diào)度短程調(diào)度用于調(diào)度的排隊(duì)圖CPU交互用戶批作業(yè)事件等待事件發(fā)生阻塞隊(duì)列阻塞掛起就緒隊(duì)列就緒掛起超時(shí)長程調(diào)度系統(tǒng)可以創(chuàng)建一個(gè)/多個(gè)新進(jìn)程一個(gè)作業(yè)終止時(shí)CPU利用率太低接受哪個(gè)作業(yè)創(chuàng)建進(jìn)程先來先服務(wù)系統(tǒng)性能相關(guān)指標(biāo)優(yōu)先級等待時(shí)間I/O需求引起短期調(diào)度的事件時(shí)鐘中斷I/O中斷OS調(diào)用信號調(diào)度準(zhǔn)則面向用戶面向系統(tǒng)與性能相關(guān)周轉(zhuǎn)時(shí)間響應(yīng)時(shí)間最后期限吞吐量CPU使用率其他可預(yù)測性公平強(qiáng)制優(yōu)先級平衡資源優(yōu)先級的使用CPURQ0RQ1RQn……阻塞隊(duì)列允許進(jìn)入剝奪阻塞喚醒RQ0>RQ1…>RQn會(huì)導(dǎo)致饑餓調(diào)度策略常用參數(shù)w進(jìn)程進(jìn)入系統(tǒng)的時(shí)間e進(jìn)程執(zhí)行的時(shí)間s進(jìn)程所需的總時(shí)間決策模式非剝奪－只能由進(jìn)程主動(dòng)釋放CPU剝奪－OS可以強(qiáng)制獲得CPU各種調(diào)度策略的特點(diǎn)算法選擇函數(shù)決策模式FCFS先來先服務(wù)Max(w)非剝奪循環(huán)常數(shù)剝奪SPNMin(s)非剝奪SRTMin(s-e)剝奪HRRNMsx(w+s/s)非剝奪反饋剝奪進(jìn)程調(diào)度示例進(jìn)程到達(dá)時(shí)間服務(wù)時(shí)間A03B26C44D65E82FCFS05101520ABCDEFCFS適合長進(jìn)程設(shè)備利用率低一般和優(yōu)先級策略結(jié)合標(biāo)準(zhǔn)化的周轉(zhuǎn)時(shí)間進(jìn)程到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間結(jié)束時(shí)間周轉(zhuǎn)時(shí)間標(biāo)準(zhǔn)化周轉(zhuǎn)時(shí)間W010111X110011011001Y21101102100100Z31001022021991.99標(biāo)準(zhǔn)化周轉(zhuǎn)時(shí)間＝周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間FCFS適合長進(jìn)程循環(huán)q=105101520ABCDE循環(huán)q=405101520ABCDE時(shí)間片大小的影響響應(yīng)時(shí)間時(shí)間段時(shí)間段>平均交互時(shí)間時(shí)間段<平均交互時(shí)間其他進(jìn)程運(yùn)行虛擬循環(huán)調(diào)度CPUI/O隊(duì)列nI/O隊(duì)列1就緒隊(duì)列輔助隊(duì)列……最短進(jìn)程優(yōu)先長進(jìn)程會(huì)餓死不適合分時(shí)系統(tǒng)和事務(wù)處理最短剩余時(shí)間增加了剝奪機(jī)制的SPN需要記錄過去的服務(wù)時(shí)間響應(yīng)時(shí)間快對長進(jìn)程不利最高響應(yīng)比響應(yīng)比＝(等待時(shí)間+服務(wù)時(shí)間)/服務(wù)時(shí)間響應(yīng)時(shí)間快長短作業(yè)的平衡較好反饋調(diào)度CPUCPUCPURQ0RQ1RQn實(shí)時(shí)計(jì)算系統(tǒng)的正確性不僅取決于計(jì)算的邏輯結(jié)果，還依賴于產(chǎn)生結(jié)果的時(shí)間最后期限－必須開始或結(jié)束的時(shí)間硬實(shí)時(shí)任務(wù)與軟實(shí)時(shí)任務(wù)實(shí)時(shí)OS的特點(diǎn)可確定性響應(yīng)性用戶控制可靠性故障弱化運(yùn)行實(shí)時(shí)調(diào)度的基本條件提供必要的信息就緒時(shí)間，開始/完成截止時(shí)間，處理時(shí)間資源要求，優(yōu)先級系統(tǒng)處理能力強(qiáng)Sum(處理時(shí)間/周期)<=1采用搶占式調(diào)度機(jī)制具有快速切換機(jī)制快速響應(yīng)外部中斷快速分派任務(wù)調(diào)度算法分類非搶占式調(diào)度算法輪轉(zhuǎn)調(diào)度優(yōu)先調(diào)度搶占式調(diào)度算法基于時(shí)鐘中斷立即搶占實(shí)時(shí)進(jìn)程調(diào)度P1P2……Pnp實(shí)時(shí)進(jìn)程到達(dá)P1pP1p剝奪點(diǎn)P1p立即剝奪放在就緒隊(duì)列頭放在就緒隊(duì)列尾常用實(shí)時(shí)調(diào)度算法－EDF最早截止時(shí)間優(yōu)先earliestdeadlinefirst開始截止時(shí)間任務(wù)執(zhí)行任務(wù)到達(dá)134213421234搶占式或非搶占式調(diào)度常用實(shí)時(shí)調(diào)度算法－LLF最低松弛度優(yōu)先leastlexityfirstA1A2A3A4A5B1B2A1B1A2B1A3B2A4B220406080A1-10B1-25A2=20B1-15