今天要來進CPU Scheduling的介紹摟
今天去台南的武廟拜拜時，就發現有個好玩的現象。相較於每尊神明，拜到月老那一間的時候，供品就會特別多，人也比較多。然後就會看到很多小哥哥小姊姊在那邊很虔誠地念自己的理想對象清單。
我每次都在想（假設拉應該是單身者居多）：該不該直接去問「要不要認識ＸＤ」。反正都是單身的，然後現場有看到人了，就順道約吃個飯之類的，認識認識如何。
但我猜想這樣一定會被當怪人ww，警察叔叔我畢業證書還沒拿到，不要抓我
在討論CPU Scheduling前，要先來說CPU Scheduling的一些守則：
第一，CPU Utilization（CPU 利用率）：指的是CPU的忙碌程度，越忙表示使用越有效率。那我們當然是希望透過各種不同的儼萬法，讓CPU Utilization越大越好。
第二，Throughput（吞吐量）：指的是CPU單位時間內完成Process的數量。那想當然，Throughput越多，代表CPU在單位時間內可以完成的工作也越多，那就是越有效率。
第三，Waiting Time（等待時間）：指的是Process在ready queue 裡乾等的時間。Waiting Time不包含執行 CPU 的時間、I/O 的時間。是 CPU 排程演算法的主要影響範圍。
第四，Turnaround Time（周轉時間）：指的是程式提交到完成的整體時間。包含等待時間（在 ready queue）、CPU 執行時間、I/O 處理時間。Turnaround Time ＝ Completion Time - Arrival Time。那這邊可以把Response Time跟Turnaround Time做一個比較：Response Time是從「提出請求」到「開始有反應」的時間；而Turnaround Time是從「提出請求」到「整個工作完成」的時間。
而CPU做Scheduling的目的，便是從Ready Queue 中選擇一個 Process 執行。
那接下來討論的CPU Scheduling演算法，便是以「單核心系統」為基礎說明～
FCFS是作業系統中最基本、最簡單的 CPU 排程方式，採用非搶佔式（Nonpreemptive）策略，也就是一旦某個 process 獲得 CPU，就會一直跑完為止，中途不會被別人搶走。
假設我們有3個process，分別是P1 = 24 ms、P2 = 3 ms、P3 = 3 ms。如果按照FCFS順序執行 (P1, P2, P3)的話：
| P1 | P2 | P3 |
0 24 27 30
平均等待時間：(0+24+27)/3 = 17ms
那如果我們按照Process花費時間最短的來跑(P2, P3, P1)的話：
| P2 | P3 | P1 |
0 3 6 30
平均等待時間：(0+3+6)/3 = 3ms
這樣一比較就會發現：雖然 FCFS 排程方式簡單，但它最大的問題點：如果先來的 process 執行時間很長，就會讓後面的短任務全部卡住。這就是著名的： Convoy Effect（護航效應）。
那FCFS的使用場景：
第一，批次處理系統（Batch System）：當任務之間沒有太大急迫性，且重視順序公平時，FCFS 可以派上用場。
第二，不適合即時性要求高的環境：像是使用者互動、需要快速回應的系統（e.g. 多人線上遊戲、UI 系統）就不建議使用 FCFS
上述舉例到的，透過Process花費時間最短的來跑，這就是SJF。SJF有兩種變形：一種是非搶佔式 SJF(一般傳統 SJF)：一旦開始執行，就不會被打斷；另一種是搶佔式 SJF(SRTF)：有新的更短的工作進來時，會中斷目前的執行。
（對了忘記說，非搶佔式 SJF是建立在所有 Process 同時到達的前提下才能舉例）
假設我們有四個 process 都同時到達，且Burst Time 分別為：P1 = 6 ms、P2 = 8 ms、P3 = 7 ms、P4 = 3 ms。那SJF的執行順序就會是：P4 (3) → P1 (6) → P3 (7) → P2 (8)
| P4 | P1 | P3 | P2 |
0 3 9 16 24
平均等待時間 = (0 + 3 + 9 + 16) / 4 = 7.00 ms
當新來的工作「剩餘時間」更短時就搶走 CPU。看一個常見範例（到達時間不同，才能體現搶佔）：
假設process到達順序分別是：P1 (burst = 8) → P2 (burst = 4) → P3 (burst = 9) → P4 (burst = 5)
搶佔式SJF的排程（每次挑選「目前可執行中、剩餘時間最短」者）得到的連續區段：
P1: 0–1 → P2: 1–5 → P4: 5–10 → P1: 10–17 → P3: 17–26
平均等待時間 = (9 + 0 + 15 + 2) / 4 = 6.50 ms
這邊就可以下一個小結論：
比起同組合在非搶佔情境下常見的策略，搶佔式SJF往往能把平均等待時間再壓低一些，但會增加切換次數與實作複雜度。
Round-Robin（RR）是一種公平的搶佔式排程演算法，非常常見於分時系統（time-sharing system）。它的核心觀念是：每個 process 分得一段固定的時間片（Time Quantum, Q）來使用 CPU，如果在時間片內完成，就結束；如果沒完成，則被中斷並放到就緒隊列尾端，等待下一輪 CPU 分配。這樣的好處是可以讓所有 process 都「輪流」執行，避免長作業佔據 CPU 太久。
假設我們有3個process，其time quantum = 4。而3個process Burst Time 分別為：P1 = 24 ms、P2 = 3 ms、P3 = 3 ms。
| P1 | P2 | P3 | P1 | P1 | P1 | P1 | P1 | P1 |
0 4 7 10 14 18 22 26 30
平均等待時間 = (6 + 4 + 7) / 3 = 5.67 ms
平均週轉時間 = (30 + 7 + 10) / 3 = 15.67 ms
所以說，RR的優點是回復速度高與公平性高，但缺點是時間片設定困難。
假設時間片過大（Q >> 平均 Burst Time）：那RR便會會退化成FCFS。雖然上下文切換（Context Switch）開銷降低了，但整體反應時間變會變慢。
假設時間片過小（Q << 平均 Burst Time）：那Context Switch 發生頻率高，同時也代表系統花在切換上的時間變多，CPU 真正執行工作的比例下降。但優點是優點是反應時間變快（以使用著的觀點來說，辨識系統變得比較「流暢」）
Priority Scheduling 是一種根據 優先順序（Priority） 來決定 CPU 分配的排程演算法。核心概念是：作業系統每次都挑選「目前就緒隊列中優先順序最高」的 process 來執行。每個 process 都會被指定一個整數或數值的優先權，數字越小或越大代表優先級越高（取決於系統設計，通常會定義「數字越小優先級越高」）。
那我們那我們也可進一步區分Non-preemptive與Preemptive：
以Non-preemptive來說：一旦某個 process 獲得 CPU，就會持續執行到結束或阻塞，中途不會被其他更高優先順序的 process 打斷。
那以Preemptive來說：若有更高優先順序的 process 到達，就會立刻中斷目前執行中的 process，讓高優先順序的先執行。
假設以下 5 個 process 同時到達（t=0），Priority 越小代表優先級越高：
P1 (burst = 10、Priority = 3)
P2 (burst = 1、Priority = 1)
P3 (burst = 2、Priority = 4)
P4 (burst = 1、Priority = 5)
P5 (burst = 5、Priority = 2)
那排程順序便會是P2（1） → P5（2） → P1（3） → P3（4） → P4（5）
| P2 | P5 | P1 | P3 | P4 |
0 1 6 16 18 19
平均等待時間 = (0 + 1 + 6 + 16 + 18) / 5 = 8.2 ms
平均週轉時間 = (1 + 6 + 16 + 18 + 19) / 5 = 12 ms
Priority Scheduling的缺點是Starvation（飢餓問題）:如果系統持續有高優先順序的 process 進來，低優先順序的 process 可能永遠輪不到（一直被排在隊尾）。
而解法辨識Aging：
隨著等待時間增加，動態調整該 process 的優先順序（提高它的權重或降低其 priority 值），確保最終能被執行。例如：每等待 5 ms，優先權值減 1（數字越小越高）。
這邊就大致介紹幾個比較主流的Scheduling，後續我們再繼續討論Scheduling比較細節的一個部分
iThome鐵人賽
看影片追技術