作業系統要實現多程序，程序排程必不可少。
有人說，程序排程是作業系統中最為重要的一個部分。我覺得這種說法說得太絕對了一點，就像很多人動輒就說"某某函式比某某函式效率高XX倍"一樣，脫離了實際環境，這些結論是比較片面的。
而程序排程究竟有多重要呢？ 首先，我們需要明確一點：程序排程是對TASK_RUNNING狀態的程序進行排程（參見《linux程序狀態淺析》）。如果程序不可執行（正在睡眠或其他），那麼它跟程序排程沒多大關係。
所以，如果你的系統負載非常低，盼星星盼月亮才出現一個可執行狀態的程序。那麼程序排程也就不會太重要。哪個程序可執行，就讓它執行去，沒有什麼需要多考慮的。
反之，如果系統負載非常高，時時刻刻都有N多個程序處於可執行狀態，等待被排程執行。那麼程序排程程式為了協調這N個程序的執行，必定得做很多工作。協調得不好，系統的效能就會大打折扣。這個時候，程序排程就是非常重要的。
儘管我們平常接觸的很多計算機（如桌面系統、網路伺服器、等）負載都比較低，但是linux作為一個通用作業系統，不能假設系統負載低，必須為應付高負載下的程序排程做精心的設計。
當然，這些設計對於低負載（且沒有什麼實時性要求）的環境，沒多大用。極端情況下，如果CPU的負載始終保持0或1（永遠都只有一個程序或沒有程序需要在CPU上執行），那麼這些設計基本上都是徒勞的。
優先順序
現在的作業系統為了協調多個程序的“同時”執行，最基本的手段就是給程序定義優先順序。定義了程序的優先順序，如果有多個程序同時處於可執行狀態，那麼誰優先順序高誰就去執行，沒有什麼好糾結的了。
那麼，程序的優先順序該如何確定呢？有兩種方式：由使用者程式指定、由核心的排程程式動態調整。（下面會說到）
linux核心將程序分成兩個級別：普通程序和實時程序。實時程序的優先順序都高於普通程序，除此之外，它們的排程策略也有所不同。
實時程序的排程
實時，原本的涵義是“給定的操作一定要在確定的時間內完成”。重點並不在於操作一定要處理得多快，而是時間要可控（在最壞情況下也不能突破給定的時間）。
這樣的“實時”稱為“硬實時”，多用於很精密的系統之中（比如什麼火箭、導彈之類的）。一般來說，硬實時的系統是相對比較專用的。
像linux這樣的通用作業系統顯然沒法滿足這樣的要求，中斷處理、虛擬記憶體、等機制的存在給處理時間帶來了很大的不確定性。硬體的cache、磁碟尋道、匯流排爭用、也會帶來不確定性。
比如考慮“i++;”這麼一句C程式碼。絕大多數情況下，它執行得很快。但是極端情況下還是有這樣的可能：
1、i的記憶體空間未分配，CPU觸發缺頁異常。而linux在缺頁異常的處理程式碼中試圖分配記憶體時，又可能由於系統記憶體緊缺而分配失敗，導致程序進入睡眠；
2、程式碼執行過程中硬體產生中斷，linux進入中斷處理程式而擱置當前程序。而中斷處理程式的處理過程中又可能發生新的硬體中斷，中斷永遠巢狀不止……；
而像linux這樣號稱實現了“實時”的通用作業系統，其實只是實現了“軟實時”，即儘可能地滿足程序的實時需求。
如果一個程序有實時需求（它是一個實時程序），則只要它是可執行狀態的，核心就一直讓它執行，以儘可能地滿足它對CPU的需要，直到它完成所需要做的事情，然後睡眠或退出（變為非可執行狀態）。
而如果有多個實時程序都處於可執行狀態，則核心會先滿足優先順序最高的實時程序對CPU的需要，直到它變為非可執行狀態。
於是，只要高優先順序的實時程序一直處於可執行狀態，低優先順序的實時程序就一直不能得到CPU；只要一直有實時程序處於可執行狀態，普通程序就一直不能得到CPU。
那麼，如果多個相同優先順序的實時程序都處於可執行狀態呢？這時就有兩種排程策略可供選擇：
1、SCHED_FIFO：先進先出。直到先被執行的程序變為非可執行狀態，後來的程序才被排程執行。在這種策略下，先來的程序可以執行sched_yield系統呼叫，自願放棄CPU，以讓權給後來的程序；
2、SCHED_RR：輪轉排程。核心為實時程序分配時間片，在時間片用完時，讓下一個程序使用CPU；
強調一下，這兩種排程策略以及sched_yield系統呼叫都僅僅針對於相同優先順序的多個實時程序同時處於可執行狀態的情況。
在linux下，使用者程式可以通過sched_setscheduler系統呼叫來設定程序的排程策略以及相關排程引數；sched_setparam系統呼叫則只用於設定排程引數。這兩個系統呼叫要求使用者程序具有設定程序優先順序的能力（CAP_SYS_NICE，一般來說需要root許可權）（參閱capability相關的文章）。
通過將程序的策略設為SCHED_FIFO或SCHED_RR，使得程序變為實時程序。而程序的優先順序則是通過以上兩個系統呼叫在設定排程引數時指定的。
對於實時程序，核心不會試圖調整其優先順序。因為程序實時與否？有多實時？這些問題都是跟使用者程式的應用場景相關，只有使用者能夠回答，核心不能臆斷。
綜上所述，實時程序的排程是非常簡單的。程序的優先順序和排程策略都由使用者定死了，核心只需要總是選擇優先順序最高的實時程序來排程執行即可。唯一稍微麻煩一點的只是在選擇具有相同優先順序的實時程序時，要考慮兩種排程策略。
普通程序的排程
實時程序排程的中心思想是，讓處於可執行狀態的最高優先順序的實時程序儘可能地佔有CPU，因為它有實時需求；而普通程序則被認為是沒有實時需求的程序，於是排程程式力圖讓各個處於可執行狀態的普通程序和平共處地分享CPU，從而讓使用者覺得這些程序是同時執行的。
與實時程序相比，普通程序的排程要複雜得多。核心需要考慮兩件麻煩事：
一、動態調整程序的優先順序
按程序的行為特徵，可以將程序分為“互動式程序”和“批處理程序”：
互動式程序（如桌面程式、伺服器、等）主要的任務是與外界互動。這樣的程序應該具有較高的優先順序，它們總是睡眠等待外界的輸入。而在輸入到來，核心將其喚醒時，它們又應該很快被排程執行，以做出響應。比如一個桌面程式，如果滑鼠點選後半秒種還沒反應，使用者就會感覺系統“卡”了；
批處理程序（如編譯程式）主要的任務是做持續的運算，因而它們會持續處於可執行狀態。這樣的程序一般不需要高優先順序，比如編譯程式多運行了幾秒種，使用者多半不會太在意；
如果使用者能夠明確知道程序應該有怎樣的優先順序，可以通過nice、setpriority系統呼叫來對優先順序進行設定。（如果要提高程序的優先順序，要求使用者程序具有CAP_SYS_NICE能力。）
然而應用程式未必就像桌面程式、編譯程式這樣典型。程式的行為可能五花八門，可能一會兒像互動式程序，一會兒又像批處理程序。以致於使用者難以給它設定一個合適的優先順序。
再者，即使使用者明確知道一個程序是互動式還是批處理，也多半礙於許可權或因為偷懶而不去設定程序的優先順序。（你又是否為某個程式設定過優先順序呢？）
於是，最終，區分互動式程序和批處理程序的重任就落到了核心的排程程式上。
排程程式關注程序近一段時間內的表現（主要是檢查其睡眠時間和執行時間），根據一些經驗性的公式，判斷它現在是互動式的還是批處理的？程度如何？最後決定給它的優先順序做一定的調整。
程序的優先順序被動態調整後，就出現了兩個優先順序：
1、使用者程式設定的優先順序（如果未設定，則使用預設值），稱為靜態優先順序。這是程序優先順序的基準，在程序執行的過程中往往是不改變的；
2、優先順序動態調整後，實際生效的優先順序。這個值是可能時時刻刻都在變化的；
二、排程的公平性
在支援多程序的系統中，理想情況下，各個程序應該是根據其優先順序公平地佔有CPU。而不會出現“誰運氣好誰佔得多”這樣的不可控的情況。
linux實現公平排程基本上是兩種思路：
1、給處於可執行狀態的程序分配時間片（按照優先順序），用完時間片的程序被放到“過期佇列”中。等可執行狀態的程序都過期了，再重新分配時間片；
2、動態調整程序的優先順序。隨著程序在CPU上執行，其優先順序被不斷調低，以便其他優先順序較低的程序得到執行機會；
後一種方式有更小的排程粒度，並且將“公平性”與“動態調整優先順序”兩件事情合而為一，大大簡化了核心排程程式的程式碼。因此，這種方式也成為核心排程程式的新寵。
強調一下，以上兩點都是僅針對普通程序的。而對於實時程序，核心既不能自作多情地去動態調整優先順序，也沒有什麼公平性可言。
普通程序具體的排程演算法非常複雜，並且隨linux核心版本的演變也在不斷更替（不僅僅是簡單的調整），所以本文就不繼續深入了。
排程程式的效率
“優先順序”明確了哪個程序應該被排程執行，而排程程式還必須要關心效率問題。排程程式跟核心中的很多過程一樣會頻繁被執行，如果效率不濟就會浪費很多CPU時間，導致系統性能下降。
在linux 2.4時，可執行狀態的程序被掛在一個連結串列中。每次排程，排程程式需要掃描整個連結串列，以找出最優的那個程序來執行。複雜度為O(n)；
在linux 2.6早期，可執行狀態的程序被掛在N(N=140)個連結串列中，每一個連結串列代表一個優先順序，系統中支援多少個優先順序就有多少個連結串列。每次排程，排程程式只需要從第一個不為空的連結串列中取出位於連結串列頭的程序即可。這樣就大大提高了排程程式的效率，複雜度為O(1)；
在linux 2.6近期的版本中，可執行狀態的程序按照優先順序順序被掛在一個紅黑樹（可以想象成平衡二叉樹）中。每次排程，排程程式需要從樹中找出優先順序最高的程序。複雜度為O(logN)。
那麼，為什麼從linux 2.6早期到近期linux 2.6版本，排程程式選擇程序時的複雜度反而增加了呢？
這是因為，與此同時，排程程式對公平性的實現從上面提到的第一種思路改變為第二種思路（通過動態調整優先順序實現）。而O(1)的演算法是基於一組數目不大的連結串列來實現的，按我的理解，這使得優先順序的取值範圍很小（區分度很低），不能滿足公平性的需求。而使用紅黑樹則對優先順序的取值沒有限制（可以用32位、64位、或更多位來表示優先順序的值），並且O(logN)的複雜度也還是很高效的。
排程觸發的時機
排程的觸發主要有如下幾種情況：
1、當前程序（正在CPU上執行的程序）狀態變為非可執行狀態。
程序執行系統呼叫主動變為非可執行狀態。比如執行nanosleep進入睡眠、執行exit退出、等等；
程序請求的資源得不到滿足而被迫進入睡眠狀態。比如執行read系統呼叫時，磁碟快取記憶體裡沒有所需要的資料，從而睡眠等待磁碟IO；
程序響應訊號而變為非可執行狀態。比如響應SIGSTOP進入暫停狀態、響應SIGKILL退出、等等；
2、搶佔。程序執行時，非預期地被剝奪CPU的使用權。這又分兩種情況：程序用完了時間片、或出現了優先順序更高的程序。
優先順序更高的程序受正在CPU上執行的程序的影響而被喚醒。如傳送訊號主動喚醒，或因為釋放互斥物件（如釋放鎖）而被喚醒；
核心在響應時鐘中斷的過程中，發現當前程序的.時間片用完；
核心在響應中斷的過程中，發現優先順序更高的程序所等待的外部資源的變為可用，從而將其喚醒。比如CPU收到網絡卡中斷，核心處理該中斷，發現某個socket可讀，於是喚醒正在等待讀這個socket的程序；再比如核心在處理時鐘中斷的過程中，觸發了定時器，從而喚醒對應的正在nanosleep系統呼叫中睡眠的程序。
所有任務都採用linux分時排程策略時：
1，建立任務指定採用分時排程策略，並指定優先順序nice值(-20~19)。
2，將根據每個任務的nice值確定在cpu上的執行時間(counter)。
3，如果沒有等待資源，則將該任務加入到就緒佇列中。
4，排程程式遍歷就緒佇列中的任務，通過對每個任務動態優先順序的計算權值(counter+20-nice)結果，選擇計算結果最大的一個去執行，當這個時間片用完後(counter減至0)或者主動放棄cpu時，該任務將被放在就緒佇列末尾(時間片用完)或等待佇列(因等待資源而放棄cpu)中。
5，此時排程程式重複上面計算過程，轉到第4步。
6，當排程程式發現所有就緒任務計算所得的權值都為不大於0時，重複第2步。
所有任務都採用FIFO時：
1，建立程序時指定採用FIFO，並設定實時優先順序rt_priority(1-99)。
2，如果沒有等待資源，則將該任務加入到就緒佇列中。
3，排程程式遍歷就緒佇列，根據實時優先順序計算排程權值(1000+rt_priority),選擇權值最高的任務使用cpu，該FIFO任務將一直佔有cpu直到有優先順序更高的任務就緒(即使優先順序相同也不行)或者主動放棄(等待資源)。
4，排程程式發現有優先順序更高的任務到達(高優先順序任務可能被中斷或定時器任務喚醒，再或被當前執行的任務喚醒，等等)，則排程程式立即在當前任務堆疊中儲存當前cpu暫存器的所有資料，重新從高優先順序任務的堆疊中載入暫存器資料到cpu，此時高優先順序的任務開始執行。重複第3步。
5，如果當前任務因等待資源而主動放棄cpu使用權，則該任務將從就緒佇列中刪除，加入等待佇列，此時重複第3步。
所有任務都採用RR排程策略時：
1，建立任務時指定排程引數為RR，並設定任務的實時優先順序和nice值(nice值將會轉換為該任務的時間片的長度)。
2，如果沒有等待資源，則將該任務加入到就緒佇列中。
3，排程程式遍歷就緒佇列，根據實時優先順序計算排程權值(1000+rt_priority),選擇權值最高的任務使用cpu。
4，如果就緒佇列中的RR任務時間片為0，則會根據nice值設定該任務的時間片，同時將該任務放入就緒佇列的末尾。重複步驟3。
5，當前任務由於等待資源而主動退出cpu，則其加入等待佇列中。重複步驟3。
系統中既有分時排程，又有時間片輪轉排程和先進先出排程：
1，RR排程和FIFO排程的程序屬於實時程序，以分時排程的程序是非實時程序。
2，當實時程序準備就緒後，如果當前cpu正在執行非實時程序，則實時程序立即搶佔非實時程序。
3，RR程序和FIFO程序都採用實時優先順序做為排程的權值標準，RR是FIFO的一個延伸。FIFO時，如果兩個程序的優先順序一樣，則這兩個優先順序一樣的程序具體執行哪一個是由其在佇列中的未知決定的，這樣導致一些不公正性(優先順序是一樣的，為什麼要讓你一直執行?),如果將兩個優先順序一樣的任務的排程策略都設為RR,則保證了這兩個任務可以迴圈執行，保證了公平。
Ingo Molnar-實時補丁
為了能併入主流核心，Ingo Molnar的實時補丁也採用了非常靈活的策略，它支援四種搶佔模式：
1．No Forced Preemption (Server)，這種模式等同於沒有使能搶佔選項的標準核心，主要適用於科學計算等伺服器環境。
2．Voluntary Kernel Preemption (Desktop)，這種模式使能了自願搶佔，但仍然失效搶佔核心選項，它通過增加搶佔點縮減了搶佔延遲，因此適用於一些需要較好的響應性的環境，如桌面環境，當然這種好的響應性是以犧牲一些吞吐率為代價的。
3．Preemptible Kernel (Low-Latency Desktop)，這種模式既包含了自願搶佔，又使能了可搶佔核心選項，因此有很好的響應延遲，實際上在一定程度上已經達到了軟實時性。它主要適用於桌面和一些嵌入式系統，但是吞吐率比模式2更低。
4．Complete Preemption (Real-Time)，這種模式使能了所有實時功能，因此完全能夠滿足軟實時需求，它適用於延遲要求為100微秒或稍低的實時系統。
實現實時是以犧牲系統的吞吐率為代價的，因此實時性越好，系統吞吐率就越低。
