程序是作業系統虛拟出來的概念，用來組織計算機中的任務。但随着程序被賦予越來越多的任務，程序好像有了真實的生命，它從誕生就随着CPU時間執行，直到最終消失。不過，程序的生命都得到了作業系統核心的關照。就好像疲于照顧幾個孩子的母親核心必須做出決定，如何在程序間配置設定有限的計算資源，最終讓使用者獲得最佳的使用體驗。核心中安排程序執行的子產品稱為排程器（scheduler）。這裡将介紹排程器的工作方式。
排程器可以切換程序狀态（process state）。一個Linux程序從被建立到死亡，可能會經過很多種狀态，比如執行、暫停、可中斷睡眠、不可中斷睡眠、退出等。我們可以把Linux下繁多的程序狀态，歸納為三種基本狀态。
就緒（Ready）: 程序已經獲得了CPU以外的所有必要資源，如程序空間、網絡連接配接等。就緒狀态下的程序等到CPU，便可立即執行。
執行（Running）：程序獲得CPU，執行程式。
阻塞（Blocked）：當程序由于等待某個事件而無法執行時，便放棄CPU，處于阻塞狀态。
圖1 程序的基本狀态
程序建立後，就自動變成了就緒狀态。如果核心把CPU時間配置設定給該程序，那麼程序就從就緒狀态變成了執行狀态。在執行狀态下，程序執行指令，最為活躍。正在執行的程序可以主動進入阻塞狀态，比如這個程序需要将一部分硬碟中的資料讀取到記憶體中。在這段讀取時間裡，程序不需要使用CPU，可以主動進入阻塞狀态，讓出CPU。當讀取結束時，計算機硬體發出信号，程序再從阻塞狀态恢複為就緒狀态。程序也可以被迫進入阻塞狀态，比如接收到SIGSTOP信号。
排程器是CPU時間的管理者。Linux排程器需要負責做兩件事：一件事是選擇某些就緒的程序來執行；另一件事是打斷某些執行中的程序，讓它們變回就緒狀态。不過，并不是所有的排程器都有第二個功能。有的排程器的狀态切換是單向的，隻能讓就緒程序變成執行狀态，不能把正在執行中的程序變回就緒狀态。支援雙向狀态切換的排程器被稱為搶占式（pre-emptive）排程器。
排程器在讓一個程序變回就緒時，就會立即讓另一個就緒的程序開始執行。多個程序接替使用CPU，進而最大效率地利用CPU時間。當然，如果執行中程序主動進入阻塞狀态，那麼排程器也會選擇另一個就緒程序來消費CPU時間。所謂的上下文切換（context switch）就是指程序在CPU中切換執行的過程。核心承擔了上下文切換的任務，負責儲存和重建程序被切換掉之前的CPU狀态，進而讓程序感覺不到自己的執行被中斷。應用程式的開發者在編寫計算機程式時，就不用專門寫代碼處理上下文切換了。
排程器配置設定CPU時間的基本依據，就是程序的優先級。根據程式任務性質的不同，程式可以有不同的執行優先級。根據優先級特點，我們可以把程序分為兩種類别。
實時程序（Real-Time Process）：優先級高、需要盡快被執行的程序。它們一定不能被普通程序所阻擋，例如視訊播放、各種監測系統。
普通程序（Normal Process）：優先級低、更長執行時間的程序。例如文本編譯器、批處理一段文檔、圖形渲染。
普通程序根據行為的不同，還可以被分成互動程序（interactive process）和批處理程序（batch process）。互動程序的例子有圖形界面，它們可能處在長時間的等待狀态，例如等待使用者的輸入。一旦特定事件發生，互動程序需要盡快被激活。一般來說，圖形界面的反應時間是50到100毫秒。批處理程序沒有與使用者互動的，往往在背景被默默地執行。
實時程序由Linux作業系統創造，普通使用者隻能建立普通程序。兩種程序的優先級不同，實時程序的優先級永遠高于普通程序。程序的優先級是一個0到139的整數。數字越小，優先級越高。其中，優先級0到99留給實時程序，100到139留給普通程序。
一個普通程序的預設優先級是120。我們可以用指令nice來修改一個程序的預設優先級。例如有一個可執行程式叫app，執行指令：
指令中的-20指的是從預設優先級上減去20。通過這個指令執行app程式，核心會将app程序的預設優先級設定成100，也就是普通程序的最高優先級。指令中的-20可以被換成-20至19中任何一個整數，包括-20 和 19。預設優先級将會變成執行時的靜态優先級（static priority）。排程器最終使用的優先級根據的是程序的動态優先級：
動态優先級 = 靜态優先級 – Bonus + 5
如果這個公式的計算結果小于100或大于139，将會取100到139範圍内最接近計算結果的數字作為實際的動态優先級。公式中的Bonus是一個估計值，這個數字越大，代表着它可能越需要被優先執行。如果核心發現這個程序需要經常跟使用者互動，将會把Bonus值設定成大于5的數字。如果程序不經常跟使用者互動，核心将會把程序的Bonus設定成小于5的數。
下面介紹Linux的排程政策。最原始的排程政策是按照優先級排列好程序，等到一個程序運作完了再運作優先級較低的一個，但這種政策完全無法發揮多任務系統的優勢。是以，随着時間推移，作業系統的排程器也多次進化。
先來看Linux 2.4核心推出的O(n)排程器。O(n)這個名字，來源于算法複雜度的大O表示法。大O符号代表這個算法在最壞情況下的複雜度。字母n在這裡代表作業系統中的活躍程序數量。O(n)表示這個排程器的時間複雜度和活躍程序的數量成正比。
O(n)排程器把時間分成大量的微小時間片（Epoch）。在每個時間片開始的時候，排程器會檢查所有處在就緒狀态的程序。排程器計算每個程序的優先級，然後選擇優先級最高的程序來執行。一旦被排程器切換到執行，程序可以不被打擾地用盡這個時間片。如果程序沒有用盡時間片，那麼該時間片的剩餘時間會增加到下一個時間片中。
O(n)排程器在每次使用時間片前都要檢查所有就緒程序的優先級。這個檢查時間和程序中程序數目n成正比，這也正是該排程器複雜度為O(n)的原因。當計算機中有大量程序在運作時，這個排程器的性能将會被大大降低。也就是說，O(n)排程器沒有很好的可拓展性。O(n)排程器是Linux 2.6之前使用的程序排程器。當Java語言逐漸流行後，由于Java虛拟機會建立大量程序，排程器的性能問題變得更加明顯。
為了解決O(n)排程器的性能問題，O(1)排程器被發明了出來，并從Linux 2.6核心開始使用。顧名思義，O(1)排程器是指排程器每次選擇要執行的程序的時間都是1個機關的常數，和系統中的程序數量無關。這樣，就算系統中有大量的程序，排程器的性能也不會下降。O(1)排程器的創新之處在于，它會把程序按照優先級排好，放入特定的資料結構中。在選擇下一個要執行的程序時，排程器不用周遊程序，就可以直接選擇優先級最高的程序。
和O(n)排程器類似，O(1)也是把時間片配置設定給程序。優先級為120以下的程序時間片為：
(140–priority)×20毫秒
優先級120及以上的程序時間片為：
(140–priority)×5 毫秒
O(1)排程器會用兩個隊列來存放程序。一個隊列稱為活躍隊列，用于存儲那些待配置設定時間片的程序。另一個隊列稱為過期隊列，用于存儲那些已經享用過時間片的程序。O(1)排程器把時間片從活躍隊列中調出一個程序。這個程序用盡時間片，就會轉移到過期隊列。當活躍隊列的所有程序都被執行過後，排程器就會把活躍隊列和過期隊列對調，用同樣的方式繼續執行這些程序。
上面的描述沒有考慮優先級。加入優先級後，情況會變得複雜一些。作業系統會建立140個活躍隊列和過期隊列，對應優先級0到139的程序。一開始，所有程序都會放在活躍隊列中。然後作業系統會從優先級最高的活躍隊列開始依次選擇程序來執行，如果兩個程序的優先級相同，他們有相同的機率被選中。執行一次後，這個程序會被從活躍隊列中剔除。如果這個程序在這次時間片中沒有徹底完成，它會被加入優先級相同的過期隊列中。當140個活躍隊列的所有程序都被執行完後，過期隊列中将會有很多程序。排程器将對調優先級相同的活躍隊列和過期隊列繼續執行下去。過期隊列和活躍隊列，如圖2所示。
圖2 過期隊列和活躍隊列（需要替換）
我們下面看一個例子，有五個程序，如表1所示。
表1 程序
Linux作業系統中的程序隊列（run queue），如表2所示。
表2 程序隊列
那麼在一個執行周期，被選中的程序依次是先A，然後B和C，随後是D，最後是E。
注意，普通程序的執行政策并沒有保證優先級為100的程序會先被執行完進入結束狀态，再執行優先級為101的程序，而是在每個對調活躍和過期隊列的周期中都有機會被執行，這種設計是為了避免程序饑餓（starvation）。所謂的程序饑餓，就是優先級低的程序很久都沒有機會被執行。
我們看到，O(1)排程器在挑選下一個要執行的程序時很簡單，不需要周遊所有程序。但是它依然有一些缺點。程序的運作順序和時間片長度極度依賴于優先級。比如，計算優先級為100、110、120、130和139這幾個程序的時間片長度，如表3所示。
表3 程序的時間片長度
從表格中你會發現，優先級為110和120的程序的時間片長度差距比120和130之間的大了10倍。也就是說，程序時間片長度的計算存在很大的随機性。O(1)排程器會根據平均休眠時間來調整程序優先級。該排程器假設那些休眠時間長的程序是在等待使用者互動。這些互動類的程序應該獲得更高的優先級，以便給使用者更好的體驗。一旦這個假設不成立，O(1)排程器對CPU的調配就會出現問題。
從2007年釋出的Linux 2.6.23版本起，完全公平排程器（CFS，Completely Fair Scheduler）取代了O(1)排程器。CFS排程器不對程序進行任何形式的估計和猜測。這一點和O(1)區分互動和非互動程序的做法完全不同。
CFS排程器增加了一個虛拟運作時（virtual runtime）的概念。每次一個程序在CPU中被執行了一段時間，就會增加它虛拟運作時的記錄。在每次選擇要執行的程序時，不是選擇優先級最高的程序，而是選擇虛拟運作時最少的程序。完全公平排程器用一種叫紅黑樹的資料結構取代了O(1)排程器的140個隊列。紅黑樹可以高效地找到虛拟運作最小的程序。
我們先通過例子來看CFS排程器。假如一台運作的計算機中本來擁有A、B、C、D四個程序。核心記錄着每個程序的虛拟運作時，如表4所示。
表4 每個程序的虛拟運作時
系統增加一個新的程序E。新建立程序的虛拟運作時不會被設定成0，而會被設定成目前所有程序最小的虛拟運作時。這能保證該程序被較快地執行。在原來的程序中，最小虛拟運作時是程序A的1 000納秒，是以E的初始虛拟運作時會被設定為1 000納秒。新的程序清單如表5所示。
表5 新的程序清單
假如排程器需要選擇下一個執行的程序，程序A會被選中執行。程序A會執行一個排程器決定的時間片。假如程序A運作了250納秒，那它的虛拟運作時增加。而其他的程序沒有運作，是以虛拟運作時不變。在A消耗完時間片後，更新後的程序清單，如表6所示。
表6 更新後的程序清單
可以看到，程序A的排序下降到了第三位，下一個将要被執行的程序是程序E。從本質上看，虛拟運作時代表了該程序已經消耗了多少CPU時間。如果它消耗得少，那麼理應優先獲得計算資源。
按照上述的基本設計理念，CFS排程器能讓所有程序公平地使用CPU。聽起來，這讓程序的優先級變得毫無意義。CFS排程器也考慮到了這一點。CFS排程器會根據程序的優先級來計算一個時間片因子。同樣是增加250納秒的虛拟運作時，優先級低的程序實際獲得的可能隻有200納秒，而優先級高的程序實際獲得可能有300納秒。這樣，優先級高的程序就獲得了更多的計算資源。
以上就是排程器的基本原理，以及Linux用過的幾種排程政策。排程器可以更加合理地把CPU時間配置設定給程序。現代計算機都是多任務系統，排程器在多任務系統中起着頂梁柱的作用。
歡迎閱讀“騎着企鵝采樹莓”系列文章
如果你喜歡這篇文章，歡迎推薦。