前面我們花了很多天處理 Concurrency：
Race Condition
↓
Atomicity
↓
Mutex
↓
Semaphore
↓
Spinlock
↓
Deadlock
但其實一直有一個更底層的問題沒有真正處理。
假設現在系統裡有：
Thread A
Thread B
Thread C
Thread D
Thread E
...

它們全部都是：Ready
問題是，假設現在只有一顆 CPU Core，同一個瞬間不可能讓五條 Thread 都在這一顆 Core 上真正執行。
所以 OS 必須決定：下一個到底要讓誰跑？

負責做這類決策的核心機制，就是：

CPU Scheduling

1. Scheduler 到底在選什麼？Ready Queue 又是什麼？

一個 Thread 在系統裡，不會永遠都在 Running。它可能處於：
Ready
Running
Waiting / Blocked例如：

Ready
  │
  │ Scheduler 選中
  ▼
Running
  │
  ├── Time Slice 用完 ──────► Ready
  │
  └── 等待 I/O ─────────────► Waiting
                                  │
                                  │ I/O 完成
                                  ▼
                                Ready

(2)其中最容易搞混的是：Ready 和 Waiting
Ready 是「我什麼都準備好了，只差 CPU」，例如 Thread A：
程式碼 ✓
Memory ✓
需要的資料 ✓
只差 CPU

那它就是 Ready。
而這些可以執行的 Tasks 管理起來，就是Queue.

Ready Queue
┌────────┐
│Thread A│
├────────┤
│Thread B│
├────────┤
│Thread C│
└────────┘
     │
     ▼
 Scheduler
     │
     ▼
    CPU

Ready Queue 的概念是：目前有哪些可以執行、正在等待 CPU 的工作。

(3)Waiting 則是 資料還沒準備好
如果資料還沒準備好，Thread 可能需要等待 I/O。
等事件：

Disk I/O 完成
Network Packet 到達
Lock 可以取得
...

之後才重新：
Waiting
   │
   │ Event Complete
   ▼
Ready

因此 Scheduler 真正要挑選的，是：已經 Ready 的工作。

2.那到底是在排 Process 還是 Thread？

現代 OS 中，**實際被排程的執行單位往往更接近 Thread / Task。**因為同一個 Process 可以有：
Process A
│
├── Thread 1
├── Thread 2
└── Thread 3

• Thread 1 可能正在 Running。
• Thread 2 可能 Ready。
• Thread 3 可能正在等 I/O。
  所以它們的 execution state 本來就可以不同。

因此這系列後面會比較常用：Task / Thread
來理解 Scheduler 正在選擇的執行單位。

3.Scheduler 到底想做到什麼？不是「平均分 CPU」這麼簡單

CPU Scheduling 真正麻煩的地方是：**不同 Workload 想要的東西不一樣。**例如:

• 有一個互動式程式：

使用者按下按鈕
      ↓
程式處理
      ↓
畫面出現結果

我按下去之後多久有反應？這叫： Response Time

• 一個長時間計算：

開始工作
   ↓
████████████████
   ↓
工作全部完成

從工作進入系統到整個完成，一共花多久？這叫：Turnaround Time
(Turnaround Time = Completion Time - Arrival Time)

• Waiting Time 描述的是：工作在 Ready Queue 裡等 CPU，總共等了多久？

Arrival
  │
  ▼
Ready ───── 等待 ─────┐
                      ▼
                   Running

• Throughput也就是：一段時間內可以完成多少工作。
  例如：
  1 second
  ↓
  完成 100 Tasks

就比：
1 second
↓
完成 20 Tasks
有更高的 Throughput。

• CPU Utilization 也就是：CPU 有多少時間真的在做有用工作，而不是閒置。

問題來了。
這些目標不一定永遠一致，例如我們為了讓互動程式反應非常快，可能頻繁進行：Context Switch切換太頻繁會產生額外成本，所以 Scheduling 本質上是在做：
1.Responsiveness
2.Fairness
3.Throughput
4.Waiting Time
5.Turnaround Time
6.Scheduling Overhead
之間的 trade-off。

4.FCFS：最直覺的「先來先服務」，為什麼反而可能很慘？

第一個演算法叫：First-Come, First-Served（FCFS）誰先進 Ready Queue，誰先使用 CPU。
假設三個 Process 同時附近到達，Burst Time 是：
P1 = 20 ms
P2 = 3 ms
P3 = 2 ms

假設執行順序：
P1 → P2 → P3

P1：Waiting Time = 0
P2 必須等 P1：Waiting Time = 20
P3 必須等：P1 + P2 = 20 + 3 = 23

平均 Waiting Time：(0 + 20 + 23) / 3 = 14.33 ms

但是 P2 和 P3 明明分別是 3 ms、2 ms 卻因為前面有一個 20 ms 的大工作，全部卡在後面。這種現象稱為：
Convoy Effect
(2)FCFS 還有一個重要特徵：Non-preemptive，FCFS 通常是：

Non-preemptive Scheduling

• Preemptive
  → OS 可以因 Scheduling Decision 強制把 CPU 從 Running Task 手上拿回來

• Non-preemptive
  → 通常等 Running Task 結束或主動進入 Waiting 等狀態

5.SJF：短工作先跑，為什麼平均等待時間會變漂亮，卻不一定實用？

Shortest Job First（SJF）假設一樣：
P1 = 20 ms
P2 = 3 ms
P3 = 2 ms
如果都已經 Ready，SJF 會選：P3 → P2 → P1

Waiting Time：
P3 = 0
P2 = 2
P1 = 2 + 3 = 5
平均：(0 + 2 + 5) / 3 = 2.33 ms(明顯短於FCFS)

在理想化條件下，如果我們知道各工作下一段 CPU Burst 的長度，SJF 對平均 Waiting Time 有很好的性質。
但問題來了：OS 怎麼知道未來？
Scheduler 要問每個thread：你接下來會用 CPU 幾毫秒？
Thread A：我哪知道。

這就是 SJF 最大的現實問題之一，OS 通常不能準確知道：下一次 CPU Burst到底會執行多久
所以實際系統如果想利用「短工作優先」的想法，往往需要根據：過去的 CPU 使用行為。

(2)SJF 還可能造成 Starvation 假設：Long Job = 100 ms 已經在等，但短工作一直來：
2 ms
1 ms
3 ms
1 ms
2 ms
...

如果 Scheduler 永遠短的優先

那 Long Job 可能：
等
等
等
等
等
...
所以「平均 Waiting Time 看起來短」並不代表：每一個工作都受到公平待遇。