Mr. Process的一生－Linux內(nèi)核的社會(huì)視角

時(shí)間：2021-10-15 16:26:28

關(guān)鍵字：內(nèi)核 ce

手機(jī)看文章

掃描二維碼
隨時(shí)隨地手機(jī)看文章

[導(dǎo)讀]Linux內(nèi)核與人類社會(huì)公司平面圖時(shí)間片和職稱Mr.P的經(jīng)歷評(píng)定動(dòng)態(tài)職稱現(xiàn)在我們回來(lái)討論Mr.PO(1)調(diào)度對(duì)交際花的優(yōu)惠政策公司里的超級(jí)特權(quán)階級(jí)－小霸王總結(jié)在研究Linux進(jìn)程調(diào)度的時(shí)候，看到這樣一篇文章，寫(xiě)的很幽默，分享給大家！為了提高閱讀體驗(yàn)，我把一些關(guān)鍵詞加了顏色。Lin...

Linux 內(nèi)核與人類社會(huì)
公司平面圖
時(shí)間片和職稱
Mr. P的經(jīng)歷
評(píng)定動(dòng)態(tài)職稱
現(xiàn)在我們回來(lái)討論Mr. P
O(1)調(diào)度
對(duì)交際花的優(yōu)惠政策
公司里的超級(jí)特權(quán)階級(jí)－小霸王
總結(jié)

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

為了提高閱讀體驗(yàn)，我把一些關(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)核與人類社會(huì)

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

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

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

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

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

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

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

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

公司平面圖

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

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

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

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

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

以下是此公司的平面圖：

圖解：

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

“凹槽門(mén)”是雙向的：比如連接工作室和休息室的門(mén)是凹槽門(mén)，職員可以走來(lái)走去。

時(shí)間片和職稱

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

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

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

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

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

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

默認(rèn)時(shí)間片長(zhǎng)點(diǎn)好還是短點(diǎn)好？

自然是不長(zhǎng)不短好（世界上的事情都是這樣）。

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

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

那是不是時(shí)間片長(zhǎng)了就好？也不是。

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

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

資本主義社會(huì)里的公司是不能讓他們的財(cái)神爺不高興的。所以，還是不長(zhǎng)不短的好。

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

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

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

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

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

Mr. P的經(jīng)歷

Mr. P 的出生

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

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

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

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

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

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

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

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

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

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

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

開(kāi)始工作

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

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

在辦公桌前工作的那個(gè)職員是不是已經(jīng)用完自己的時(shí)間片了。

是不是有更高動(dòng)態(tài)職稱（dynamic priority）的職員在活動(dòng)沙發(fā)上等著。

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

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

他能輕松地找到動(dòng)態(tài)職稱最高的職員(sched_find_first)，因?yàn)槁殕T們都是按動(dòng)態(tài)職稱來(lái)坐的（在活動(dòng)沙發(fā)上），動(dòng)態(tài)職稱相同的職員坐在一起（參考struct prio_array）。

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

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

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

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

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

評(píng)定動(dòng)態(tài)職稱

公司里的兩類人：

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

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

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

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

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

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

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

當(dāng)一個(gè)職員常常睡覺(jué)，公司就知道這人是交際花了，因?yàn)樗３Ｒ驗(yàn)榈瓤蛻舻捻憫?yīng)而睡覺(jué)。

當(dāng)一個(gè)職員很少睡覺(jué)，公司就知道這人是個(gè)工作狂了，因?yàn)樗苌僖驗(yàn)榈瓤蛻舻捻憫?yīng)而睡覺(jué)。

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

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

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

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

如果Mr. P的動(dòng)態(tài)職稱高于當(dāng)前正在工作的職員的動(dòng)態(tài)職稱，那么Mr. P就會(huì)搶掉這個(gè)職員的辦公桌。

如果不高于的話，Mr. P就只是先到休息室里坐著。

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

O(1)調(diào)度

又過(guò)了一段時(shí)間，Mr. P的時(shí)間片用完了，該離開(kāi)了。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

FIFO(First In First Out)：當(dāng)一個(gè)小霸王完成自己工作的時(shí)間，其他小霸王才能去工作。但是當(dāng)有職稱更高的小霸王到來(lái)時(shí)，職稱更高的小霸王能搶占當(dāng)前的小霸王的辦公桌。

RR(Route Robin)：相同優(yōu)先級(jí)的小霸王轉(zhuǎn)著用辦公桌，每人用一段時(shí)間。