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

而進(jìn)程調(diào)度究竟有多重要呢？ 首先，我們需要明確一點(diǎn)：進(jìn)程調(diào)度是對(duì)TASK_RUNNING狀態(tài)的進(jìn)程進(jìn)行調(diào)度（參見《linux進(jìn)程狀態(tài)淺析》）。如果進(jìn)程不可執(zhí)行（正在睡眠或其他），那么它跟進(jìn)程調(diào)度沒多大關(guān)系。
所以，如果你的系統(tǒng)負(fù)載非常低，盼星星盼月亮才出現(xiàn)一個(gè)可執(zhí)行狀態(tài)的進(jìn)程。那么進(jìn)程調(diào)度也就不會(huì)太重要。哪個(gè)進(jìn)程可執(zhí)行，就讓它執(zhí)行去，沒有什么需要多考慮的。
反之，如果系統(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ù)載（且沒有什么實(shí)時(shí)性要求）的環(huán)境，沒多大用。極端情況下，如果CPU的負(fù)載始終保持0或1（永遠(yuǎn)都只有一個(gè)進(jìn)程或沒有進(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í)行，沒有什么好糾結(jié)的了。
那么，進(jìn)程的優(yōu)先級(jí)該如何確定呢？有兩種方式：由用戶程序指定、由內(nèi)核的調(diào)度程序動(dòng)態(tài)調(diào)整。（下面會(huì)說到）

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)說，硬實(shí)時(shí)的系統(tǒng)是相對(duì)比較專用的。

像linux這樣的通用操作系統(tǒng)顯然沒法滿足這樣的要求，中斷處理、虛擬內(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í)行過程中硬件產(chǎn)生中斷，linux進(jìn)入中斷處理程序而擱置當(dāng)前進(jìn)程。而中斷處理程序的處理過程中又可能發(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。

那么，如果多個(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)程可以執(zhí)行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)度策略以及sched_yield系統(tǒng)調(diào)用都僅僅針對(duì)于相同優(yōu)先級(jí)的多個(gè)實(shí)時(shí)進(jìn)程同時(shí)處于可執(zhí)行狀態(tài)的情況。

在linux下，用戶程序可以通過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)說需要root權(quán)限）（參閱capability相關(guān)的文章）。
通過將進(jìn)程的策略設(shè)為SCHED_FIFO或SCHED_RR，使得進(jìn)程變?yōu)閷?shí)時(shí)進(jìn)程。而進(jìn)程的優(yōu)先級(jí)則是通過以上兩個(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í)？這些問題都是跟用戶程序的應(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)為是沒有實(shí)時(shí)需求的進(jìn)程，于是調(diào)度程序力圖讓各個(gè)處于可執(zhí)行狀態(tài)的普通進(jìn)程和平共處地分享CPU，從而讓用戶覺得這些進(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)擊后半秒種還沒反應(yīng)，用戶就會(huì)感覺系統(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í)，可以通過nice、setpriority系統(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è)置過優(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í)行的過程中往往是不改變的；
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)程被放到“過期隊(duì)列”中。等可執(zhí)行狀態(tài)的進(jìn)程都過期了，再重新分配時(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í)，也沒有什么公平性可言。

普通進(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)心效率問題。調(diào)度程序跟內(nèi)核中的很多過程一樣會(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è)紅黑樹（可以想象成平衡二叉樹）中。每次調(diào)度，調(diào)度程序需要從樹中找出優(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思路（通過動(dòng)態(tài)調(diào)整優(yōu)先級(jí)實(shí)現(xiàn)）。而O(1)的算法是基于一組數(shù)目不大的鏈表來(lái)實(shí)現(xiàn)的，按我的理解，這使得優(yōu)先級(jí)的取值范圍很?。▍^(qū)分度很低），不能滿足公平性的需求。而使用紅黑樹則對(duì)優(yōu)先級(jí)的取值沒有限制（可以用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í)，磁盤高速緩存里沒有所需要的數(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í)鐘中斷的過程中，發(fā)現(xiàn)當(dāng)前進(jìn)程的時(shí)間片用完；
內(nèi)核在響應(yīng)中斷的過程中，發(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í)鐘中斷的過程中，觸發(fā)了定時(shí)器，從而喚醒對(duì)應(yīng)的正在nanosleep系統(tǒng)調(diào)用中睡眠的進(jìn)程。
 
 
所有任務(wù)都采用linux分時(shí)調(diào)度策略時(shí)：
1，創(chuàng)建任務(wù)指定采用分時(shí)調(diào)度策略，并指定優(yōu)先級(jí)nice值(-20~19)。
2，將根據(jù)每個(gè)任務(wù)的nice值確定在cpu上的執(zhí)行時(shí)間(counter)。
3，如果沒有等待資源，則將該任務(wù)加入到就緒隊(duì)列中。
4，調(diào)度程序遍歷就緒隊(duì)列中的任務(wù)，通過對(duì)每個(gè)任務(wù)動(dòng)態(tài)優(yōu)先級(jí)的計(jì)算權(quán)值(counter+20-nice)結(jié)果，選擇計(jì)算結(jié)果最大的一個(gè)去運(yùn)行，當(dāng)這個(gè)時(shí)間片用完后(counter減至0)或者主動(dòng)放棄cpu時(shí)，該任務(wù)將被放在就緒隊(duì)列末尾(時(shí)間片用完)或等待隊(duì)列(因等待資源而放棄cpu)中。
5，此時(shí)調(diào)度程序重復(fù)上面計(jì)算過程，轉(zhuǎn)到第4步。
6，當(dāng)調(diào)度程序發(fā)現(xiàn)所有就緒任務(wù)計(jì)算所得的權(quán)值都為不大于0時(shí)，重復(fù)第2步。
 
所有任務(wù)都采用FIFO時(shí)：
1，創(chuàng)建進(jìn)程時(shí)指定采用FIFO，并設(shè)置實(shí)時(shí)優(yōu)先級(jí)rt_priority(1-99)。
2，如果沒有等待資源，則將該任務(wù)加入到就緒隊(duì)列中。
3，調(diào)度程序遍歷就緒隊(duì)列，根據(jù)實(shí)時(shí)優(yōu)先級(jí)計(jì)算調(diào)度權(quán)值(1000+rt_priority),選擇權(quán)值最高的任務(wù)使用cpu，該FIFO任務(wù)將一直占有cpu直到有優(yōu)先級(jí)更高的任務(wù)就緒(即使優(yōu)先級(jí)相同也不行)或者主動(dòng)放棄(等待資源)。
4，調(diào)度程序發(fā)現(xiàn)有優(yōu)先級(jí)更高的任務(wù)到達(dá)(高優(yōu)先級(jí)任務(wù)可能被中斷或定時(shí)器任務(wù)喚醒，再或被當(dāng)前運(yùn)行的任務(wù)喚醒，等等)，則調(diào)度程序立即在當(dāng)前任務(wù)堆棧中保存當(dāng)前cpu寄存器的所有數(shù)據(jù)，重新從高優(yōu)先級(jí)任務(wù)的堆棧中加載寄存器數(shù)據(jù)到cpu，此時(shí)高優(yōu)先級(jí)的任務(wù)開始運(yùn)行。重復(fù)第3步。
5，如果當(dāng)前任務(wù)因等待資源而主動(dòng)放棄cpu使用權(quán)，則該任務(wù)將從就緒隊(duì)列中刪除，加入等待隊(duì)列，此時(shí)重復(fù)第3步。
 
所有任務(wù)都采用RR調(diào)度策略時(shí)：
1，創(chuàng)建任務(wù)時(shí)指定調(diào)度參數(shù)為RR，并設(shè)置任務(wù)的實(shí)時(shí)優(yōu)先級(jí)和nice值(nice值將會(huì)轉(zhuǎn)換為該任務(wù)的時(shí)間片的長(zhǎng)度)。
2，如果沒有等待資源，則將該任務(wù)加入到就緒隊(duì)列中。
3，調(diào)度程序遍歷就緒隊(duì)列，根據(jù)實(shí)時(shí)優(yōu)先級(jí)計(jì)算調(diào)度權(quán)值(1000+rt_priority),選擇權(quán)值最高的任務(wù)使用cpu。
4，如果就緒隊(duì)列中的RR任務(wù)時(shí)間片為0，則會(huì)根據(jù)nice值設(shè)置該任務(wù)的時(shí)間片，同時(shí)將該任務(wù)放入就緒隊(duì)列的末尾。重復(fù)步驟3。
5，當(dāng)前任務(wù)由于等待資源而主動(dòng)退出cpu，則其加入等待隊(duì)列中。重復(fù)步驟3。
 
系統(tǒng)中既有分時(shí)調(diào)度，又有時(shí)間片輪轉(zhuǎn)調(diào)度和先進(jìn)先出調(diào)度：
1，RR調(diào)度和FIFO調(diào)度的進(jìn)程屬于實(shí)時(shí)進(jìn)程，以分時(shí)調(diào)度的進(jìn)程是非實(shí)時(shí)進(jìn)程。
2，當(dāng)實(shí)時(shí)進(jìn)程準(zhǔn)備就緒后，如果當(dāng)前cpu正在運(yùn)行非實(shí)時(shí)進(jìn)程，則實(shí)時(shí)進(jìn)程立即搶占非實(shí)時(shí)進(jìn)程。
3，RR進(jìn)程和FIFO進(jìn)程都采用實(shí)時(shí)優(yōu)先級(jí)做為調(diào)度的權(quán)值標(biāo)準(zhǔn)，RR是FIFO的一個(gè)延伸。FIFO時(shí)，如果兩個(gè)進(jìn)程的優(yōu)先級(jí)一樣，則這兩個(gè)優(yōu)先級(jí)一樣的進(jìn)程具體執(zhí)行哪一個(gè)是由其在隊(duì)列中的未知決定的，這樣導(dǎo)致一些不公正性(優(yōu)先級(jí)是一樣的，為什么要讓你一直運(yùn)行?),如果將兩個(gè)優(yōu)先級(jí)一樣的任務(wù)的調(diào)度策略都設(shè)為RR,則保證了這兩個(gè)任務(wù)可以循環(huán)執(zhí)行，保證了公平。
 
Ingo Molnar-實(shí)時(shí)補(bǔ)丁
為了能并入主流內(nèi)核，Ingo Molnar的實(shí)時(shí)補(bǔ)丁也采用了非常靈活的策略，它支持四種搶占模式：
1．No Forced Preemption (Server)，這種模式等同于沒有使能搶占選項(xiàng)的標(biāo)準(zhǔn)內(nèi)核，主要適用于科學(xué)計(jì)算等服務(wù)器環(huán)境。
2．Voluntary Kernel Preemption (Desktop)，這種模式使能了自愿搶占，但仍然失效搶占內(nèi)核選項(xiàng)，它通過增加搶占點(diǎn)縮減了搶占延遲，因此適用于一些需要較好的響應(yīng)性的環(huán)境，如桌面環(huán)境，當(dāng)然這種好的響應(yīng)性是以犧牲一些吞吐率為代價(jià)的。
3．Preemptible Kernel (Low-Latency Desktop)，這種模式既包含了自愿搶占，又使能了可搶占內(nèi)核選項(xiàng)，因此有很好的響應(yīng)延遲，實(shí)際上在一定程度上已經(jīng)達(dá)到了軟實(shí)時(shí)性。它主要適用于桌面和一些嵌入式系統(tǒng)，但是吞吐率比模式2更低。
4．Complete Preemption (Real-Time)，這種模式使能了所有實(shí)時(shí)功能，因此完全能夠滿足軟實(shí)時(shí)需求，它適用于延遲要求為100微秒或稍低的實(shí)時(shí)系統(tǒng)。
 
實(shí)現(xiàn)實(shí)時(shí)是以犧牲系統(tǒng)的吞吐率為代價(jià)的，因此實(shí)時(shí)性越好，系統(tǒng)吞吐率就越低。