調(diào)度器簡介，以及Linux的調(diào)度策略-創(chuàng)新互聯(lián)

進(jìn)程是操作系統(tǒng)虛擬出來的概念，用來組織計(jì)算機(jī)中的任務(wù)。但隨著進(jìn)程被賦予越來越多的任務(wù)，進(jìn)程好像有了真實(shí)的生命，它從誕生就隨著CPU時(shí)間執(zhí)行，直到最終消失。不過，進(jìn)程的生命都得到了操作系統(tǒng)內(nèi)核的關(guān)照。就好像疲于照顧幾個(gè)孩子的母親內(nèi)核必須做出決定，如何在進(jìn)程間分配有限的計(jì)算資源，最終讓用戶獲得最佳的使用體驗(yàn)。內(nèi)核中安排進(jìn)程執(zhí)行的模塊稱為調(diào)度器（scheduler）。這里將介紹 調(diào)度器的工作方式。
進(jìn)程狀態(tài)

調(diào)度器可以切換進(jìn)程狀態(tài)（process state）。一個(gè)Linux進(jìn)程從被創(chuàng)建到死亡，可能會(huì)經(jīng)過很多種狀態(tài)，比如執(zhí)行、暫停、可中斷睡眠、不可中斷睡眠、退出等。我們可以把Linux下繁多的進(jìn)程狀態(tài)，歸納為三種基本狀態(tài)。

    就緒（Ready）: 進(jìn)程已經(jīng)獲得了CPU以外的所有必要資源，如進(jìn)程空間、網(wǎng)絡(luò)連接等。就緒狀態(tài)下的進(jìn)程等到CPU，便可立即執(zhí)行。
    執(zhí)行（Running）：進(jìn)程獲得CPU，執(zhí)行程序。
    阻塞（Blocked）：當(dāng)進(jìn)程由于等待某個(gè)事件而無法執(zhí)行時(shí)，便放棄CPU，處于阻塞狀態(tài)。

 

圖1 進(jìn)程的基本狀態(tài)

進(jìn)程創(chuàng)建后，就自動(dòng)變成了就緒狀態(tài)。如果內(nèi)核把CPU時(shí)間分配給該進(jìn)程，那么進(jìn)程就從就緒狀態(tài)變成了執(zhí)行狀態(tài)。在執(zhí)行狀態(tài)下，進(jìn)程執(zhí)行指令，最為活躍。正在執(zhí)行的進(jìn)程可以主動(dòng)進(jìn)入阻塞狀態(tài)，比如這個(gè)進(jìn)程需要將一部分硬盤中的數(shù)據(jù)讀取到內(nèi)存中。在這段讀取時(shí)間里，進(jìn)程不需要使用CPU，可以主動(dòng)進(jìn)入阻塞狀態(tài)，讓出CPU。當(dāng)讀取結(jié)束時(shí)，計(jì)算機(jī)硬件發(fā)出信號(hào)，進(jìn)程再從阻塞狀態(tài)恢復(fù)為就緒狀態(tài)。進(jìn)程也可以被迫進(jìn)入阻塞狀態(tài)，比如接收到SIGSTOP信號(hào)。

調(diào)度器是CPU時(shí)間的管理員。Linux調(diào)度器需要負(fù)責(zé)做兩件事：一件事是選擇某些就緒的進(jìn)程來執(zhí)行；另一件事是打斷某些執(zhí)行中的進(jìn)程，讓它們變回就緒狀態(tài)。不過，并不是所有的調(diào)度器都有第二個(gè)功能。有的調(diào)度器的狀態(tài)切換是單向的，只能讓就緒進(jìn)程變成執(zhí)行狀態(tài)，不能把正在執(zhí)行中的進(jìn)程變回就緒狀態(tài)。支持雙向狀態(tài)切換的調(diào)度器被稱為搶占式（pre-emptive）調(diào)度器。

調(diào)度器在讓一個(gè)進(jìn)程變回就緒時(shí)，就會(huì)立即讓另一個(gè)就緒的進(jìn)程開始執(zhí)行。多個(gè)進(jìn)程接替使用CPU，從而大效率地利用CPU時(shí)間。當(dāng)然，如果執(zhí)行中進(jìn)程主動(dòng)進(jìn)入阻塞狀態(tài)，那么調(diào)度器也會(huì)選擇另一個(gè)就緒進(jìn)程來消費(fèi)CPU時(shí)間。所謂的上下文切換（context switch）就是指進(jìn)程在CPU中切換執(zhí)行的過程。內(nèi)核承擔(dān)了上下文切換的任務(wù)，負(fù)責(zé)儲(chǔ)存和重建進(jìn)程被切換掉之前的CPU狀態(tài)，從而讓進(jìn)程感覺不到自己的執(zhí)行被中斷。應(yīng)用程序的開發(fā)者在編寫計(jì)算機(jī)程序時(shí)，就不用專門寫代碼處理上下文切換了。
進(jìn)程的優(yōu)先級(jí)

調(diào)度器分配CPU時(shí)間的基本依據(jù)，就是進(jìn)程的優(yōu)先級(jí)。根據(jù)程序任務(wù)性質(zhì)的不同，程序可以有不同的執(zhí)行優(yōu)先級(jí)。根據(jù)優(yōu)先級(jí)特點(diǎn)，我們可以把進(jìn)程分為兩種類別。

    實(shí)時(shí)進(jìn)程（Real-Time Process）：優(yōu)先級(jí)高、需要盡快被執(zhí)行的進(jìn)程。它們一定不能被普通進(jìn)程所阻擋，例如視頻播放、各種監(jiān)測(cè)系統(tǒng)。
    普通進(jìn)程（Normal Process）：優(yōu)先級(jí)低、更長執(zhí)行時(shí)間的進(jìn)程。例如文本編譯器、批處理一段文檔、圖形渲染。

普通進(jìn)程根據(jù)行為的不同，還可以被分成互動(dòng)進(jìn)程（interactive process）和批處理進(jìn)程（batch process）?；?dòng)進(jìn)程的例子有圖形界面，它們可能處在長時(shí)間的等待狀態(tài)，例如等待用戶的輸入。一旦特定事件發(fā)生，互動(dòng)進(jìn)程需要盡快被激活。一般來說，圖形界面的反應(yīng)時(shí)間是50到100毫秒。批處理進(jìn)程沒有與用戶交互的，往往在后臺(tái)被默默地執(zhí)行。

實(shí)時(shí)進(jìn)程由Linux操作系統(tǒng)創(chuàng)造，普通用戶只能創(chuàng)建普通進(jìn)程。兩種進(jìn)程的優(yōu)先級(jí)不同，實(shí)時(shí)進(jìn)程的優(yōu)先級(jí)永遠(yuǎn)高于普通進(jìn)程。進(jìn)程的優(yōu)先級(jí)是一個(gè)0到139的整數(shù)。數(shù)字越小，優(yōu)先級(jí)越高。其中，優(yōu)先級(jí)0到99留給實(shí)時(shí)進(jìn)程，100到139留給普通進(jìn)程。

 

一個(gè)普通進(jìn)程的默認(rèn)優(yōu)先級(jí)是120。我們可以用命令nice來修改一個(gè)進(jìn)程的默認(rèn)優(yōu)先級(jí)。例如有一個(gè)可執(zhí)行程序叫app，執(zhí)行命令：

$nice -n -20 ./app

命令中的-20指的是從默認(rèn)優(yōu)先級(jí)上減去20。通過這個(gè)命令執(zhí)行app程序，內(nèi)核會(huì)將app進(jìn)程的默認(rèn)優(yōu)先級(jí)設(shè)置成100，也就是普通進(jìn)程的最高優(yōu)先級(jí)。命令中的-20可以被換成-20至19中任何一個(gè)整數(shù)，包括-20 和 19。默認(rèn)優(yōu)先級(jí)將會(huì)變成執(zhí)行時(shí)的靜態(tài)優(yōu)先級(jí)（static priority）。調(diào)度器最終使用的優(yōu)先級(jí)根據(jù)的是進(jìn)程的動(dòng)態(tài)優(yōu)先級(jí)：

    動(dòng)態(tài)優(yōu)先級(jí) = 靜態(tài)優(yōu)先級(jí) – Bonus + 5

如果這個(gè)公式的計(jì)算結(jié)果小于100或大于139，將會(huì)取100到139范圍內(nèi)最接近計(jì)算結(jié)果的數(shù)字作為實(shí)際的動(dòng)態(tài)優(yōu)先級(jí)。公式中的Bonus是一個(gè)估計(jì)值，這個(gè)數(shù)字越大，代表著它可能越需要被優(yōu)先執(zhí)行。如果內(nèi)核發(fā)現(xiàn)這個(gè)進(jìn)程需要經(jīng)常跟用戶交互，將會(huì)把Bonus值設(shè)置成大于5的數(shù)字。如果進(jìn)程不經(jīng)常跟用戶交互，內(nèi)核將會(huì)把進(jìn)程的Bonus設(shè)置成小于5的數(shù)。

 
O(n)和O(1)調(diào)度器

下面介紹Linux的調(diào)度策略。最原始的調(diào)度策略是按照優(yōu)先級(jí)排列好進(jìn)程，等到一個(gè)進(jìn)程運(yùn)行完了再運(yùn)行優(yōu)先級(jí)較低的一個(gè)，但這種策略完全無法發(fā)揮多任務(wù)系統(tǒng)的優(yōu)勢(shì)。因此，隨著時(shí)間推移，操作系統(tǒng)的調(diào)度器也多次進(jìn)化。

先來看Linux 2.4內(nèi)核推出的O(n)調(diào)度器。O(n)這個(gè)名字，來源于算法復(fù)雜度的大O表示法。大O符號(hào)代表這個(gè)算法在最壞情況下的復(fù)雜度。字母n在這里代表操作系統(tǒng)中的活躍進(jìn)程數(shù)量。O(n)表示這個(gè)調(diào)度器的時(shí)間復(fù)雜度和活躍進(jìn)程的數(shù)量成正比。

O(n)調(diào)度器把時(shí)間分成大量的微小時(shí)間片（Epoch）。在每個(gè)時(shí)間片開始的時(shí)候，調(diào)度器會(huì)檢查所有處在就緒狀態(tài)的進(jìn)程。調(diào)度器計(jì)算每個(gè)進(jìn)程的優(yōu)先級(jí)，然后選擇優(yōu)先級(jí)最高的進(jìn)程來執(zhí)行。一旦被調(diào)度器切換到執(zhí)行，進(jìn)程可以不被打擾地用盡這個(gè)時(shí)間片。如果進(jìn)程沒有用盡時(shí)間片，那么該時(shí)間片的剩余時(shí)間會(huì)增加到下一個(gè)時(shí)間片中。

O(n)調(diào)度器在每次使用時(shí)間片前都要檢查所有就緒進(jìn)程的優(yōu)先級(jí)。這個(gè)檢查時(shí)間和進(jìn)程中進(jìn)程數(shù)目n成正比，這也正是該調(diào)度器復(fù)雜度為O(n)的原因。當(dāng)計(jì)算機(jī)中有大量進(jìn)程在運(yùn)行時(shí)，這個(gè)調(diào)度器的性能將會(huì)被大大降低。也就是說，O(n)調(diào)度器沒有很好的可拓展性。O(n)調(diào)度器是Linux 2.6之前使用的進(jìn)程調(diào)度器。當(dāng)Java語言逐漸流行后，由于Java虛擬機(jī)會(huì)創(chuàng)建大量進(jìn)程，調(diào)度器的性能問題變得更加明顯。

為了解決O(n)調(diào)度器的性能問題，O(1)調(diào)度器被發(fā)明了出來，并從Linux 2.6內(nèi)核開始使用。顧名思義，O(1)調(diào)度器是指調(diào)度器每次選擇要執(zhí)行的進(jìn)程的時(shí)間都是1個(gè)單位的常數(shù)，和系統(tǒng)中的進(jìn)程數(shù)量無關(guān)。這樣，就算系統(tǒng)中有大量的進(jìn)程，調(diào)度器的性能也不會(huì)下降。O(1)調(diào)度器的創(chuàng)新之處在于，它會(huì)把進(jìn)程按照優(yōu)先級(jí)排好，放入特定的數(shù)據(jù)結(jié)構(gòu)中。在選擇下一個(gè)要執(zhí)行的進(jìn)程時(shí)，調(diào)度器不用遍歷進(jìn)程，就可以直接選擇優(yōu)先級(jí)最高的進(jìn)程。

和O(n)調(diào)度器類似，O(1)也是把時(shí)間片分配給進(jìn)程。優(yōu)先級(jí)為120以下的進(jìn)程時(shí)間片為：

    (140–priority)×20毫秒

 

優(yōu)先級(jí)120及以上的進(jìn)程時(shí)間片為：

    (140–priority)×5 毫秒

O(1)調(diào)度器會(huì)用兩個(gè)隊(duì)列來存放進(jìn)程。一個(gè)隊(duì)列稱為活躍隊(duì)列，用于存儲(chǔ)那些待分配時(shí)間片的進(jìn)程。另一個(gè)隊(duì)列稱為過期隊(duì)列，用于存儲(chǔ)那些已經(jīng)享用過時(shí)間片的進(jìn)程。O(1)調(diào)度器把時(shí)間片從活躍隊(duì)列中調(diào)出一個(gè)進(jìn)程。這個(gè)進(jìn)程用盡時(shí)間片，就會(huì)轉(zhuǎn)移到過期隊(duì)列。當(dāng)活躍隊(duì)列的所有進(jìn)程都被執(zhí)行過后，調(diào)度器就會(huì)把活躍隊(duì)列和過期隊(duì)列對(duì)調(diào)，用同樣的方式繼續(xù)執(zhí)行這些進(jìn)程。

上面的描述沒有考慮優(yōu)先級(jí)。加入優(yōu)先級(jí)后，情況會(huì)變得復(fù)雜一些。操作系統(tǒng)會(huì)創(chuàng)建140個(gè)活躍隊(duì)列和過期隊(duì)列，對(duì)應(yīng)優(yōu)先級(jí)0到139的進(jìn)程。一開始，所有進(jìn)程都會(huì)放在活躍隊(duì)列中。然后操作系統(tǒng)會(huì)從優(yōu)先級(jí)最高的活躍隊(duì)列開始依次選擇進(jìn)程來執(zhí)行，如果兩個(gè)進(jìn)程的優(yōu)先級(jí)相同，他們有相同的概率被選中。執(zhí)行一次后，這個(gè)進(jìn)程會(huì)被從活躍隊(duì)列中剔除。如果這個(gè)進(jìn)程在這次時(shí)間片中沒有徹底完成，它會(huì)被加入優(yōu)先級(jí)相同的過期隊(duì)列中。當(dāng)140個(gè)活躍隊(duì)列的所有進(jìn)程都被執(zhí)行完后，過期隊(duì)列中將會(huì)有很多進(jìn)程。調(diào)度器將對(duì)調(diào)優(yōu)先級(jí)相同的活躍隊(duì)列和過期隊(duì)列繼續(xù)執(zhí)行下去。過期隊(duì)列和活躍隊(duì)列，如圖2所示。

 

圖2 過期隊(duì)列和活躍隊(duì)列（需要替換）

 

我們下面看一個(gè)例子，有五個(gè)進(jìn)程，如表1所示。

表1 進(jìn)程 Linux操作系統(tǒng)中的進(jìn)程隊(duì)列（run queue），如表2所示。

表2 進(jìn)程隊(duì)列

那么在一個(gè)執(zhí)行周期，被選中的進(jìn)程依次是先A，然后B和C，隨后是D，最后是E。

注意，普通進(jìn)程的執(zhí)行策略并沒有保證優(yōu)先級(jí)為100的進(jìn)程會(huì)先被執(zhí)行完進(jìn)入結(jié)束狀態(tài)，再執(zhí)行優(yōu)先級(jí)為101的進(jìn)程，而是在每個(gè)對(duì)調(diào)活躍和過期隊(duì)列的周期中都有機(jī)會(huì)被執(zhí)行，這種設(shè)計(jì)是為了避免進(jìn)程饑餓（starvation）。所謂的進(jìn)程饑餓，就是優(yōu)先級(jí)低的進(jìn)程很久都沒有機(jī)會(huì)被執(zhí)行。

我們看到，O(1)調(diào)度器在挑選下一個(gè)要執(zhí)行的進(jìn)程時(shí)很簡單，不需要遍歷所有進(jìn)程。但是它依然有一些缺點(diǎn)。進(jìn)程的運(yùn)行順序和時(shí)間片長度極度依賴于優(yōu)先級(jí)。比如，計(jì)算優(yōu)先級(jí)為100、110、120、130和139這幾個(gè)進(jìn)程的時(shí)間片長度，如表3所示。

表3 進(jìn)程的時(shí)間片長度

從表格中你會(huì)發(fā)現(xiàn)，優(yōu)先級(jí)為110和120的進(jìn)程的時(shí)間片長度差距比120和130之間的大了10倍。也就是說，進(jìn)程時(shí)間片長度的計(jì)算存在很大的隨機(jī)性。O(1)調(diào)度器會(huì)根據(jù)平均休眠時(shí)間來調(diào)整進(jìn)程優(yōu)先級(jí)。該調(diào)度器假設(shè)那些休眠時(shí)間長的進(jìn)程是在等待用戶互動(dòng)。這些互動(dòng)類的進(jìn)程應(yīng)該獲得更高的優(yōu)先級(jí)，以便給用戶更好的體驗(yàn)。一旦這個(gè)假設(shè)不成立，O(1)調(diào)度器對(duì)CPU的調(diào)配就會(huì)出現(xiàn)問題。
完全公平調(diào)度器

從2007年發(fā)布的Linux 2.6.23版本起，完全公平調(diào)度器（CFS，Completely Fair Scheduler）取代了O(1)調(diào)度器。CFS調(diào)度器不對(duì)進(jìn)程進(jìn)行任何形式的估計(jì)和猜測(cè)。這一點(diǎn)和O(1)區(qū)分互動(dòng)和非互動(dòng)進(jìn)程的做法完全不同。

CFS調(diào)度器增加了一個(gè)虛擬運(yùn)行時(shí)（virtual runtime）的概念。每次一個(gè)進(jìn)程在CPU中被執(zhí)行了一段時(shí)間，就會(huì)增加它虛擬運(yùn)行時(shí)的記錄。在每次選擇要執(zhí)行的進(jìn)程時(shí)，不是選擇優(yōu)先級(jí)最高的進(jìn)程，而是選擇虛擬運(yùn)行時(shí)最少的進(jìn)程。完全公平調(diào)度器用一種叫紅黑樹的數(shù)據(jù)結(jié)構(gòu)取代了O(1)調(diào)度器的140個(gè)隊(duì)列。紅黑樹可以高效地找到虛擬運(yùn)行最小的進(jìn)程。

我們先通過例子來看CFS調(diào)度器。假如一臺(tái)運(yùn)行的計(jì)算機(jī)中本來擁有A、B、C、D四個(gè)進(jìn)程。內(nèi)核記錄著每個(gè)進(jìn)程的虛擬運(yùn)行時(shí)，如表4所示。

表4 每個(gè)進(jìn)程的虛擬運(yùn)行時(shí)

系統(tǒng)增加一個(gè)新的進(jìn)程E。新創(chuàng)建進(jìn)程的虛擬運(yùn)行時(shí)不會(huì)被設(shè)置成0，而會(huì)被設(shè)置成當(dāng)前所有進(jìn)程最小的虛擬運(yùn)行時(shí)。這能保證該進(jìn)程被較快地執(zhí)行。在原來的進(jìn)程中，最小虛擬運(yùn)行時(shí)是進(jìn)程A的1 000納秒，因此E的初始虛擬運(yùn)行時(shí)會(huì)被設(shè)置為1 000納秒。新的進(jìn)程列表如表5所示。

表5 新的進(jìn)程列表

假如調(diào)度器需要選擇下一個(gè)執(zhí)行的進(jìn)程，進(jìn)程A會(huì)被選中執(zhí)行。進(jìn)程A會(huì)執(zhí)行一個(gè)調(diào)度器決定的時(shí)間片。假如進(jìn)程A運(yùn)行了250納秒，那它的虛擬運(yùn)行時(shí)增加。而其他的進(jìn)程沒有運(yùn)行，所以虛擬運(yùn)行時(shí)不變。在A消耗完時(shí)間片后，更新后的進(jìn)程列表，如表6所示。

表6 更新后的進(jìn)程列表

可以看到，進(jìn)程A的排序下降到了第三位，下一個(gè)將要被執(zhí)行的進(jìn)程是進(jìn)程E。從本質(zhì)上看，虛擬運(yùn)行時(shí)代表了該進(jìn)程已經(jīng)消耗了多少CPU時(shí)間。如果它消耗得少，那么理應(yīng)優(yōu)先獲得計(jì)算資源。

按照上述的基本設(shè)計(jì)理念，CFS調(diào)度器能讓所有進(jìn)程公平地使用CPU。聽起來，這讓進(jìn)程的優(yōu)先級(jí)變得毫無意義。CFS調(diào)度器也考慮到了這一點(diǎn)。CFS調(diào)度器會(huì)根據(jù)進(jìn)程的優(yōu)先級(jí)來計(jì)算一個(gè)時(shí)間片因子。同樣是增加250納秒的虛擬運(yùn)行時(shí)，優(yōu)先級(jí)低的進(jìn)程實(shí)際獲得的可能只有200納秒，而優(yōu)先級(jí)高的進(jìn)程實(shí)際獲得可能有300納秒。這樣，優(yōu)先級(jí)高的進(jìn)程就獲得了更多的計(jì)算資源。

以上就是調(diào)度器的基本原理，以及Linux用過的幾種調(diào)度策略。調(diào)度器可以更加合理地把CPU時(shí)間分配給進(jìn)程?，F(xiàn)代計(jì)算機(jī)都是多任務(wù)系統(tǒng)，調(diào)度器在多任務(wù)系統(tǒng)中起著頂梁柱的作用。

創(chuàng)新互聯(lián)建站主要從事網(wǎng)站制作、成都做網(wǎng)站、網(wǎng)頁設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)門頭溝,10多年網(wǎng)站建設(shè)經(jīng)驗(yàn),價(jià)格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):18982081108

文章題目：調(diào)度器簡介，以及Linux的調(diào)度策略-創(chuàng)新互聯(lián)
轉(zhuǎn)載來源：http://www.muchs.cn/article12/pccgc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制開發(fā)、企業(yè)建站、標(biāo)簽優(yōu)化、做網(wǎng)站、網(wǎng)站制作、外貿(mào)網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)