【正文】 等待事件 后 備 隊(duì) 列 批量作業(yè) 中級調(diào)度 掛起就緒隊(duì)列 掛起阻塞隊(duì)列 阻塞隊(duì)列 18 2022/2/16 調(diào)度算法選擇準(zhǔn)則 ? OS中調(diào)度方式和算法的選擇取決于 OS的類型和目標(biāo) ? 面向用戶準(zhǔn)則 ? 周轉(zhuǎn) 時(shí)間短 ? 響應(yīng) 時(shí)間快 ? 截止 時(shí)間的保證 ? 優(yōu)先權(quán)準(zhǔn)則 ? 面向系統(tǒng)準(zhǔn)則 ? 系統(tǒng)吞吐量高：評價(jià)批處理系統(tǒng)的重要準(zhǔn)則 ? 處理機(jī)利用率好：多用于大中型多用戶系統(tǒng)、分時(shí)系統(tǒng) ? 各類資源平衡利用：多用于大中型系統(tǒng) 23 2022/2/16 調(diào)度算法 先來先服務(wù)與短作業(yè)優(yōu)先 1 高優(yōu)先權(quán)優(yōu)先調(diào)度算法 2 時(shí)間片輪轉(zhuǎn)的調(diào)度算法 3 24 2022/2/16 調(diào)度算法定義 ? 根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法，不同系統(tǒng)需求采用不同的調(diào)度算法 25 2022/2/16 先來先服務(wù)調(diào)度算法（ FCFS） ? 作業(yè)調(diào)度 ：按照進(jìn)入后備隊(duì)列的時(shí)間先后順序選擇一個(gè)或多個(gè)作業(yè)，使之進(jìn)入內(nèi)存并為之分配資源、創(chuàng)建進(jìn)程、插入就緒隊(duì)列 ?進(jìn)程調(diào)度 ：指定最早進(jìn)入就緒隊(duì)列的進(jìn)程可以獲得處理機(jī)，使之運(yùn)行，直到進(jìn)程完成調(diào)度或發(fā)生某事件而阻塞后才放棄處理機(jī) ? FCFS利于長作業(yè)和 CPU繁忙型作業(yè) 的調(diào)度，不利于短作業(yè)和 I/O繁忙型作業(yè)調(diào)度 26 2022/2/16 FCFS 進(jìn)程 到達(dá)時(shí)間 服務(wù)時(shí)間（執(zhí) 行時(shí)間） 開始執(zhí)行時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 A 0 1 0 1 1 1 B 1 100 1 101 100 1 C 2 1 101 102 100 100 D 3 100 102 202 199 平均周轉(zhuǎn)時(shí)間 T=400/4=100 平均帶權(quán)周轉(zhuǎn)時(shí)間 W=周轉(zhuǎn)時(shí)間 =完成時(shí)間 到達(dá)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 =周轉(zhuǎn)時(shí)間 /執(zhí)行時(shí)間 27 2022/2/16 短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法 SJ(P)F ? 短作業(yè)優(yōu)先 ：從后備隊(duì)列中選擇一個(gè)或多個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)調(diào)入內(nèi)存運(yùn)行 ? 短進(jìn)程優(yōu)先 ：從就緒隊(duì)列中選擇一個(gè)估計(jì)運(yùn)行時(shí)間最短的進(jìn)程獲取處理機(jī)，使之立即執(zhí)行直至任務(wù)完成或因?yàn)槟呈录蛔枞? ? 相對于 FCFS， SJ(P)F的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間都顯著改善，即降低了作業(yè)的平均等待時(shí)間，提高了系統(tǒng)吞吐量 28 2022/2/16 SJ(P)F的缺點(diǎn) ? 對長作業(yè)不利：進(jìn)入系統(tǒng)的長作業(yè)可能被長期忽視 ? 未考慮作業(yè)的緊迫程度（優(yōu)先權(quán)） ? 作業(yè)運(yùn)行時(shí)間的長短由用戶自身提供，錯(cuò)誤的估算會影響真正的短作業(yè)的執(zhí)行 29 2022/2/16 FCFS和 SJ(P)F的性能比較 進(jìn)程名 A B C D E 平均 到達(dá)時(shí)間 0 1 2 3 4 服務(wù)時(shí)間 8 7 5 3 6 FCFS 完成時(shí)間 8 15 20 23 29 周轉(zhuǎn)時(shí)間 8 14 18 20 25 17 帶權(quán)周轉(zhuǎn)時(shí)間 1 2 SJ(P)F 完成時(shí)間 8 29 16 11 22 周轉(zhuǎn)時(shí)間 8 28 14 8 18 帶權(quán)周轉(zhuǎn)時(shí)間 1 4 3 30 2022/2/16 高優(yōu)先權(quán)優(yōu)先調(diào)度算法 FPF ? 為保證緊迫型任務(wù)的優(yōu)先完成而引入 ? 作業(yè)調(diào)度 ：從后備隊(duì)列中選取若干個(gè)優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存 ? 進(jìn)程調(diào)度 ：把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程 ? 非搶占式優(yōu)先權(quán)算法：常見于批處理系統(tǒng)或?qū)崟r(shí)性要求不高的實(shí)時(shí)系統(tǒng) ? 搶占式優(yōu)先權(quán)算法：常用于嚴(yán)格實(shí)時(shí)系統(tǒng)或高性能要求的批處理、分時(shí) OS中 31 2022/2/16 FPF ? FPF算法的關(guān)鍵在于使用 靜態(tài)優(yōu)先權(quán) 還是 動態(tài)優(yōu)先權(quán) 以及如何確定進(jìn)程的優(yōu)先權(quán) ? 優(yōu)先權(quán)類型 ? 靜態(tài)優(yōu)先權(quán)：進(jìn)程 創(chuàng)建時(shí)確定 且在進(jìn)程生命期中 保持不變 ，這種方法實(shí)現(xiàn)簡單、開銷小但不精確，可能會產(chǎn)生低優(yōu)先權(quán)進(jìn)程 饑餓 ，用于低要求的 OS ? 動態(tài)優(yōu)先權(quán)：進(jìn)程創(chuàng)建時(shí)確定的優(yōu)先數(shù)可能隨進(jìn)程發(fā)展或等待時(shí)間增加等因素而變化，確保了更優(yōu)良的調(diào)度性能 32 2022/2/16 FPF ? 確定優(yōu)先權(quán)的依據(jù) ? 進(jìn)程類型：系統(tǒng)進(jìn)程高于用戶進(jìn)程 ? 進(jìn)程對資源的需求：對系統(tǒng)資源的需求量小的進(jìn)程可以優(yōu)先運(yùn)行 ? 用戶要求：根據(jù)用戶進(jìn)程緊迫程度和用戶所付費(fèi)用決定優(yōu)先權(quán) 33 2022/2/16 高響應(yīng)比優(yōu)先調(diào)度算法 ? 此算法結(jié)合了 SJ(P)F和 FPF的優(yōu)點(diǎn)，為 SJ(P)F中的所有進(jìn)程引入 動態(tài)優(yōu)先權(quán) ，并使作業(yè)的優(yōu)先數(shù)隨著等待時(shí)間的增加而以速率 a提高，則長作業(yè)在等待一定時(shí)間后一定有機(jī)會獲得處理機(jī) 34 2022/2/16 高響應(yīng)比優(yōu)先調(diào)度算法 ?這種優(yōu)先權(quán)可以表示為 Rp =(tw+ts)/ts 其中， tw為等待時(shí)間， ts為預(yù)估的服務(wù)時(shí)間， Rp稱為響應(yīng)比 ? 特點(diǎn) ? 短作業(yè)優(yōu)先：前提為等待時(shí)間相同 ? 先來先服務(wù)：前提為預(yù)估服務(wù)時(shí)間相同 ? 長作業(yè)調(diào)度有保證：前提是該長作業(yè)等待時(shí)間足夠長，使得其優(yōu)先級升到足夠高 ? 增加系統(tǒng)開銷：響應(yīng)比的計(jì)算需要在每次調(diào)度前進(jìn)行 35 2022/2/16 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法 ? 回顧：分時(shí)系統(tǒng)中采用基于時(shí)間片的輪轉(zhuǎn)式進(jìn)程調(diào)度算法來保證對用戶請求的及時(shí)響應(yīng) ? 分類 ? 時(shí)間片輪轉(zhuǎn) ? 多級反饋隊(duì)列調(diào)度算法 36 2022/2/16 時(shí)間片輪轉(zhuǎn)法 ? 早期的時(shí)間片輪轉(zhuǎn)調(diào)度法將所有進(jìn)入系統(tǒng)的就緒進(jìn)程按照先來先服務(wù)原則排隊(duì)，每次調(diào)度時(shí)均由隊(duì)首進(jìn)程獲取 CPU并執(zhí)行一個(gè)時(shí)間片；時(shí)間片用完后，計(jì)時(shí)器發(fā)出中斷請求，調(diào)度程序 中止 當(dāng)前進(jìn)程將