CPU調度
背景
-
CPU調度
- 從就緒隊列中挑選一個進程/線程作為CPU將要運行的下一個進程/線程
- 調度程序：挑選進程/線程的內核函數(shù)
- 什么時候進行調度
-
調度時機
- 進程從運行狀態(tài)切換到等待狀態(tài)
- 進程被終結了
非搶占系統(tǒng)：調度程序必須等待事件結束，當前進程主動放棄CPU時
-
可搶占系統(tǒng)
- 中斷請求被服務例程響應完成時
- 當前進程被搶占：進程時間片用完；進程從等待切換到就緒
調度準則
- CPU使用率：CPU處于忙狀態(tài)的時間百分比
- 吞吐量：單位時間內完成的進程數(shù)量
- 周轉時間：進程從初始化到結束的總時間
- 等待時間：進程在就緒隊列中的總時間
- 響應時間：從提交請求到產(chǎn)生響應所花費的總時間
調度算法
-
先來先服務（First Come First Served汁展，F(xiàn)CFS）:依據(jù)進程進入就緒狀態(tài)的先后順序排列
- 優(yōu)點：簡單
-
缺點
- 平均等待時間波動較大缠黍，短進程可能排在長進程后面
- I/O資源和CPU資源的利用率較低
-
短進程優(yōu)先算法（SPN捧挺，SJF州泊，SRT）：選擇就緒隊列中執(zhí)行時間最短進程占用CPU進入運行狀態(tài)
- 短剩余時間優(yōu)先算法（SRT）：可搶占捕捂，SPN算法的可搶占改進
-
缺點
- 可能導致饑餓励背，連續(xù)的短任務流會使長進程無法獲得CPU資源
- 需要預知未來春霍，如何預估下一個CPU計算的持續(xù)時間：詢問用戶，如果用戶欺騙就殺死相應進程
-
最高響應比優(yōu)先算法（Highest Response Ratio Next叶眉，HRRN）：選擇就緒隊列中響應比R值最高的進程舆床，R=(w+s)/s各墨，w：等待時間；s：執(zhí)行時間
- 在SPN調度的基礎上改進
- 不可搶占
- 關注進程的等待時間
- 防止無限期推遲
-
時間片輪轉算法（Round Robin，RR）：時間片結束時颊埃，按FCFS算法切換到下一個就緒進程
- 算法開銷檐涝，額外上下文切換
- 時間片太長庭猩，等待時間過長狞山，極限情況退化成FCFS
- 時間片太小，反應迅速绩郎，但產(chǎn)生大量上下文切換
- 時間片選擇目標潘鲫，維持上下文切換開銷處于1%以內
-
多級反饋隊列算法（MultiLevel Feedback Queues，MLFQ）
- 就緒隊列被劃分成獨立的隊列
- 每個隊列擁有自己的調度策略
- 調度必須在隊列間進行：固定優(yōu)先級肋杖、時間切片
- 進程可在不同隊列間移動的多級列算法
- 時間片大小隨優(yōu)先級別增加而增加
- CPU密集型進程的優(yōu)先級下降很快
- 如進程在當前的時間片沒有完成溉仑，則降到下一個優(yōu)先級
- I/O密集型進程停留在高優(yōu)先級
-
公平共享調度算法（Fair Share Scheduling，F(xiàn)SS）
- 一些用戶組比其它用戶組更重要
- 保證不重要的組無法壟斷資源
- 未使用的資源按比例分配
- 沒有達到資源使用率目標的組獲得更高的優(yōu)先級
實時調度
實時操作系統(tǒng)：正確性依賴于其實際和功能兩方面的操作系統(tǒng)
-
性能指標
- 時間約束的及時性
- 速度和平均性能相對不重要
-
特性：
- 時間約束的可預測性
強實時操作系統(tǒng)：要求在指定的時間內必須完成重要任務
弱實時操作系統(tǒng)：重要進程有高優(yōu)先級兽愤，要求盡量但非必須完成
-
速率單調調度算法（RM彼念，Rate Monntonic）
- 通過周期安排優(yōu)先級
- 周期越短優(yōu)先級越高
- 執(zhí)行周期最短的任務
-
最早截止時間優(yōu)先算法（EDF挪圾，Earliest Deadline First）
- 截止時間越早優(yōu)先級越高
- 執(zhí)行截止時間最早的任務
多處理器調度
-
多處理機調度的特征
- 多個處理機組成一個多處理機系統(tǒng)
- 處理機間可負載共享
-
對稱多處理器（SMP，Symmetric multiprocessing）調度
- 每個處理器運行自己的調度程序
- 調度程序對共享資源的訪問需要進行同步
-
靜態(tài)進程分配
- 進程從開始到結束都被分配到一個固定的處理機上執(zhí)行
- 每個處理機有自己的就緒隊列
- 調度開銷小
- 各處理機可能忙閑不均
-
動態(tài)進程分配
- 進程在執(zhí)行中可分配到任意空閑處理機執(zhí)行
- 所有處理機共享一個公共的就緒隊列
- 調度開銷大
- 各處理機的負載是均衡的
優(yōu)先級反轉
操作系統(tǒng)中出現(xiàn)高優(yōu)先級進程長時間等待低優(yōu)先級進程所占用資源的現(xiàn)象
基于優(yōu)先級的可搶占調度算法存在優(yōu)先級反置
-
優(yōu)先級繼承：占用資源的低優(yōu)先級進程繼承申請資源的高優(yōu)先級進程的優(yōu)先級
- 只在占有資源的低優(yōu)先級進程被阻塞時逐沙，才提高占用資源進程的優(yōu)先級
-
優(yōu)先級天花板協(xié)議：占用資源進程的優(yōu)先級和所有可能申請該資源的進程的最高優(yōu)先級相同
- 不管是否發(fā)生等待哲思，都提升占用資源進程的優(yōu)先級
- 優(yōu)先級高于系統(tǒng)中所有被鎖定的資源的優(yōu)先級上限，任務執(zhí)行臨界區(qū)時不會被阻塞
更多精彩吩案，關注“咋家”
