本文介紹作業系統中「排程」的基礎概念，主要是在講四種演算法 FCFS、Priority Scheduling、SJF、RR，並說明各演算法延伸出的概念。
排程的四種演算法
FCFS
- 先來先做
- Convoy effect
- 很多短時間的 Process，都在等一個長時間的 Process 時，所產生的效應
Priority Scheduling
- 號碼牌 (Priority) + FCFS
- Starvation
- 解決方法：Aging → 將等待了長時間的 Process 的優先權提高
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
缺點：有些 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
全部拿去實際操作，但非常耗時、耗資源。
以上資源是我自己整理過後的筆記，若有錯誤歡迎隨時和我聯繫