linux進程調(diào)度淺析

操作系統(tǒng)要實現(xiàn)多進程，進程調(diào)度必不可少。
有人說，進程調(diào)度是操作系統(tǒng)中最為重要的一個部分。我覺得這種說法說得太絕對了一點，就像很多人動輒就說"某某函數(shù)比某某函數(shù)效率高XX倍"一樣，脫離了實際環(huán)境，這些結(jié)論是比較片面的。?

而進程調(diào)度究竟有多重要呢？ 首先，我們需要明確一點：進程調(diào)度是對TASK_RUNNING狀態(tài)的進程進行調(diào)度。如果進程不可執(zhí)行（正在睡眠或其他），那么它跟進程調(diào)度沒多大關系。
所以，如果你的系統(tǒng)負載非常低，盼星星盼月亮才出現(xiàn)一個可執(zhí)行狀態(tài)的進程。那么進程調(diào)度也就不會太重要。哪個進程可執(zhí)行，就讓它執(zhí)行去，沒有什么需要多考慮的。
反之，如果系統(tǒng)負載非常高，時時刻刻都有N多個進程處于可執(zhí)行狀態(tài)，等待被調(diào)度運行。那么進程調(diào)度程序為了協(xié)調(diào)這N個進程的執(zhí)行，必定得做很多工作。協(xié)調(diào)得不好，系統(tǒng)的性能就會大打折扣。這個時候，進程調(diào)度就是非常重要的。

盡管我們平常接觸的很多計算機（如桌面系統(tǒng)、網(wǎng)絡服務器、等）負載都比較低，但是linux作為一個通用操作系統(tǒng)，不能假設系統(tǒng)負載低，必須為應付高負載下的進程調(diào)度做精心的設計。
當然，這些設計對于低負載（且沒有什么實時性要求）的環(huán)境，沒多大用。極端情況下，如果CPU的負載始終保持0或1（永遠都只有一個進程或沒有進程需要在CPU上運行），那么這些設計基本上都是徒勞的。

優(yōu)先級
現(xiàn)在的操作系統(tǒng)為了協(xié)調(diào)多個進程的“同時”運行，最基本的手段就是給進程定義優(yōu)先級。定義了進程的優(yōu)先級，如果有多個進程同時處于可執(zhí)行狀態(tài)，那么誰優(yōu)先級高誰就去執(zhí)行，沒有什么好糾結(jié)的了。
那么，進程的優(yōu)先級該如何確定呢？有兩種方式：由用戶程序指定、由內(nèi)核的調(diào)度程序動態(tài)調(diào)整。（下面會說到）

linux內(nèi)核將進程分成兩個級別：普通進程和實時進程。實時進程的優(yōu)先級都高于普通進程，除此之外，它們的調(diào)度策略也有所不同。

實時進程的調(diào)度
實時，原本的涵義是“給定的操作一定要在確定的時間內(nèi)完成”。重點并不在于操作一定要處理得多快，而是時間要可控（在最壞情況下也不能突破給定的時間）。
這樣的“實時”稱為“硬實時”，多用于很精密的系統(tǒng)之中（比如什么火箭、導彈之類的）。一般來說，硬實時的系統(tǒng)是相對比較專用的。

像linux這樣的通用操作系統(tǒng)顯然沒法滿足這樣的要求，中斷處理、虛擬內(nèi)存、等機制的存在給處理時間帶來了很大的不確定性。硬件的cache、磁盤尋道、總線爭用、也會帶來不確定性。
比如考慮“i++;”這么一句C代碼。絕大多數(shù)情況下，它執(zhí)行得很快。但是極端情況下還是有這樣的可能：
1、i的內(nèi)存空間未分配，CPU觸發(fā)缺頁異常。而linux在缺頁異常的處理代碼中試圖分配內(nèi)存時，又可能由于系統(tǒng)內(nèi)存緊缺而分配失敗，導致進程進入睡眠；
2、代碼執(zhí)行過程中硬件產(chǎn)生中斷，linux進入中斷處理程序而擱置當前進程。而中斷處理程序的處理過程中又可能發(fā)生新的硬件中斷，中斷永遠嵌套不止……；
等等……
而像linux這樣號稱實現(xiàn)了“實時”的通用操作系統(tǒng)，其實只是實現(xiàn)了“軟實時”，即盡可能地滿足進程的實時需求。

如果一個進程有實時需求（它是一個實時進程），則只要它是可執(zhí)行狀態(tài)的，內(nèi)核就一直讓它執(zhí)行，以盡可能地滿足它對CPU的需要，直到它完成所需要做的事情，然后睡眠或退出（變?yōu)榉强蓤?zhí)行狀態(tài)）。
而如果有多個實時進程都處于可執(zhí)行狀態(tài)，則內(nèi)核會先滿足優(yōu)先級最高的實時進程對CPU的需要，直到它變?yōu)榉强蓤?zhí)行狀態(tài)。
于是，只要高優(yōu)先級的實時進程一直處于可執(zhí)行狀態(tài)，低優(yōu)先級的實時進程就一直不能得到CPU；只要一直有實時進程處于可執(zhí)行狀態(tài)，普通進程就一直不能得到CPU。
（后來，內(nèi)核添加了/proc/sys/kernel/sched_rt_runtime_us和/proc/sys/kernel/sched_rt_period_us兩個參數(shù)，限定了在以sched_rt_period_us為周期的時間內(nèi)，實時進程最多只能運行sched_rt_runtime_us這么多時間。這樣就在一直有實時進程處于可執(zhí)行狀態(tài)的情況下，給普通進程留了一點點能夠得到執(zhí)行的機會。

那么，如果多個相同優(yōu)先級的實時進程都處于可執(zhí)行狀態(tài)呢？這時就有兩種調(diào)度策略可供選擇：
1、SCHED_FIFO：先進先出。直到先被執(zhí)行的進程變?yōu)榉强蓤?zhí)行狀態(tài)，后來的進程才被調(diào)度執(zhí)行。在這種策略下，先來的進程可以執(zhí)行sched_yield系統(tǒng)調(diào)用，自愿放棄CPU，以讓權給后來的進程；
2、SCHED_RR：輪轉(zhuǎn)調(diào)度。內(nèi)核為實時進程分配時間片，在時間片用完時，讓下一個進程使用CPU；
強調(diào)一下，這兩種調(diào)度策略僅僅針對于相同優(yōu)先級的多個實時進程同時處于可執(zhí)行狀態(tài)的情況。

在linux下，用戶程序可以通過sched_setscheduler系統(tǒng)調(diào)用來設置進程的調(diào)度策略以及相關調(diào)度參數(shù)；sched_setparam系統(tǒng)調(diào)用則只用于設置調(diào)度參數(shù)。這兩個系統(tǒng)調(diào)用要求用戶進程具有設置進程優(yōu)先級的能力（CAP_SYS_NICE，一般來說需要root權限）。
通過將進程的策略設為SCHED_FIFO或SCHED_RR，使得進程變?yōu)閷崟r進程。而進程的優(yōu)先級則是通過以上兩個系統(tǒng)調(diào)用在設置調(diào)度參數(shù)時指定的。

對于實時進程，內(nèi)核不會試圖調(diào)整其優(yōu)先級。因為進程實時與否？有多實時？這些問題都是跟用戶程序的應用場景相關，只有用戶能夠回答，內(nèi)核不能臆斷。

綜上所述，實時進程的調(diào)度是非常簡單的。進程的優(yōu)先級和調(diào)度策略都由用戶定死了，內(nèi)核只需要總是選擇優(yōu)先級最高的實時進程來調(diào)度執(zhí)行即可。唯一稍微麻煩一點的只是在選擇具有相同優(yōu)先級的實時進程時，要考慮兩種調(diào)度策略。

普通進程的調(diào)度
實時進程調(diào)度的中心思想是，讓處于可執(zhí)行狀態(tài)的最高優(yōu)先級的實時進程盡可能地占有CPU，因為它有實時需求；而普通進程則被認為是沒有實時需求的進程，于是調(diào)度程序力圖讓各個處于可執(zhí)行狀態(tài)的普通進程和平共處地分享CPU，從而讓用戶覺得這些進程是同時運行的。
與實時進程相比，普通進程的調(diào)度要復雜得多。內(nèi)核需要考慮兩件麻煩事：

一、動態(tài)調(diào)整進程的優(yōu)先級
按進程的行為特征，可以將進程分為“交互式進程”和“批處理進程”：
交互式進程（如桌面程序、服務器、等）主要的任務是與外界交互。這樣的進程應該具有較高的優(yōu)先級，它們總是睡眠等待外界的輸入。而在輸入到來，內(nèi)核將其喚醒時，它們又應該很快被調(diào)度執(zhí)行，以做出響應。比如一個桌面程序，如果鼠標點擊后半秒種還沒反應，用戶就會感覺系統(tǒng)“卡”了；
批處理進程（如編譯程序）主要的任務是做持續(xù)的運算，因而它們會持續(xù)處于可執(zhí)行狀態(tài)。這樣的進程一般不需要高優(yōu)先級，比如編譯程序多運行了幾秒種，用戶多半不會太在意；

如果用戶能夠明確知道進程應該有怎樣的優(yōu)先級，可以通過nice、setpriority系統(tǒng)調(diào)用來對優(yōu)先級進行設置。（如果要提高進程的優(yōu)先級，要求用戶進程具有CAP_SYS_NICE能力。）
然而應用程序未必就像桌面程序、編譯程序這樣典型。程序的行為可能五花八門，可能一會兒像交互式進程，一會兒又像批處理進程。以致于用戶難以給它設置一個合適的優(yōu)先級。
再者，即使用戶明確知道一個進程是交互式還是批處理，也多半礙于權限或因為偷懶而不去設置進程的優(yōu)先級。（你又是否為某個程序設置過優(yōu)先級呢？）
于是，最終，區(qū)分交互式進程和批處理進程的重任就落到了內(nèi)核的調(diào)度程序上。

調(diào)度程序關注進程近一段時間內(nèi)的表現(xiàn)（主要是檢查其睡眠時間和運行時間），根據(jù)一些經(jīng)驗性的公式，判斷它現(xiàn)在是交互式的還是批處理的？程度如何？最后決定給它的優(yōu)先級做一定的調(diào)整。
進程的優(yōu)先級被動態(tài)調(diào)整后，就出現(xiàn)了兩個優(yōu)先級：
1、用戶程序設置的優(yōu)先級（如果未設置，則使用默認值），稱為靜態(tài)優(yōu)先級。這是進程優(yōu)先級的基準，在進程執(zhí)行的過程中往往是不改變的；
2、優(yōu)先級動態(tài)調(diào)整后，實際生效的優(yōu)先級。這個值是可能時時刻刻都在變化的；

二、調(diào)度的公平性
在支持多進程的系統(tǒng)中，理想情況下，各個進程應該是根據(jù)其優(yōu)先級公平地占有CPU。而不會出現(xiàn)“誰運氣好誰占得多”這樣的不可控的情況。
linux實現(xiàn)公平調(diào)度基本上是兩種思路：
1、給處于可執(zhí)行狀態(tài)的進程分配時間片（按照優(yōu)先級），用完時間片的進程被放到“過期隊列”中。等可執(zhí)行狀態(tài)的進程都過期了，再重新分配時間片；
2、動態(tài)調(diào)整進程的優(yōu)先級。隨著進程在CPU上運行，其優(yōu)先級被不斷調(diào)低，以便其他優(yōu)先級較低的進程得到運行機會；
后一種方式有更小的調(diào)度粒度，并且將“公平性”與“動態(tài)調(diào)整優(yōu)先級”兩件事情合而為一，大大簡化了內(nèi)核調(diào)度程序的代碼。因此，這種方式也成為內(nèi)核調(diào)度程序的新寵。

強調(diào)一下，以上兩點都是僅針對普通進程的。而對于實時進程，內(nèi)核既不能自作多情地去動態(tài)調(diào)整優(yōu)先級，也沒有什么公平性可言。

普通進程具體的調(diào)度算法非常復雜，并且隨linux內(nèi)核版本的演變也在不斷更替（不僅僅是簡單的調(diào)整），所以本文就不繼續(xù)深入了。有興趣的朋友可以參考下面的鏈接：
《Linux 調(diào)度器發(fā)展簡述》
《鼠眼看Linux調(diào)度器》
《鼠眼再看Linux調(diào)度器［1］》
《鼠眼再看Linux調(diào)度器［2］》

調(diào)度程序的效率
“優(yōu)先級”明確了哪個進程應該被調(diào)度執(zhí)行，而調(diào)度程序還必須要關心效率問題。調(diào)度程序跟內(nèi)核中的很多過程一樣會頻繁被執(zhí)行，如果效率不濟就會浪費很多CPU時間，導致系統(tǒng)性能下降。
在linux 2.4時，可執(zhí)行狀態(tài)的進程被掛在一個鏈表中。每次調(diào)度，調(diào)度程序需要掃描整個鏈表，以找出最優(yōu)的那個進程來運行。復雜度為O(n)；
在linux 2.6早期，可執(zhí)行狀態(tài)的進程被掛在N(N=140)個鏈表中，每一個鏈表代表一個優(yōu)先級，系統(tǒng)中支持多少個優(yōu)先級就有多少個鏈表。每次調(diào)度，調(diào)度程序只需要從第一個不為空的鏈表中取出位于鏈表頭的進程即可。這樣就大大提高了調(diào)度程序的效率，復雜度為O(1)；
在linux 2.6近期的版本中，可執(zhí)行狀態(tài)的進程按照優(yōu)先級順序被掛在一個紅黑樹（可以想象成平衡二叉樹）中。每次調(diào)度，調(diào)度程序需要從樹中找出優(yōu)先級最高的進程。復雜度為O(logN)。

那么，為什么從linux 2.6早期到近期linux 2.6版本，調(diào)度程序選擇進程時的復雜度反而增加了呢？
這是因為，與此同時，調(diào)度程序?qū)叫缘膶崿F(xiàn)從上面提到的第一種思路改變?yōu)榈诙N思路（通過動態(tài)調(diào)整優(yōu)先級實現(xiàn)）。而O(1)的算法是基于一組數(shù)目不大的鏈表來實現(xiàn)的，按我的理解，這使得優(yōu)先級的取值范圍很小（區(qū)分度很低），不能滿足公平性的需求。而使用紅黑樹則對優(yōu)先級的取值沒有限制（可以用32位、64位、或更多位來表示優(yōu)先級的值），并且O(logN)的復雜度也還是很高效的。

調(diào)度觸發(fā)的時機
調(diào)度的觸發(fā)主要有如下幾種情況：
1、當前進程（正在CPU上運行的進程）狀態(tài)變?yōu)榉强蓤?zhí)行狀態(tài)。
進程執(zhí)行系統(tǒng)調(diào)用主動變?yōu)榉强蓤?zhí)行狀態(tài)。比如執(zhí)行nanosleep進入睡眠、執(zhí)行exit退出、等等；
進程請求的資源得不到滿足而被迫進入睡眠狀態(tài)。比如執(zhí)行read系統(tǒng)調(diào)用時，磁盤高速緩存里沒有所需要的數(shù)據(jù)，從而睡眠等待磁盤IO；
進程響應信號而變?yōu)榉强蓤?zhí)行狀態(tài)。比如響應SIGSTOP進入暫停狀態(tài)、響應SIGKILL退出、等等；

2、搶占。進程運行時，非預期地被剝奪CPU的使用權。這又分兩種情況：進程用完了時間片、或出現(xiàn)了優(yōu)先級更高的進程。
優(yōu)先級更高的進程受正在CPU上運行的進程的影響而被喚醒。如發(fā)送信號主動喚醒，或因為釋放互斥對象（如釋放鎖）而被喚醒；
內(nèi)核在響應時鐘中斷的過程中，發(fā)現(xiàn)當前進程的時間片用完；
內(nèi)核在響應中斷的過程中，發(fā)現(xiàn)優(yōu)先級更高的進程所等待的外部資源的變?yōu)榭捎?，從而將其喚醒。比如CPU收到網(wǎng)卡中斷，內(nèi)核處理該中斷，發(fā)現(xiàn)某個socket可讀，于是喚醒正在等待讀這個socket的進程；再比如內(nèi)核在處理時鐘中斷的過程中，觸發(fā)了定時器，從而喚醒對應的正在nanosleep系統(tǒng)調(diào)用中睡眠的進程；

其他問題
1、內(nèi)核搶占
理想情況下，只要滿足“出現(xiàn)了優(yōu)先級更高的進程”這個條件，當前進程就應該被立刻搶占。但是，就像多線程程序需要用鎖來保護臨界區(qū)資源一樣，內(nèi)核中也存在很多這樣的臨界區(qū)，不大可能隨時隨地都能接收搶占。
linux 2.4時的設計就非常簡單，內(nèi)核不支持搶占。進程運行在內(nèi)核態(tài)時（比如正在執(zhí)行系統(tǒng)調(diào)用、正處于異常處理函數(shù)中），是不允許搶占的。必須等到返回用戶態(tài)時才會觸發(fā)調(diào)度（確切的說，是在返回用戶態(tài)之前，內(nèi)核會專門檢查一下是否需要調(diào)度）；
linux 2.6則實現(xiàn)了內(nèi)核搶占，但是在很多地方還是為了保護臨界區(qū)資源而需要臨時性的禁用內(nèi)核搶占。

也有一些地方是出于效率考慮而禁用搶占，比較典型的是spin_lock。spin_lock是這樣一種鎖，如果請求加鎖得不到滿足（鎖已被別的進程占有），則當前進程在一個死循環(huán)中不斷檢測鎖的狀態(tài)，直到鎖被釋放。
為什么要這樣忙等待呢？因為臨界區(qū)很小，比如只保護“i+=j++;”這么一句。如果因為加鎖失敗而形成“睡眠-喚醒”這么個過程，就有些得不償失了。
那么既然當前進程忙等待（不睡眠），誰又來釋放鎖呢？其實已得到鎖的進程是運行在另一個CPU上的，并且是禁用了內(nèi)核搶占的。這個進程不會被其他進程搶占，所以等待鎖的進程只有可能運行在別的CPU上。（如果只有一個CPU呢？那么就不可能存在等待鎖的進程了。）
而如果不禁用內(nèi)核搶占呢？那么得到鎖的進程將可能被搶占，于是可能很久都不會釋放鎖。于是，等待鎖的進程可能就不知何年何月得償所望了。

對于一些實時性要求更高的系統(tǒng)，則不能容忍spin_lock這樣的東西。寧可改用更費勁的“睡眠-喚醒”過程，也不能因為禁用搶占而讓更高優(yōu)先級的進程等待。比如，嵌入式實時linux montavista就是這么干的。
由此可見，實時并不代表高效。很多時候為了實現(xiàn)“實時”，還是需要對性能做一定讓步的。

2、多處理器下的負載均衡
前面我們并沒有專門討論多處理器對調(diào)度程序的影響，其實也沒有什么特別的，就是在同一時刻能有多個進程并行地運行而已。那么，為什么會有“多處理器負載均衡”這個事情呢？
如果系統(tǒng)中只有一個可執(zhí)行隊列，哪個CPU空閑了就去隊列中找一個最合適的進程來執(zhí)行。這樣不是很好很均衡嗎？
的確如此，但是多處理器共用一個可執(zhí)行隊列會有一些問題。顯然，每個CPU在執(zhí)行調(diào)度程序時都需要把隊列鎖起來，這會使得調(diào)度程序難以并行，可能導致系統(tǒng)性能下降。而如果每個CPU對應一個可執(zhí)行隊列則不存在這樣的問題。
另外，多個可執(zhí)行隊列還有一個好處。這使得一個進程在一段時間內(nèi)總是在同一個CPU上執(zhí)行，那么很可能這個CPU的各級cache中都緩存著這個進程的數(shù)據(jù)，很有利于系統(tǒng)性能的提升。
所以，在linux下，每個CPU都有著對應的可執(zhí)行隊列，而一個可執(zhí)行狀態(tài)的進程在同一時刻只能處于一個可執(zhí)行隊列中。

于是，“多處理器負載均衡”這個麻煩事情就來了。內(nèi)核需要關注各個CPU可執(zhí)行隊列中的進程數(shù)目，在數(shù)目不均衡時做出適當調(diào)整。什么時候需要調(diào)整，以多大力度進程調(diào)整，這些都是內(nèi)核需要關心的。當然，盡量不要調(diào)整最好，畢竟調(diào)整起來又要耗CPU、又要鎖可執(zhí)行隊列，代價還是不小的。
另外，內(nèi)核還得關心各個CPU的關系。兩個CPU之間，可能是相互獨立的、可能是共享cache的、甚至可能是由同一個物理CPU通過超線程技術虛擬出來的……CPU之間的關系也是實現(xiàn)負載均衡的重要依據(jù)。關系越緊密，進程在它們之間遷移的代價就越小。

3、優(yōu)先級繼承
由于互斥，一個進程（設為A）可能因為等待進入臨界區(qū)而睡眠。直到正在占有相應資源的進程（設為B）退出臨界區(qū)，進程A才被喚醒。
可能存在這樣的情況：A的優(yōu)先級非常高，B的優(yōu)先級非常低。B進入了臨界區(qū)，但是卻被其他優(yōu)先級較高的進程（設為C）搶占了，而得不到運行，也就無法退出臨界區(qū)。于是A也就無法被喚醒。
A有著很高的優(yōu)先級，但是現(xiàn)在卻淪落到跟B一起，被優(yōu)先級并不太高的C搶占，導致執(zhí)行被推遲。這種現(xiàn)象就叫做優(yōu)先級反轉(zhuǎn)。

出現(xiàn)這種現(xiàn)象是很不合理的。較好的應對措施是：當A開始等待B退出臨界區(qū)時，B臨時得到A的優(yōu)先級（還是假設A的優(yōu)先級高于B），以便順利完成處理過程，退出臨界區(qū)。之后B的優(yōu)先級恢復。這就是優(yōu)先級繼承的方法。
為了實現(xiàn)優(yōu)先級繼承，內(nèi)核又得做很多事情。更細節(jié)的東西可以參考一下關于“優(yōu)先級反轉(zhuǎn)”或“優(yōu)先級繼承”的文章。

4、中斷處理線程化
在linux下，中斷處理程序運行于一個不可調(diào)度的上下文中。從CPU響應硬件中斷自動跳轉(zhuǎn)到內(nèi)核設定的中斷處理程序去執(zhí)行，到中斷處理程序退出，整個過程是不能被搶占的。
一個進程如果被搶占了，可以通過保存在它的進程控制塊（task_struct）中的信息，在之后的某個時間恢復它的運行。而中斷上下文則沒有task_struct，被搶占了就沒法恢復了。
中斷處理程序不能被搶占，也就意味著中斷處理程序的“優(yōu)先級”比任何進程都高（必須等中斷處理程序完成了，進程才能被執(zhí)行）。但是在實際的應用場景中，可能某些實時進程應該得到比中斷處理程序更高的優(yōu)先級。
于是，一些實時性要求更高的系統(tǒng)就給中斷處理程序賦予了task_struct以及優(yōu)先級，使得它們在必要的時候能夠被高優(yōu)先級的進程搶占。但是顯然，做這些工作是會給系統(tǒng)造成一定開銷的，這也是為了實現(xiàn)“實時”而對性能做出的一種讓步。
更多細節(jié)可以參考一下關于“中斷線程化”的文章。