【CPU】CPU排程演算法(CPU scheduling algorithm) 介紹
CPU 排程演算法是作業系統中用來決定哪個程序（process）應該獲得 CPU 資源的規則。常見的 CPU 排程演算法有以下幾種：
1. 先來先服務（FCFS, First-Come, First-Served）
- 原理：按照程序到達的順序進行處理，先進來的程序先被執行。
- 優點：實現簡單，公平。
- 缺點：可能會造成「等待時間」過長，特別是在處理時間較長的程序之後，其他程序需要等很久（「長作業佔用」問題）。
2. 最短工作優先（SJF, Shortest Job First）
- 原理：選擇執行時間最短的程序優先執行。
- 優點：可以最小化平均等待時間。
- 缺點：需要預測每個程序的執行時間，難以實現，可能導致「飢餓」問題，長時間不執行較長的程序。
3. 最短剩餘時間優先（SRTF, Shortest Remaining Time First）
- 原理：類似 SJF，但這是一種搶占式（preemptive）的排程，當一個新的程序到達且它的剩餘執行時間比當前程序的剩餘時間短時，會打斷當前程序，優先執行新的程序。
- 優點：比 SJF 更能適應動態環境，能有效降低平均等待時間。
- 缺點：同樣需要預測執行時間，並且存在長作業飢餓問題。
4. 優先權排程（Priority Scheduling）
- 原理：每個程序都有一個優先級，優先級高的程序先執行。
- 優點：能夠確保高優先級的程序優先獲得資源。
- 缺點：可能導致低優先級的程序一直不被執行（飢餓問題）。可通過「老化（Aging）」技術提升長時間未執行程序的優先級來解決。
5. 輪轉法（Round Robin, RR）
- 原理：每個程序依次被分配一個固定長度的時間片來執行，時間片用完後會將 CPU 分配給下個程序，直到所有程序都執行完畢。
- 優點：能夠確保每個程序都能定期獲得 CPU 資源，適合即時系統。
- 缺點：時間片設置過長會影響響應速度，設置過短則會增加上下文切換開銷。
6. 多級佇列排程（Multilevel Queue Scheduling）
- 原理：將程序按特性（如交互式程序與批處理程序）劃分到不同的佇列中，每個佇列有自己的排程演算法。
- 優點：能有效管理不同類型的程序，分別處理。
- 缺點：佇列之間的調度和優先級管理可能較為複雜。
7. 多級反饋佇列排程（Multilevel Feedback Queue Scheduling）
- 原理：多級佇列排程的擴展，程序可以在不同優先級的佇列之間移動，通常新程序會在高優先級的佇列中執行，長時間執行後會被調到低優先級佇列。
- 優點：動態調整程序的優先級，適應性強，能夠平衡各類型程序的需求。
- 缺點：調整策略較為複雜，且上下文切換次數可能增加。
8. 最短截止時間優先（EDF, Earliest Deadline First）
- 原理：主要用於即時系統，選擇最接近截止時間的程序優先執行。
- 優點：適合即時系統中的硬性需求，能保證任務按時完成。
- 缺點：需要準確的截止時間資訊，並且在高負荷情況下難以保證所有任務按時完成。
這些排程演算法根據不同的需求和場景會有不同的應用，作業系統通常會選擇合適的排程策略來平衡效能和響應速度。
參考資料
- ChatGPT
