目錄
1. 基本概念
1.1 CPU-I/O執行周期
1.2 CPU排程程式（CPU scheduler）
1.3 程序狀态模型
1.4 搶占排程
1.5 排程程式（dispatcher）
1.6 排程準則
2. 排程算法
2.1 先到先服務（FCFS）
2.2 最短作業優先排程（SJF）
2.3 優先級排程
2.4 輪轉排程（RR）
2.5 多級隊列排程
2.6 多級回報隊列排程
3 線程排程
參考資料：
程序排程的目的：在程序間切換CPU，最大化CPU使用率，通過作業系統的排程使得計算機資源配置設定和使用更加高效。
1. 基本概念
1.1 CPU-I/O執行周期
程序的屬性：程序執行包括周期進行CPU執行和I/O等待。據此可以将程式分為CPU密集型程式和I/O密集型程式。
CPU密集型程式一般隻有少量長CPU執行；I/O密集型程式一般具有大量短CPU執行。
1.2 CPU排程程式（CPU scheduler）
CPU空閑時，作業系統從就緒隊列中選擇一個程序來執行，程序選擇采用短期排程程式（short-term scheduler）或CPU排程程式。
排程程式分為：短期排程程式，中期排程程式和長期排程程式。
- 短期排程程式：從準備執行的程序中選擇程序，并配置設定CPU，這裡準備執行的程序了解為記憶體中就緒的程序。
- 長期排程程式：從外部大容量儲存設備（通常為磁盤）的緩沖池中選擇程序，加載到記憶體。
- 中期排程程式：将程序從記憶體（或從CPU競争）中移出，進而降低多道程式程度（記憶體中的程序數量）。被調出的程序可被重新調入記憶體，并從中斷處繼續運作，這種方案稱為交換（swap）。通過中期排程程式，程序可換入（swap in）和換出（swap out）。
1.3 程序狀态模型
可以參考之前的博文——【作業系統——程序狀态】。
其中七狀态模型包含的情況比較全面，除了程序的建立、就緒、運作、等待、終止這五個狀态，考慮在執行虛拟記憶體管理的作業系統中，可以将暫時不用的程序（處于就緒态和等待态的程序）換出（swap out）到外部儲存設備（如硬碟）中，在适當的時間再将其換入（swap in）到記憶體中，此時引入了就緒挂起和等待挂起狀态。
1.4 搶占排程
需要CPU排程的4種情況：
- 當一個程序從運作狀态切換到等待狀态（例如I/O請求，或wait()調用）
- 當一個程序從運作狀态切換到就緒狀态（例如當出現中斷）
- 當一個程序從等待狀态切換到就緒狀态（例如I/O完成）
- 當一個程序終止。
排程方案分為兩種：（1）非搶占的（nonpreemptive）或協作的（cooperative）；（2）搶占的（preemptive）。非搶占排程下，一旦某個程序配置設定到CPU，該程序會一直使用CPU，直到它終止或切換到等待狀态。搶占排程允許第二個程序搶占第一個程序的運作，這中間可能涉及程序共享資料的一緻性問題，程序同步問題。
1.5 排程程式（dispatcher）
這個排程程式在英文原書中稱為“dispatcher”，與上面說的CPU排程程式（CPU scheduler）不同，CPU scheduler負責程序的選擇（排程），而dispatcher負責将CPU控制交給由CPU schedule（即短期排程程式）選擇的程序，CPU scheduler負責程序選擇，dispatcher實作排程過程的程序切換細節，個人感覺二者屬于上下遊關系。
dispatcher的主要功能如下：
- 切換上下文；
- 切換到使用者模式；
- 跳轉到使用者程式的合适位置，以便重新啟動程式；
排程程式停止一個程式而啟動另一個程式所需的時間稱為排程延遲（dispatch latency）。
1.6 排程準則
為了比較不同的CPU排程算法，采用一些比較準則來評價CPU排程算法的特性，具體的一些比較準則包括：
- CPU使用率；
- 吞吐量（throughput）：一個時間單元内程序完成的數量；
- 周轉時間（turnaround time）：程序從送出到程序完成的時間段；
- 等待時間：程序在就緒隊列種因等待所需的時間；
- 響應時間：程序從送出請求到産生第一響應的時間。
程序排程的理想情況是：最大化CPU使用率和吞吐量，最小化周轉時間、等待時間和響應時間。
2. 排程算法
2.1 先到先服務（FCFS）
先到先服務（First-Come First-Served，FCFS）排程算法。通過FIFO隊列實作，當一個程序進入就緒隊列中的時候，它的PCB會被連結到隊列尾部；當CPU空閑時，它會配置設定給位于隊列頭部的程序，并且這個程序從隊列中移去。
特點：
- 平均等待時間往往很長；
- 非搶占，可能導緻一個程序占用CPU時間過長；
- 會存在多個I/O程序在就緒隊列中等待CPU密集型程序的完成（其他程序都等待一個大程序釋放CPU），稱為護航效果（convoy effect），導緻CPU和裝置的使用率降低。
2.2 最短作業優先排程（SJF）
最短作業優先（Shortest-Job-First，SJF）排程算法。将每個程序與其下次CPU執行長度關聯起來，CPU空閑時會被賦給具有最短CPU執行時間（注意是下次CPU執行的時間最短而不是總的時間最短）的程序執行。另一種叫法是：最短下次CPU執行（shortest-next-CPU-burst）算法。
特點：
- SJF算法可以證明是最優的，對于給定的一組程序，SJF算法的平均等待時間最短。
- SJF算法困難在于如何确定下次CPU執行的長度。下次CPU執行通常預測為以前CPU執行的測量長度的指數平均（exponential average）。
- SJF算法可以是搶占或非搶占的。
2.3 優先級排程
優先級排程（priority-scheduling）算法為每個程序關聯一個優先級，具有最高優先級的程序會分到CPU；具有相同優先級的程序按照FCFS的順序排程。SJF算法是一個簡單的優先級算法，其優先級（p）為下次（預測的）CPU執行時間的導數。
特點：
- 優先級算法可以是搶占的或非搶占的；
- 主要問題是會導緻無窮阻塞（indefinite blocking）或饑餓（starvation）；
- 解決低優先級程序的無窮等待的方案之一：老化（aging），即逐漸增加在系統中等待時間很長的程序的優先級。
2.4 輪轉排程（RR）
輪轉（Round-Robin，RR）排程算法，類似FCFS排程，但是增加了搶占以切換程序。将一個較小的時間單元定義為時間量（time quantum）或時間片（time slice），将就緒隊列作為循環隊列，CPU排程整個就緒隊列，為每個程序配置設定不超過一個是時間片的CPU。
特點：
- RR算法的性能很大程度上取決于時間片的大小：時間片太小，頻繁的程序上下文切換耗費大量資源；時間片太大，RR退化成FCFS。一般根據經驗，80％的CPU執行應小于時間片。
2.5 多級隊列排程
多級隊列（multilevel queue）排程算法，将就緒隊列分成多個單獨的隊列，根據程序屬性（如記憶體大小、程序優先級、程序類型等），一個程序永久分到一個隊列，每個隊列有自己的排程算法。例如可有兩個隊列分别用于前台程序和背景程序，前台隊列可采用RR算法排程，背景隊列采用FCFS算法排程。
多級隊列排程算法執行個體，有五個隊列，優先級由高到低，分别為：（1）系統程序；（2）互動程序；（3）互動編輯程序；（4）批處理程序；（5）學生程序。其中每個隊列與更低層隊列相比具有絕對的優先，例如隻有系統程序、互動程序和互動編輯程序隊列都為空，批處理隊列内的程序才能運作。如果一個批處理程序運作過程中有一個互動程序進入就緒隊列，那麼該批處理程序會被搶占。
另一種可能是，在隊列之間劃分時間片，每個隊列具有一定比例的CPU時間，可用于排程隊列内的程序。例如對于前台-背景隊列例子，前台隊列可有80％的CPU時間，用于程序之間的RR排程；背景隊列可以有20％的CPU時間，用于按FCFS算法來排程程序。
2.6 多級回報隊列排程
多級回報隊列排程（multilevel feedback queue）排程算法允許程序在隊列之間遷移，其特點在于：
- 如果程序使用過多的CPU時間，其将會被放到更低的優先級隊列；
- I/O密集型和互動程序放在更高優先級隊列上；
- 在較低優先級隊列中等待過長的程序會被移到更高優先級隊列，以阻止饑餓的發生。
多級回報隊列排程程式可由下列參數定義：
- 隊列數量；
- 每個隊列的排程算法；
- 用以确定何時更新到最高優先級隊列的方法；
- 用以确定何時降級到最低優先級隊列的方法；
- 用以确定程序在需要服務時将會進入那個隊列的方法。
3 線程排程
線程可以分為使用者級（user-level）線程和核心級（kernel-level）線程。在支援線程的作業系統上，核心級線程（而不是程序）才是作業系統所排程的。這裡了解為上述的程序排程算法，其實就CPU而言，并不嚴格區分該算法究竟是用于排程程序還是用于排程線程，而是用于排程基本的排程單元，在支援線程的作業系統上，線程才是CPU排程的基本單元，此時上述排程算法此時用于線程排程。
關于使用者級線程和核心級線程：使用者級線程是由線程庫管理的，核心并不知道。使用者級線程最後運作在CPU上，映射到相應的核心級線程，這種映射不是直接的，可能采用輕量級程序（Light Weight Process，LWP），是以核心級線程和使用者級線程的排程具體實作仍有所差別。
- 程序競争範圍（Process-Contention Scope，PCS）：對于實作多對一和多對多模型的系統線程庫會調用使用者級線程，以便在可用LWP上運作。線程排程到可用LWP上并不意味着線程真實運作在一個CPU上，而是需要系統排程核心線程到實體CPU）
- 系統競争範圍（System-Contention Scope）：為了決定哪個核心線程排程到同一個處理器上，核心采用SCS競争CPU。采用一對一模型的系統如Windows、Linux和Solaris隻采用SCS排程
參考資料：
[1] Silberschatz, A., Galvin, P. B., and Gagne, G. 作業系統概念(原書第9版) (鄭扣根等譯)[M]. 機械工業出版社, 2020.