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

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

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

 

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

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

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

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

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

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

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

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

 

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

$nice -n -20 ./app

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

    動態(tài)優(yōu)先級 = 靜態(tài)優(yōu)先級 – Bonus + 5

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

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

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

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

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

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

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

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

    (140–priority)×20毫秒

 

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

    (140–priority)×5 毫秒

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

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

 

圖2 過期隊列和活躍隊列（需要替換）

 

我們下面看一個例子，有五個進程，如表1所示。

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

表2 進程隊列

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

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

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

表3 進程的時間片長度

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

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

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

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

表4 每個進程的虛擬運行時

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

表5 新的進程列表

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

表6 更新后的進程列表

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

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

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

創(chuàng)新互聯(lián)公司主要從事網(wǎng)站制作、網(wǎng)站建設、網(wǎng)頁設計、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務。立足成都服務蕪湖縣,10余年網(wǎng)站建設經(jīng)驗,價格優(yōu)惠、服務專業(yè),歡迎來電咨詢建站服務:028-86922220

文章標題：調(diào)度器簡介，以及Linux的調(diào)度策略
鏈接URL：http://m.2m8n56k.cn/article38/jdgpsp.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站維護、App設計、定制開發(fā)、手機網(wǎng)站建設、搜索引擎優(yōu)化、云服務器

廣告

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