CPU 調度與排程策略（CPU Scheduling）

目標：理解程式的排程策略，如何讓多個應用程式同時執行

CPU 調度是作業系統分配 CPU 資源的關鍵任務，確保多個應用程式能有效率地共享處理能力。當多個程式同時運行時，CPU 需要一種策略來決定誰先使用資源，誰後執行，避免資源浪費與系統過載。

CPU Scheduling Criteria（CPU 調度準則）

CPU Scheduling in Operating Systems

CPU Scheduling Criteria（CPU 調度準則）

排程的好壞取決於一些重要的指標，類似於排隊系統中的等待與服務時間：

1. 到達時間（Arrival Time）：
2. • 程式進入等待執行隊列的時間點，越早到達的程式通常越早被考慮執行。
2. 完成時間 (Completion Time)：
3. • 程式完全執行結束的時間點，反映了程式在系統中的生命週期。
3. 執行時間(Burst Time)：程式運作開始的時間點。
4. 等待時間 (Waiting Time)：
5. • 程式在等待隊列中等待執行的時間，公式： Waiting Time = Turn Around Time  –  Burst Time
5. 周轉時間 (Turnaround Time)：
6. • 程式從到達到完成所經歷的總時間，公式： Turn Around Time = Completion Time  –  Arrival Time

CPU Scheduling（Preemptive & Non-Preemptive）

1. Non-Preemptive (非搶占式排程)

• 一旦 CPU 分配給某個程式，該程式必須執行完成後才能釋放資源。
• 比喻： 像舉辦單場比賽，選手一上場就要比賽到結束，中間不會有人插隊。

2. Preemptive (搶占式排程)

• 當有更高優先級的程式到達時，CPU 可以中斷當前執行的程式，將資源重新分配。
• 比喻： 像音樂椅遊戲，當新的玩家到場時，原本坐在椅子上的人可能會被擠下去。

八種常見的 CPU 排程策略

1. 先來先服務 (First-Come, First-Served, FCFS)
2. • 到得早的程式先執行。
   • 比喻： 排隊買票，先排到的人先買到。
2. 短作業優先 (Shortest Job Next, SJN)
3. • 執行時間最短的程式先執行。
   • 比喻： 點菜時先做簡單的菜，節省等待時間。
3. 最短剩餘時間優先 (Shortest Remaining Time, SRT)
4. • 執行時間最短、剩餘時間少的程式優先，中途可能搶占。
   • 比喻： 快做好的菜優先端給顧客。
4. 優先權排程 (Priority Scheduling)
5. • 優先級最高的程式先執行。
   • 比喻： 急診室中的危重病人先治療。
5. 輪轉法 (Round Robin, RR)
6. • 每個程式輪流執行固定時間片。
   • 比喻： 籃球比賽輪流上場，每隊有固定的上場時間。
6. 多層隊列排程 (Multilevel Queue Scheduling)
7. • 根據不同類型的程式分配到不同的隊列，先處理高優先級的隊列。
   • 比喻： 機場安檢，頭等艙旅客有專屬快速通道。
7. 多層回饋隊列排程 (Multilevel Feedback Queue Scheduling)
8. • 類似多層隊列，但允許程式在不同隊列間移動，根據其執行情況調整優先級。
   • 比喻： 根據學生的學習進度調整補習班的課程安排。
8. 最短期限優先 (Earliest Deadline First, EDF)
9. • 最接近截止時間的程式優先執行，常用於即時系統。
   • 比喻： 考試日期越近的功課優先完成。

結論：選擇適合的排程策略

不同的 CPU 調度策略適用於不同的情境。對於即時系統，需要快速響應的排程方式；而對於批次處理系統，則可以選擇非搶占式策略來最大化資源使用率。理解這些策略有助於設計更高效的作業系統和應用程式。