作業系統 - 學習筆記 (4) 排程
本文介紹作業系統「排程」的基礎概念,主要是在講四種演算法:FCFS、Priority Scheduling、SJF、RR,並說明各演算法延伸出的概念。
排程的四種演算法
FCFS
- 先來先做
- Convoy effect
- 很多短時間的 Process,都在等一個長時間的 Process 時,所產生的效應
Priority Scheduling
- 號碼牌 (Priority) + FCFS
- Starvation
- 解決方法:Aging
- 將等待了長時間的 Process 的優先權提高
- 解決方法:Aging
SJF
- 選擇執行當前 Process 裡 Burst Time 最小者
Non-preemptive SJF
- 不會被插隊
Preemptive SJF
- 可以插隊
- 又稱 Shortest-remaining-time-first
RR
- q + FCFS
- 公平輪流
- q 太大 - 等於 FCFS
- q 太小 - context switch 過多
Multilevel Queue
- 把 Ready Queue 分成兩種 queue
- Foreground queue
- 需交談
- I/O Bound Process
- FCFS
- Background queue
- 需批次處理
- RR
- Foreground queue
- 缺點:有些 process 可能做上面的演算法比較好,但是不能上去做
Multilevel Feedback Queue
- 允許 Process 在 queue 之間移動,是一種 Aging 技術的形式
- 比起 Multilevel Queue,可以互相連通,較靈活
硬體多工
Muti-processor
- Asymmetric multiprocessing
- 非對稱式
- 其中一個 CPU 主導排程分配
- Symmetric multiprocessing
- SMP
- 每一個 Process 自己來做 Scheduling
- 現在電腦大多都是 SMP 架構
Multicore Processors
- 多顆 CPU 封裝成一顆,比 Muti-processor 更快更省電
SMP 架構中,CPU 的溝通問題
溝通問題:NUMA
- local / remote data access 時間不一致的現象
解決方法:Process affinity
- 盡量安排所有東西都在同一個 processor 上做,盡量減少跨部門動作
- 硬性 hard affinity:強迫安排
- 軟性 soft affinity:盡量安排
結果:導致某些 CPU 閒置(idle) 或 Overload
再解決方法:Load balancing
- Push migration:Loading 太重的 processor 丟掉工作
- Pull migration:閒置的 processor 去其他 CPU 拿工作
Real-Time System
- 保證每個 process 可以被即時執行,不會有很長的等待時間,且能夠在 deadline 前完成任務
- 一般 Real-Time System 分成兩類
- Soft Real-Time System:盡量達到即時 (影片播放器)
- Hard Real-Time System:不允許延遲 (煞車系統、安全氣囊)
Real-Time Scheduling
Rate Montonic Scheduling
- 一般 Real time 中最常使用到的演算法
- 類似 SJF,Process 的週期 (Period time) 愈短者,優先權 (priority) 愈高
- 但可能會超出 deadline
Earliest Deadline First Scheduling (EDF)
- Rate Montonic Scheduling 的改善方式
- 愈接近 Deadline 的 process,給予愈高的優先權 (priority)
Proportional Share Scheduling
- 比較注重公平性
- 類似 RR 演算法
- 平均分配固定的區隔時間
- 當前總共 CPU 時間是 T,共有 N 個 process 要分享 (N<T),則每個 process 輪流做 N/T 的時間
評估最合適的演算法
Deterministic Modeling
- 每個演算法都給一個固定的工作量去做,看哪個花得時間最少
Queuing Model
- 使用 Little Formula 的統計結果來評估
Simulation
- 模擬當時的環境情況,並隨機產生數據去測試
Implementation
- 全部拿去實際操作,但非常耗時、耗資源
以上資源是我自己整理過後的筆記,若有錯誤歡迎隨時和我聯繫