進程調度程式是多任務操作系統的基礎，它是確保進程能有效工作的一個內核子系統，負責決定哪個進程投入運行、何時運行以及運行多長時間。只有通過進程調度程式的合理調度，系統資源才能夠最大限度地發揮作用，多進程才會有併發執行的效果。在一組處於可運行狀態的進程中選擇一個來執行，是調度程式所需完成的基本工作。 在 ...
進程調度程式是多任務操作系統的基礎，它是確保進程能有效工作的一個內核子系統，負責決定哪個進程投入運行、何時運行以及運行多長時間。只有通過進程調度程式的合理調度，系統資源才能夠最大限度地發揮作用，多進程才會有併發執行的效果。在一組處於可運行狀態的進程中選擇一個來執行，是調度程式所需完成的基本工作。
在前期的 Linux 版本中，Linux 的調度程式都相當簡陋，設計近乎原始，雖然容易理解，但是在可運行進程多或者多處理器的環境下都難以勝任。在 Linux2.5 系列內核中，開始採用一種叫做 O(1) 調度程式的新調度程式，解決了先前版本 Linux 調度程式的許多不足。在 Linux2.6 版本內核開發過程中，又引入了新的進程調度演算法，其中最為出名的是 RSDL 演算法，該演算法引入了公平調度的概念，隨後演化為 CFS：完全公平調度演算法。
一、多任務操作系統
多任務操作系統就是能夠同時併發地交互執行多個進程的操作系統。可以分為兩類：非搶占式多任務系統和搶占式多任務系統。
1.1、非搶占式多任務系統：
在非搶占式多任務系統下，除非進程自己主動停止運行，否則它會一直執行下去。進程主動掛起自己的操作稱為讓步。理想情況下，進程通常會做出讓步，以便讓每個可運行進程享有足夠的處理器時間。這種機制有很多缺點：調度程式無法對每個進程該執行多長時間做出統一規定，所以進程獨占的處理器時間可能會很長；更糟的是，如果一個進程一直不作出讓步，會使系統崩潰。現在的大多數系統都採用搶占式多任務模式，除了 MAC 0S 9（及其前身）以及 Windows 3.1（及其前身）。
1.2、搶占式多任務系統：
搶占式多任務系統下，由調度程式來決定什麼時候停止一個程式的運行，以便其他進程能夠得到執行機會，這個強制的掛起動作稱為搶占。被搶占的進程仍然是處於 TASK_RUNNING 狀態的，只是暫時沒有被CPU運行。進程的搶占發生在進程處於用戶態執行階段，在內核態執行時是不能被搶占的。 Linux 是搶占式多任務系統。
二、調度策略
調度策略決定調度程式在何時讓什麼進程運行，調度策略要根據多方因素擬定，以便讓系統資源得到最大限度的利用。
2.1、I/O 消耗型和處理器消耗型進程
進程大致可以被分為 I/O 消耗型和處理器消耗型（還可以既是 I/O 消耗型也是處理器消耗型）：
I/O消耗型進程的大部分時間用來提交 I/O 請求或是等待 I/O 請求。這樣的進程經常處於可運行狀態，但通常運行時間都很短，因為它在等待更多的 I/O 請求時最後總會阻塞（這裡的 I/O 是指任何類型的可阻塞資源，如鍵盤輸入、網路I/O）。
處理器消耗型進程則是把大部分時間用在執行代碼上，除非被搶占，否則它們通常都一直不停地運行，因為它們沒有太多的 I/O 需求。對於這類進程，調度策略往往是降低它們的調度頻率，而延長其運行時間。
調度策略通常要在兩個矛盾的目標中間尋找平衡：進程響應迅速和最大系統利用率。為此，調度程式通常採用一套非常複雜的演算法來決定最值得運行的進程投入運行，但它往往並不保證低優先順序進程會被公平對待。Linux 為了保證互動式應用和桌面系統的性能，對進程的響應做了優化，更傾向於優先調用 I/O 消耗型。
2.2、進程優先順序
調度演算法中最基本的一類就是基於優先順序的調度。通常的做法是（Linux並未完全採用），優先順序高的進程先運行，低的後運行，相同優先順序的進程按輪轉方式進行調度。調度程式總是選擇時間片未用盡而優先順序最高的進程先運行。用戶和系統都可以通過設置進程的優先順序來影響系統的調度。
Linux 採用了兩種不同的優先順序範圍：
1）nice值：
nice值是所有 UNIX 系統中的標準化概念，但是不同的 UNIX 系統由於調度演算法不同，nice 值的運用方式也有所差異。 nice 值的範圍是從 -20 到 +19 ，預設值為 0；越大的 nice 值意味著更低的優先順序，相比高 nice 值（低優先順序）的進程，低 nice 值（高優先順序）的進程可以獲得更多的處理器時間。
在 Linux 系統中，nice 值代表時間片的比例。使用以下指令可以查看進程的 nice 值：
ps -eo uid,pid,nice
其中，nice 選項就是查看進程的 nice 值，在輸出結果中，NI 那一列即為進程的 nice 值。
2）實時優先順序：
實時優先順序的值是可以配置的，預設情況下它的變化範圍是從 0 到 99（包括0 和 99）。與 nice 值相反，實時優先順序值越高意味著進程優先順序越高，任何實時進程的優先順序都高於普通的進程（即實時優先順序和 nice 優先順序處於兩個互不相交的範疇）。可以使用如下指令查看進程的實時優先順序：
ps -eo uid,pid,rtprio
其中，rtprio 選項就是進程的實時優先順序，在輸出結果中， RTPRIO那一列就是。如果有進程對應列顯示為“-”，則說明該進程不是實時進程。
2.3、時間片 與 處理器使用比
在 UNIX 系統中，進程在被搶占之前能夠運行的時間是預先設置好的，被稱為時間片。時間片是一個數值，它表明進程在被搶占前所能持續運行的時間。調度策略必須規定一個預設的時間片，既不能太長，也不能太短：時間片太長，則系統交互性較差；時間片太短，則會增大進程切換帶來的處理器耗時。一般而言，系統的預設時間片很短，比如10ms。
但是，Linux 的 CFS 調度器並沒有直接分配時間片到進程，Linux 使用的是處理器使用比的方式，將處理器使用比劃分給進程，這樣一來，進程所獲得的處理器時間其實是和系統負載密切相關的。
處理器使用比受 nice 值影響，具有較高 nice 值的進程將獲得較低的處理器使用比；具有較低 nice 值的進程將獲得較高的處理器使用比。而 CFS 調度器，則會根據進程的處理器使用比來決定搶占的時機：如果消耗的使用比比當前進程小，則新進程立刻投入運行，搶占當前進程；否則，將推遲其運行。通過擯棄時間片而是分配給進程一個處理器使用比的方式，CFS 確保了進程調度中能有恆定的公平性，而將切換頻率置於不斷的變動中。
三、Linux 調度演算法
3.1、調度器類
Linux 以模塊的方式提供調度器，這樣做的目的是允許不同類型的進程可以有針對性地選擇調度演算法。這種模塊化結構被稱為調度器類，它允許多種不同的可動態添加的調度演算法並存，調度屬於自己範疇的進程。每個調度器都有一個優先順序，基礎的調度器代碼定義在 kernel/sched.c 文件中，它會按照優先順序順序遍歷調度類，擁有一個可執行進程的最高優先順序的調度器類勝出，去選擇下麵要執行的那一個程式。
在 linux 2.6.34 版本內核里，有三種調度器類：idle_sched_class、rt_sched_class 和 fail_sched_class，在最新的 linux 4.6版本里，已經增加到了五種，另外兩種是 stop_sched_class 和 dl_sched_class：
| 調度器類 | 描述 | 對應調度策略 |
| stop_sched_class | 優先順序最高的線程，會中斷所有其他線程，且不會被其他任務打斷 | 無，不需要調度普通進程 |
| dl_sched_class | 採用 EDF 最早截止時間優先演算法調度實時進程 | SCHED_DEADLINE |
| rt_sched_class | 採用提供 Roound_Robin 演算法或者 FIFO 演算法調度實時進程，具體調度策略由進程的 task_struct -> policy 指定 |
SCHED_FIFO, SCHED_RR |
| fair_sched_class | 採用 CFS 演算法調度普通的非實時進程 |
SCHED_NORMAL, SCHED_BATCH |
| idle_sched_class | 每個 CPU 的第一個pid=0線程：swapper，是一個靜態線程；一般運行在開機過程和 CPU 異常的時候做 dump | SCHED_IDLE |
可以看到，五種調度器類共有六種調度策略（即調度演算法），用於對不同類型的進程進行調度，或者支持某些特殊的功能。
鑒於筆者所看的內核版本以及能力問題，暫時就先簡單討論一下實時調度器和完全公平調度器這兩種。實際上，大部分進程也都是屬於實時調度器和完全公平調度器的：
3.2、完全公平調度
完全公平調度（CFS）是一個針對普通進程的調度類，在 Linux 中被稱為 SCHED_NORMAL（也被稱作 SCHED_OTHER），CFS 演算法實現定義在文件 kernel/sched_fair.c 中。
CFS 的出發點基於這樣一個理念：進程調度的效果應該能讓系統感覺像是具備一個理想中的完美多任務處理器。在完美多任務處理器下，每個進程將能獲得 1/n 的處理器時間（n 指的是可運行進程的數量）。同時，我們可以調度給它們無限小的時間周期，所以，在任何可測量周期內，我們給予 n 個進程中每個進程同樣多的運行時間。但是，這種模型是不現實的，首先，我們無法在一個處理器上真的同時運行多個進程，其次，每個進程的運行時間太小的話，將會增大進程切換帶來的額外消耗，這是不高效的。
CFS 的做法是允許每個進程運行一段時間、迴圈輪轉、選擇運行最少的進程作為下一個運行進程，而不是採用分配給每個進程時間片的做法；CFS 在所有可運行進程總數基礎上計算出一個進程應該運行多久，而不是依靠 nice 值來計算時間片。每個進程都按其權重在全部可運行進程中所占比例的“時間片”來運行，為了計算準確的時間片，CFS 為完美多任務中的無限小調度周期的近似值設立了一個目標，稱為“目標延遲”，目標延遲越小，則系統的交互性越好，同時也更接近完美的多任務；與之相對的，是更高的切換代價和更差的系統總吞吐能力。同時，為了避免可運行進程過多而導致每個進程所獲得的處理器使用比太小帶來的巨額切換消耗，CFS 引入了最小粒度的概念，用來表示每個進程所能獲得的時間片的底線，預設情況下，最小粒度為 1ms。
在 CFS 策略下，任何進程所獲得的處理器時間是由它自己和其他所有可運行進程 nice 值的相對差值決定的，nice 值對時間片的作用不再是算數加權，而是幾何加權。所對應的也不再是一個絕對的時間片，而是處理器的使用比。CFS 通過保證分配每個進程的處理器使用比的公平性，從而達到公平調度。當然，CFS 也不是完美的公平，而是近乎完美的多任務，但是確實在一定程度上提升了進程調度公平性。
3.3、實時調度
實時調度是針對實時進程的調度類，Linux 提供了兩種實時調度策略：SCHED_FIFO 和 SCHED_RR。
SCHED_FIFO 實現了一種簡單的、先入先出的演算法：它不使用時間片。處於可運行狀態的 SCHED_FIFO 級的進程回比任何 SCHED_NORMAL 級的進程都先得到調度。一旦一個 SCHED_FIFO 進程處於可執行狀態，它就會一直執行，知道它自己受阻塞或顯式的釋放處理器為止。它不基於時間片，可以一直執行下去。只有更高優先順序的 SCHED_FIFO 或者 SCHED_RR 任務才能搶占 SCHED_FIFO 任務。如果有兩個或更多同優先順序的 SCHED_FIFO 級進程，它們會輪流執行，但是依然只有在它們願意讓出處理器時才會退出。只要有 SCHED_FIFO 級進程在執行，其他級別較低的進程就只有等待它變為不可運行狀態後才有機會執行。
SCHED_RR 與 SCHED_FIFO 大體相同，只是 SCHED_RR 級的進程在耗盡事先分配給它的時間後就不在繼續執行了。也就是說，SCHED_RR 是帶有時間片的 SCHED_FIFO —— 這是一種實時輪流調度演算法。當 SCHED_RR 任務耗盡它的時間片時，處於同一優先順序的其他實時進程被輪流調度。時間片只用來重新調度同一優先順序的進程。對於 SCHED_FIFO 進程，高優先順序總是立即搶占低優先順序，但是低優先順序進程決不能搶占 SCHED_RR 任務，即使它的時間片耗盡。
內核版本：2.6.34
參考：https://blog.csdn.net/gatieme/article/details/51702662
參考書籍：Linux內核設計與實現（第3版）
