Linux 進(jìn)程調(diào)度淺析

概述

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

而進(jìn)程調(diào)度究竟有多重要呢？ 首先，我們需要明確1點(diǎn)：進(jìn)程調(diào)度是對(duì) TASK_RUNNING 狀態(tài)的進(jìn)程進(jìn)行調(diào)度。如果進(jìn)程不可履行（正在睡眠或其他），那末它跟進(jìn)程調(diào)度沒多大關(guān)系。所以，如果你的系統(tǒng)負(fù)載非常低，盼星星盼月亮才出現(xiàn)1個(gè)可履行狀態(tài)的進(jìn)程。那末進(jìn)程調(diào)度也就不會(huì)太重要。哪一個(gè)進(jìn)程可履行，就讓它履行去，沒有甚么需要多斟酌的。反之，如果系統(tǒng)負(fù)載非常高，時(shí)時(shí)刻刻都有 N 多個(gè)進(jìn)程處于可履行狀態(tài)，等待被調(diào)度運(yùn)行。那末進(jìn)程調(diào)度程序?yàn)榱苏{(diào)和這 N 個(gè)進(jìn)程的履行，一定得做很多工作。調(diào)和得不好，系統(tǒng)的性能就會(huì)大打折扣。這個(gè)時(shí)候，進(jìn)程調(diào)度就是非常重要的。

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

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

那末，進(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)度

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

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


如果1個(gè)進(jìn)程有實(shí)時(shí)需求（它是1個(gè)實(shí)時(shí)進(jìn)程），則只要它是可履行狀態(tài)的，內(nèi)核就1直讓它履行，以盡量地滿足它對(duì) CPU 的需要，直到它完成所需要做的事情，然后睡眠或退出（變成非可履行狀態(tài)）。而如果有多個(gè)實(shí)時(shí)進(jìn)程都處于可履行狀態(tài)，則內(nèi)核會(huì)先滿足優(yōu)先級(jí)最高的實(shí)時(shí)進(jìn)程對(duì) CPU 的需要，直到它變成非可履行狀態(tài)。

因而，只要高優(yōu)先級(jí)的實(shí)時(shí)進(jìn)程1直處于可履行狀態(tài)，低優(yōu)先級(jí)的實(shí)時(shí)進(jìn)程就1直不能得到 CPU；只要1直有實(shí)時(shí)進(jìn)程處于可履行狀態(tài)，普通進(jìn)程就1直不能得到 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í)間。這樣就在1直有實(shí)時(shí)進(jìn)程處于可履行狀態(tài)的情況下，給普通進(jìn)程留了1點(diǎn)點(diǎn)能夠得到履行的機(jī)會(huì)。


那末，如果多個(gè)相同優(yōu)先級(jí)的實(shí)時(shí)進(jìn)程都處于可履行狀態(tài)呢？這時(shí)候就有兩種調(diào)度策略可供選擇：
1、SCHED_FIFO：先進(jìn)先出。直到先被履行的進(jìn)程變成非可履行狀態(tài)，后來(lái)的進(jìn)程才被調(diào)度履行。在這類策略下，先來(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í)，讓下1個(gè)進(jìn)程使用 CPU；

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


在 linux 下，用戶程序可以通過(guò) sched_setscheduler 系統(tǒng)調(diào)用來(lái)設(shè)置進(jìn)程的調(diào)度策略和相干調(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，1般來(lái)講需要 root 權(quán)限）。

通過(guò)將進(jìn)程的策略設(shè)為 SCHED_FIFO 或 SCHED_RR，使得進(jìn)程變成實(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í)。由于進(jìn)程實(shí)時(shí)與否？有多實(shí)時(shí)？這些問(wèn)題都是跟用戶程序的利用場(chǎng)景相干，只有用戶能夠回答，內(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)度履行便可。唯1略微麻煩1點(diǎn)的只是在選擇具有相同優(yōu)先級(jí)的實(shí)時(shí)進(jìn)程時(shí)，要斟酌兩種調(diào)度策略。

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

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


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


如果用戶能夠明確知道進(jìn)程應(yīng)當(dāng)有怎樣的優(yōu)先級(jí)，可以通過(guò) 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 能力。）

但是利用程序未必就像桌面程序、編譯程序這樣典型。程序的行動(dòng)可能5花8門，可能1會(huì)兒像交互式進(jìn)程，1會(huì)兒又像批處理進(jìn)程。以致于用戶難以給它設(shè)置1個(gè)適合的優(yōu)先級(jí)。再者，即便用戶明確知道1個(gè)進(jìn)程是交互式還是批處理，也多半礙于權(quán)限或由于偷懶而不去設(shè)置進(jìn)程的優(yōu)先級(jí)。（你又是不是為某個(gè)程序設(shè)置過(guò)優(yōu)先級(jí)呢？）因而，終究，辨別交互式進(jìn)程和批處理進(jìn)程的重?fù)?dān)就落到了內(nèi)核的調(diào)度程序上。

調(diào)度程序關(guān)注進(jìn)程近1段時(shí)間內(nèi)的表現(xiàn)（主要是檢查其睡眠時(shí)間和運(yùn)行時(shí)間），根據(jù)1些經(jīng)驗(yàn)性的公式，判斷它現(xiàn)在是交互式的還是批處理的？程度如何？最后決定給它的優(yōu)先級(jí)做1定的調(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è)置，則使用默許值），稱為靜態(tài)優(yōu)先級(jí)。這是進(jìn)程優(yōu)先級(jí)的基準(zhǔn)，在進(jìn)程履行的進(jìn)程中常常是不改變的；
2、優(yōu)先級(jí)動(dòng)態(tài)調(diào)劑后，實(shí)際生效的優(yōu)先級(jí)。這個(gè)值是可能時(shí)時(shí)刻刻都在變化的；


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

linux實(shí)現(xiàn)公平調(diào)度基本上是兩種思路：
1、給處于可履行狀態(tài)的進(jìn)程分配時(shí)間片（依照優(yōu)先級(jí)），用完時(shí)間片的進(jìn)程被放到“過(guò)期隊(duì)列”中。等可履行狀態(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ì)；

后1種方式有更小的調(diào)度粒度，并且將“公平性”與“動(dòng)態(tài)調(diào)劑優(yōu)先級(jí)”兩件事情合而為1，大大簡(jiǎn)化了內(nèi)核調(diào)度程序的代碼。因此，這類方式同樣成為內(nèi)核調(diào)度程序的新寵。


強(qiáng)調(diào)1下，以上兩點(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ù)深入了。有興趣的朋友可以參考下面的鏈接：
《Linux 調(diào)度器發(fā)展簡(jiǎn)述》
《鼠眼看Linux調(diào)度器》
《鼠眼再看Linux調(diào)度器［1］》
《鼠眼再看Linux調(diào)度器［2］》

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

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

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

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

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

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

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

進(jìn)程履行系統(tǒng)調(diào)用主動(dòng)變成非可履行狀態(tài)。比如履行nanosleep進(jìn)入眠眠、履行exit退出、等等；

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

進(jìn)程響應(yīng)信號(hào)而變成非可履行狀態(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)喚醒，或由于釋放互斥對(duì)象（如釋放鎖）而被喚醒；

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

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

其他問(wèn)題

linux 2.4時(shí)的設(shè)計(jì)就非常簡(jiǎn)單，內(nèi)核不支持搶占。進(jìn)程運(yùn)行在內(nèi)核態(tài)時(shí)（比如正在履行系統(tǒng)調(diào)用、正處于異常處理函數(shù)中），是不允許搶占的。必須等到返回用戶態(tài)時(shí)才會(huì)觸發(fā)調(diào)度（確切的說(shuō)，是在返回用戶態(tài)之前，內(nèi)核會(huì)專門檢查1下是不是需要調(diào)度）；
linux 2.6則實(shí)現(xiàn)了內(nèi)核搶占，但是在很多地方還是為了保護(hù)臨界區(qū)資源而需要臨時(shí)性的禁用內(nèi)核搶占。

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

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

那末既然當(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上。（如果只有1個(gè)CPU呢？那末就不可能存在等待鎖的進(jìn)程了。）

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

對(duì)1些實(shí)時(shí)性要求更高的系統(tǒng)，則不能容忍spin_lock這樣的東西。寧可改用更費(fèi)力的“睡眠-喚醒”進(jìn)程，也不能由于禁用搶占而讓更高優(yōu)先級(jí)的進(jìn)程等待。比如，嵌入式實(shí)時(shí)linux montavista就是這么干的。

因而可知，實(shí)時(shí)其實(shí)不代表高效。很多時(shí)候?yàn)榱藢?shí)現(xiàn)“實(shí)時(shí)”，還是需要對(duì)性能做1定妥協(xié)的。

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

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

的確如此，但是多處理器共用1個(gè)可履行隊(duì)列會(huì)有1些問(wèn)題。明顯，每一個(gè)CPU在履行調(diào)度程序時(shí)都需要把隊(duì)列鎖起來(lái)，這會(huì)使得調(diào)度程序難以并行，可能致使系統(tǒng)性能降落。而如果每一個(gè)CPU對(duì)應(yīng)1個(gè)可履行隊(duì)列則不存在這樣的問(wèn)題。
另外，多個(gè)可履行隊(duì)列還有1個(gè)好處。這使得1個(gè)進(jìn)程在1段時(shí)間內(nèi)總是在同1個(gè)CPU上履行，那末極可能這個(gè)CPU的各級(jí)cache中都緩存著這個(gè)進(jìn)程的數(shù)據(jù)，很有益于系統(tǒng)性能的提升。

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

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

另外，內(nèi)核還得關(guān)心各個(gè)CPU的關(guān)系。兩個(gè)CPU之間，多是相互獨(dú)立的、多是同享cache的、乃至多是由同1個(gè)物理CPU通過(guò)超線程技術(shù)虛擬出來(lái)的……CPU之間的關(guān)系也是實(shí)現(xiàn)負(fù)載均衡的重要根據(jù)。關(guān)系越緊密，就應(yīng)當(dāng)越能容忍“不均衡”。

更細(xì)節(jié)的東西可以參考1下關(guān)于“調(diào)度域”的文章。

3、優(yōu)先級(jí)繼承
由于互斥，1個(gè)進(jìn)程（設(shè)為A）可能由于等待進(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)行，也就沒法退出臨界區(qū)。因而A也就沒法被喚醒。

A有著很高的優(yōu)先級(jí)，但是現(xiàn)在卻淪落到跟B1起，被優(yōu)先級(jí)其實(shí)不太高的C搶占，致使履行被推延。這類現(xiàn)象就叫做優(yōu)先級(jí)反轉(zhuǎn)。

出現(xiàn)這類現(xiàn)象是很不公道的。較好的應(yīng)對(duì)措施是：當(dāng)A開始等待B退出臨界區(qū)時(shí)，B臨時(shí)得到A的優(yōu)先級(jí)（還是假定A的優(yōu)先級(jí)高于B），以便順利完成處理進(jìn)程，退出臨界區(qū)。以后B的優(yōu)先級(jí)恢復(fù)。這就是優(yōu)先級(jí)繼承的方法。

為了實(shí)現(xiàn)優(yōu)先級(jí)繼承，內(nèi)核又得做很多事情。更細(xì)節(jié)的東西可以參考1下關(guān)于“優(yōu)先級(jí)反轉(zhuǎn)”或“優(yōu)先級(jí)繼承”的文章。

4、中斷處理線程化
在linux下，中斷處理程序運(yùn)行于1個(gè)不可調(diào)度的上下文中。從CPU響應(yīng)硬件中斷自動(dòng)跳轉(zhuǎn)到內(nèi)核設(shè)定的中斷處理程序去履行，到中斷處理程序退出，全部進(jìn)程是不能被搶占的。

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

中斷處理程序不能被搶占，也就意味著中斷處理程序的“優(yōu)先級(jí)”比任何進(jìn)程都高（必須等中斷處理程序完成了，進(jìn)程才能被履行）。但是在實(shí)際的利用場(chǎng)景中，可能某些實(shí)時(shí)進(jìn)程應(yīng)當(dāng)?shù)玫奖戎袛嗵幚沓绦蚋叩膬?yōu)先級(jí)。

因而，1些實(shí)時(shí)性要求更高的系統(tǒng)就給中斷處理程序賦予了task_struct和優(yōu)先級(jí)，使得它們?cè)?/span>必要的時(shí)候能夠被高優(yōu)先級(jí)的進(jìn)程搶占。但是明顯，做這些工作是會(huì)給系統(tǒng)造成1定開消的，這也是為了實(shí)現(xiàn)“實(shí)時(shí)”而對(duì)性能做出的1種妥協(xié)。

更多細(xì)節(jié)可以參考1下關(guān)于“中斷線程化”的文章。

轉(zhuǎn)自：linux 進(jìn)程調(diào)度淺析  

生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)