linux的進程調度演算法

① linux系統中的進程調度介紹

操作系統要實現多進程，進程調度必不可少。
有人說，進程調度是操作系統中最為重要的一個部分。我覺得這種說法說得太絕對了一點，就像很多人動輒就說"某某函數比某某函數效率高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_setscheler系統調用來設置進程的調度策略以及相關調度參數;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微秒或稍低的實時系統。
實現實時是以犧牲系統的吞吐率為代價的，因此實時性越好，系統吞吐率就越低。

② 鏈変竴涓鍏鋒湁涓ら亾浣滀笟鐨勬壒澶勭悊緋葷粺錛屼綔涓氳皟搴﹂噰鐢ㄧ煭浣滀笟浼樺厛璋冨害綆楁硶錛岃繘紼嬭皟搴﹂噰鐢ㄤ互浼樺厛鏁頒負鍩虹鐨勬姠鍗犲紡

鏈棰樹腑鐨勭郴緇熸槸涓ら亾浣滀笟緋葷粺錛屽洜姝ゆ瘡嬈″彧鑳芥湁涓や釜浣滀笟榪涘叆緋葷粺錛屼綔涓氳皟搴﹂噰

鐢ㄧ煭浣滀笟浼樺厛綆楁硶錛屽彧鏈夎皟搴﹁繘鍏ョ郴緇熺殑榪涚▼鏂硅兘鍙備笌榪涚▼璋冨害錛涜繘紼嬭皟搴﹂噰鐢

鍩轟簬浼樺厛鏁扮殑鎶㈠崰寮忚皟搴︾畻娉曪紝楂樹紭鍏堢駭鐨勮繘紼嬪彲浠ユ姠鍗犵郴緇熷勭悊鏈恆

鏈棰樼殑浣滀笟鍜岃繘紼嬬殑鎺ㄨ繘榪囩▼濡備笅錛

10錛00 A浣滀笟鍒拌揪錛岃浣滀笟璋冨害紼嬪簭璋冨害榪涘叆緋葷粺錛岃榪涚▼璋冨害紼嬪簭璋冨害寮濮嬭繍琛

10錛20 A浣滀笟榪愯20鍒嗛挓錛屽墿浣20鍒嗛挓錛岀敱浜庝紭鍏堢駭浣庯紝琚榪涚▼璋冨害紼嬪簭璋冨害澶勪簬灝辯華鐘舵

B浣滀笟鍒拌揪錛岃浣滀笟璋冨害紼嬪簭璋冨害榪涘叆緋葷粺錛岀敱浜庝紭鍏堢駭楂橈紝琚榪涚▼璋冨害紼嬪簭璋冨害澶勪簬寮濮嬭繍琛岀姸鎬

10錛30 A浣滀笟絳夊緟10鍒嗛挓錛屽墿浣20鍒嗛挓錛岀戶緇絳夊緟

B浣滀笟榪愯10鍒嗛挓錛屽墿浣20鍒嗛挓錛岀戶緇榪愯

C浣滀笟鍒拌揪錛岀瓑寰呰浣滀笟璋冨害紼嬪簭璋冨害

10錛50 A浣滀笟絳夊緟30鍒嗛挓錛屽墿浣20鍒嗛挓錛岀敱浜庝紭鍏堢駭楂橈紝琚榪涚▼璋冨害紼嬪簭璋冨害澶勪簬寮濮嬭繍琛岀姸鎬

B浣滀笟榪愯30鍒嗛挓錛屼綔涓氬畬鎴愶紝緇撴潫榪愯

C浣滀笟絳夊緟20鍒嗛挓錛岀敱浜庝及璁¤繍琛屾椂闂磋緝闀匡紝浠嶆湭琚璋冨叆緋葷粺涓榪愯

D浣滀笟鍒拌揪錛岃榪涚▼璋冨害紼嬪簭璋冨害澶勪簬灝辯華鐘舵

11錛10 A浣滀笟榪愯40鍒嗛挓錛屼綔涓氬畬鎴愶紝緇撴潫榪愯

C浣滀笟絳夊緟30鍒嗛挓錛岃浣滀笟璋冨害紼嬪簭璋冨害榪涘叆緋葷粺錛岀敱浜庝紭鍏堢駭楂橈紝琚榪涚▼璋冨害紼嬪簭璋冨害澶勪簬寮濮嬭繍琛岀姸鎬

D浣滀笟絳夊緟10鍒嗛挓錛岀敱浜庝紭鍏堢駭浣庯紝琚榪涚▼璋冨害紼嬪簭璋冨害澶勪簬灝辯華鐘舵

12錛00 C浣滀笟榪愯50鍒嗛挓錛屼綔涓氬畬鎴愶紝緇撴潫榪愯

D浣滀笟絳夊緟70鍒嗛挓錛岃榪涚▼璋冨害紼嬪簭璋冨害澶勪簬寮濮嬭繍琛岀姸鎬

12錛20 D浣滀笟榪愯20鍒嗛挓錛屼綔涓氬畬鎴愶紝緇撴潫榪愯

鍚勪綔涓氬懆杞鏃墮棿涓猴細

浣滀笟A 70錛屼綔涓欱 30錛屼綔涓欳 90錛屼綔涓欴 90銆

騫沖潎浣滀笟鍛ㄨ漿鏃墮棿涓70鍒嗛挓銆

鍙傝1.緗戦〉閾炬帴

2.緗戦〉閾炬帴

鐣ユ敼鍔ㄣ