[作業系統概念]第三部分——CPU排程

CPU排程

• CPU排程的方案可以分為“非搶占式”排程（又稱“協作式”排程），以及“搶占式”排程。

所謂搶占，是指在稍後的時間啟動的一個程序，因為優先級或者所需資源少等原因，可以打斷目前CPU執行的程序，搶占目前程序的CPU資源（以及其他資源）歸自己所用。現代作業系統基本都是搶占式的排程，非搶占式的排程主要用于嵌入式的系統，因為非搶占式不需要特别的硬體。

CPU排程可能出現在4種情況下：

1. 一個程序從運作切換到等待
2. 一個程序從運作切換到就緒
3. 一個程序從等待切換到就緒
4. 一個程序從運作完畢，終結

如果一個排程方案隻處理程序終止、程序切換到等待兩種情況的話，則這個排程方案是“非搶占”的，否則是“搶占式”的。

CPU排程方案的評判條件

1. CPU使用率：排程方案應當是CPU盡可能不空閑
2. 吞吐量：機關時間内完成的程序數量
3. 周轉時間：指程序從送出到執行完畢的所有之間之和，包括阻塞調用的等待時間，也包括在就緒隊列中的等待時間
4. 等待時間：特指在就緒隊列中等待的時間
5. 響應時間：指從程序送出到程序産生第一響應的時間，因為有些對于有些程序，人們關心它産生響應的快慢勝過對整個程序執行耗時的多少。

CPU排程算法

1. 先到先服務排程（FCFS）：非搶占式的排程方案。按時間排序，先送出的程序先執行，一直等到程序執行結束或者因為I/O操作等阻塞操作而等待再執行下一個程序的方案。
   • 優缺點：最簡單，但是無腦，程序的平均等待時間不是最短的，而且因為是非搶占式的，對于分時系統（多使用者系統）來說很不好。

2. 最短作業優先排程（SJF）：也稱“最短下一個CPU區間”算法。可以是搶占式也可以是非搶占式，衍生的搶占SJF也被成為“最短剩餘時間優先”算法。在目前時刻，對所有已經送出的程序用時排序，按最短耗時到最長好使排序，優先執行最短耗時的程序（任務），相同耗時的按FCFS排程。

   優缺點：可以證明SJF是最好的，平均時間是最短的。但是SJF算法難在知道下一個CPU區間的長度（也就是程序的耗時）。對于批處理系統，可以将使用者指定的程序時間極限作為耗時。進而，SJF通常用于批處理系統。

3. 優先級排程算法：将程序按貼上優先級的标簽，按優先級的高低來判斷是否優先執行，相同優先級按FCFS排程。上面提到的SJF，就是一種優先級排程算法，這裡的優先級是按程序耗時的倒數計算。

   優缺點：優先級排程最大的問題是可能一個優先級第的程序長時間不能執行，導緻程序餓死，解決的辦法是“程序老化”——每經過一個時間段，将程序的優先級提高一定級别，進而避免餓死。

4. 輪轉法（RR）：相當于搶占式的FCFS算法。通過将程序放入一個循環隊列當中，劃分時間片，每過一個時間片，如果程序執行完，則執行下一個（隊列首）程序，如果沒執行完，則放入循環隊列的隊尾再次等待執行，有新程序來臨也放入隊列的隊尾。
   • 如果輪轉法的時間片設定的過長，以至于所有程序在一個時間片中都能執行完畢，那麼這就成了FCFS算法，但是如果時間片設定的過于短，每次程序切換導緻的上下文切換（堆棧資料儲存恢複，寄存器資料儲存恢複等）開銷太大，也不好。推薦是時間片最好大于80%的程序耗時。
5. 多級隊列排程：因為不同類型的程序（CPU密集型和I/O密集型，長期任務和短期任務）的特征是不同的，使用者對不同類型程序的排程要求也不同，是以幹脆，将不同類型的程序配置設定在優先級不同的隊列當中，隊列間按優先級排程，隊列内部選用合适的排程算法。
6. 多級回報隊列排程：類似與上述第5中“多級隊列排程”，但是增加了隊列之間，程序可以提升優先級或者将低優先級切換所在隊列，優化計算機的效率。

多CPU排程的問題

單核排程比較友善，多核因為涉及到協調通信問題，更加複雜。

一般将多核的排程方法分成兩大類：非對稱多處理方法和對稱多處理方法。

* 非對稱多處理方法：多個CPU的地位不對等，一般是有一個主CPU處理所有排程決定和系統程序，通路系統的資料結構，其他CPU服從主CPU的指揮和執行使用者代碼

* 對稱多處理方法：多個CPU地位對等，各自執行自己的排程方法，多個CPU之間協同通信處理。

對稱多處理方法的問題

• 處理器親和性：一個處理器對一個程序的臨時資料，緩存可能已經儲存了一遍了，如果程序下次被排程到另一個處理器上執行，這些資料需要再生成一遍，浪費資源，是以一般都要盡量保持一個程序在一個處理器上執行完。
• 負載均衡：多處理器中，可能出現幾個處理器無所事事，另幾個處理器卻忙的要死的情況。