在操作系統(tǒng)的復(fù)雜世界里，進(jìn)程就如同一個(gè)個(gè)忙碌的 “小工人”，它們都渴望獲得 CPU 的 “青睞”，以執(zhí)行自己的任務(wù)。而在這背后，有一位默默掌控全局的 “指揮官”，它就是 Linux 進(jìn)程調(diào)度器。想象一下，當(dāng)你在電腦上同時(shí)打開(kāi)多個(gè)應(yīng)用程序，一邊瀏覽網(wǎng)頁(yè)，一邊播放音樂(lè)，還在運(yùn)行著辦公軟件，這些進(jìn)程看似和諧共處，實(shí)則在激烈競(jìng)爭(zhēng)著有限的 CPU 資源。

那么，究竟是誰(shuí)在有條不紊地安排它們的執(zhí)行順序，讓整個(gè)系統(tǒng)能夠高效穩(wěn)定地運(yùn)行呢？沒(méi)錯(cuò)，就是 Linux 進(jìn)程調(diào)度器。今天，就讓我們一同走進(jìn)這個(gè)神秘的領(lǐng)域，揭開(kāi) Linux 進(jìn)程調(diào)度器的神秘面紗，看看它是如何在幕后指揮著這場(chǎng)進(jìn)程 “交響樂(lè)” 的 。

一、進(jìn)程調(diào)度簡(jiǎn)介

進(jìn)程調(diào)度是操作系統(tǒng)最重要的內(nèi)容之一，也是學(xué)習(xí)操作系統(tǒng)的重點(diǎn)和難點(diǎn)。關(guān)于進(jìn)程調(diào)度，我們首先就會(huì)問(wèn)出一些問(wèn)題，什么是進(jìn)程調(diào)度，為什么要進(jìn)程調(diào)度，如何進(jìn)行調(diào)度。下面我們用一幅圖把這些問(wèn)題關(guān)聯(lián)起來(lái)：

圖片

這張圖把進(jìn)程調(diào)度的所有問(wèn)題和知識(shí)點(diǎn)都關(guān)聯(lián)了起來(lái)，本文后面所有的內(nèi)容都是對(duì)這張圖的解釋和擴(kuò)展延伸，下面讓我們來(lái)一一講解。

⑴什么是調(diào)度

什么是調(diào)度？調(diào)度是CPU資源管理器。操作系統(tǒng)的作用之一就是系統(tǒng)資源管理器。CPU是計(jì)算機(jī)系統(tǒng)中最重要的資源，當(dāng)然也要管理。所有進(jìn)程的運(yùn)行都需要CPU，對(duì)CPU該如何管理呢？對(duì)于直接共享型的事物，我們有兩種管理方法：一種是時(shí)間分割管理，另一種是空間分割管理。由于CPU自身的特性，沒(méi)有空間分割相似性，只有時(shí)間分割相似性，所以我們只能對(duì)CPU進(jìn)行時(shí)間分割管理。對(duì)CPU進(jìn)行時(shí)間分割管理的具體做法就叫做進(jìn)程調(diào)度。

那么調(diào)度的是什么呢？進(jìn)程調(diào)度，調(diào)度的當(dāng)然是進(jìn)程啦，也對(duì)也不對(duì)。我們知道進(jìn)程是資源分配的單位，線程是執(zhí)行的單位。早期的時(shí)候沒(méi)有多線程，進(jìn)程就是線程，線程就是進(jìn)程，所以此時(shí)進(jìn)程調(diào)度調(diào)度的是進(jìn)程。但是當(dāng)有了多線程之后，線程變成了執(zhí)行的單位，進(jìn)程不再是執(zhí)行的單位，進(jìn)程調(diào)度調(diào)度的就是線程了。不過(guò)由于歷史原因，大家都習(xí)慣叫進(jìn)程調(diào)度，所以現(xiàn)在這個(gè)領(lǐng)域的名稱還是叫進(jìn)程調(diào)度。后文中說(shuō)到調(diào)度進(jìn)程的地方都是調(diào)度的線程，由于習(xí)慣問(wèn)題，我們還說(shuō)調(diào)度進(jìn)程不說(shuō)調(diào)度線程，請(qǐng)大家要注意。

對(duì)線程的調(diào)度可以有兩種方式：一種是直接調(diào)度線程，不考慮它們所屬的進(jìn)程，這種方式叫做直接調(diào)度或者一級(jí)調(diào)度；另一種是先調(diào)度進(jìn)程，再在進(jìn)程內(nèi)部調(diào)度線程，這種方式叫做間接調(diào)度或者二級(jí)調(diào)度。POSIX規(guī)定，操作系統(tǒng)可以選擇這兩種方式中的任何一種都行。Linux選擇的是一級(jí)調(diào)度，為什么會(huì)這么選擇呢？主要是為了提高進(jìn)程的并發(fā)性，充分利用多CPU多核的優(yōu)勢(shì)。如果使用二級(jí)調(diào)度的話，看似每個(gè)進(jìn)程之間都公平了，但是有些進(jìn)程的計(jì)算量比較大，就無(wú)法通過(guò)多開(kāi)線程提高自己的性能，這樣對(duì)系統(tǒng)整體的性能是有害的，也不利用發(fā)揮計(jì)算機(jī)多CPU的優(yōu)勢(shì)。一級(jí)調(diào)度看似對(duì)有些進(jìn)程不公平，但是計(jì)算量小的進(jìn)程少開(kāi)線程，計(jì)算量大的進(jìn)程多開(kāi)線程，相對(duì)還是很公平的。

就像國(guó)家希望每個(gè)企業(yè)都做大做強(qiáng)，但是同時(shí)也會(huì)反壟斷一樣。Linux也推出了cgroup組調(diào)度機(jī)制，來(lái)限制某個(gè)或者某一類進(jìn)程對(duì)CPU資源的過(guò)度占用。本文中不講cgroup組調(diào)度機(jī)制，后文的講解都是假設(shè)沒(méi)有cgroup組調(diào)度。

⑵為什么要調(diào)度

我們知道了什么是調(diào)度，那么為什么要調(diào)度呢，沒(méi)有調(diào)度會(huì)怎么樣呢？最早的計(jì)算機(jī)是沒(méi)有調(diào)度的，程序只能一個(gè)一個(gè)地運(yùn)行，一個(gè)進(jìn)程死亡之后才能去運(yùn)行下一個(gè)進(jìn)程。這里面首先存在的問(wèn)題就是我們沒(méi)法同時(shí)運(yùn)行多個(gè)進(jìn)程。其次就算我們不需要同時(shí)運(yùn)行多個(gè)進(jìn)程，程序在運(yùn)行的過(guò)程中如果要等IO，CPU就只能空轉(zhuǎn)，這也十分浪費(fèi)CPU資源。

于是最早的多任務(wù)——協(xié)作式多任務(wù)誕生了，當(dāng)程序由于要等IO而阻塞時(shí)就會(huì)去調(diào)度執(zhí)行其它的進(jìn)程。但是協(xié)作式多任務(wù)存在著很大的問(wèn)題，就是每個(gè)進(jìn)程運(yùn)行的時(shí)間片長(zhǎng)短是不確定的，而且是很偶然很隨機(jī)的。如果一個(gè)進(jìn)程它一直在做運(yùn)算就是不進(jìn)行IO操作，那么它就會(huì)一直霸占CPU。

針對(duì)這個(gè)問(wèn)題，當(dāng)時(shí)想出的方法是道德解決方案。內(nèi)核向進(jìn)程提供系統(tǒng)調(diào)用sched_yield，它會(huì)使進(jìn)程主動(dòng)放棄CPU讓其它進(jìn)程來(lái)執(zhí)行。然后要求所有的程序員在程序中合適的地方盡量多地加入sched_yield調(diào)用。這個(gè)方法在當(dāng)時(shí)是管用的，因?yàn)楫?dāng)時(shí)計(jì)算機(jī)的使用者(同時(shí)也是程序員)僅限于少數(shù)科研機(jī)構(gòu)和政府機(jī)關(guān)的部分人員，一臺(tái)電腦的共同使用者都認(rèn)識(shí)，面子上還得過(guò)得去。

后來(lái)隨著計(jì)算機(jī)的普及，以及計(jì)算機(jī)的使用者和程序員這兩個(gè)角色的分離，主要靠道德約束的協(xié)作式多任務(wù)已經(jīng)行不通了，我們需要強(qiáng)制性多任務(wù)，也就是搶占式多任務(wù)。搶占式多任務(wù)使得每個(gè)進(jìn)程都可以相對(duì)公平地平分CPU時(shí)間，如果一個(gè)進(jìn)程運(yùn)行了過(guò)長(zhǎng)的時(shí)間就會(huì)被強(qiáng)制性地調(diào)度出去，不管這個(gè)進(jìn)程是否愿意。

有了搶占式多任務(wù)，我們?cè)诤暧^上不僅可以同時(shí)運(yùn)行多個(gè)進(jìn)程，而且它們會(huì)一起齊頭并進(jìn)地往前運(yùn)行，不會(huì)出現(xiàn)某個(gè)進(jìn)程被餓死的情況，這樣我們使用電腦的體驗(yàn)就非常完美了。搶占式多任務(wù)和協(xié)作式多任務(wù)不是對(duì)立的，它們是相互獨(dú)立的，可以同時(shí)存在于系統(tǒng)中。

搶占又分為用戶搶占和內(nèi)核搶占。由于搶占對(duì)進(jìn)程來(lái)說(shuō)是異步的，進(jìn)程被搶占時(shí)不一定運(yùn)行在什么地方，有可能運(yùn)行在用戶空間，也有可能運(yùn)行在內(nèi)核空間(進(jìn)程通過(guò)系統(tǒng)調(diào)用進(jìn)入內(nèi)核空間)。如果搶占點(diǎn)是在用戶空間，那么搶占就是安全的，如果在內(nèi)核空間就不一定安全，這是為什么呢？因?yàn)閷?duì)于用戶空間來(lái)說(shuō)，如果搶占會(huì)導(dǎo)致線程同步問(wèn)題，那么用戶空間有責(zé)任使用線程同步機(jī)制來(lái)保護(hù)臨界區(qū)，只要用戶空間做好同步就不會(huì)出問(wèn)題。

如果內(nèi)核也做好了同步措施，內(nèi)核搶占也不會(huì)出問(wèn)題，但是內(nèi)核最初的設(shè)計(jì)就沒(méi)有考慮內(nèi)核搶占問(wèn)題，所以剛開(kāi)始的時(shí)候內(nèi)核是不能搶占的。后來(lái)內(nèi)核開(kāi)發(fā)者對(duì)內(nèi)核進(jìn)行了完善，把內(nèi)核所有的臨界區(qū)都加上了同步措施，然后內(nèi)核就是可搶占的了。內(nèi)核能搶占了不代表內(nèi)核一定會(huì)搶占，內(nèi)核會(huì)不會(huì)搶占由config選項(xiàng)控制，可以開(kāi)啟也可以關(guān)閉，因?yàn)閮?nèi)核搶占還會(huì)影響系統(tǒng)的響應(yīng)性和性能。

開(kāi)啟內(nèi)核搶占會(huì)提高系統(tǒng)的響應(yīng)性但是會(huì)降低一點(diǎn)性能，關(guān)閉內(nèi)核搶占會(huì)降低系統(tǒng)的響應(yīng)性但是會(huì)提高一點(diǎn)性能。因此把內(nèi)核搶占做成配置項(xiàng)，可以讓大家靈活配置。服務(wù)器系統(tǒng)一般不需要與用戶交互，所以會(huì)關(guān)閉內(nèi)核搶占來(lái)提高性能，桌面系統(tǒng)會(huì)開(kāi)啟內(nèi)核搶占來(lái)提高系統(tǒng)的響應(yīng)性，來(lái)增加用戶體驗(yàn)。

現(xiàn)在我們?cè)賮?lái)看一下為什么要調(diào)度。因?yàn)槿绻麤](méi)有調(diào)度的話，就不能實(shí)現(xiàn)多任務(wù)，一次就只能運(yùn)行一個(gè)程序，我們使用電腦的體驗(yàn)就會(huì)大大降低。有了調(diào)度就有了多任務(wù)，我們就能同時(shí)在電腦上做很多事情，使用體驗(yàn)就會(huì)非常好。

⑶為什么能調(diào)度

我們?cè)賮?lái)看看為什么能調(diào)度呢。我們把協(xié)作式多任務(wù)叫做主動(dòng)調(diào)度，搶占式多任務(wù)叫做被動(dòng)調(diào)度。為什么能調(diào)度分為兩部分：為什么能觸發(fā)調(diào)度和為什么能執(zhí)行調(diào)度。對(duì)于主動(dòng)調(diào)度，調(diào)度是進(jìn)程主動(dòng)觸發(fā)的，這個(gè)是肯定能的。對(duì)于被動(dòng)調(diào)度，在圖靈機(jī)模型中是做不到的，因?yàn)閳D靈機(jī)是一條線性一直往前走的，進(jìn)程在執(zhí)行時(shí)，進(jìn)程要是不主動(dòng)，是不可能跳到其它進(jìn)程來(lái)執(zhí)行的。

被動(dòng)調(diào)度能做到的原因關(guān)鍵就在于中斷機(jī)制，因?yàn)橹袛嗍菑?qiáng)行在正常的執(zhí)行流中插入了一段代碼，它能改變后續(xù)代碼的走向。有了中斷機(jī)制，我們就可以創(chuàng)建一個(gè)定時(shí)器中斷，以固定的時(shí)間間隔比如每10ms來(lái)觸發(fā)中斷，檢測(cè)進(jìn)程是否運(yùn)行時(shí)間過(guò)長(zhǎng)，如果過(guò)長(zhǎng)就觸發(fā)調(diào)度。這樣任何進(jìn)程都不可能霸占CPU，所以進(jìn)程都能公平地共享CPU時(shí)間。

圖片

可以看到在純圖靈機(jī)模型中，進(jìn)程如果不主動(dòng)進(jìn)行調(diào)度，是沒(méi)有外力強(qiáng)迫進(jìn)程進(jìn)行調(diào)度的，進(jìn)程就能一直霸占CPU。有了中斷機(jī)制之后，在中斷的處理中可以觸發(fā)調(diào)度，在中斷返回的點(diǎn)可以執(zhí)行調(diào)度，這樣就可以避免進(jìn)程霸占CPU了。

前面說(shuō)的是為何能觸發(fā)進(jìn)程調(diào)度，主動(dòng)調(diào)度是進(jìn)程自己觸發(fā)的，被動(dòng)調(diào)度是在中斷中觸發(fā)的?，F(xiàn)在來(lái)看看為何能執(zhí)行調(diào)度，執(zhí)行調(diào)度包括兩部分：選擇進(jìn)程和切換進(jìn)程。選擇進(jìn)程是純軟件的，肯定能實(shí)現(xiàn)。切換進(jìn)程是怎么切換呢？一個(gè)進(jìn)程執(zhí)行得好好的，怎么就切換了呢，需不需要硬件的支持呢？進(jìn)程切換主要是切換執(zhí)行棧和用戶空間，這兩個(gè)都需要用到CPU特定的指令。

⑷何時(shí)調(diào)度

我們前面已經(jīng)講了主動(dòng)調(diào)度(協(xié)作式多任務(wù))和被動(dòng)調(diào)度(搶占式多任務(wù))。

對(duì)于主動(dòng)調(diào)度，觸發(fā)調(diào)度和執(zhí)行調(diào)度是同步的、一體的，觸發(fā)即執(zhí)行。主動(dòng)調(diào)度發(fā)生的時(shí)機(jī)有IO等待、加鎖失敗等各種阻塞操作以及用戶空間主動(dòng)調(diào)用sched_yield。

對(duì)于被動(dòng)調(diào)度，觸發(fā)調(diào)度和執(zhí)行調(diào)度是異步的、分離的，觸發(fā)調(diào)度并不會(huì)立馬執(zhí)行調(diào)度，而是做個(gè)需要調(diào)度的標(biāo)記，然后在之后的某個(gè)合適的地方會(huì)檢測(cè)這個(gè)標(biāo)記，如果被設(shè)置就進(jìn)行調(diào)度。觸發(fā)調(diào)度的點(diǎn)有：在定時(shí)器中斷中發(fā)現(xiàn)當(dāng)前進(jìn)程超時(shí)了，在喚醒進(jìn)程時(shí)發(fā)現(xiàn)新進(jìn)程需要搶占當(dāng)前進(jìn)程，在遷移進(jìn)程時(shí)發(fā)現(xiàn)新進(jìn)程需要搶占當(dāng)前進(jìn)程，在改變進(jìn)程優(yōu)先級(jí)時(shí)發(fā)現(xiàn)新進(jìn)程需要搶占當(dāng)前進(jìn)程。

其中第一個(gè)觸發(fā)點(diǎn)是當(dāng)前進(jìn)程需要被搶占，它是用來(lái)保證公平調(diào)度，防止進(jìn)程霸占CPU的，后三個(gè)觸發(fā)點(diǎn)是新進(jìn)程需要搶占當(dāng)前進(jìn)程，它是用來(lái)提高系統(tǒng)響應(yīng)性的。執(zhí)行調(diào)度的點(diǎn)有：系統(tǒng)調(diào)用完成之后即將返回用戶空間，中斷完成之后即將返回用戶空間，如果開(kāi)啟了內(nèi)核搶占的話則還有,中斷完成之后即將返回內(nèi)核,如果中斷發(fā)生在禁止搶占臨界區(qū)中，那么中斷完成之后返回內(nèi)核是不會(huì)執(zhí)行調(diào)度的，而是會(huì)在臨界區(qū)結(jié)束的時(shí)候執(zhí)行調(diào)度。

圖片

系統(tǒng)調(diào)用完成之后即將返回用戶空間和中斷完成之后即將返回用戶空間，是非常好的執(zhí)行進(jìn)行調(diào)度的點(diǎn)，也就是此圖中的三個(gè)箭頭的地方。CPU異常在意義上不是系統(tǒng)調(diào)用，但是在形式上和邏輯上相當(dāng)于是系統(tǒng)調(diào)用。

圖片

圖片

中斷發(fā)生在內(nèi)核空間的場(chǎng)景，如果開(kāi)啟了內(nèi)核搶占，如果被搶占的內(nèi)核代碼不是在禁用搶占臨界區(qū)，中斷返回時(shí)是執(zhí)行調(diào)度的點(diǎn)。如果被搶占的內(nèi)核代碼在禁用搶占臨界區(qū)中，在執(zhí)行調(diào)度的點(diǎn)被推遲到了臨界區(qū)的出口處。

⑸如何調(diào)度

現(xiàn)在到了執(zhí)行調(diào)度的時(shí)刻了。執(zhí)行調(diào)度分為兩步：一是選擇下一個(gè)要執(zhí)行的進(jìn)程，二是切換進(jìn)程。選擇下一個(gè)要執(zhí)行的進(jìn)程，這就是調(diào)度算法了。首先調(diào)度算法只能從Runnable的進(jìn)程中進(jìn)行選擇，不能選擇Blocked進(jìn)程，因?yàn)檫x擇了也沒(méi)有意義。其次算法還要區(qū)分進(jìn)程類型，比如普通進(jìn)程與實(shí)時(shí)進(jìn)程，肯定要優(yōu)先選擇實(shí)時(shí)進(jìn)程，在同一類型的進(jìn)程中還要有具體的算法來(lái)決定到底選擇哪個(gè)進(jìn)程。在Linux中一共把進(jìn)程分為了5類，每一類都有一個(gè)具體的算法。類之間的關(guān)系是優(yōu)先選擇高類的進(jìn)程，只有當(dāng)高類沒(méi)有Runnable進(jìn)程時(shí)才會(huì)去選擇低類進(jìn)程。

進(jìn)程選擇好了之后就要切換進(jìn)程了。切換進(jìn)程分兩步：第一步是切換用戶空間，第二步是切換執(zhí)行棧(線程棧)。如果要切換的兩個(gè)線程屬于同一個(gè)進(jìn)程就不需要切換用戶空間了。切換用戶空間是一個(gè)CPU架構(gòu)相關(guān)的事情，在x86 CPU上是給CR3寄存器賦值新進(jìn)程的頁(yè)表樹(shù)的根指針。

此時(shí)切換的執(zhí)行棧是線程的內(nèi)核棧，執(zhí)行棧代表的是當(dāng)前線程的執(zhí)行情況，切換執(zhí)行棧就是切換線程。線程的用戶棧信息都在內(nèi)核棧里保存著。切換完內(nèi)核棧之后，線程繼續(xù)執(zhí)行就會(huì)返回用戶空間，由于此時(shí)用戶空間已經(jīng)切換完成，內(nèi)核棧上也保存著用戶棧的信息，所以線程能返回到正確的用戶空間線程上去。下面我們畫(huà)個(gè)圖來(lái)看一下：

圖片

對(duì)于一個(gè)CPU來(lái)說(shuō)，永遠(yuǎn)只有一個(gè)當(dāng)前進(jìn)程在運(yùn)行，當(dāng)執(zhí)行進(jìn)程調(diào)度時(shí)，需要從其它進(jìn)程中選擇一個(gè)進(jìn)程，把它旋轉(zhuǎn)到最下方作為當(dāng)前進(jìn)程，它就開(kāi)始運(yùn)行了。

⑹調(diào)度均衡

前面所說(shuō)的都是針對(duì)一個(gè)CPU的情況，對(duì)于多個(gè)CPU來(lái)說(shuō)，每個(gè)CPU也是這樣的邏輯。但是有一點(diǎn)不同的是，如果一個(gè)系統(tǒng)上的多個(gè)CPU忙的忙死閑的閑死，顯然不太好，因此多個(gè)CPU之間會(huì)進(jìn)行調(diào)度均衡。調(diào)度均衡可以分為個(gè)體均衡和總體均衡。個(gè)體均衡是從進(jìn)程的角度出發(fā)選擇到一個(gè)相對(duì)清閑的CPU上去運(yùn)行。總體均衡是從CPU的角度出發(fā)如何從別的CPU上拉取一些進(jìn)程到自己這來(lái)執(zhí)行，使得所有CPU的工作量盡量平均。

個(gè)體均衡的觸發(fā)點(diǎn)有三個(gè)：一是新進(jìn)程剛創(chuàng)建時(shí)，二是進(jìn)程要執(zhí)行新程序時(shí)，三是進(jìn)程被喚醒時(shí)，在這三個(gè)點(diǎn)進(jìn)程都可以選擇去哪個(gè)CPU的運(yùn)行隊(duì)列上去等待執(zhí)行。在個(gè)體均衡下，每個(gè)進(jìn)程都盡量選擇相對(duì)清閑的CPU，所以所有CPU的負(fù)載應(yīng)該還是會(huì)比較均衡的。但是時(shí)間長(zhǎng)了可能還是會(huì)出現(xiàn)負(fù)載不均衡的情況，此時(shí)就要進(jìn)行總體均衡了。總體均衡的觸發(fā)點(diǎn)有三個(gè)：一是CPU即將idle前會(huì)去找到最忙的CPU然后拉取一些任務(wù)過(guò)來(lái)；二是定時(shí)器中斷的周期性檢測(cè)，會(huì)檢查是否所有的CPU都一樣忙，如果忙閑差別太大就會(huì)進(jìn)行進(jìn)程遷移，使得所有CPU忙閑程度接近；三是在idle進(jìn)程中如果CPU發(fā)現(xiàn)自己太忙而有的CPU在idle就會(huì)喚醒那個(gè)CPU進(jìn)行負(fù)載均衡。

二、基礎(chǔ)概念解析

2.1進(jìn)程的定義與分類

在計(jì)算機(jī)系統(tǒng)中，進(jìn)程堪稱最基礎(chǔ)且重要的概念之一。從本質(zhì)上講，進(jìn)程是程序在計(jì)算機(jī)中的一次動(dòng)態(tài)執(zhí)行過(guò)程。打個(gè)比方，當(dāng)你在 Linux 系統(tǒng)中啟動(dòng)一個(gè)應(yīng)用程序，如文本編輯器，系統(tǒng)便會(huì)為該程序創(chuàng)建一個(gè)進(jìn)程，這個(gè)進(jìn)程涵蓋了程序運(yùn)行所需的各種資源，包括代碼、數(shù)據(jù)、打開(kāi)的文件以及分配的內(nèi)存空間等。

進(jìn)程可以依據(jù)不同的標(biāo)準(zhǔn)進(jìn)行分類。常見(jiàn)的分類方式有：按照對(duì)資源的需求特性，可分為 I/O 受限型進(jìn)程和 CPU 受限型進(jìn)程 。I/O 受限型進(jìn)程，正如其名，這類進(jìn)程的執(zhí)行過(guò)程中，大部分時(shí)間都在等待 I/O 操作的完成，例如讀取文件、網(wǎng)絡(luò)請(qǐng)求等，像瀏覽器在加載網(wǎng)頁(yè)時(shí)，就需要頻繁地進(jìn)行網(wǎng)絡(luò) I/O 操作，此時(shí)它就是一個(gè)典型的 I/O 受限型進(jìn)程。而 CPU 受限型進(jìn)程則主要將時(shí)間花費(fèi)在 CPU 的計(jì)算上，像一些科學(xué)計(jì)算程序、加密算法程序等，它們需要大量的 CPU 計(jì)算資源來(lái)完成復(fù)雜的運(yùn)算任務(wù)。

依據(jù)進(jìn)程的實(shí)時(shí)性要求，進(jìn)程又可分為實(shí)時(shí)進(jìn)程和普通進(jìn)程 。實(shí)時(shí)進(jìn)程對(duì)響應(yīng)時(shí)間有著極高的要求，必須在規(guī)定的時(shí)間內(nèi)完成任務(wù)，否則可能會(huì)導(dǎo)致嚴(yán)重的后果。以工業(yè)控制系統(tǒng)中的實(shí)時(shí)監(jiān)控進(jìn)程為例，它需要實(shí)時(shí)采集傳感器的數(shù)據(jù)，并及時(shí)做出響應(yīng)，以確保生產(chǎn)過(guò)程的安全和穩(wěn)定。如果這個(gè)進(jìn)程不能在規(guī)定時(shí)間內(nèi)完成數(shù)據(jù)采集和處理，就可能引發(fā)生產(chǎn)事故。相比之下，普通進(jìn)程對(duì)響應(yīng)時(shí)間的要求相對(duì)寬松，它們可以在系統(tǒng)資源允許的情況下，逐步完成任務(wù)，如我們?nèi)粘Ｊ褂玫奈谋揪庉?、文件下載等操作對(duì)應(yīng)的進(jìn)程。

2.2進(jìn)程狀態(tài)詳解

Linux 進(jìn)程有多種狀態(tài)，常見(jiàn)的狀態(tài)包括：

• R（可執(zhí)行狀態(tài)）：進(jìn)程處于 ready 狀態(tài)，即隨時(shí)可以執(zhí)行。在系統(tǒng)中，處于這個(gè)狀態(tài)的進(jìn)程意味著它已經(jīng)具備了運(yùn)行的條件，只等待被分配 CPU 資源。
• S（可中斷睡眠狀態(tài)）：可以中斷的睡眠狀態(tài)。當(dāng)進(jìn)程接受消息隊(duì)列、執(zhí)行 sleep 等操作時(shí)，進(jìn)程處于阻塞狀態(tài)（S）。這種狀態(tài)下的進(jìn)程可以被某些信號(hào)中斷，從而轉(zhuǎn)換狀態(tài)。例如，當(dāng)接收到特定的信號(hào)時(shí)，進(jìn)程可以從睡眠狀態(tài)被喚醒，進(jìn)入可執(zhí)行狀態(tài)。
• D（不可中斷睡眠狀態(tài)）：不可中斷的睡眠狀態(tài)，比較少見(jiàn)。處于這種狀態(tài)的進(jìn)程通常在等待某些關(guān)鍵資源，并且不能被一般的信號(hào)中斷。比如在等待磁盤(pán) I/O 完成的過(guò)程中，進(jìn)程可能處于不可中斷睡眠狀態(tài)。
• T（暫?；蛘吒櫊顟B(tài)）：暫停狀態(tài)是指進(jìn)程收到 sigstopt 信號(hào)變?yōu)闀和顟B(tài)，跟蹤狀態(tài)則是在被調(diào)試或跟蹤時(shí)的狀態(tài)。例如，在使用調(diào)試工具時(shí)，進(jìn)程可以被設(shè)置為跟蹤狀態(tài)，以便開(kāi)發(fā)者觀察其執(zhí)行過(guò)程。
• Z（僵尸狀態(tài)）：退出狀態(tài)，進(jìn)程稱為僵尸進(jìn)程（子進(jìn)程退出）。當(dāng)子進(jìn)程完成任務(wù)后，它會(huì)進(jìn)入僵尸狀態(tài)，等待父進(jìn)程讀取其退出狀態(tài)信息。如果父進(jìn)程沒(méi)有及時(shí)處理，僵尸進(jìn)程會(huì)一直占用系統(tǒng)資源。
• X（退出狀態(tài)，進(jìn)程即將被銷毀）：退出狀態(tài)，進(jìn)程即將被銷毀。當(dāng)進(jìn)程完成所有任務(wù)并釋放了所有資源后，會(huì)進(jìn)入這個(gè)狀態(tài)，等待系統(tǒng)最終清理。

進(jìn)程狀態(tài)之間可以相互轉(zhuǎn)換。一般來(lái)說(shuō)，進(jìn)程可能從可執(zhí)行狀態(tài)（R）進(jìn)入睡眠狀態(tài)（S 或 D），當(dāng)?shù)却氖录l(fā)生時(shí)，又從睡眠狀態(tài)轉(zhuǎn)換回可執(zhí)行狀態(tài)。如果進(jìn)程收到暫停信號(hào)，會(huì)從可執(zhí)行狀態(tài)轉(zhuǎn)換為暫停狀態(tài)（T），收到繼續(xù)執(zhí)行的信號(hào)后再轉(zhuǎn)換回可執(zhí)行狀態(tài)。當(dāng)進(jìn)程完成任務(wù)后，會(huì)從可執(zhí)行狀態(tài)轉(zhuǎn)換為退出狀態(tài)（Z 或 X）。

三、常見(jiàn)調(diào)度策略

3.1實(shí)時(shí)調(diào)度策略

實(shí)時(shí)調(diào)度策略對(duì)于那些對(duì)時(shí)間極為敏感的任務(wù)而言，無(wú)疑是至關(guān)重要的保障。在 Linux 系統(tǒng)中，實(shí)時(shí)調(diào)度策略主要包含 DEADLINE、SCHED_FIFO 以及 SCHED_RR 這幾種類型 。

DEADLINE 調(diào)度策略，猶如一位精準(zhǔn)的時(shí)間管家，它主要依據(jù)任務(wù)的截止時(shí)間來(lái)進(jìn)行調(diào)度決策。每個(gè)任務(wù)在創(chuàng)建之初，都會(huì)被分配運(yùn)行時(shí)（Runtime）、周期（Period）以及最后期限（Deadline）這三個(gè)關(guān)鍵參數(shù)。調(diào)度器會(huì)如同嚴(yán)格的監(jiān)工，時(shí)刻緊盯任務(wù)的最后期限，優(yōu)先調(diào)度那些截止時(shí)間最早的任務(wù)。舉例來(lái)說(shuō)，在工業(yè)自動(dòng)化生產(chǎn)線上，傳感器數(shù)據(jù)的實(shí)時(shí)采集與處理任務(wù)就對(duì)時(shí)間有著嚴(yán)苛的要求，DEADLINE 調(diào)度策略能夠確保這些任務(wù)在規(guī)定的時(shí)間內(nèi)完成，從而保障生產(chǎn)線的穩(wěn)定、高效運(yùn)行。

Linux 實(shí)時(shí)進(jìn)程采用 SCHED_FIFO 和 SCHED_RR 調(diào)度算法：

①SCHED_FIFO

特點(diǎn)：實(shí)現(xiàn)了一種簡(jiǎn)單的、先入先出的調(diào)度算法，不使用時(shí)間片。處于可運(yùn)行狀態(tài)的 SCHED_FIFO 級(jí)的進(jìn)程會(huì)比任何 SCHED_NORMAL 級(jí)的進(jìn)程都先得到調(diào)用。一旦一個(gè) SCHED_FIFO 級(jí)進(jìn)程處于可執(zhí)行狀態(tài)，就會(huì)一直執(zhí)行，直到它自己受阻塞或顯式地釋放處理器為止。只有更高優(yōu)先級(jí)的 SCHED_FIFO 或者 SCHED_RR 任務(wù)才能搶占 SCHED_FIFO 任務(wù)。如果有兩個(gè)或者更多的同優(yōu)先級(jí)的 SCHED_FIFO 級(jí)進(jìn)程，它們會(huì)輪流執(zhí)行，但是依然只有在它們?cè)敢庾尦鎏幚砥鲿r(shí)才會(huì)退出。只要有 SCHED_FIFO 級(jí)進(jìn)程在執(zhí)行，其他級(jí)別較低的進(jìn)程就只能等待它變?yōu)椴豢蛇\(yùn)行態(tài)后才有機(jī)會(huì)執(zhí)行。

實(shí)時(shí)優(yōu)先級(jí)的靜態(tài)特性影響：實(shí)時(shí)優(yōu)先級(jí)只有靜態(tài)優(yōu)先級(jí)，不會(huì)調(diào)整優(yōu)先級(jí)，默認(rèn)優(yōu)先級(jí)為 0 - 99（MAX_RT_PRIO = 100）。這意味著一旦確定了實(shí)時(shí)進(jìn)程的優(yōu)先級(jí)，在整個(gè)運(yùn)行過(guò)程中它不會(huì)因?yàn)槠渌蛩囟淖?，保證了高優(yōu)先級(jí)的實(shí)時(shí)進(jìn)程能夠在需要時(shí)盡快得到執(zhí)行。

②SCHED_RR

特點(diǎn)：與 SCHED_FIFO 大體相同，只是 SCHED_RR 級(jí)的進(jìn)程在耗盡事先分配給它的時(shí)間后就不能再繼續(xù)執(zhí)行了。也就是說(shuō)，SCHED_RR 是帶有時(shí)間片的 SCHED_FIFO，是一種實(shí)時(shí)輪流調(diào)度算法。當(dāng) SCHED_RR 任務(wù)耗盡它的時(shí)間片時(shí)，在同一優(yōu)先級(jí)的其他實(shí)時(shí)進(jìn)程被輪流調(diào)度。時(shí)間片只用來(lái)重新調(diào)度同一優(yōu)先級(jí)的進(jìn)程。對(duì)于 SCHED_FIFO 進(jìn)程，優(yōu)先級(jí)總是立即搶占低優(yōu)先級(jí)，但低優(yōu)先級(jí)進(jìn)程決不能搶占 SCHED_RR 任務(wù)，即使它的時(shí)間片耗盡。

實(shí)時(shí)優(yōu)先級(jí)的靜態(tài)特性影響：同樣，由于實(shí)時(shí)優(yōu)先級(jí)是靜態(tài)的，SCHED_RR 進(jìn)程在確定了優(yōu)先級(jí)后，其執(zhí)行順序和時(shí)間片的分配都是基于這個(gè)固定的優(yōu)先級(jí)。這使得系統(tǒng)在處理實(shí)時(shí)任務(wù)時(shí)能夠有明確的調(diào)度規(guī)則，確保關(guān)鍵任務(wù)能夠在規(guī)定的時(shí)間內(nèi)得到執(zhí)行。

3.2完全公平調(diào)度策略（CFS）

完全公平調(diào)度策略（CFS）是 Linux 進(jìn)程調(diào)度器的核心組成部分，其設(shè)計(jì)理念精妙絕倫，旨在為系統(tǒng)中的每個(gè)進(jìn)程都提供公平的 CPU 時(shí)間分配。

CFS 的核心思想建立在虛擬運(yùn)行時(shí)間（vruntime）這一創(chuàng)新概念之上。簡(jiǎn)單來(lái)講，虛擬運(yùn)行時(shí)間是一個(gè)相對(duì)值，它用于衡量每個(gè)進(jìn)程在 CPU 上的執(zhí)行時(shí)間份額。每個(gè)進(jìn)程都擁有一個(gè)屬于自己的 vruntime，其數(shù)值會(huì)隨著進(jìn)程的運(yùn)行而不斷增加。不過(guò)，這里存在一個(gè)關(guān)鍵的區(qū)別，那就是不同優(yōu)先級(jí)的進(jìn)程，其 vruntime 的增加速度并不相同。具體而言，高優(yōu)先級(jí)的進(jìn)程，其 vruntime 的增長(zhǎng)速度相對(duì)較慢；而低優(yōu)先級(jí)的進(jìn)程，vruntime 的增長(zhǎng)速度則會(huì)更快。這就好比在一場(chǎng)比賽中，高優(yōu)先級(jí)的選手被賦予了較慢的前進(jìn)速度，而低優(yōu)先級(jí)的選手則以較快的速度前進(jìn)，這樣一來(lái)，最終的結(jié)果是所有選手在虛擬的時(shí)間賽道上能夠相對(duì)公平地競(jìng)爭(zhēng)。

為了更直觀地理解，我們不妨假設(shè)系統(tǒng)中有兩個(gè)進(jìn)程 A 和 B，進(jìn)程 A 的優(yōu)先級(jí)較高，進(jìn)程 B 的優(yōu)先級(jí)較低。在開(kāi)始時(shí)，它們的 vruntime 都為 0。隨著時(shí)間的推移，進(jìn)程 A 和 B 都開(kāi)始運(yùn)行。由于進(jìn)程 A 的優(yōu)先級(jí)高，它的 vruntime 增長(zhǎng)速度較慢，假設(shè)在一段時(shí)間內(nèi)，進(jìn)程 A 的 vruntime 只增加了 1；而進(jìn)程 B 由于優(yōu)先級(jí)低，其 vruntime 增長(zhǎng)速度較快，在相同的時(shí)間內(nèi)，進(jìn)程 B 的 vruntime 增加了 3。此時(shí)，調(diào)度器在進(jìn)行調(diào)度決策時(shí)，會(huì)優(yōu)先選擇 vruntime 值最小的進(jìn)程，也就是進(jìn)程 A。這樣，高優(yōu)先級(jí)的進(jìn)程 A 就能夠得到更多的 CPU 運(yùn)行時(shí)間，同時(shí)，低優(yōu)先級(jí)的進(jìn)程 B 也不會(huì)被完全忽視，依然有機(jī)會(huì)在合適的時(shí)候運(yùn)行。

在 CFS 的實(shí)現(xiàn)過(guò)程中，使用了紅黑樹(shù)這種高效的數(shù)據(jù)結(jié)構(gòu)來(lái)管理所有進(jìn)程。紅黑樹(shù)以 vruntime 作為鍵值，將所有可運(yùn)行的進(jìn)程按照 vruntime 的大小進(jìn)行排序。這樣，在每次進(jìn)行調(diào)度時(shí)，調(diào)度器只需要從紅黑樹(shù)的最左端選取 vruntime 值最小的進(jìn)程，即可實(shí)現(xiàn)高效、公平的調(diào)度。這種方式不僅保證了進(jìn)程間的公平性，還能夠有效減少調(diào)度的開(kāi)銷，提高系統(tǒng)的整體性能。

完全公平調(diào)度算法依賴于虛擬時(shí)鐘，用以度量等待進(jìn)程在完全公平系統(tǒng)中所能得到的CPU時(shí)間。但數(shù)據(jù)結(jié)構(gòu)中并沒(méi)有虛擬時(shí)鐘的表示，這是因?yàn)樘摂M時(shí)鐘可以通過(guò)實(shí)際時(shí)鐘，以及與每個(gè)進(jìn)程相關(guān)的負(fù)荷權(quán)重計(jì)算出來(lái)；所有和虛擬時(shí)鐘相關(guān)的計(jì)算都在update_curr中進(jìn)行的，該函數(shù)在系統(tǒng)中各個(gè)不同的地方調(diào)用。

336 static void update_curr(struct cfs_rq *cfs_rq)
 337 {
 338     struct sched_entity *curr = cfs_rq->curr;
 339     u64 now = rq_of(cfs_rq)->clock;
 340     unsigned long delta_exec;
 341 
 342     if (unlikely(!curr))
 343         return;
 344 
 345     /*
 346      * Get the amount of time the current task was running
 347      * since the last time we changed load (this cannot
 348      * overflow on 32 bits):
 349      */
 350     delta_exec = (unsigned long)(now - curr->exec_start);
 351 
 352     __update_curr(cfs_rq, curr, delta_exec);
 353     curr->exec_start = now;
 354 
 355     if (entity_is_task(curr)) {
 356         struct task_struct *curtask = task_of(curr);
 357 
 358         cpuacct_charge(curtask, delta_exec);
 359     }
 360 }

339 rq_of(cfs_rq)->clock 用于實(shí)現(xiàn)就緒隊(duì)列自身的時(shí)鐘，每次調(diào)用周期性調(diào)度器時(shí)，都會(huì)更新clock的值。

350 curr->exec_start保存了上次更改load時(shí)的時(shí)間，注意并不是進(jìn)程的上一次運(yùn)行時(shí)間。當(dāng)前進(jìn)程在一次運(yùn)行過(guò)程中，可能會(huì)發(fā)生多次update_curr。

__update_curr

304 static inline void
 305 __update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
 306           unsigned long delta_exec)
 307 {
 308     unsigned long delta_exec_weighted;
 309     u64 vruntime;
 310 
 311     schedstat_set(curr->exec_max, max((u64)delta_exec, curr->exec_max));
 312 
 313     curr->sum_exec_runtime += delta_exec;
 314     schedstat_add(cfs_rq, exec_clock, delta_exec);
 315     delta_exec_weighted = delta_exec;
 316     if (unlikely(curr->load.weight != NICE_0_LOAD)) {
 317         delta_exec_weighted = calc_delta_fair(delta_exec_weighted,
 318                             &curr->load);
 319     }
 320     curr->vruntime += delta_exec_weighted;
 321 
 322     /*
 323      * maintain cfs_rq->min_vruntime to be a monotonic increasing
 324      * value tracking the leftmost vruntime in the tree.
 325      */
 326     if (first_fair(cfs_rq)) {
 327         vruntime = min_vruntime(curr->vruntime,
 328                 __pick_next_entity(cfs_rq)->vruntime);
 329     } else
 330         vruntime = curr->vruntime;
 331 
 332     cfs_rq->min_vruntime =
 333         max_vruntime(cfs_rq->min_vruntime, vruntime);
 334 }

• 313 sum_exec_runtime 該進(jìn)程消耗的CPU時(shí)間累積值，@delta_exec是上一次更新負(fù)荷統(tǒng)計(jì)量時(shí)兩次的差值，二者都是真實(shí)時(shí)間。
• 316 如果進(jìn)程的優(yōu)先級(jí)為120（nice = 0），那么虛擬時(shí)間和物理時(shí)間相同，否則通過(guò)calc_delta_mine計(jì)算虛擬執(zhí)行時(shí)間。
• 326 first_fait檢測(cè)樹(shù)上是否有最左邊的節(jié)點(diǎn)，即是否有進(jìn)程在樹(shù)上等待調(diào)度。
• 332 cfs_rq->min_vruntime是單調(diào)增加的。

在運(yùn)行過(guò)程中，進(jìn)程調(diào)度實(shí)體的vruntime是單調(diào)增加的，優(yōu)先級(jí)越高的進(jìn)程，增加的速度越慢，因此他們向右移動(dòng)的速度也就越慢。這樣被調(diào)度的機(jī)會(huì)就越大。

延遲跟蹤：內(nèi)核有一個(gè)固有的概念，稱之為調(diào)度延遲，保證每個(gè)進(jìn)程至少被運(yùn)行一次的時(shí)間間隔。

sysctl_sched_latency：參數(shù)用來(lái)控制這個(gè)行為，缺省定義為20ms，可以通過(guò)/proc/sys/kernel/sched_latency_ns來(lái)控制。

sched_nr_latency：控制在一個(gè)延遲周期內(nèi)處理的最大活動(dòng)數(shù)目。如果活動(dòng)進(jìn)程的數(shù)據(jù)超過(guò)了該上限，則延遲周期也成比例的線性擴(kuò)展。

__sched_period：延遲周期的長(zhǎng)度，通常就是sysctl_sched_latency，但是如果有更多的進(jìn)程正在運(yùn)行，那么其值要通過(guò)如下公式計(jì)算：

__sched_period = sysctl_sched_latency * nr_running / sched_nr_latency

在一個(gè)延遲周期內(nèi)，通過(guò)考慮各個(gè)進(jìn)程的權(quán)重，將延遲周期的時(shí)間在活動(dòng)進(jìn)程之間進(jìn)行分配。對(duì)于有某個(gè)調(diào)度實(shí)體表示的給定進(jìn)程，分配到的時(shí)間如下計(jì)算：

static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    u64 slice = __sched_period(cfs_rq->nr_running);
 
    slice *= se->load.weight;
    do_div(slice, cfs_rq->load.weight);
 
    return slice;
}

四、調(diào)度器的工作機(jī)制

4.1進(jìn)程優(yōu)先級(jí)的確定

在 Linux 進(jìn)程調(diào)度的復(fù)雜體系中，進(jìn)程優(yōu)先級(jí)的確定猶如精密儀器的校準(zhǔn)，是保障系統(tǒng)高效、穩(wěn)定運(yùn)行的關(guān)鍵環(huán)節(jié)。這一過(guò)程并非簡(jiǎn)單隨意，而是受到諸多因素的綜合影響，其中，Nice 值和 Priority 權(quán)重值起著核心作用。

Nice 值，作為用戶可以對(duì)進(jìn)程優(yōu)先級(jí)進(jìn)行調(diào)整的重要手段，其取值范圍在 - 20 到 19 之間 。這里需要明確的是，數(shù)值越小，代表進(jìn)程的優(yōu)先級(jí)越高。例如，當(dāng)一個(gè)進(jìn)程的 Nice 值被設(shè)置為 - 10 時(shí)，相較于 Nice 值為 5 的進(jìn)程，它在 CPU 資源競(jìng)爭(zhēng)中會(huì)更具優(yōu)勢(shì)，更有可能優(yōu)先獲得 CPU 的執(zhí)行時(shí)間。

通常情況下，普通用戶僅能將 Nice 值設(shè)置在 0 到 19 的區(qū)間內(nèi)，這意味著普通用戶只能降低自己進(jìn)程的優(yōu)先級(jí)，以避免對(duì)系統(tǒng)中其他重要進(jìn)程造成資源搶占。而超級(jí)用戶則擁有更大的權(quán)限，能夠在 - 20 到 19 的全范圍內(nèi)進(jìn)行調(diào)整，從而根據(jù)系統(tǒng)的實(shí)際需求，靈活地為特定進(jìn)程賦予更高或更低的優(yōu)先級(jí)。比如，在進(jìn)行系統(tǒng)維護(hù)任務(wù)時(shí)，超級(jí)用戶可以將相關(guān)維護(hù)進(jìn)程的 Nice 值設(shè)置為較低數(shù)值，以確保這些任務(wù)能夠優(yōu)先且高效地執(zhí)行。

Priority 權(quán)重值，并非孤立存在，它與 Nice 值緊密關(guān)聯(lián)，共同影響著進(jìn)程的優(yōu)先級(jí) 。系統(tǒng)會(huì)依據(jù)一系列復(fù)雜的算法，結(jié)合 Nice 值以及其他諸如進(jìn)程的資源使用情況、運(yùn)行歷史等因素，來(lái)精確計(jì)算出每個(gè)進(jìn)程的 Priority 權(quán)重值。這個(gè)權(quán)重值就如同進(jìn)程在 CPU 資源分配 “賽場(chǎng)” 上的實(shí)力評(píng)估指標(biāo)，權(quán)重值越高，進(jìn)程在競(jìng)爭(zhēng) CPU 資源時(shí)的地位就越有利，能夠獲得的 CPU 時(shí)間份額也就越多。

例如，對(duì)于一個(gè)長(zhǎng)時(shí)間運(yùn)行且對(duì)系統(tǒng)性能至關(guān)重要的后臺(tái)服務(wù)進(jìn)程，系統(tǒng)可能會(huì)根據(jù)其穩(wěn)定的資源使用情況和重要性，為其分配較高的 Priority 權(quán)重值，從而保證它在多進(jìn)程環(huán)境中能夠持續(xù)、穩(wěn)定地獲得足夠的 CPU 資源，以維持服務(wù)的高效運(yùn)行。

Linux 提供兩種優(yōu)先級(jí)：普通進(jìn)程優(yōu)先級(jí)和實(shí)時(shí)進(jìn)程優(yōu)先級(jí)。

⑴實(shí)時(shí)進(jìn)程優(yōu)先級(jí)：

實(shí)時(shí)優(yōu)先級(jí)采用兩種調(diào)度算法：SCHED_FIFO（先入先出調(diào)度算法）和 SCHED_RR（時(shí)間片輪詢調(diào)度算法）。

實(shí)時(shí)優(yōu)先級(jí)只有靜態(tài)優(yōu)先級(jí)，不會(huì)調(diào)整優(yōu)先級(jí)，默認(rèn)優(yōu)先級(jí)為 0 - 99（MAX_RT_PRIO = 100）。nice 值只影響 100 ~ 100 + 40 的進(jìn)程優(yōu)先級(jí)。

對(duì)于 SCHED_FIFO 算法，只有當(dāng)進(jìn)程執(zhí)行完畢才能輪到其他進(jìn)程執(zhí)行；對(duì)于 SCHED_RR 算法，一旦時(shí)間片消耗完，則將該進(jìn)程放到隊(duì)列末端，其他進(jìn)程才能執(zhí)行。

⑵普通進(jìn)程優(yōu)先級(jí)

普通優(yōu)先級(jí)采用的調(diào)度算法是 SCHED_NORMAL（CFS 調(diào)度器實(shí)現(xiàn)）。

普通優(yōu)先級(jí)根據(jù)動(dòng)態(tài)優(yōu)先級(jí)調(diào)度，動(dòng)態(tài)優(yōu)先級(jí)由靜態(tài)優(yōu)先級(jí)調(diào)整而來(lái)。靜態(tài)優(yōu)先級(jí)由內(nèi)核隱藏，但可以由 nice 值計(jì)算得到：static_prio = MAX_RT_PRIO（默認(rèn) 100）+ nice + 20。nice 取值范圍是 -20 ~ 19，所以靜態(tài)優(yōu)先級(jí)為 100 ~ 139。

進(jìn)程時(shí)間片也是由靜態(tài)優(yōu)先級(jí)得到。如果靜態(tài)優(yōu)先級(jí)小于 120，時(shí)間片為 (140 - static_prio) * 20；如果靜態(tài)優(yōu)先級(jí)大于等于 120，時(shí)間片為 (140 - static_prio) * 5。

動(dòng)態(tài)優(yōu)先級(jí)主要考慮靜態(tài)優(yōu)先級(jí)和進(jìn)程平均運(yùn)行時(shí)間 bouns 值，計(jì)算公式為：dynamic_prio = max (100, min (static_prio - bouns + 5, 139))。當(dāng) bouns 值大于 5 表示優(yōu)先級(jí)提高，小于 5 時(shí)優(yōu)先級(jí)變低。Linux 內(nèi)核會(huì)根據(jù)進(jìn)程的平均運(yùn)行時(shí)間動(dòng)態(tài)改變進(jìn)程的動(dòng)態(tài)優(yōu)先級(jí)。一般來(lái)說(shuō)，交互式進(jìn)程的平均運(yùn)行時(shí)間比較長(zhǎng)，因此 Linux 內(nèi)核會(huì)獎(jiǎng)勵(lì)從而增加 bouns 的值。

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

進(jìn)程調(diào)度的時(shí)機(jī)與觸發(fā)，就像是一場(chǎng)精心編排的交響樂(lè)演出中的節(jié)奏轉(zhuǎn)換，在 Linux 系統(tǒng)運(yùn)行的每一刻都發(fā)揮著關(guān)鍵作用。了解這一過(guò)程，能夠讓我們深入洞悉系統(tǒng)是如何在不同場(chǎng)景下，巧妙地進(jìn)行進(jìn)程切換，以實(shí)現(xiàn)資源的最優(yōu)配置。

當(dāng)進(jìn)程的狀態(tài)發(fā)生變化時(shí)，調(diào)度器會(huì)敏銳地捕捉到這一信號(hào)，并適時(shí)地介入調(diào)度 。比如，當(dāng)一個(gè)進(jìn)程從運(yùn)行狀態(tài)轉(zhuǎn)變?yōu)榈却隣顟B(tài)時(shí)，這通常意味著它需要等待某種外部資源的就緒，如等待磁盤(pán) I/O 操作完成、等待網(wǎng)絡(luò)數(shù)據(jù)的接收等。以一個(gè)正在讀取大型文件的進(jìn)程為例，當(dāng)它發(fā)出讀取文件的請(qǐng)求后，由于磁盤(pán)讀寫(xiě)速度相對(duì)較慢，它不得不進(jìn)入等待狀態(tài)，此時(shí)調(diào)度器會(huì)感知到這一狀態(tài)變化，將 CPU 資源從該進(jìn)程轉(zhuǎn)移到其他處于就緒狀態(tài)的進(jìn)程上，以避免 CPU 資源的閑置浪費(fèi)。同樣，當(dāng)進(jìn)程從等待狀態(tài)轉(zhuǎn)變?yōu)榫途w狀態(tài)時(shí)，例如等待的網(wǎng)絡(luò)數(shù)據(jù)已經(jīng)接收完畢，調(diào)度器會(huì)將其重新納入可調(diào)度的進(jìn)程隊(duì)列中，參與 CPU 資源的競(jìng)爭(zhēng)。

時(shí)間片用完也是引發(fā)調(diào)度的重要時(shí)機(jī) 。在 Linux 系統(tǒng)中，每個(gè)進(jìn)程在被調(diào)度執(zhí)行時(shí)，都會(huì)被分配一個(gè)特定的時(shí)間片，這就好比運(yùn)動(dòng)員在比賽中被分配的一段特定比賽時(shí)間。當(dāng)進(jìn)程的時(shí)間片耗盡時(shí)，即使該進(jìn)程尚未完成當(dāng)前任務(wù)，系統(tǒng)也會(huì)強(qiáng)制暫停它的運(yùn)行，并將 CPU 資源分配給其他就緒進(jìn)程。這樣做的目的在于確保系統(tǒng)中的各個(gè)進(jìn)程都能有機(jī)會(huì)公平地使用 CPU 資源，避免某個(gè)進(jìn)程長(zhǎng)時(shí)間獨(dú)占 CPU，導(dǎo)致其他進(jìn)程饑餓。例如，在一個(gè)多用戶的服務(wù)器環(huán)境中，如果某個(gè)進(jìn)程長(zhǎng)時(shí)間占用大量 CPU 時(shí)間，會(huì)使得其他用戶的進(jìn)程響應(yīng)遲緩，而通過(guò)時(shí)間片輪轉(zhuǎn)機(jī)制，能夠保證每個(gè)用戶的進(jìn)程都能在合理的時(shí)間內(nèi)得到執(zhí)行，提高系統(tǒng)的整體公平性和響應(yīng)性能。

此外，當(dāng)系統(tǒng)中出現(xiàn)中斷事件時(shí)，調(diào)度也可能會(huì)發(fā)生 。中斷是指計(jì)算機(jī)在運(yùn)行過(guò)程中，由于外部設(shè)備或內(nèi)部事件的觸發(fā)，暫時(shí)停止當(dāng)前正在執(zhí)行的程序，轉(zhuǎn)而執(zhí)行相應(yīng)的中斷處理程序的過(guò)程。例如，當(dāng)用戶按下鍵盤(pán)上的某個(gè)按鍵時(shí)，會(huì)產(chǎn)生一個(gè)鍵盤(pán)中斷信號(hào)，通知系統(tǒng)有新的輸入事件發(fā)生。在處理中斷的過(guò)程中，系統(tǒng)可能會(huì)根據(jù)當(dāng)前的進(jìn)程狀態(tài)和資源需求，決定是否進(jìn)行進(jìn)程調(diào)度。如果在中斷處理完成后，發(fā)現(xiàn)有更適合運(yùn)行的進(jìn)程，調(diào)度器會(huì)及時(shí)進(jìn)行切換，以確保系統(tǒng)能夠快速響應(yīng)各種外部事件，保持高效的運(yùn)行狀態(tài)。

4.3進(jìn)程調(diào)度器特點(diǎn)

Linux 進(jìn)程調(diào)度器對(duì)于 CPU 進(jìn)程調(diào)度，采用時(shí)間分片的方式，特點(diǎn)如下：

• 每個(gè)進(jìn)程近似相等的 CPU 使用權(quán)：每一個(gè)進(jìn)程有近乎相等的執(zhí)行時(shí)間，對(duì)于邏輯 CPU 而言，進(jìn)程調(diào)度使用輪詢的方式執(zhí)行，當(dāng)輪詢完成則回到第一個(gè)進(jìn)程反復(fù)。進(jìn)程數(shù)量消耗時(shí)間和進(jìn)程量成正比，雖然這種方式可能導(dǎo)致一些重要任務(wù)延遲，但使得系統(tǒng)最為穩(wěn)定。
• 進(jìn)程狀態(tài)與調(diào)度：對(duì)于大部分進(jìn)程來(lái)說(shuō)，不使用時(shí)多數(shù)處于睡眠狀態(tài)。除了睡眠狀態(tài)之外，進(jìn)程還有運(yùn)行狀態(tài)、僵死狀態(tài)、就緒狀態(tài)等。當(dāng)進(jìn)程處于睡眠狀態(tài)時(shí)，不占用 CPU 時(shí)間，只有在某些條件觸發(fā)時(shí)才會(huì)獲得 CPU 調(diào)度分配，如外部存儲(chǔ)器訪問(wèn)、用戶鍵入或者鼠標(biāo)操作觸發(fā)事件、等待指定時(shí)間等。
• 吞吐量和延遲：吞吐量是處理完成的進(jìn)程數(shù)量與耗費(fèi)時(shí)間的比值。如果進(jìn)程多過(guò)邏輯 CPU 的數(shù)量，則再增加進(jìn)程無(wú)法增加吞吐量。延遲是結(jié)束處理時(shí)間與開(kāi)始處理時(shí)間的差值，多個(gè)進(jìn)程執(zhí)行會(huì)獲得近似平均的延遲，進(jìn)程越多延遲越高。在實(shí)際系統(tǒng)中，可能出現(xiàn)空閑進(jìn)程、進(jìn)程運(yùn)行態(tài)但未就緒、進(jìn)程運(yùn)行態(tài)且都就緒等情況，不同情況會(huì)對(duì)延遲和吞吐量產(chǎn)生不同影響。

五、Linux調(diào)度器的演變歷程

Linux 調(diào)度器的發(fā)展歷程，猶如一部不斷演進(jìn)的科技史詩(shī)，見(jiàn)證了操作系統(tǒng)為滿足日益復(fù)雜的計(jì)算需求而進(jìn)行的持續(xù)創(chuàng)新與優(yōu)化 。

早期的 Linux 系統(tǒng)采用了相對(duì)簡(jiǎn)單的調(diào)度算法，如 O (n) 調(diào)度器。這種調(diào)度器的工作方式較為直觀，它會(huì)在一個(gè)全局的任務(wù)隊(duì)列中，依次遍歷所有進(jìn)程，從中挑選出優(yōu)先級(jí)最高的進(jìn)程來(lái)執(zhí)行。不難想象，當(dāng)系統(tǒng)中的進(jìn)程數(shù)量較少時(shí)，這種調(diào)度方式能夠較為有效地工作。然而，隨著計(jì)算機(jī)技術(shù)的飛速發(fā)展，系統(tǒng)中同時(shí)運(yùn)行的進(jìn)程數(shù)量大幅增加，O (n) 調(diào)度器的弊端便逐漸暴露出來(lái)。由于每次調(diào)度都需要遍歷整個(gè)任務(wù)隊(duì)列，其時(shí)間復(fù)雜度與進(jìn)程數(shù)量成正比，這就導(dǎo)致在高負(fù)載情況下，調(diào)度的效率急劇下降，系統(tǒng)性能受到嚴(yán)重影響。

為了應(yīng)對(duì) O (n) 調(diào)度器的性能瓶頸，O (1) 調(diào)度器應(yīng)運(yùn)而生。它的出現(xiàn)，猶如為 Linux 系統(tǒng)注入了一劑強(qiáng)心針，帶來(lái)了顯著的性能提升。O (1) 調(diào)度器的核心創(chuàng)新在于，為每個(gè) CPU 都配備了獨(dú)立的運(yùn)行隊(duì)列，并且通過(guò)精妙的算法，實(shí)現(xiàn)了在常數(shù)時(shí)間內(nèi)完成調(diào)度決策。這意味著，無(wú)論系統(tǒng)中存在多少進(jìn)程，調(diào)度器都能以幾乎相同的速度進(jìn)行調(diào)度，極大地提高了調(diào)度效率。具體來(lái)說(shuō)，O (1) 調(diào)度器將進(jìn)程按照優(yōu)先級(jí)分為不同的隊(duì)列，通過(guò)維護(hù)活動(dòng)隊(duì)列和過(guò)期隊(duì)列，以及使用位圖等數(shù)據(jù)結(jié)構(gòu)，快速地找到下一個(gè)需要執(zhí)行的進(jìn)程。這種設(shè)計(jì)使得 O (1) 調(diào)度器在多處理器系統(tǒng)中表現(xiàn)出色，能夠更好地平衡負(fù)載，提高系統(tǒng)的整體性能。

然而，技術(shù)的發(fā)展永無(wú)止境，O (1) 調(diào)度器在使用過(guò)程中也逐漸暴露出一些問(wèn)題。例如，它在處理 I/O 密集型任務(wù)時(shí)，識(shí)別準(zhǔn)確率有待提高；而且，在進(jìn)行活動(dòng)隊(duì)列和過(guò)期隊(duì)列的交換以及重新評(píng)估優(yōu)先級(jí)時(shí)，會(huì)耗費(fèi)一定的時(shí)間，這在一定程度上影響了系統(tǒng)的性能。為了解決這些問(wèn)題，Completely Fair Scheduler（CFS）調(diào)度器橫空出世 。CFS 調(diào)度器的設(shè)計(jì)理念獨(dú)樹(shù)一幟，它摒棄了傳統(tǒng)的固定時(shí)間片概念，引入了虛擬運(yùn)行時(shí)間（vruntime）的創(chuàng)新概念。每個(gè)進(jìn)程都擁有自己的 vruntime，這個(gè)值會(huì)隨著進(jìn)程的運(yùn)行而不斷變化。CFS 調(diào)度器通過(guò)紅黑樹(shù)數(shù)據(jù)結(jié)構(gòu)，對(duì)所有進(jìn)程的 vruntime 進(jìn)行排序，每次調(diào)度時(shí)，選擇 vruntime 最小的進(jìn)程運(yùn)行，從而確保了每個(gè)進(jìn)程都能公平地獲得 CPU 時(shí)間。這種公平性的設(shè)計(jì)，使得 CFS 調(diào)度器在多任務(wù)環(huán)境下表現(xiàn)卓越，能夠?yàn)楦鞣N類型的進(jìn)程提供高效、公平的調(diào)度服務(wù)。

近年來(lái)，隨著硬件技術(shù)的不斷進(jìn)步，如多核處理器、超線程技術(shù)的廣泛應(yīng)用，以及用戶對(duì)系統(tǒng)性能和響應(yīng)性要求的日益提高，Linux 調(diào)度器也在持續(xù)進(jìn)化。一些新的調(diào)度器，如 SCHED_DEADLINE、BORE（Burst-Oriented Response Enhancer）等應(yīng)運(yùn)而生 。SCHED_DEADLINE 調(diào)度器專門(mén)針對(duì)具有嚴(yán)格時(shí)間限制的任務(wù)，能夠確保這些任務(wù)在截止日期前完成，在實(shí)時(shí)性要求極高的場(chǎng)景，如工業(yè)自動(dòng)化控制、航空航天等領(lǐng)域，發(fā)揮著重要作用。BORE 調(diào)度器則通過(guò)引入 “突發(fā)性” 這一概念，對(duì)任務(wù)的權(quán)重和延遲進(jìn)行動(dòng)態(tài)調(diào)整，能夠更好地適應(yīng)不同類型的系統(tǒng)負(fù)載，在多任務(wù)環(huán)境中，為用戶提供更流暢、高效的使用體驗(yàn)。

回顧 Linux 調(diào)度器的演變歷程，從簡(jiǎn)單的 O (n) 調(diào)度器到高效的 O (1) 調(diào)度器，再到公平的 CFS 調(diào)度器以及不斷涌現(xiàn)的新型調(diào)度器，每一次的變革都緊密圍繞著硬件的發(fā)展和用戶的需求展開(kāi)。這些演進(jìn)不僅提升了 Linux 系統(tǒng)的性能和穩(wěn)定性，還為用戶帶來(lái)了更加出色的使用體驗(yàn)，使得 Linux 操作系統(tǒng)在各種領(lǐng)域中都能保持強(qiáng)大的競(jìng)爭(zhēng)力。

六、案例分析

在實(shí)際的應(yīng)用場(chǎng)景中，Linux 進(jìn)程調(diào)度器的作用得到了淋漓盡致的體現(xiàn)。以服務(wù)器端的 Web 應(yīng)用為例，在高并發(fā)的訪問(wèn)情況下，大量的 HTTP 請(qǐng)求如潮水般涌來(lái)，每個(gè)請(qǐng)求都對(duì)應(yīng)著一個(gè)進(jìn)程或線程。此時(shí)，Linux 進(jìn)程調(diào)度器憑借其高效的調(diào)度策略，能夠迅速且合理地為這些進(jìn)程分配 CPU 資源，確保每個(gè)請(qǐng)求都能得到及時(shí)的處理。比如，當(dāng)一個(gè)用戶在瀏覽器中快速點(diǎn)擊多個(gè)鏈接，發(fā)起一系列的頁(yè)面請(qǐng)求時(shí)，調(diào)度器會(huì)快速響應(yīng)，優(yōu)先處理那些對(duì)響應(yīng)時(shí)間要求較高的交互式請(qǐng)求，讓用戶感受到流暢的瀏覽體驗(yàn)，避免出現(xiàn)長(zhǎng)時(shí)間等待或頁(yè)面卡頓的情況。

在實(shí)時(shí)控制系統(tǒng)中，Linux 進(jìn)程調(diào)度器同樣發(fā)揮著關(guān)鍵作用。以自動(dòng)駕駛汽車的控制系統(tǒng)為例，車輛在行駛過(guò)程中，需要實(shí)時(shí)采集各種傳感器的數(shù)據(jù)，如攝像頭圖像數(shù)據(jù)、雷達(dá)距離數(shù)據(jù)等，并對(duì)這些數(shù)據(jù)進(jìn)行快速處理，以做出準(zhǔn)確的駕駛決策，如加速、剎車、轉(zhuǎn)向等。Linux 進(jìn)程調(diào)度器能夠確保這些實(shí)時(shí)任務(wù)在嚴(yán)格的時(shí)間限制內(nèi)完成，保證車輛的行駛安全。在工業(yè)自動(dòng)化生產(chǎn)線中，各種設(shè)備的控制和數(shù)據(jù)采集任務(wù)也對(duì)實(shí)時(shí)性要求極高，調(diào)度器能夠根據(jù)任務(wù)的優(yōu)先級(jí)和時(shí)間要求，精確地調(diào)度各個(gè)進(jìn)程，確保生產(chǎn)線的高效、穩(wěn)定運(yùn)行。

在移動(dòng)設(shè)備領(lǐng)域，Linux 系統(tǒng)也被廣泛應(yīng)用。以智能手機(jī)為例，當(dāng)用戶同時(shí)運(yùn)行多個(gè)應(yīng)用程序，如微信、音樂(lè)播放器、瀏覽器等時(shí)，Linux 進(jìn)程調(diào)度器會(huì)根據(jù)各個(gè)應(yīng)用的優(yōu)先級(jí)和資源需求，合理分配 CPU 時(shí)間。對(duì)于正在前臺(tái)運(yùn)行的應(yīng)用，調(diào)度器會(huì)給予較高的優(yōu)先級(jí)，確保其能夠流暢運(yùn)行，為用戶提供良好的交互體驗(yàn)；而對(duì)于后臺(tái)運(yùn)行的應(yīng)用，調(diào)度器會(huì)適當(dāng)降低其優(yōu)先級(jí)，在保證系統(tǒng)整體性能的前提下，讓它們?cè)诳臻e時(shí)間進(jìn)行數(shù)據(jù)更新等操作。這樣，用戶在使用手機(jī)時(shí)，就能夠感受到多個(gè)應(yīng)用的同時(shí)運(yùn)行，而不會(huì)出現(xiàn)明顯的卡頓或延遲現(xiàn)象。

七、全文總結(jié)

Linux 進(jìn)程調(diào)度器作為操作系統(tǒng)的核心組件，歷經(jīng)多年的發(fā)展與演進(jìn)，已經(jīng)成為一個(gè)功能強(qiáng)大、高度優(yōu)化的資源管理系統(tǒng)。從早期簡(jiǎn)單的調(diào)度算法到如今復(fù)雜而精妙的調(diào)度策略，每一次的變革都緊密貼合著硬件技術(shù)的發(fā)展以及用戶不斷增長(zhǎng)的需求。它不僅確保了系統(tǒng)的高效運(yùn)行，還為各種應(yīng)用場(chǎng)景提供了堅(jiān)實(shí)的支持。

實(shí)時(shí)調(diào)度策略為對(duì)時(shí)間要求極高的任務(wù)提供了精準(zhǔn)的保障，使得諸如工業(yè)自動(dòng)化、航空航天等關(guān)鍵領(lǐng)域的系統(tǒng)能夠穩(wěn)定、可靠地運(yùn)行。而完全公平調(diào)度策略（CFS）則秉持著公平的理念，為系統(tǒng)中的每個(gè)進(jìn)程都分配了合理的 CPU 時(shí)間，有效避免了進(jìn)程饑餓現(xiàn)象的發(fā)生，極大地提升了系統(tǒng)的整體性能和用戶體驗(yàn)。

展望未來(lái)，隨著科技的飛速發(fā)展，Linux 進(jìn)程調(diào)度器有望迎來(lái)更多令人矚目的創(chuàng)新與突破。隨著人工智能和機(jī)器學(xué)習(xí)技術(shù)的蓬勃興起，將這些先進(jìn)技術(shù)融入到調(diào)度器的設(shè)計(jì)中，實(shí)現(xiàn)更加智能化的調(diào)度決策，是一個(gè)極具潛力的發(fā)展方向。通過(guò)對(duì)系統(tǒng)運(yùn)行狀態(tài)的實(shí)時(shí)監(jiān)測(cè)和深度分析，調(diào)度器能夠精準(zhǔn)預(yù)測(cè)進(jìn)程的資源需求，并據(jù)此動(dòng)態(tài)調(diào)整調(diào)度策略，從而進(jìn)一步提升系統(tǒng)的資源利用率和響應(yīng)速度。

此外，隨著硬件技術(shù)的不斷革新，如新型處理器架構(gòu)的不斷涌現(xiàn)，Linux 進(jìn)程調(diào)度器也需要持續(xù)優(yōu)化，以充分發(fā)揮這些硬件的強(qiáng)大性能。在面對(duì)未來(lái)復(fù)雜多變的應(yīng)用場(chǎng)景和用戶需求時(shí)，相信 Linux 進(jìn)程調(diào)度器將憑借其強(qiáng)大的適應(yīng)性和創(chuàng)新性，不斷發(fā)展壯大，為 Linux 操作系統(tǒng)的持續(xù)領(lǐng)先地位奠定堅(jiān)實(shí)的基礎(chǔ)。