操作系統(tǒng)要實(shí)現(xiàn)多進(jìn)程，進(jìn)程調(diào)度必不可少。進(jìn)程調(diào)度是對(duì)TASK_RUNNING狀態(tài)的進(jìn)程進(jìn)行調(diào)度。如果進(jìn)程不可執(zhí)行（正在睡眠或其他），那么它跟進(jìn)程調(diào)度沒(méi)多大關(guān)系。

所以，如果你的系統(tǒng)負(fù)載非常低，盼星星盼月亮才出現(xiàn)一個(gè)可執(zhí)行狀態(tài)的進(jìn)程。那么進(jìn)程調(diào)度也就不會(huì)太重要。哪個(gè)進(jìn)程可執(zhí)行，就讓它執(zhí)行去，沒(méi)有什么需要多考慮的。

反之，如果系統(tǒng)負(fù)載非常高，時(shí)時(shí)刻刻都有N多個(gè)進(jìn)程處于可執(zhí)行狀態(tài)，等待被調(diào)度運(yùn)行。那么進(jìn)程調(diào)度程序?yàn)榱藚f(xié)調(diào)這N個(gè)進(jìn)程的執(zhí)行，必定得做很多工作。協(xié)調(diào)得不好，系統(tǒng)的性能就會(huì)大打折扣。這個(gè)時(shí)候，進(jìn)程調(diào)度就是非常重要的。

盡管我們平常接觸的很多計(jì)算機(jī)（如桌面系統(tǒng)、網(wǎng)絡(luò)服務(wù)器、等）負(fù)載都比較低，但是linux作為一個(gè)通用操作系統(tǒng)，不能假設(shè)系統(tǒng)負(fù)載低，必須為應(yīng)付高負(fù)載下的進(jìn)程調(diào)度做精心的設(shè)計(jì)。

當(dāng)然，這些設(shè)計(jì)對(duì)于低負(fù)載（且沒(méi)有什么實(shí)時(shí)性要求）的環(huán)境，沒(méi)多大用。極端情況下，如果CPU的負(fù)載始終保持0或1（永遠(yuǎn)都只有一個(gè)進(jìn)程或沒(méi)有進(jìn)程需要在CPU上運(yùn)行），那么這些設(shè)計(jì)基本上都是徒勞的。

優(yōu)先級(jí)

現(xiàn)在的操作系統(tǒng)為了協(xié)調(diào)多個(gè)進(jìn)程的“同時(shí)”運(yùn)行，最基本的手段就是給進(jìn)程定義優(yōu)先級(jí)。定義了進(jìn)程的優(yōu)先級(jí)，如果有多個(gè)進(jìn)程同時(shí)處于可執(zhí)行狀態(tài)，那么誰(shuí)優(yōu)先級(jí)高誰(shuí)就去執(zhí)行，沒(méi)有什么好糾結(jié)的了。

那么，進(jìn)程的優(yōu)先級(jí)該如何確定呢？有兩種方式：由用戶程序指定、由內(nèi)核的調(diào)度程序動(dòng)態(tài)調(diào)整。（下面會(huì)說(shuō)到）

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

實(shí)時(shí)進(jìn)程的調(diào)度

實(shí)時(shí)，原本的涵義是“給定的操作一定要在確定的時(shí)間內(nèi)完成”。重點(diǎn)并不在于操作一定要處理得多快，而是時(shí)間要可控（在最壞情況下也不能突破給定的時(shí)間）。

這樣的“實(shí)時(shí)”稱為“硬實(shí)時(shí)”，多用于很精密的系統(tǒng)之中（比如什么火箭、導(dǎo)彈之類的）。一般來(lái)說(shuō)，硬實(shí)時(shí)的系統(tǒng)是相對(duì)比較專用的。

像linux這樣的通用操作系統(tǒng)顯然沒(méi)法滿足這樣的要求，中斷處理、虛擬內(nèi)存、等機(jī)制的存在給處理時(shí)間帶來(lái)了很大的不確定性。硬件的cache、磁盤尋道、總線爭(zhēng)用、也會(huì)帶來(lái)不確定性。

比如考慮“i++;”這么一句C代碼。絕大多數(shù)情況下，它執(zhí)行得很快。但是極端情況下還是有這樣的可能：

1、i的內(nèi)存空間未分配，CPU觸發(fā)缺頁(yè)異常。而linux在缺頁(yè)異常的處理代碼中試圖分配內(nèi)存時(shí)，又可能由于系統(tǒng)內(nèi)存緊缺而分配失敗，導(dǎo)致進(jìn)程進(jìn)入睡眠；
2、代碼執(zhí)行過(guò)程中硬件產(chǎn)生中斷，linux進(jìn)入中斷處理程序而擱置當(dāng)前進(jìn)程。而中斷處理程序的處理過(guò)程中又可能發(fā)生新的硬件中斷，中斷永遠(yuǎn)嵌套不止……；等等……

而像linux這樣號(hào)稱實(shí)現(xiàn)了“實(shí)時(shí)”的通用操作系統(tǒng)，其實(shí)只是實(shí)現(xiàn)了“軟實(shí)時(shí)”，即盡可能地滿足進(jìn)程的實(shí)時(shí)需求。

如果一個(gè)進(jìn)程有實(shí)時(shí)需求（它是一個(gè)實(shí)時(shí)進(jìn)程），則只要它是可執(zhí)行狀態(tài)的，內(nèi)核就一直讓它執(zhí)行，以盡可能地滿足它對(duì)CPU的需要，直到它完成所需要做的事情，然后睡眠或退出（變?yōu)榉强蓤?zhí)行狀態(tài)）。

而如果有多個(gè)實(shí)時(shí)進(jìn)程都處于可執(zhí)行狀態(tài)，則內(nèi)核會(huì)先滿足優(yōu)先級(jí)最高的實(shí)時(shí)進(jìn)程對(duì)CPU的需要，直到它變?yōu)榉强蓤?zhí)行狀態(tài)。于是，只要高優(yōu)先級(jí)的實(shí)時(shí)進(jìn)程一直處于可執(zhí)行狀態(tài)，低優(yōu)先級(jí)的實(shí)時(shí)進(jìn)程就一直不能得到CPU；只要一直有實(shí)時(shí)進(jìn)程處于可執(zhí)行狀態(tài)，普通進(jìn)程就一直不能得到CPU。

（后來(lái)，內(nèi)核添加了/proc/sys/kernel/sched_rt_runtime_us和/proc/sys/kernel/sched_rt_period_us兩個(gè)參數(shù)，限定了在以sched_rt_period_us為周期的時(shí)間內(nèi)，實(shí)時(shí)進(jìn)程最多只能運(yùn)行sched_rt_runtime_us這么多時(shí)間。這樣就在一直有實(shí)時(shí)進(jìn)程處于可執(zhí)行狀態(tài)的情況下，給普通進(jìn)程留了一點(diǎn)點(diǎn)能夠得到執(zhí)行的機(jī)會(huì)。）

那么，如果多個(gè)相同優(yōu)先級(jí)的實(shí)時(shí)進(jìn)程都處于可執(zhí)行狀態(tài)呢？這時(shí)就有兩種調(diào)度策略可供選擇：

1、SCHED_FIFO：先進(jìn)先出。直到先被執(zhí)行的進(jìn)程變?yōu)榉强蓤?zhí)行狀態(tài)，后來(lái)的進(jìn)程才被調(diào)度執(zhí)行。在這種策略下，先來(lái)的進(jìn)程可以行sched_yield系統(tǒng)調(diào)用，自愿放棄CPU，以讓權(quán)給后來(lái)的進(jìn)程；

2、SCHED_RR：輪轉(zhuǎn)調(diào)度。內(nèi)核為實(shí)時(shí)進(jìn)程分配時(shí)間片，在時(shí)間片用完時(shí)，讓下一個(gè)進(jìn)程使用CPU；

強(qiáng)調(diào)一下，這兩種調(diào)度策略僅僅針對(duì)于相同優(yōu)先級(jí)的多個(gè)實(shí)時(shí)進(jìn)程同時(shí)處于可執(zhí)行狀態(tài)的情況。

在linux下，用戶程序可以通過(guò)sched_setscheduler系統(tǒng)調(diào)用來(lái)設(shè)置進(jìn)程的調(diào)度策略以及相關(guān)調(diào)度參數(shù)；sched_setparam系統(tǒng)調(diào)用則只用于設(shè)置調(diào)度參數(shù)。這兩個(gè)系統(tǒng)調(diào)用要求用戶進(jìn)程具有設(shè)置進(jìn)程優(yōu)先級(jí)的能力（CAP_SYS_NICE，一般來(lái)說(shuō)需要root權(quán)限）。

通過(guò)將進(jìn)程的策略設(shè)為SCHED_FIFO或SCHED_RR，使得進(jìn)程變?yōu)閷?shí)時(shí)進(jìn)程。而進(jìn)程的優(yōu)先級(jí)則是通過(guò)以上兩個(gè)系統(tǒng)調(diào)用在設(shè)置調(diào)度參數(shù)時(shí)指定的。

對(duì)于實(shí)時(shí)進(jìn)程，內(nèi)核不會(huì)試圖調(diào)整其優(yōu)先級(jí)。因?yàn)檫M(jìn)程實(shí)時(shí)與否？有多實(shí)時(shí)？這些問(wèn)題都是跟用戶程序的應(yīng)用場(chǎng)景相關(guān)，只有用戶能夠回答，內(nèi)核不能臆斷。

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

普通進(jìn)程的調(diào)度

實(shí)時(shí)進(jìn)程調(diào)度的中心思想是，讓處于可執(zhí)行狀態(tài)的最高優(yōu)先級(jí)的實(shí)時(shí)進(jìn)程盡可能地占有CPU，因?yàn)樗袑?shí)時(shí)需求；而普通進(jìn)程則被認(rèn)為是沒(méi)有實(shí)時(shí)需求的進(jìn)程，于是調(diào)度程序力圖讓各個(gè)處于可執(zhí)行狀態(tài)的普通進(jìn)程和平共處地分享CPU，從而讓用戶覺(jué)得這些進(jìn)程是同時(shí)運(yùn)行的。

與實(shí)時(shí)進(jìn)程相比，普通進(jìn)程的調(diào)度要復(fù)雜得多。內(nèi)核需要考慮兩件麻煩事：

一、動(dòng)態(tài)調(diào)整進(jìn)程的優(yōu)先級(jí)

按進(jìn)程的行為特征，可以將進(jìn)程分為“交互式進(jìn)程”和“批處理進(jìn)程”：

交互式進(jìn)程（如桌面程序、服務(wù)器、等）主要的任務(wù)是與外界交互。這樣的進(jìn)程應(yīng)該具有較高的優(yōu)先級(jí)，它們總是睡眠等待外界的輸入。而在輸入到來(lái)，內(nèi)核將其喚醒時(shí)，它們又應(yīng)該很快被調(diào)度執(zhí)行，以做出響應(yīng)。比如一個(gè)桌面程序，如果鼠標(biāo)點(diǎn)擊后半秒種還沒(méi)反應(yīng)，用戶就會(huì)感覺(jué)系統(tǒng)“卡”了；

批處理進(jìn)程（如編譯程序）主要的任務(wù)是做持續(xù)的運(yùn)算，因而它們會(huì)持續(xù)處于可執(zhí)行狀態(tài)。這樣的進(jìn)程一般不需要高優(yōu)先級(jí)，比如編譯程序多運(yùn)行了幾秒種，用戶多半不會(huì)太在意；

如果用戶能夠明確知道進(jìn)程應(yīng)該有怎樣的優(yōu)先級(jí)，可以通過(guò)nice、setpriority（非實(shí)時(shí)進(jìn)程優(yōu)先級(jí)的設(shè)置）系統(tǒng)調(diào)用來(lái)對(duì)優(yōu)先級(jí)進(jìn)行設(shè)置。（如果要提高進(jìn)程的優(yōu)先級(jí)，要求用戶進(jìn)程具有CAP_SYS_NICE能力。

然而應(yīng)用程序未必就像桌面程序、編譯程序這樣典型。程序的行為可能五花八門，可能一會(huì)兒像交互式進(jìn)程，一會(huì)兒又像批處理進(jìn)程。以致于用戶難以給它設(shè)置一個(gè)合適的優(yōu)先級(jí)。再者，即使用戶明確知道一個(gè)進(jìn)程是交互式還是批處理，也多半礙于權(quán)限或因?yàn)橥祽卸蝗ピO(shè)置進(jìn)程的優(yōu)先級(jí)。（你又是否為某個(gè)程序設(shè)置過(guò)優(yōu)先級(jí)呢？）

于是，最終，區(qū)分交互式進(jìn)程和批處理進(jìn)程的重任就落到了內(nèi)核的調(diào)度程序上。

調(diào)度程序關(guān)注進(jìn)程近一段時(shí)間內(nèi)的表現(xiàn)（主要是檢查其睡眠時(shí)間和運(yùn)行時(shí)間），根據(jù)一些經(jīng)驗(yàn)性的公式，判斷它現(xiàn)在是交互式的還是批處理的？程度如何？最后決定給它的優(yōu)先級(jí)做一定的調(diào)整。

進(jìn)程的優(yōu)先級(jí)被動(dòng)態(tài)調(diào)整后，就出現(xiàn)了兩個(gè)優(yōu)先級(jí)：

1、用戶程序設(shè)置的優(yōu)先級(jí)（如果未設(shè)置，則使用默認(rèn)值），稱為靜態(tài)優(yōu)先級(jí)。這是進(jìn)程優(yōu)先級(jí)的基準(zhǔn)，在進(jìn)程執(zhí)行的過(guò)程中往往是不改變的；
2、優(yōu)先級(jí)動(dòng)態(tài)調(diào)整后，實(shí)際生效的優(yōu)先級(jí)。這個(gè)值是可能時(shí)時(shí)刻刻都在變化的；

二、調(diào)度的公平性

在支持多進(jìn)程的系統(tǒng)中，理想情況下，各個(gè)進(jìn)程應(yīng)該是根據(jù)其優(yōu)先級(jí)公平地占有CPU。而不會(huì)出現(xiàn)“誰(shuí)運(yùn)氣好誰(shuí)占得多”這樣的不可控的情況。

linux實(shí)現(xiàn)公平調(diào)度基本上是兩種思路：

1、給處于可執(zhí)行狀態(tài)的進(jìn)程分配時(shí)間片（按照優(yōu)先級(jí)），用完時(shí)間片的進(jìn)程被放到“過(guò)期隊(duì)列”中。等可執(zhí)行狀態(tài)的進(jìn)程都過(guò)期了，再重新分配時(shí)間片；
2、動(dòng)態(tài)調(diào)整進(jìn)程的優(yōu)先級(jí)。隨著進(jìn)程在CPU上運(yùn)行，其優(yōu)先級(jí)被不斷調(diào)低，以便其他優(yōu)先級(jí)較低的進(jìn)程得到運(yùn)行機(jī)會(huì)；
后一種方式有更小的調(diào)度粒度，并且將“公平性”與“動(dòng)態(tài)調(diào)整優(yōu)先級(jí)”兩件事情合而為一，大大簡(jiǎn)化了內(nèi)核調(diào)度程序的代碼。因此，這種方式也成為內(nèi)核調(diào)度程序的新寵。

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

普通進(jìn)程具體的調(diào)度算法非常復(fù)雜，并且隨linux內(nèi)核版本的演變也在不斷更替（不僅僅是簡(jiǎn)單的調(diào)整），所以本文就不繼續(xù)深入了。

調(diào)度程序的效率

“優(yōu)先級(jí)”明確了哪個(gè)進(jìn)程應(yīng)該被調(diào)度執(zhí)行，而調(diào)度程序還必須要關(guān)心效率問(wèn)題。調(diào)度程序跟內(nèi)核中的很多過(guò)程一樣會(huì)頻繁被執(zhí)行，如果效率不濟(jì)就會(huì)浪費(fèi)很多CPU時(shí)間，導(dǎo)致系統(tǒng)性能下降。

在linux 2.4時(shí)，可執(zhí)行狀態(tài)的進(jìn)程被掛在一個(gè)鏈表中。每次調(diào)度，調(diào)度程序需要掃描整個(gè)鏈表，以找出最優(yōu)的那個(gè)進(jìn)程來(lái)運(yùn)行。復(fù)雜度為O(n)；

在linux 2.6早期，可執(zhí)行狀態(tài)的進(jìn)程被掛在N(N=140)個(gè)鏈表中，每一個(gè)鏈表代表一個(gè)優(yōu)先級(jí)，系統(tǒng)中支持多少個(gè)優(yōu)先級(jí)就有多少個(gè)鏈表。每次調(diào)度，調(diào)度程序只需要從第一個(gè)不為空的鏈表中取出位于鏈表頭的進(jìn)程即可。這樣就大大提高了調(diào)度程序的效率，復(fù)雜度為O(1)；

在linux 2.6近期的版本中，可執(zhí)行狀態(tài)的進(jìn)程按照優(yōu)先級(jí)順序被掛在一個(gè)紅黑樹(shù)（可以想象成平衡二叉樹(shù)）中。每次調(diào)度，調(diào)度程序需要從樹(shù)中找出優(yōu)先級(jí)最高的進(jìn)程。復(fù)雜度為O(logN)。

那么，為什么從linux 2.6早期到近期linux 2.6版本，調(diào)度程序選擇進(jìn)程時(shí)的復(fù)雜度反而增加了呢？

這是因?yàn)?，與此同時(shí)，調(diào)度程序?qū)叫缘膶?shí)現(xiàn)從上面提到的第一種思路改變?yōu)榈诙N思路（通過(guò)動(dòng)態(tài)調(diào)整優(yōu)先級(jí)實(shí)現(xiàn)）。而O(1)的算法是基于一組數(shù)目不大的鏈表來(lái)實(shí)現(xiàn)的，按我的理解，這使得優(yōu)先級(jí)的取值范圍很?。▍^(qū)分度很低），不能滿足公平性的需求。而使用紅黑樹(shù)則對(duì)優(yōu)先級(jí)的取值沒(méi)有限制（可以用32位、64位、或更多位來(lái)表示優(yōu)先級(jí)的值），并且O(logN)的復(fù)雜度也還是很高效的。

調(diào)度觸發(fā)的時(shí)機(jī)

調(diào)度的觸發(fā)主要有如下幾種情況：

1、當(dāng)前進(jìn)程（正在CPU上運(yùn)行的進(jìn)程）狀態(tài)變?yōu)榉强蓤?zhí)行狀態(tài)。

進(jìn)程執(zhí)行系統(tǒng)調(diào)用主動(dòng)變?yōu)榉强蓤?zhí)行狀態(tài)。比如執(zhí)行nanosleep進(jìn)入睡眠、執(zhí)行exit退出、等等；

進(jìn)程請(qǐng)求的資源得不到滿足而被迫進(jìn)入睡眠狀態(tài)。比如執(zhí)行read系統(tǒng)調(diào)用時(shí)，磁盤高速緩存里沒(méi)有所需要的數(shù)據(jù)，從而睡眠等待磁盤IO；

進(jìn)程響應(yīng)信號(hào)而變?yōu)榉强蓤?zhí)行狀態(tài)。比如響應(yīng)SIGSTOP進(jìn)入暫停狀態(tài)、響應(yīng)SIGKILL退出、等等；

2、搶占。進(jìn)程運(yùn)行時(shí)，非預(yù)期地被剝奪CPU的使用權(quán)。這又分兩種情況：進(jìn)程用完了時(shí)間片、或出現(xiàn)了優(yōu)先級(jí)更高的進(jìn)程。

優(yōu)先級(jí)更高的進(jìn)程受正在CPU上運(yùn)行的進(jìn)程的影響而被喚醒。如發(fā)送信號(hào)主動(dòng)喚醒，或因?yàn)獒尫呕コ鈱?duì)象（如釋放鎖）而被喚醒；

內(nèi)核在響應(yīng)時(shí)鐘中斷的過(guò)程中，發(fā)現(xiàn)當(dāng)前進(jìn)程的時(shí)間片用完；

內(nèi)核在響應(yīng)中斷的過(guò)程中，發(fā)現(xiàn)優(yōu)先級(jí)更高的進(jìn)程所等待的外部資源的變?yōu)榭捎?，從而將其喚醒。比如CPU收到網(wǎng)卡中斷，內(nèi)核處理該中斷，發(fā)現(xiàn)某個(gè)socket可讀，于是喚醒正在等待讀這個(gè)socket的進(jìn)程；再比如內(nèi)核在處理時(shí)鐘中斷的過(guò)程中，觸發(fā)了定時(shí)器，從而喚醒對(duì)應(yīng)的正在nanosleep系統(tǒng)調(diào)用中睡眠的進(jìn)程；

其他問(wèn)題

1、內(nèi)核搶占

理想情況下，只要滿足“出現(xiàn)了優(yōu)先級(jí)更高的進(jìn)程”這個(gè)條件，當(dāng)前進(jìn)程就應(yīng)該被立刻搶占。但是，就像多線程程序需要用鎖來(lái)保護(hù)臨界區(qū)資源一樣，內(nèi)核中也存在很多這樣的臨界區(qū)，不大可能隨時(shí)隨地都能接收搶占。

linux 2.4時(shí)的設(shè)計(jì)就非常簡(jiǎn)單，內(nèi)核不支持搶占。進(jìn)程運(yùn)行在內(nèi)核態(tài)時(shí)（比如正在執(zhí)行系統(tǒng)調(diào)用、正處于異常處理函數(shù)中），是不允許搶占的。必須等到返回用戶態(tài)時(shí)才會(huì)觸發(fā)調(diào)度（確切的說(shuō)，是在返回用戶態(tài)之前，內(nèi)核會(huì)專門檢查一下是否需要調(diào)度）；

linux 2.6則實(shí)現(xiàn)了內(nèi)核搶占，但是在很多地方還是為了保護(hù)臨界區(qū)資源而需要臨時(shí)性的禁用內(nèi)核搶占。

也有一些地方是出于效率考慮而禁用搶占，比較典型的是spin_lock。spin_lock是這樣一種鎖，如果請(qǐng)求加鎖得不到滿足（鎖已被別的進(jìn)程占有），則當(dāng)前進(jìn)程在一個(gè)死循環(huán)中不斷檢測(cè)鎖的狀態(tài)，直到鎖被釋放。

為什么要這樣忙等待呢？因?yàn)榕R界區(qū)很小，比如只保護(hù)“i+=j++;”這么一句。如果因?yàn)榧渔i失敗而形成“睡眠-喚醒”這么個(gè)過(guò)程，就有些得不償失了。那么既然當(dāng)前進(jìn)程忙等待（不睡眠），誰(shuí)又來(lái)釋放鎖呢？其實(shí)已得到鎖的進(jìn)程是運(yùn)行在另一個(gè)CPU上的，并且是禁用了內(nèi)核搶占的。這個(gè)進(jìn)程不會(huì)被其他進(jìn)程搶占，所以等待鎖的進(jìn)程只有可能運(yùn)行在別的CPU上。（如果只有一個(gè)CPU呢？那么就不可能存在等待鎖的進(jìn)程了。）

而如果不禁用內(nèi)核搶占呢？那么得到鎖的進(jìn)程將可能被搶占，于是可能很久都不會(huì)釋放鎖。于是，等待鎖的進(jìn)程可能就不知何年何月得償所望了。

對(duì)于一些實(shí)時(shí)性要求更高的系統(tǒng)，則不能容忍spin_lock這樣的東西。寧可改用更費(fèi)勁的“睡眠-喚醒”過(guò)程，也不能因?yàn)榻脫屨级尭邇?yōu)先級(jí)的進(jìn)程等待。比如，嵌入式實(shí)時(shí)linux montavista就是這么干的。
由此可見(jiàn)，實(shí)時(shí)并不代表高效。很多時(shí)候?yàn)榱藢?shí)現(xiàn)“實(shí)時(shí)”，還是需要對(duì)性能做一定讓步的。

2、多處理器下的負(fù)載均衡

前面我們并沒(méi)有專門討論多處理器對(duì)調(diào)度程序的影響，其實(shí)也沒(méi)有什么特別的，就是在同一時(shí)刻能有多個(gè)進(jìn)程并行地運(yùn)行而已。那么，為什么會(huì)有“多處理器負(fù)載均衡”這個(gè)事情呢？

如果系統(tǒng)中只有一個(gè)可執(zhí)行隊(duì)列，哪個(gè)CPU空閑了就去隊(duì)列中找一個(gè)最合適的進(jìn)程來(lái)執(zhí)行。這樣不是很好很均衡嗎？

的確如此，但是多處理器共用一個(gè)可執(zhí)行隊(duì)列會(huì)有一些問(wèn)題。顯然，每個(gè)CPU在執(zhí)行調(diào)度程序時(shí)都需要把隊(duì)列鎖起來(lái)，這會(huì)使得調(diào)度程序難以并行，可能導(dǎo)致系統(tǒng)性能下降。而如果每個(gè)CPU對(duì)應(yīng)一個(gè)可執(zhí)行隊(duì)列則不存在這樣的問(wèn)題。

另外，多個(gè)可執(zhí)行隊(duì)列還有一個(gè)好處。這使得一個(gè)進(jìn)程在一段時(shí)間內(nèi)總是在同一個(gè)CPU上執(zhí)行，那么很可能這個(gè)CPU的各級(jí)cache中都緩存著這個(gè)進(jìn)程的數(shù)據(jù)，很有利于系統(tǒng)性能的提升。

所以，在linux下，每個(gè)CPU都有著對(duì)應(yīng)的可執(zhí)行隊(duì)列，而一個(gè)可執(zhí)行狀態(tài)的進(jìn)程在同一時(shí)刻只能處于一個(gè)可執(zhí)行隊(duì)列中。

于是，“多處理器負(fù)載均衡”這個(gè)麻煩事情就來(lái)了。內(nèi)核需要關(guān)注各個(gè)CPU可執(zhí)行隊(duì)列中的進(jìn)程數(shù)目，在數(shù)目不均衡時(shí)做出適當(dāng)調(diào)整。什么時(shí)候需要調(diào)整，以多大力度進(jìn)程調(diào)整，這些都是內(nèi)核需要關(guān)心的。當(dāng)然，盡量不要調(diào)整最好，畢竟調(diào)整起來(lái)又要耗CPU、又要鎖可執(zhí)行隊(duì)列，代價(jià)還是不小的。

另外，內(nèi)核還得關(guān)心各個(gè)CPU的關(guān)系。兩個(gè)CPU之間，可能是相互獨(dú)立的、可能是共享cache的、甚至可能是由同一個(gè)物理CPU通過(guò)超線程技術(shù)虛擬出來(lái)的……CPU之間的關(guān)系也是實(shí)現(xiàn)負(fù)載均衡的重要依據(jù)。關(guān)系越緊密，進(jìn)程在它們之間遷移的代價(jià)就越小。

3、優(yōu)先級(jí)繼承

由于互斥，一個(gè)進(jìn)程（設(shè)為A）可能因?yàn)榈却M(jìn)入臨界區(qū)而睡眠。直到正在占有相應(yīng)資源的進(jìn)程（設(shè)為B）退出臨界區(qū)，進(jìn)程A才被喚醒。

可能存在這樣的情況：A的優(yōu)先級(jí)非常高，B的優(yōu)先級(jí)非常低。B進(jìn)入了臨界區(qū)，但是卻被其他優(yōu)先級(jí)較高的進(jìn)程（設(shè)為C）搶占了，而得不到運(yùn)行，也就無(wú)法退出臨界區(qū)。于是A也就無(wú)法被喚醒。

A有著很高的優(yōu)先級(jí)，但是現(xiàn)在卻淪落到跟B一起，被優(yōu)先級(jí)并不太高的C搶占，導(dǎo)致執(zhí)行被推遲。這種現(xiàn)象就叫做優(yōu)先級(jí)反轉(zhuǎn)。

出現(xiàn)這種現(xiàn)象是很不合理的。較好的應(yīng)對(duì)措施是：當(dāng)A開(kāi)始等待B退出臨界區(qū)時(shí)，B臨時(shí)得到A的優(yōu)先級(jí)（還是假設(shè)A的優(yōu)先級(jí)高于B），以便順利完成處理過(guò)程，退出臨界區(qū)。之后B的優(yōu)先級(jí)恢復(fù)。這就是優(yōu)先級(jí)繼承的方法。
為了實(shí)現(xiàn)優(yōu)先級(jí)繼承，內(nèi)核又得做很多事情。

4、中斷處理線程化

在linux下，中斷處理程序運(yùn)行于一個(gè)不可調(diào)度的上下文中。從CPU響應(yīng)硬件中斷自動(dòng)跳轉(zhuǎn)到內(nèi)核設(shè)定的中斷處理程序去執(zhí)行，到中斷處理程序退出，整個(gè)過(guò)程是不能被搶占的。

一個(gè)進(jìn)程如果被搶占了，可以通過(guò)保存在它的進(jìn)程控制塊（task_struct）中的信息，在之后的某個(gè)時(shí)間恢復(fù)它的運(yùn)行。而中斷上下文則沒(méi)有task_struct，被搶占了就沒(méi)法恢復(fù)了。

中斷處理程序不能被搶占，也就意味著中斷處理程序的“優(yōu)先級(jí)”比任何進(jìn)程都高（必須等中斷處理程序完成了，進(jìn)程才能被執(zhí)行）。但是在實(shí)際的應(yīng)用場(chǎng)景中，可能某些實(shí)時(shí)進(jìn)程應(yīng)該得到比中斷處理程序更高的優(yōu)先級(jí)。

于是，一些實(shí)時(shí)性要求更高的系統(tǒng)就給中斷處理程序賦予了task_struct以及優(yōu)先級(jí)，使得它們?cè)诒匾臅r(shí)候能夠被高優(yōu)先級(jí)的進(jìn)程搶占。但是顯然，做這些工作是會(huì)給系統(tǒng)造成一定開(kāi)銷的，這也是為了實(shí)現(xiàn)“實(shí)時(shí)”而對(duì)性能做出的一種讓步。