課件調(diào)度算法課程概述課程目標(biāo)掌握各類調(diào)度算法原理學(xué)習(xí)內(nèi)容基礎(chǔ)理論與算法實(shí)例分析考核方式第一章：調(diào)度算法基礎(chǔ)調(diào)度的概念進(jìn)程執(zhí)行順序的決策機(jī)制調(diào)度的目的提高系統(tǒng)資源利用率調(diào)度的層次調(diào)度的類型1短程調(diào)度CPU調(diào)度，頻率最高2中程調(diào)度內(nèi)存與交換調(diào)度3長(zhǎng)程調(diào)度作業(yè)調(diào)度，頻率最低進(jìn)程狀態(tài)轉(zhuǎn)換運(yùn)行態(tài)正在CPU上執(zhí)行就緒態(tài)等待分配CPU阻塞態(tài)等待某事件發(fā)生創(chuàng)建態(tài)進(jìn)程正在被創(chuàng)建終止態(tài)進(jìn)程執(zhí)行完畢調(diào)度算法評(píng)價(jià)指標(biāo)周轉(zhuǎn)時(shí)間提交到完成的時(shí)間等待時(shí)間進(jìn)程在就緒隊(duì)列中的總時(shí)間CPU利用率CPU忙碌時(shí)間百分比吞吐量單位時(shí)間內(nèi)完成進(jìn)程數(shù)第二章：先來(lái)先服務(wù)(FCFS)調(diào)度算法算法原理按進(jìn)程到達(dá)順序分配CPU數(shù)據(jù)結(jié)構(gòu)使用隊(duì)列存儲(chǔ)就緒進(jìn)程實(shí)現(xiàn)方法簡(jiǎn)單隊(duì)列管理，先進(jìn)先出FCFS算法示例進(jìn)程到達(dá)時(shí)間執(zhí)行時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間P10242424P2132726P3263331FCFS算法優(yōu)缺點(diǎn)分析優(yōu)點(diǎn)實(shí)現(xiàn)簡(jiǎn)單直觀無(wú)饑餓現(xiàn)象適合批處理系統(tǒng)缺點(diǎn)平均等待時(shí)間可能較長(zhǎng)護(hù)航效應(yīng)明顯不利于交互式系統(tǒng)第三章：短作業(yè)優(yōu)先(SJF)調(diào)度算法算法原理選擇執(zhí)行時(shí)間最短的進(jìn)程優(yōu)先級(jí)確定執(zhí)行時(shí)間越短優(yōu)先級(jí)越高實(shí)現(xiàn)方法優(yōu)先隊(duì)列或排序鏈表SJF算法示例SJF算法優(yōu)缺點(diǎn)分析優(yōu)點(diǎn)平均等待時(shí)間最短平均周轉(zhuǎn)時(shí)間最佳系統(tǒng)吞吐量高缺點(diǎn)長(zhǎng)作業(yè)可能饑餓需預(yù)知執(zhí)行時(shí)間不適合交互系統(tǒng)第四章：優(yōu)先級(jí)調(diào)度算法算法原理按進(jìn)程優(yōu)先級(jí)高低調(diào)度靜態(tài)優(yōu)先級(jí)進(jìn)程創(chuàng)建時(shí)確定不變動(dòng)態(tài)優(yōu)先級(jí)運(yùn)行過(guò)程中可調(diào)整優(yōu)先級(jí)調(diào)度算法示例進(jìn)程到達(dá)時(shí)間執(zhí)行時(shí)間優(yōu)先級(jí)執(zhí)行順序P101032P21611P32244P43423優(yōu)先級(jí)反轉(zhuǎn)問(wèn)題及解決方案問(wèn)題定義低優(yōu)先級(jí)進(jìn)程阻塞高優(yōu)先級(jí)進(jìn)程發(fā)生原因資源競(jìng)爭(zhēng)與互斥訪問(wèn)優(yōu)先級(jí)繼承臨時(shí)提升資源持有者優(yōu)先級(jí)優(yōu)先級(jí)天花板預(yù)設(shè)資源訪問(wèn)最高優(yōu)先級(jí)第五章：輪轉(zhuǎn)調(diào)度算法(RR)算法原理每個(gè)進(jìn)程分配固定時(shí)間片時(shí)間片耗盡進(jìn)程回到隊(duì)列尾部時(shí)間片選擇過(guò)長(zhǎng)類似FCFS，過(guò)短增加開銷循環(huán)執(zhí)行直到所有進(jìn)程完成RR算法示例4進(jìn)程數(shù)P1,P2,P3,P420ms時(shí)間片每進(jìn)程每輪獲得時(shí)長(zhǎng)3輪轉(zhuǎn)次數(shù)最長(zhǎng)進(jìn)程需要的輪數(shù)RR算法優(yōu)缺點(diǎn)分析優(yōu)點(diǎn)公平性好響應(yīng)時(shí)間短適合交互系統(tǒng)無(wú)進(jìn)程饑餓缺點(diǎn)平均周轉(zhuǎn)時(shí)間較長(zhǎng)上下文切換開銷大時(shí)間片選擇困難第六章：多級(jí)反饋隊(duì)列調(diào)度算法算法原理多個(gè)優(yōu)先級(jí)隊(duì)列動(dòng)態(tài)調(diào)整隊(duì)列設(shè)置高優(yōu)先級(jí)短時(shí)間片，低優(yōu)先級(jí)長(zhǎng)時(shí)間片優(yōu)先級(jí)降低時(shí)間片用完降至低優(yōu)先級(jí)隊(duì)列多級(jí)反饋隊(duì)列調(diào)度算法示例第一級(jí)隊(duì)列優(yōu)先級(jí)最高，時(shí)間片8ms第二級(jí)隊(duì)列中等優(yōu)先級(jí)，時(shí)間片16ms第三級(jí)隊(duì)列優(yōu)先級(jí)最低，時(shí)間片32ms多級(jí)反饋隊(duì)列調(diào)度算法優(yōu)缺點(diǎn)分析優(yōu)點(diǎn)兼顧交互性和周轉(zhuǎn)時(shí)間動(dòng)態(tài)調(diào)整進(jìn)程優(yōu)先級(jí)響應(yīng)時(shí)間短自適應(yīng)能力強(qiáng)缺點(diǎn)實(shí)現(xiàn)復(fù)雜參數(shù)設(shè)置難度大可能出現(xiàn)饑餓現(xiàn)象開銷較大第七章：高響應(yīng)比優(yōu)先調(diào)度算法(HRRN)算法原理綜合考慮等待時(shí)間和服務(wù)時(shí)間響應(yīng)比計(jì)算響應(yīng)比=(等待時(shí)間+服務(wù)時(shí)間)/服務(wù)時(shí)間調(diào)度原則選擇響應(yīng)比最高的進(jìn)程HRRN算法示例進(jìn)程到達(dá)時(shí)間服務(wù)時(shí)間等待時(shí)間響應(yīng)比調(diào)度順序P101001.01P22582.62P338122.53HRRN算法優(yōu)缺點(diǎn)分析優(yōu)點(diǎn)考慮等待時(shí)間因素防止短作業(yè)優(yōu)先的饑餓現(xiàn)象平衡周轉(zhuǎn)時(shí)間和響應(yīng)時(shí)間缺點(diǎn)需要預(yù)知服務(wù)時(shí)間計(jì)算開銷相對(duì)較大非搶占式特性限制響應(yīng)性第八章：多處理器調(diào)度算法負(fù)載均衡使各處理器工作負(fù)荷均衡親和性調(diào)度進(jìn)程盡量運(yùn)行在同一CPU上隊(duì)列結(jié)構(gòu)全局隊(duì)列與每CPU本地隊(duì)列負(fù)載遷移動(dòng)態(tài)平衡各CPU工作負(fù)載多處理器調(diào)度算法示例負(fù)載前負(fù)載后第九章：實(shí)時(shí)調(diào)度算法實(shí)時(shí)系統(tǒng)特點(diǎn)時(shí)間約束嚴(yán)格可預(yù)測(cè)性要求高響應(yīng)時(shí)間是關(guān)鍵硬實(shí)時(shí)系統(tǒng)任務(wù)必須在截止期限內(nèi)完成超時(shí)導(dǎo)致系統(tǒng)失效例如：飛行控制系統(tǒng)軟實(shí)時(shí)系統(tǒng)允許偶爾錯(cuò)過(guò)截止期限性能下降但不失效例如：視頻播放系統(tǒng)速率單調(diào)調(diào)度算法(RMS)算法原理周期短的任務(wù)優(yōu)先級(jí)高可調(diào)度條件n個(gè)任務(wù)總利用率≤n(2^(1/n)-1)任務(wù)特性周期任務(wù)，固定執(zhí)行時(shí)間優(yōu)先級(jí)分配靜態(tài)優(yōu)先級(jí)，周期越短優(yōu)先級(jí)越高最早截止時(shí)間優(yōu)先算法(EDF)算法原理截止時(shí)間最早的任務(wù)優(yōu)先動(dòng)態(tài)優(yōu)先級(jí)根據(jù)當(dāng)前截止時(shí)間動(dòng)態(tài)調(diào)整理論利用率處理器利用率可達(dá)100%最低松弛度優(yōu)先算法(LLF)算法原理選擇松弛度最小的任務(wù)松弛度計(jì)算松弛度=截止時(shí)間-當(dāng)前時(shí)間-剩余執(zhí)行時(shí)間優(yōu)先級(jí)變化動(dòng)態(tài)優(yōu)先級(jí)，頻繁重新計(jì)算第十章：公平調(diào)度算法完全公平調(diào)度(CFS)模擬理想的多任務(wù)處理器虛擬運(yùn)行時(shí)間記錄進(jìn)程已獲得的CPU時(shí)間紅黑樹結(jié)構(gòu)基于虛擬運(yùn)行時(shí)間排序調(diào)度周期動(dòng)態(tài)根據(jù)系統(tǒng)負(fù)載調(diào)整CFS算法示例虛擬運(yùn)行時(shí)間進(jìn)程P1:145ms虛擬運(yùn)行時(shí)間進(jìn)程P2:120ms虛擬運(yùn)行時(shí)間進(jìn)程P3:90ms調(diào)度決策選擇P3執(zhí)行（最小虛擬時(shí)間）4第十一章：多隊(duì)列調(diào)度算法多隊(duì)列設(shè)計(jì)不同類型進(jìn)程使用不同隊(duì)列隊(duì)列間調(diào)度確定各隊(duì)列服務(wù)順序與比例隊(duì)列內(nèi)調(diào)度各隊(duì)列可使用不同調(diào)度算法多隊(duì)列調(diào)度算法示例1系統(tǒng)進(jìn)程隊(duì)列FCFS算法，最高優(yōu)先級(jí)2交互進(jìn)程隊(duì)列RR算法，中等優(yōu)先級(jí)3批處理隊(duì)列SJF算法，最低優(yōu)先級(jí)第十二章：隨機(jī)調(diào)度算法隨機(jī)選擇原理以概率方式選擇下一執(zhí)行進(jìn)程彩票調(diào)度分配彩票數(shù)量代表優(yōu)先級(jí)公平性保證長(zhǎng)期運(yùn)行結(jié)果接近權(quán)重比例隨機(jī)調(diào)度算法示例P1P2P3P4第十三章：I/O調(diào)度算法磁盤特性尋道時(shí)間是主要瓶頸I/O請(qǐng)求特點(diǎn)位置隨機(jī)，需優(yōu)化訪問(wèn)順序常見(jiàn)算法FCFS、SSTF、SCAN、C-SCANSCAN算法電梯算法原理磁頭單向移動(dòng)直到盡頭再反向上升掃描磁頭從低磁道向高磁道移動(dòng)下降掃描磁頭從高磁道向低磁道移動(dòng)C-SCAN算法循環(huán)掃描原理單向服務(wù)請(qǐng)求，快速返回起點(diǎn)向上掃描處理上行路徑所有請(qǐng)求2快速返回到達(dá)最高磁道立即返回最低磁道重新掃描從最低磁道重新開始向上掃描LOOK和C-LOOK算法LOOK算法SCAN改進(jìn)版本無(wú)需掃描至磁盤兩端到達(dá)最遠(yuǎn)請(qǐng)求處即反向C-LOOK算法C-SCAN改進(jìn)版本單向掃描減少方向變化最遠(yuǎn)請(qǐng)求處直接返回不訪問(wèn)無(wú)請(qǐng)求區(qū)域第十四章：網(wǎng)絡(luò)調(diào)度算法數(shù)據(jù)包調(diào)度決定數(shù)據(jù)包發(fā)送順序帶寬分配公平分配網(wǎng)絡(luò)資源延遲控制保障實(shí)時(shí)業(yè)務(wù)服務(wù)質(zhì)量流量控制防止網(wǎng)絡(luò)擁塞加權(quán)公平排隊(duì)(WFQ)算法語(yǔ)音視頻網(wǎng)頁(yè)郵件第十五章：作業(yè)調(diào)度算法批處理特點(diǎn)一次性提交多個(gè)作業(yè)作業(yè)調(diào)度決定作業(yè)進(jìn)入系統(tǒng)順序進(jìn)程調(diào)度決定進(jìn)程獲取CPU的順序最短作業(yè)優(yōu)先(SJF)在作業(yè)調(diào)度中的應(yīng)用30%周轉(zhuǎn)時(shí)間減少相比FCFS作業(yè)調(diào)度25%吞吐量提升單位時(shí)間處理作業(yè)數(shù)量40%平均等待時(shí)間降低提高用戶滿意度第十六章：分布式系統(tǒng)調(diào)度算法負(fù)載均衡將計(jì)算任務(wù)分散到多個(gè)節(jié)點(diǎn)任務(wù)遷移在節(jié)點(diǎn)間動(dòng)態(tài)轉(zhuǎn)移工作負(fù)載資源發(fā)現(xiàn)找到可用計(jì)算資源容錯(cuò)處理節(jié)點(diǎn)失效時(shí)重新調(diào)度任務(wù)分布式調(diào)度算法示例任務(wù)分配前任務(wù)分配后第十七章：能耗感知調(diào)度算法能耗優(yōu)化目標(biāo)降低功耗同時(shí)保持性能DVFS技術(shù)動(dòng)態(tài)調(diào)整處理器電壓頻率休眠狀態(tài)管理閑置組件進(jìn)入低功耗模式熱管理避免熱點(diǎn)區(qū)域過(guò)度使用能耗感知調(diào)度算法示例性能能耗第十八章：調(diào)度算法在操作系統(tǒng)中的實(shí)現(xiàn)Linux調(diào)度器O(1)調(diào)度器完全公平調(diào)度器(CFS)實(shí)時(shí)調(diào)度器(RT)BF調(diào)度器(BFS)Windows調(diào)度器多級(jí)反饋隊(duì)列搶占式優(yōu)先級(jí)調(diào)度處理器親和性量子值動(dòng)態(tài)調(diào)整LinuxCFS調(diào)度器詳解發(fā)展歷程2.6.23內(nèi)核引入，替代O(1)調(diào)度器數(shù)據(jù)結(jié)構(gòu)紅黑樹存儲(chǔ)就緒進(jìn)程公平性實(shí)現(xiàn)虛擬運(yùn)行時(shí)間追蹤C(jī)PU使用用戶交互通過(guò)nice值設(shè)置進(jìn)程權(quán)重Windows調(diào)度器詳解優(yōu)先級(jí)分類32個(gè)優(yōu)先級(jí)級(jí)別優(yōu)先級(jí)提升I/O完成導(dǎo)致臨時(shí)提升量子值調(diào)整前臺(tái)應(yīng)用獲更多處理器時(shí)間處理器親和性線程優(yōu)先在指定CPU上運(yùn)行第十九章：調(diào)度算法性能評(píng)估模擬仿真算法模型構(gòu)建工作負(fù)載生成性能指標(biāo)收集結(jié)果統(tǒng)計(jì)分析實(shí)際系統(tǒng)測(cè)試基準(zhǔn)測(cè)試程序真實(shí)應(yīng)用場(chǎng)景性能監(jiān)控工具數(shù)據(jù)處理與可視化調(diào)度算法性能指標(biāo)對(duì)比響應(yīng)時(shí)間吞吐量公平性第二十章：調(diào)度算法優(yōu)化技術(shù)調(diào)度開銷降低減少上下文切換頻率緩存親和性優(yōu)化提高緩存命中率鎖競(jìng)爭(zhēng)減少避免共享資源爭(zhēng)用NUMA感知調(diào)度考慮內(nèi)存訪問(wèn)局部性調(diào)度算法優(yōu)化案例分析優(yōu)化前上下文切換頻繁緩存命中率低進(jìn)程頻繁遷移響應(yīng)時(shí)間不穩(wěn)定優(yōu)化策略時(shí)間片調(diào)整親和性設(shè)置優(yōu)先級(jí)調(diào)整NUMA優(yōu)化優(yōu)化后上下文切換減少40%緩存命中率提升25%吞吐量提高15%響應(yīng)時(shí)間穩(wěn)定第二十一章：新興調(diào)度算法研究機(jī)器學(xué)習(xí)調(diào)度自適應(yīng)負(fù)載預(yù)測(cè)與資源分配量子調(diào)度量子計(jì)算資源管理新模型異構(gòu)計(jì)算調(diào)度CPU/GPU協(xié)