• Linux 內(nèi)核與人類社會

  
  

• 公司平面圖

  
  

• 時間片和職稱

  
  

• Mr. P的經(jīng)歷

  
  

• 評定動態(tài)職稱

  
  

• 現(xiàn)在我們回來討論Mr. P

  
  

• O(1)調(diào)度

  
  

• 對交際花的優(yōu)惠政策

  
  

• 公司里的超級特權(quán)階級－小霸王

  
  

• 總結(jié)

  
  

在研究 Linux 進(jìn)程調(diào)度的時候，看到這樣一篇文章，寫的很幽默，分享給大家！

為了提高閱讀體驗，我把一些關(guān)鍵詞加了顏色。

ce編輯器" style="margin-top: 30px;margin-bottom: 15px;font-weight: bold;color: black;border-bottom: 2px solid rgb(239, 112, 96);font-size: 1.3em;">Linux 內(nèi)核與人類社會

Linux 內(nèi)核是一個無比復(fù)雜的系統(tǒng)，要想看清大致的脈絡(luò)也非易事。其實，可以把運(yùn)行中的Linux想像成一個人類的社會，當(dāng)中的進(jìn)程就是社會中的人。

人有生老病死，進(jìn)程有創(chuàng)建、異常、終止。

人有各種各樣的財產(chǎn)，進(jìn)程有對應(yīng)的地址空間、設(shè)備等等。

人被各種各樣的東西限制著，被人管著，進(jìn)程也是。

內(nèi)核無比巨大，從哪著手？我想，從進(jìn)程的視角來看是個好辦法。

并且，在學(xué)習(xí)Linux內(nèi)核的同時，類比人類社會來看，會有更深刻的印象，理解得更透徹。

本來也應(yīng)該從進(jìn)程的創(chuàng)建開始寫的，但是最近在看調(diào)度的相關(guān)論文，就又把Linux調(diào)度的東西看了一下。

所以，就先寫調(diào)度相關(guān)的東西吧。

公司平面圖

首先介紹與進(jìn)程所在環(huán)境對應(yīng)的人類場景：

這是一個公司，公司里有很多人（進(jìn)程），每個人都有其對應(yīng)的職稱（優(yōu)先級）。

這個公司很奇怪，只有一張辦公桌（CPU），在任意時刻，只能有一個人在工作(TASK_RUNNING正在運(yùn)行狀態(tài))。

其他人呢，要么在休息室時短暫地休息（對應(yīng)TASK_RUNNING就緒狀態(tài)），要么就在寢室Sleep(對應(yīng)TASK_INTERRUPTABLE或TASK_UNINTERRUPTABLE)，要么就是死人了，在停尸間（TASK_ZOMBIE）。

是的，這是真的，這個公司就是個血汗工廠，干活累死了，就直接丟進(jìn)停尸間，慘絕人寰！

以下是此公司的平面圖：

圖解：

“推門”是單向的：比如連接工作室和太平間的是推門，職員只能從工作室走到太平間，不能從太平間走到工作室（這太嚇人了）。

“凹槽門”是雙向的：比如連接工作室和休息室的門是凹槽門，職員可以走來走去。

時間片和職稱

時間片(time slice)：這個公司的工資特別高，按工作的小時數(shù)計算。工作者得錢，不工作者不得錢。

所以，所有的人都特想去辦公桌那里工作，爭著搶著要去。為了讓大家都有機(jī)會去工作（避免有的人沒錢拿，餓死，i.e. starve to death），所以公司出了條規(guī)定，每個人每次工作的時間不能超過公司分給自己的時間片（time slice）。時間片的大小由此人的職稱(優(yōu)先級)決定。

職稱（也就是內(nèi)核中的priority）：職稱有兩種，一種是靜態(tài)職稱（static priority），一種是動態(tài)職稱（dynamic priority）。

靜態(tài)職稱是先天的，由此人的老爸決定（富二代有先天優(yōu)勢?。?。

動態(tài)優(yōu)先級是看在公司里的工作表現(xiàn)的。

職稱是很重要的東西，職稱越高，你到辦公桌上賺錢的機(jī)會越大。

默認(rèn)時間片長點好還是短點好？

自然是不長不短好（世界上的事情都是這樣）。

如果太短了，比如說某職員時間片是1分鐘（對應(yīng)的Linux里的時間片應(yīng)該差不多是0.1ms吧，可能還得少點），這個人在辦公桌前屁股沒坐熱就要走了，從起身到回到休息室，再到下一個人起身走到辦公桌前坐下，這也得要一分鐘。

如果這樣的話，這公司將有一半的時間花在走路上。這樣搞是不行的，在資本主義社會，大家都要努力搞高生產(chǎn)率。

那是不是時間片長了就好？也不是。

比如時間片是一個小時，當(dāng)兩個客戶（對應(yīng)Linux中的兩個用戶）同時要和此公司展開業(yè)務(wù)（對應(yīng)Linux中的啟動進(jìn)程），有兩個職員會分別處理這兩個業(yè)務(wù)。

A職員一上去就占著辦公室一個小時，B職員在這一個小時結(jié)束前沒法子處理他的客戶的業(yè)務(wù)，所以B職員的客戶就得在寒風(fēng)中等一個小時！

資本主義社會里的公司是不能讓他們的財神爺不高興的。所以，還是不長不短的好。

回到真實的Linux內(nèi)核中:很多人認(rèn)為時間片過長會導(dǎo)致程序的響應(yīng)（比如字處理程序的I/O響應(yīng)）變慢，因為要等時間片用完才能處理。

其實不然，字處理程序等交互性強(qiáng)的程序,他們的優(yōu)先級高，可以搶占當(dāng)前正在運(yùn)行的進(jìn)程，從而得到執(zhí)行。

在公司里，就比如B職員的職稱高，他可以把A職員從辦公桌上踢走。

事實上，從后面對動態(tài)優(yōu)先級的討論我們可以看到，要是A職員一直霸占著辦公桌不走，他/她的動態(tài)職稱會變低的，結(jié)果是，在休息室里的其他職員的職稱就自然而然地可能比A高了。

職員目錄(Process list)：公司有個目錄，在這個目錄中，列出了所有公司的職員。這對應(yīng)Linux里的Process List，里面存有所有進(jìn)程的信息。

Mr. P的經(jīng)歷

Mr. P 的出生

這是世界上最怪異的公司，職員都是單性的，都是男的。

并且不要交配，自己調(diào)用系統(tǒng)調(diào)用fork()，就可以生了。生出來的小孩子也都是男的。

在這里為了問題的簡化，就只討論與調(diào)度的關(guān)系比較緊密的內(nèi)容。

如上圖所示，在休息室里其實還有兩個沙發(fā)。一個沙發(fā)叫做活動隊列（往后我們叫它活動沙發(fā)吧），一個沙發(fā)叫做過期隊列（往后我們叫它過期沙發(fā)）。

坐在活動沙發(fā)上的職員都還有時間片沒有用完，坐在過期沙發(fā)上的職員的時間片剛剛被用完了（但他們手上都拿著新分配到的時間片，這個是2.5版內(nèi)核新引入的O(1)調(diào)度，后面再講）。

Mr. P的父親在辦公桌旁邊工作的時候，突然fork()了一下，就生出了Mr.P。

一出生，Mr. P就擁有和父親一樣的靜態(tài)職稱（static priority）。

他一出生就坐在了活動沙發(fā)上，拿走了父親一半的時間片。比如生MR. P之前，MR. P的父親有10ms的時間片，MR.P出生后，他父親有5ms，Mr. P有5ms。

：試想，有一人，自己有10ms的時間片，他一直生啊生，生了100個孩子，那么這個程序就有了10 10*100ms的時間片了。

然后他的孩子斷續(xù)生啊生，那么有可能系統(tǒng)中絕大部分的時間片都是他家的了，那他的街坊鄰居還要不要活啊，沒時間片等于不能做事，等于沒工資，等于沒食物，等于餓死。

另外，不幸的是，即使是在發(fā)達(dá)的資本主義社會，孩子也是有可能夭折的（由于各種原因，在第一次到辦公桌上工作之前就死掉了）。在這種情況下，公司會把孩子沒用的時間片還給他父親。多么人性化的公司…

開始工作

像其他所有孩子一樣，Mr. P一生下來就能工作了，他坐在活動沙發(fā)上等著做事。

他人事部的同事Miss Schedule (以下簡稱Miss S)會在每個tick(內(nèi)核的時間單位，時間很短)結(jié)束時檢查一下以下兩種情況有沒有發(fā)生：

1. 在辦公桌前工作的那個職員是不是已經(jīng)用完自己的時間片了。
2. 是不是有更高動態(tài)職稱（dynamic priority）的職員在活動沙發(fā)上等著。

其中一種情況成立，這個在辦公桌前工作的那個職員就要被趕出來，換在活動沙發(fā)上坐著的動態(tài)職稱最高的職員進(jìn)去工作。

假設(shè)經(jīng)過一段時間后，沒有人的動態(tài)職稱比Mr. P高了。在一個時間tick結(jié)束時，Miss S到休息室檢查大家當(dāng)前的職稱。

他能輕松地找到動態(tài)職稱最高的職員(sched_find_first)，因為職員們都是按動態(tài)職稱來坐的（在活動沙發(fā)上），動態(tài)職稱相同的職員坐在一起（參考struct prio_array）。

Miss S只要按順序找下去，第一個在沙發(fā)上找到的職員就是職稱最高的。

當(dāng)Miss S用上面的方法發(fā)現(xiàn)Mr. P當(dāng)前的動態(tài)職稱是最高的時，在辦公桌前工作的是職員C，Miss S把C從辦公桌前拉到休息室。

如果此時C的時間片已經(jīng)用完了，他就會被安排坐在過期沙發(fā)上（這也就是expired的含義）；如果此時C的時間片沒有用完，他就會被安排坐在活動沙發(fā)上。

C被拉到休息室時，他的工作用具，筆啊紙啊什么的，都要從辦公桌上拿走（這是關(guān)于進(jìn)程上下文切換的問題）。

C走了之后，Mr. P帶著他的東西到辦公桌前坐下，整理好辦工用品（進(jìn)程上下文切換）。好的，Mr. P可以開始工作了。

評定動態(tài)職稱

公司里的兩類人：

交際花（I/O消耗型進(jìn)程）：這類人常常與外部的客戶打交道(IO操作比較多)，而客戶的反應(yīng)總是不怎么快。所以，交際花常常要等客戶做出反應(yīng)。公司為了不讓交際花在等客戶反應(yīng)的時候也占用著辦公桌，所以，當(dāng)交際花要等待客戶的響應(yīng)時，他就會被移到寢室去睡覺(Sleep)。

工作狂（處理器消耗型）：這類人就是傳說中的苦干王，很少和外界打交道（IO操作比較少），就知道在辦工桌上做事。這種工作狂給公司造成一些困擾，如果他們老占著辦公桌，交際花就沒法做事了。要知道，一個公司還是需要人去跑跑業(yè)務(wù)的。

公司有一套機(jī)制，這一套機(jī)制能很好的區(qū)分這兩類人，并且給他們評定職稱（調(diào)整優(yōu)先級）。

判斷的標(biāo)準(zhǔn)就是他們的平均睡眠時間（average sleep time）。

睡眠時間包括在寢室里的時間（TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE）和在休息室時等待的時間。

但平均睡眠時間的計算并不是加和再求平均那么簡單。在TASK_INT和TASK_UNINT兩種狀態(tài)下，平均睡眠時間的增長情況是不一樣的。

在運(yùn)行的時間，平均睡眠時間是在減少的。具體的平均睡眠時間的算法在recalc_task_prio()中。

1. 當(dāng)一個職員常常睡覺，公司就知道這人是交際花了，因為他常常因為等客戶的響應(yīng)而睡覺。
2. 當(dāng)一個職員很少睡覺，公司就知道這人是個工作狂了，因為他很少因為等客戶的響應(yīng)而睡覺。

現(xiàn)在我們回來討論Mr. P

假設(shè)Mr. P在工作的時候要等待一個客戶給數(shù)據(jù)給他(比如說鍵盤數(shù)據(jù))，他就把自己的加入一個等待隊列里，將自己設(shè)為TASK_INT，這樣他就進(jìn)入了寢室（休眠）里。

Mr. P在那里苦苦地等待他要的數(shù)據(jù)到來。

終于，客戶敲下了鍵盤，給出了數(shù)據(jù)。然后鍵盤事件的管理者調(diào)用wake_up()函數(shù)，將Mr. P喚醒。

1. 如果Mr. P的動態(tài)職稱高于當(dāng)前正在工作的職員的動態(tài)職稱，那么Mr. P就會搶掉這個職員的辦公桌。
2. 如果不高于的話，Mr. P就只是先到休息室里坐著。

我們假設(shè)Mr. P的動態(tài)職稱很高，所以，現(xiàn)在Mr. P又搶到了辦公桌。

O(1)調(diào)度

又過了一段時間，Mr. P的時間片用完了，該離開了。

這時他該被Miss S帶到過期沙發(fā)上了，在從辦公桌走到過期沙發(fā)的路上，Miss S會幫他重新算時間片（依照動態(tài)職稱來決定時間片的長短）。

事實上，每個職員被帶到過期沙發(fā)上坐著的時候，Miss S都會幫他算好時間片。

這樣，過期沙發(fā)上的所有職員手中都拿著時間片。這樣做的好處是，當(dāng)活動沙發(fā)空了的時間，只要把活動沙發(fā)和過期沙發(fā)上貼著的“活動沙發(fā)”和“過期沙發(fā)”的標(biāo)簽互換 一下，原來的過期沙發(fā)就變成了活動沙發(fā)，原來的活動沙發(fā)就變成了過期沙發(fā)。

這樣，Miss S就又可以從活動沙發(fā)上叫人去工作了。而這個“互換標(biāo)簽”的動作的時間復(fù)雜度是O(1)。這就是2.5版內(nèi)核所引入的O(1)調(diào)度。

試想一下沒有這個O(1)調(diào)試之前是什么情況?

每次所有進(jìn)程的時間片都用完時，要重新計算所有TASK_RUNNING狀態(tài)的進(jìn)程的時間片。

當(dāng)一個系統(tǒng)中只有幾個進(jìn)程的情況還好，但是對于有成千上萬個進(jìn)程的大型系統(tǒng)，這是相關(guān)耗時的。

對交際花的優(yōu)惠政策

在一個公司來說，交際花是非常重要的，他們的表現(xiàn)直接關(guān)系到客戶的滿意度和公司的形象。所以，Linux公司有一些專門針對交際花的優(yōu)惠政策。

假設(shè)Mr. P就是一個十足的交際花：上班打扮得花枝招展（雖然是個男的），見人說人話見鬼說鬼話，關(guān)鍵是，他有一些客戶特別愛和他把交道。

當(dāng)Mr. P用完一個時間片的時候，照常理，他是應(yīng)該被Miss S帶到過期沙發(fā)上去等待下一次工作的。

但這樣的等待有可能太久了－要等到所有活動沙發(fā)上的職員都用完時間片。所以，Miss S為了客戶的滿意度（如果等太久，客戶是不滿意的），就在重新計算Mr. P的時間片之后，讓他留在了活動沙發(fā)上。這樣，Mr. P就能更快地處理客戶的IO事件。

這看起來是對交際花的特權(quán)，其實這是為了公司的長遠(yuǎn)利益著想。

如果客戶的需求得不到及時的滿足，客戶不滿意，就不會有人用這公司的產(chǎn)品了，即使工作狂們的工作做得很好。

公司里的超級特權(quán)階級－小霸王(real-time process)

交際花是有一些特權(quán)，但權(quán)利再大也大不過小霸王。

公司有時會有一些時間很緊的項目要做，這些項目有deadline。為了能完成這些重要的項目，公司里發(fā)展了一種特權(quán)階級，就是小霸王。

他們的職稱高于其他所有普通員工，除非他們完成了自己的工作，否則其他職工不能去工作。

這些小霸王的工作方式有兩種：

1. FIFO(First In First Out)：當(dāng)一個小霸王完成自己工作的時間，其他小霸王才能去工作。但是當(dāng)有職稱更高的小霸王到來時，職稱更高的小霸王能搶占當(dāng)前的小霸王的辦公桌。
2. RR(Route Robin)：相同優(yōu)先級的小霸王轉(zhuǎn)著用辦公桌，每人用一段時間。

總結(jié)

在這篇文章里，以Mr. P的工作經(jīng)歷來說明了Linux調(diào)度的一些比較重要的機(jī)制。

介紹了IO消耗型進(jìn)程和處理器消耗型的進(jìn)程，O(1)調(diào)度等等。

這些是比較大的方面，當(dāng)大的方面理解了之后，那些世界頂尖高手寫的源碼也就更容易看懂一些了。

免責(zé)聲明：本文轉(zhuǎn)自網(wǎng)絡(luò)文章，轉(zhuǎn)載此文章僅為個人收藏，分享知識，如有侵權(quán)，請聯(lián)系我進(jìn)行刪除。