操作系統要實現多進程，進程調度必不可少。
而進程調度究竟有多重要呢？ 首先，我們需要明確一點：進程調度是對TASK_RUNNING狀態的進程進行調度。如果進程不可執行（正在睡眠或其他），那麼它跟進程調度沒多大關系。
linux內核將進程分成兩個級別：普通進程和實時進程。實時進程的優先級都高於普通進程，除此之外，它們的調度策略也有所不同。
實時進程的實時，原本的涵義是“給定的操作一定要在確定的時間內完成”。重點並不在於操作一定要處理得多快，而是時間要可控（在最壞情況下也不能突破給定的時間）。
這樣的“實時”稱為“硬實時”，多用於很精密的系統之中（比如什麼火箭、導彈之類的）。一般來說，硬實時的系統是相對比較專用的。
像linux這樣的通用操作系統顯然沒法滿足這樣的要求，中斷處理、虛擬內存、等機制的存在給處理時間帶來了很大的不確定性。硬件的cache、磁盤尋道、總線爭用、也會帶來不確定性。linux這樣號稱實現了“實時”的通用操作系統，其實只是實現了“軟實時”，即盡可能地滿足進程的實時需求。
如果一個進程有實時需求（它是一個實時進程），則只要它是可執行狀態的，內核就一直讓它執行，以盡可能地滿足它對CPU的需要，直到它完成所需要做的事情，然後睡眠或退出（變為非可執行狀態）。而如果有多個實時進程都處於可執行狀態，則內核會先滿足優先級最高的實時進程對CPU的需要，直到它變為非可執行狀態。
於是，只要高優先級的實時進程一直處於可執行狀態，低優先級的實時進程就一直不能得到CPU；只要一直有實時進程處於可執行狀態，普通進程就一直不能得到CPU。
（後來，內核添加了/proc/sys/kernel/sched_rt_runtime_us和/proc/sys/kernel/sched_rt_period_us兩個參數，限定了在以sched_rt_period_us為周期的時間內，實時進程最多只能運行sched_rt_runtime_us這麼多時間。這樣就在一直有實時進程處於可執行狀態的情況下，給普通進程留了一點點能夠得到執行的機會。
那麼，如果多個相同優先級的實時進程都處於可執行狀態呢？這時就有兩種調度策略可供選擇：
l SCHED_FIFO
先進先出。直到先被執行的進程變為非可執行狀態，後來的進程才被調度執行。在這種策略下，先來的進程可以執行sched_yield系統調用，自願放棄CPU，以讓權給後來的進程；
l SCHED_RR：
輪轉調度。內核為實時進程分配時間片，在時間片用完時，讓下一個進程使用CPU，和FIFO的區別是使用了時間片；
在linux下，用戶程序可以通過sched_setscheduler系統調用來設置進程的調度策略以及相關調度參數；sched_setparam系統調用則只用於設置調度參數。這兩個系統調用要求用戶進程具有設置進程優先級的能力（CAP_SYS_NICE，一般來說需要root權限）通過將進程的策略設為SCHED_FIFO或SCHED_RR，使得進程變為實時進程。而進程的優先級則是通過以上兩個系統調用在設置調度參數時指定的。
對於實時進程，內核不會試圖調整其優先級。因為進程實時與否？有多實時？這些問題都是跟用戶程序的應用場景相關，只有用戶能夠回答，內核不能臆斷。
綜上所述，實時進程的調度是非常簡單的。進程的優先級和調度策略都由用戶定死了，內核只需要總是選擇優先級最高的實時進程來調度執行即可。唯一稍微麻煩一點的只是在選擇具有相同優先級的實時進程時，要考慮兩種調度策略。
實時進程調度的中心思想是，讓處於可執行狀態的最高優先級的實時進程盡可能地占有CPU，因為它有實時需求；而普通進程則被認為是沒有實時需求的進程，於是調度程序力圖讓各個處於可執行狀態的普通進程和平共處地分享CPU，從而讓用戶覺得這些進程是同時運行的。
與實時進程相比，普通進程的調度要復雜得多。內核需要考慮兩件麻煩事：
(1) 動態調整進程的優先級
按進程的行為特征，可以將進程分為“交互式進程”和“批處理進程”：
交互式進程（如桌面程序、服務器、等）主要的任務是與外界交互。這樣的進程應該具有較高的優先級，它們總是睡眠等待外界的輸入。而在輸入到來，內核將其喚醒時，它們又應該很快被調度執行，以做出響應。比如一個桌面程序，如果鼠標點擊後半秒種還沒反應，用戶就會感覺系統“卡”了；
批處理進程（如編譯程序）主要的任務是做持續的運算，因而它們會持續處於可執行狀態。這樣的進程一般不需要高優先級，比如編譯程序多運行了幾秒種，用戶多半不會太在意；
如果用戶能夠明確知道進程應該有怎樣的優先級，可以通過nice、setpriority系統調用來對優先級進行設置。然而應用程序未必就像桌面程序、編譯程序這樣典型。程序的行為可能五花八門，可能一會兒像交互式進程，一會兒又像批處理進程。以致於用戶難以給它設置一個合適的優先級。於是，最終，區分交互式進程和批處理進程的重任就落到了內核的調度程序上。
調度程序關注進程近一段時間內的表現（主要是檢查其睡眠時間和運行時間），根據一些經驗性的公式，判斷它現在是交互式的還是批處理的？程度如何？最後決定給它的優先級做一定的調整。
進程的優先級被動態調整後，就出現了兩個優先級：
a. 用戶程序設置的優先級（如果未設置，則使用默認值），稱為靜態優先級。這是進程優先級的基准，在進程執行的過程中往往是不改變的；
b. 優先級動態調整後，實際生效的優先級,稱為動態優先級。這個值是可能時時刻刻都在變化的。
(2) 調度的公平性
在支持多進程的系統中，理想情況下，各個進程應該是根據其優先級公平地占有CPU。而不會出現“誰運氣好誰占得多”這樣的不可控的情況。
linux實現公平調度基本上是兩種思路：
a. 給處於可執行狀態的進程分配時間片（按照優先級），用完時間片的進程被放到“過期隊列”中。等可執行狀態的進程都過期了，再重新分配時間片；
b. 動態調整進程的優先級。隨著進程在CPU上運行，其優先級被不斷調低，以便其他優先級較低的進程得到運行機會；
後一種方式有更小的調度粒度，並且將“公平性”與“動態調整優先級”兩件事情合而為一，大大簡化了內核調度程序的代碼。因此，這種方式也成為內核調度程序的新寵。
強調一下，以上兩點都是僅針對普通進程的。而對於實時進程，內核既不能自作多情地去動態調整優先級，也沒有什麼公平性可言。
“優先級”明確了哪個進程應該被調度執行，而調度程序還必須要關心效率問題。調度程序跟內核中的很多過程一樣會頻繁被執行，如果效率不濟就會浪費很多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的使用權。這又分兩種情況：進程用完了時間片、或出現了優先級更高的進程。
l 多處理器下的負載均衡
在linux下，每個CPU都有著對應的可執行隊列，而一個可執行狀態的進程在同一時刻只能處於一個可執行隊列中。
於是，“多處理器負載均衡”這個麻煩事情就來了。內核需要關注各個CPU可執行隊列中的進程數目，在數目不均衡時做出適當調整。什麼時候需要調整，以多大力度進程調整，這些都是內核需要關心的。當然，盡量不要調整最好，畢竟調整起來又要耗CPU、又要鎖可執行隊列，代價還是不小的。
另外，內核還得關心各個CPU的關系。兩個CPU之間，可能是相互獨立的、可能是共享cache的、甚至可能是由同一個物理CPU通過超線程技術虛擬出來的……CPU之間的關系也是實現負載均衡的重要依據。關系越緊密，進程在它們之間遷移的代價就越小。
l 優先級繼承
由於互斥，一個進程（設為A）可能因為等待進入臨界區而睡眠。直到正在占有相應資源的進程（設為B）退出臨界區，進程A才被喚醒。
可能存在這樣的情況：A的優先級非常高，B的優先級非常低。B進入了臨界區，但是卻被其他優先級較高的進程（設為C）搶占了，而得不到運行，也就無法退出臨界區。於是A也就無法被喚醒。
A有著很高的優先級，但是現在卻淪落到跟B一起，被優先級並不太高的C搶占，導致執行被推遲。這種現象就叫做優先級反轉。
出現這種現象是很不合理的。較好的應對措施是：當A開始等待B退出臨界區時，B臨時得到A的優先級（還是假設A的優先級高於B），以便順利完成處理過程，退出臨界區。之後B的優先級恢復。這就是優先級繼承的方法。
為了實現優先級繼承，內核又得做很多事情。
l 中斷處理線程化
在linux下，中斷處理程序運行於一個不可調度的上下文中。從CPU響應硬件中斷自動跳轉到內核設定的中斷處理程序去執行，到中斷處理程序退出，整個過程是不能被搶占的。
一個進程如果被搶占了，可以通過保存在它的進程控制塊（task_struct）中的信息，在之後的某個時間恢復它的運行。而中斷上下文則沒有task_struct，被搶占了就沒法恢復了。中斷處理程序不能被搶占，也就意味著中斷處理程序的“優先級”比任何進程都高（必須等中斷處理程序完成了，進程才能被執行）。但是在實際的應用場景中，可能某些實時進程應該得到比中斷處理程序更高的優先級。
於是，一些實時性要求更高的系統就給中斷處理程序賦予了task_struct以及優先級，使得它們在必要的時候能夠被高優先級的進程搶占。但是顯然，做這些工作是會給系統造成一定開銷的，這也是為了實現“實時”而對性能做出的一種讓步。
