04第四章 處理機(jī)調(diào)度.ppt

1 第四章處理機(jī)調(diào)度 CPU是計算機(jī)系統(tǒng)中一個十分重要的資源 在早期的計算機(jī)系統(tǒng)中 因為系統(tǒng)只有一個作業(yè)在運(yùn)行 所以 不存在處理機(jī)的分配和調(diào)度問題 但在多道程序設(shè)計環(huán)境下 不同的CPU管理方法將為用戶提供不同性能的操作系統(tǒng) CPU調(diào)度的基本原則是 盡量提高CPU的效率和增加作業(yè)的吞吐率 這樣 在考慮作業(yè)調(diào)度算法時 要盡可能使作業(yè)搭配合理 例如 運(yùn)算量大的作業(yè)和I O量大的作業(yè)在一起運(yùn)行 這樣可使各種資源得到充分利用 2 4 1分級調(diào)度4 2作業(yè)調(diào)度4 3進(jìn)程調(diào)度4 4調(diào)度算法4 5算法評價4 6實時系統(tǒng)調(diào)度算法 3 4 1分級調(diào)度 1 作業(yè)狀態(tài)及其轉(zhuǎn)換圖 4 2 調(diào)度的層次 作業(yè)調(diào)度 又稱為宏觀調(diào)度或高級調(diào)度 其主要任務(wù)是按一定的原則對外存輸入井上的大量后備作業(yè)進(jìn)行選擇 給選出的作業(yè)分配內(nèi)存 輸入輸出設(shè)備等必要資源 并建立了相應(yīng)的進(jìn)程 以使該作業(yè)的進(jìn)程獲得競爭處理機(jī)的權(quán)利 交換調(diào)度 又稱為中級調(diào)度 其主要任務(wù)是按一定的原則和策略 將處于外存交換區(qū)中的就緒狀態(tài)或就緒等待狀態(tài)的進(jìn)程調(diào)入內(nèi)存 或把處于內(nèi)存就緒狀態(tài)或內(nèi)存等待狀態(tài)的進(jìn)程交換到外存交換區(qū) 交換調(diào)度主要涉及內(nèi)存管理與擴(kuò)充 進(jìn)程調(diào)度 又稱為微觀調(diào)度或低級調(diào)度 其主要任務(wù)是按照某種策略和方法選取一個處于就緒狀態(tài)的進(jìn)程占用處理機(jī) 線程調(diào)度 5 4 2作業(yè)調(diào)度 1 作業(yè)調(diào)度的功能 記錄系統(tǒng)中各作業(yè)的狀況 從后備隊列中挑選出一部分作業(yè)投入運(yùn)行 為選中的作業(yè)做好執(zhí)行前的準(zhǔn)備工作 在作業(yè)執(zhí)行結(jié)束時做善后處理工作 如 撤銷該作業(yè)的全部進(jìn)程PCB和作業(yè)控制塊JCB 2 作業(yè)調(diào)度的目標(biāo) 對所有的作業(yè)應(yīng)該是公平合理的 應(yīng)使設(shè)備具有較高的利用率 單位時間內(nèi)執(zhí)行盡可能多的作業(yè) 有較快的響應(yīng)時間 6 3 衡量調(diào)度算法優(yōu)劣的標(biāo)準(zhǔn) 1 周轉(zhuǎn)時間 作業(yè)i的周轉(zhuǎn)時間Ti為 Ti Tei Tsi其中 Tsi為作業(yè)的提交時間Tei為作業(yè)的完成時間 所有作業(yè)的平均周轉(zhuǎn)時間為T n其中 n為作業(yè)數(shù) T越小越好 2 帶權(quán)周轉(zhuǎn)時間 帶權(quán)周轉(zhuǎn)時間是作業(yè)周轉(zhuǎn)時間與作業(yè)執(zhí)行時間之比 Wi Ti Tri其中 Tri作業(yè)的執(zhí)行時間 平均帶權(quán)周轉(zhuǎn)時間為 W n 7 4 3進(jìn)程調(diào)度 1 進(jìn)程調(diào)度的功能記錄系統(tǒng)中所有進(jìn)程的執(zhí)行情況 操作系統(tǒng)的進(jìn)程管理模塊必須將系統(tǒng)中各進(jìn)程的執(zhí)行情況和運(yùn)行狀態(tài)記錄在各進(jìn)程的PCB表中 選擇占有處理機(jī)的進(jìn)程 進(jìn)程管理模塊按照一定的策略選擇一個處于就緒狀態(tài)的進(jìn)程 使其獲得處理機(jī)執(zhí)行 進(jìn)行進(jìn)程上下文的切換 一個進(jìn)程的上下文包括進(jìn)程的狀態(tài) 有關(guān)變量和數(shù)據(jù)結(jié)構(gòu)的值 硬件寄存器的值和PCB以及程序等 一個進(jìn)程的執(zhí)行是在進(jìn)程的上下文中執(zhí)行 當(dāng)正在執(zhí)行的進(jìn)程由于某種原因要讓出處理機(jī)時 系統(tǒng)要進(jìn)行上下文的切換 以使另一個進(jìn)程在CPU上運(yùn)行 8 2 進(jìn)程調(diào)度的時機(jī) 引起進(jìn)程調(diào)度的原因主要包括以下幾類 1 正在執(zhí)行的進(jìn)程執(zhí)行完畢 2 執(zhí)行中的進(jìn)程自己調(diào)用阻塞原語將自己阻塞起來進(jìn)入睡眠狀態(tài) 3 執(zhí)行中的進(jìn)程因申請外部設(shè)備而沒有得到被阻塞 4 使用CPU的時間片到 5 就緒隊列中的某進(jìn)程的優(yōu)先級變得高于當(dāng)前執(zhí)行進(jìn)程的優(yōu)先級 從而也將引發(fā)進(jìn)程調(diào)度 9 3 進(jìn)程上下文切換 進(jìn)程上下文切換的步驟1 決定是否做上下文切換以及是否允許做上下文切換 2 保存當(dāng)前執(zhí)行進(jìn)程的上下文 3 依據(jù)一定的調(diào)度算法選擇一個處于就緒狀態(tài)的進(jìn)程 4 恢復(fù)或裝配所選進(jìn)程的上下文 將CPU控制權(quán)交給所選進(jìn)程 進(jìn)程上下文內(nèi)容包括 1 計算機(jī)系統(tǒng)執(zhí)行該進(jìn)程有關(guān)各種寄存器 通用寄存器 程序計數(shù)器PC 程序狀態(tài)字PS等 的值 2 程序段的機(jī)器指令代碼集 正文段 數(shù)據(jù)集 3 各種堆棧值和PCB結(jié)構(gòu) 10 4 進(jìn)程調(diào)度性能評價 進(jìn)程調(diào)度性能的衡量方法 有定形和定量兩種方法 定形衡量 1 可靠性 包括一次進(jìn)程調(diào)度是否可能引起數(shù)據(jù)結(jié)構(gòu)的破壞 這要求對調(diào)度時機(jī)的選擇和保存CPU現(xiàn)場非常謹(jǐn)慎 2 簡潔性 要求進(jìn)程調(diào)度不要產(chǎn)生較大的系統(tǒng)開銷 以免消耗過多資源 定量衡量 1 CPU利用率評價 2 進(jìn)程在就緒隊列中等待時間與執(zhí)行時間之比 11 4 4調(diào)度算法 先來先服務(wù)時間片輪轉(zhuǎn)算法短作業(yè)優(yōu)先優(yōu)先級算法多級隊列算法多級反饋隊列算法 12 1 先來先服務(wù) FCFS 調(diào)度的基本原則是按照作業(yè)到達(dá)系統(tǒng)或進(jìn)程進(jìn)入就緒隊列的先后次序來選擇作業(yè)或進(jìn)程 注 FCFS很少用作主要的調(diào)度策略 但它常與其它調(diào)度算法結(jié)合使用 13 2 時間片輪轉(zhuǎn) RoundRobin 算法 基本思想 將處于就緒隊列的進(jìn)程按到達(dá)的時間來排序 進(jìn)程調(diào)度總是選擇隊列中的第一個進(jìn)程 即按先來先服務(wù) 占有CPU 但每個進(jìn)程占有相同的時間片 注 此算法最適合分時系統(tǒng) 關(guān)鍵問題是時間片長短的選擇 14 3 短作業(yè)優(yōu)先 該算法主要用于作業(yè)調(diào)度 它是從后備作業(yè)隊列中挑選那些所需的運(yùn)行時間 估計時間 最短的作業(yè)進(jìn)入主存運(yùn)行 優(yōu)點 比FCFS改善平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間 縮短作業(yè)的等待時間 提高系統(tǒng)的吞吐量 缺點 對長作業(yè)不利 可能長時間得不到執(zhí)行 未能依據(jù)作業(yè)的緊迫程度來劃分執(zhí)行的優(yōu)先級 難以準(zhǔn)確估計作業(yè) 進(jìn)程 的執(zhí)行時間 從而影響調(diào)度性能 15 4 優(yōu)先級算法 按照進(jìn)程的優(yōu)先級大小來調(diào)度 使高優(yōu)先級的進(jìn)程優(yōu)先得到處理的調(diào)度策略 進(jìn)程的優(yōu)先級大小可由系統(tǒng)自動地按照一定的原則賦給它 也可由外部來安排 也可由用戶支付高費用來購買 優(yōu)先級調(diào)度算法分為兩種 1 非搶占優(yōu)先級調(diào)度算法即一旦進(jìn)程占有的處理機(jī) 就一直運(yùn)行下去 直到由于本身的原因而主動讓出處理機(jī) 2