Linux 進程調度淺析

概述

操作系統要實現多進程，進程調度必不可少。有人說，進程調度是操作系統中最為重要的1個部份。我覺得這類說法說得太絕對了1點，就像很多人動輒就說“某某函數比某某函數效力高XX倍”1樣，脫離了實際環境，這些結論是比較片面的。 

而進程調度究竟有多重要呢？ 首先，我們需要明確1點：進程調度是對 TASK_RUNNING 狀態的進程進行調度。如果進程不可履行（正在睡眠或其他），那末它跟進程調度沒多大關系。所以，如果你的系統負載非常低，盼星星盼月亮才出現1個可履行狀態的進程。那末進程調度也就不會太重要。哪一個進程可履行，就讓它履行去，沒有甚么需要多斟酌的。反之，如果系統負載非常高，時時刻刻都有 N 多個進程處于可履行狀態，等待被調度運行。那末進程調度程序為了調和這 N 個進程的履行，一定得做很多工作。調和得不好，系統的性能就會大打折扣。這個時候，進程調度就是非常重要的。

雖然我們平常接觸的很多計算機（如桌面系統、網絡服務器、等）負載都比較低，但是 linux 作為1個通用操作系統，不能假定系統負載低，必須為應付高負載下的進程調度做精心的設計。固然，這些設計對低負載（且沒有甚么實時性要求）的環境，沒多大用。極端情況下，如果 CPU 的負載始終保持 0 或 1（永久都只有1個進程或沒有進程需要在 CPU 上運行），那末這些設計基本上都是徒勞的。

優先級

那末，進程的優先級該如何肯定呢？有兩種方式：由用戶程序指定、由內核的調度程序動態調劑。（下面會說到）


linux 內核將進程分成兩個級別：普通進程和實時進程。實時進程的優先級都高于普通進程，除此以外，它們的調度策略也有所不同。

實時進程的調度

比如斟酌“i++;”這么1句 C 代碼。絕大多數情況下，它履行得很快。但是極端情況下還是有這樣的可能：
1、i 的內存空間未分配，CPU 觸發缺頁異常。而 linux 在缺頁異常的處理代碼中試圖分配內存時，又可能由于系統內存緊缺而分配失敗，致使進程進入眠眠；
2、代碼履行進程中硬件產生中斷，linux 進入中斷處理程序而擱置當前進程。而中斷處理程序的處理進程中又可能產生新的硬件中斷，中斷永久嵌套不止……；
等等……

而像 linux 這樣號稱實現了“實時”的通用操作系統，其實只是實現了“軟實時”，即盡量地滿足進程的實時需求。


如果1個進程有實時需求（它是1個實時進程），則只要它是可履行狀態的，內核就1直讓它履行，以盡量地滿足它對 CPU 的需要，直到它完成所需要做的事情，然后睡眠或退出（變成非可履行狀態）。而如果有多個實時進程都處于可履行狀態，則內核會先滿足優先級最高的實時進程對 CPU 的需要，直到它變成非可履行狀態。

因而，只要高優先級的實時進程1直處于可履行狀態，低優先級的實時進程就1直不能得到 CPU；只要1直有實時進程處于可履行狀態，普通進程就1直不能得到 CPU。
（后來，內核添加了 /proc/sys/kernel/sched_rt_runtime_us和 /proc/sys/kernel/sched_rt_period_us 兩個參數，限定了在以 sched_rt_period_us 為周期的時間內，實時進程最多只能運行 sched_rt_runtime_us 這么多時間。這樣就在1直有實時進程處于可履行狀態的情況下，給普通進程留了1點點能夠得到履行的機會。


那末，如果多個相同優先級的實時進程都處于可履行狀態呢？這時候就有兩種調度策略可供選擇：
1、SCHED_FIFO：先進先出。直到先被履行的進程變成非可履行狀態，后來的進程才被調度履行。在這類策略下，先來的進程可以履行 sched_yield 系統調用，自愿放棄CPU，以讓權給后來的進程；
2、SCHED_RR：輪轉調度。內核為實時進程分配時間片，在時間片用完時，讓下1個進程使用 CPU；

強調1下，這兩種調度策略僅僅針對相同優先級的多個實時進程同時處于可履行狀態的情況。


在 linux 下，用戶程序可以通過 sched_setscheduler 系統調用來設置進程的調度策略和相干調度參數；sched_setparam 系統調用則只用于設置調度參數。這兩個系統調用要求用戶進程具有設置進程優先級的能力（CAP_SYS_NICE，1般來講需要 root 權限）。

通過將進程的策略設為 SCHED_FIFO 或 SCHED_RR，使得進程變成實時進程。而進程的優先級則是通過以上兩個系統調用在設置調度參數時指定的。


對實時進程，內核不會試圖調劑其優先級。由于進程實時與否？有多實時？這些問題都是跟用戶程序的利用場景相干，只有用戶能夠回答，內核不能臆斷。


綜上所述，實時進程的調度是非常簡單的。進程的優先級和調度策略都由用戶定死了，內核只需要總是選擇優先級最高的實時進程來調度履行便可。唯1略微麻煩1點的只是在選擇具有相同優先級的實時進程時，要斟酌兩種調度策略。

普通進程的調度

與實時進程相比，普通進程的調度要復雜很多。內核需要斟酌兩件麻煩事：


1、動態調劑進程的優先級
按進程的行動特點，可以將進程分為“交互式進程”和“批處理進程”：
交互式進程（如桌面程序、服務器、等）主要的任務是與外界交互。這樣的進程應當具有較高的優先級，它們總是睡眠等待外界的輸入。而在輸入到來，內核將其喚醒時，它們又應當很快被調度履行，以做出響應。比如1個桌面程序，如果鼠標點擊后半秒種還沒反應，用戶就會感覺系統“卡”了；
批處理進程（如編譯程序）主要的任務是做延續的運算，因此它們會延續處于可履行狀態。這樣的進程1般不需要高優先級，比如編譯程序多運行了幾秒種，用戶多半不會太在乎；


如果用戶能夠明確知道進程應當有怎樣的優先級，可以通過 nice、setpriority 系統調用來對優先級進行設置。（如果要提高進程的優先級，要求用戶進程具有 CAP_SYS_NICE 能力。）

但是利用程序未必就像桌面程序、編譯程序這樣典型。程序的行動可能5花8門，可能1會兒像交互式進程，1會兒又像批處理進程。以致于用戶難以給它設置1個適合的優先級。再者，即便用戶明確知道1個進程是交互式還是批處理，也多半礙于權限或由于偷懶而不去設置進程的優先級。（你又是不是為某個程序設置過優先級呢？）因而，終究，辨別交互式進程和批處理進程的重擔就落到了內核的調度程序上。

調度程序關注進程近1段時間內的表現（主要是檢查其睡眠時間和運行時間），根據1些經驗性的公式，判斷它現在是交互式的還是批處理的？程度如何？最后決定給它的優先級做1定的調劑。

進程的優先級被動態調劑后，就出現了兩個優先級：
1、用戶程序設置的優先級（如果未設置，則使用默許值），稱為靜態優先級。這是進程優先級的基準，在進程履行的進程中常常是不改變的；
2、優先級動態調劑后，實際生效的優先級。這個值是可能時時刻刻都在變化的；


2、調度的公平性
在支持多進程的系統中，理想情況下，各個進程應當是根據其優先級公平地占有 CPU。而不會出現“誰運氣好誰占很多”這樣的不可控的情況。

linux實現公平調度基本上是兩種思路：
1、給處于可履行狀態的進程分配時間片（依照優先級），用完時間片的進程被放到“過期隊列”中。等可履行狀態的進程都過期了，再重新分配時間片；
2、動態調劑進程的優先級。隨著進程在CPU上運行，其優先級被不斷調低，以便其他優先級較低的進程得到運行機會；

后1種方式有更小的調度粒度，并且將“公平性”與“動態調劑優先級”兩件事情合而為1，大大簡化了內核調度程序的代碼。因此，這類方式同樣成為內核調度程序的新寵。


強調1下，以上兩點都是僅針對普通進程的。而對實時進程，內核既不能自作多情地去動態調劑優先級，也沒有甚么公平性可言。


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

調度程序的效力

在linux 2.4時，可履行狀態的進程被掛在1個鏈表中。每次調度，調度程序需要掃描全部鏈表，以找出最優的那個進程來運行。復雜度為O(n)；

在linux 2.6初期，可履行狀態的進程被掛在N(N=140)個鏈表中，每個鏈表代表1個優先級，系統中支持多少個優先級就有多少個鏈表。每次調度，調度程序只需要從第1個不為空的鏈表中取出位于鏈表頭的進程便可。這樣就大大提高了調度程序的效力，復雜度為O(1)；

在linux 2.6近期的版本中，可履行狀態的進程依照優先級順序被掛在1個紅黑樹（可以想象成平衡2叉樹）中。每次調度，調度程序需要從樹中找出優先級最高的進程。復雜度為O(logN)。

那末，為何從linux 2.6初期到近期linux 2.6版本，調度程序選擇進程時的復雜度反而增加了呢？

這是由于，與此同時，調度程序對公平性的實現從上面提到的第1種思路改變成第2種思路（通過動態調劑優先級實現）。而O(1)的算法是基于1組數目不大的鏈表來實現的，按我的理解，這使得優先級的取值范圍很小（辨別度很低），不能滿足公平性的需求。而使用紅黑樹則對優先級的取值沒有限制（可以用32位、 64位、或更多位來表示優先級的值），并且O(logN)的復雜度也還是很高效的。

調度觸發的時機

進程履行系統調用主動變成非可履行狀態。比如履行nanosleep進入眠眠、履行exit退出、等等；

進程要求的資源得不到滿足而被迫進入眠眠狀態。比如履行read系統調用時，磁盤高速緩存里沒有所需要的數據，從而睡眠等待磁盤IO；

進程響應信號而變成非可履行狀態。比如響應SIGSTOP進入暫停狀態、響應SIGKILL退出、等等；

2、搶占。

進程運行時，非預期地被剝奪CPU的使用權。這又分兩種情況：進程用完了時間片、或出現了優先級更高的進程。

優先級更高的進程受正在CPU上運行的進程的影響而被喚醒。如發送信號主動喚醒，或由于釋放互斥對象（如釋放鎖）而被喚醒；

內核在響應時鐘中斷的進程中，發現當前進程的時間片用完；

內核在響應中斷的進程中，發現優先級更高的進程所等待的外部資源的變成可用，從而將其喚醒。比如CPU收到網卡中斷，內核處理該中斷，發現某個 socket可讀，因而喚醒正在等待讀這個socket的進程；再比如內核在處理時鐘中斷的進程中，觸發了定時器，從而喚醒對應的正在nanosleep 系統調用中睡眠的進程；

其他問題

linux 2.4時的設計就非常簡單，內核不支持搶占。進程運行在內核態時（比如正在履行系統調用、正處于異常處理函數中），是不允許搶占的。必須等到返回用戶態時才會觸發調度（確切的說，是在返回用戶態之前，內核會專門檢查1下是不是需要調度）；
linux 2.6則實現了內核搶占，但是在很多地方還是為了保護臨界區資源而需要臨時性的禁用內核搶占。

也有1些地方是出于效力斟酌而禁用搶占，比較典型的是spin_lock。spin_lock是這樣1種鎖，如果要求加鎖得不到滿足（鎖已被別的進程占有），則當前進程在1個死循環中不斷檢測鎖的狀態，直到鎖被釋放。

為何要這樣忙等待呢？由于臨界區很小，比如只保護“i+=j++;”這么1句。如果由于加鎖失敗而構成“睡眠-喚醒”這么個進程，就有些得不償失了。

那末既然當前進程忙等待（不睡眠），誰又來釋放鎖呢？其實已得到鎖的進程是運行在另外一個CPU上的，并且是禁用了內核搶占的。這個進程不會被其他進程搶占，所以等待鎖的進程只有可能運行在別的CPU上。（如果只有1個CPU呢？那末就不可能存在等待鎖的進程了。）

而如果不由用內核搶占呢？那末得到鎖的進程將可能被搶占，因而可能很久都不會釋放鎖。因而，等待鎖的進程可能就不知何年何月得償所望了。

對1些實時性要求更高的系統，則不能容忍spin_lock這樣的東西。寧可改用更費力的“睡眠-喚醒”進程，也不能由于禁用搶占而讓更高優先級的進程等待。比如，嵌入式實時linux montavista就是這么干的。

因而可知，實時其實不代表高效。很多時候為了實現“實時”，還是需要對性能做1定妥協的。

2、多處理器下的負載均衡
前面我們并沒有專門討論多處理器對調度程序的影響，其實也沒有甚么特別的，就是在同1時刻能有多個進程并行地運行而已。那末，為何會有“多處理器負載均衡”這個事情呢？

如果系統中只有1個可履行隊列，哪一個CPU空閑了就去隊列中找1個最適合的進程來履行。這樣不是很好很均衡嗎？

的確如此，但是多處理器共用1個可履行隊列會有1些問題。明顯，每一個CPU在履行調度程序時都需要把隊列鎖起來，這會使得調度程序難以并行，可能致使系統性能降落。而如果每一個CPU對應1個可履行隊列則不存在這樣的問題。
另外，多個可履行隊列還有1個好處。這使得1個進程在1段時間內總是在同1個CPU上履行，那末極可能這個CPU的各級cache中都緩存著這個進程的數據，很有益于系統性能的提升。

所以，在linux下，每一個CPU都有著對應的可履行隊列，而1個可履行狀態的進程在同1時刻只能處于1個可履行隊列中。

因而，“多處理器負載均衡”這個麻煩事情就來了。內核需要關注各個CPU可履行隊列中的進程數目，在數目不均衡時做出適當調劑。甚么時候需要調劑，以多大力度進程調劑，這些都是內核需要關心的。固然，盡可能不要調劑最好，畢竟調劑起來又要耗CPU、又要鎖可履行隊列，代價還是不小的。

另外，內核還得關心各個CPU的關系。兩個CPU之間，多是相互獨立的、多是同享cache的、乃至多是由同1個物理CPU通過超線程技術虛擬出來的……CPU之間的關系也是實現負載均衡的重要根據。關系越緊密，就應當越能容忍“不均衡”。

更細節的東西可以參考1下關于“調度域”的文章。

3、優先級繼承
由于互斥，1個進程（設為A）可能由于等待進入臨界區而睡眠。直到正在占有相應資源的進程（設為B）退出臨界區，進程A才被喚醒。

可能存在這樣的情況：A的優先級非常高，B的優先級非常低。B進入了臨界區，但是卻被其他優先級較高的進程（設為C）搶占了，而得不到運行，也就沒法退出臨界區。因而A也就沒法被喚醒。

A有著很高的優先級，但是現在卻淪落到跟B1起，被優先級其實不太高的C搶占，致使履行被推延。這類現象就叫做優先級反轉。

出現這類現象是很不公道的。較好的應對措施是：當A開始等待B退出臨界區時，B臨時得到A的優先級（還是假定A的優先級高于B），以便順利完成處理進程，退出臨界區。以后B的優先級恢復。這就是優先級繼承的方法。

為了實現優先級繼承，內核又得做很多事情。更細節的東西可以參考1下關于“優先級反轉”或“優先級繼承”的文章。

4、中斷處理線程化
在linux下，中斷處理程序運行于1個不可調度的上下文中。從CPU響應硬件中斷自動跳轉到內核設定的中斷處理程序去履行，到中斷處理程序退出，全部進程是不能被搶占的。

1個進程如果被搶占了，可以通過保存在它的進程控制塊（task_struct）中的信息，在以后的某個時間恢復它的運行。而中斷上下文則沒有task_struct，被搶占了就沒法恢復了。

中斷處理程序不能被搶占，也就意味著中斷處理程序的“優先級”比任何進程都高（必須等中斷處理程序完成了，進程才能被履行）。但是在實際的利用場景中，可能某些實時進程應當得到比中斷處理程序更高的優先級。

因而，1些實時性要求更高的系統就給中斷處理程序賦予了task_struct和優先級，使得它們在必要的時候能夠被高優先級的進程搶占。但是明顯，做這些工作是會給系統造成1定開消的，這也是為了實現“實時”而對性能做出的1種妥協。

更多細節可以參考1下關于“中斷線程化”的文章。

轉自：linux 進程調度淺析  

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈