Linux進(jìn)程調(diào)度的目標(biāo)

　　　　1.高效性：高效意味著在相同的時(shí)間下要完成更多的任務(wù),。調(diào)度程序會(huì)被頻繁的執(zhí)行,，所以調(diào)度程序要盡可能的高效；

　　　　2.加強(qiáng)交互性能:在系統(tǒng)相當(dāng)?shù)呢?fù)載下,，也要保證系統(tǒng)的響應(yīng)時(shí)間,；

　　　　3.保證公平和避免饑渴；

　　　　4.SMP調(diào)度：調(diào)度程序必須支持多處理系統(tǒng),；

　　　　5.軟實(shí)時(shí)調(diào)度：系統(tǒng)必須有效的調(diào)用實(shí)時(shí)進(jìn)程,，但不保證一定滿(mǎn)足其要求；

Linux進(jìn)程優(yōu)先級(jí)

　　進(jìn)程提供了兩種優(yōu)先級(jí),，一種是普通的進(jìn)程優(yōu)先級(jí),，第二個(gè)是實(shí)時(shí)優(yōu)先級(jí)。前者適用SCHED_NORMAL調(diào)度策略,，后者可選SCHED_FIFO或SCHED_RR調(diào)度策略,。任何時(shí)候，實(shí)時(shí)進(jìn)程的優(yōu)先級(jí)都高于普通進(jìn)程,，實(shí)時(shí)進(jìn)程只會(huì)被更高級(jí)的實(shí)時(shí)進(jìn)程搶占,，同級(jí)實(shí)時(shí)進(jìn)程之間是按照FIFO（一次機(jī)會(huì)做完）或者RR（多次輪轉(zhuǎn)）規(guī)則調(diào)度的。

　　首先,，說(shuō)下實(shí)時(shí)進(jìn)程的調(diào)度

　　實(shí)時(shí)進(jìn)程,，只有靜態(tài)優(yōu)先級(jí)，因?yàn)閮?nèi)核不會(huì)再根據(jù)休眠等因素對(duì)其靜態(tài)優(yōu)先級(jí)做調(diào)整,，其范圍在0~MAX_RT_PRIO-1間,。默認(rèn)MAX_RT_PRIO配置為100,，也即，默認(rèn)的實(shí)時(shí)優(yōu)先級(jí)范圍是0~99,。而nice值,，影響的是優(yōu)先級(jí)在MAX_RT_PRIO~MAX_RT_PRIO+40范圍內(nèi)的進(jìn)程。

　　不同與普通進(jìn)程,，系統(tǒng)調(diào)度時(shí),，實(shí)時(shí)優(yōu)先級(jí)高的進(jìn)程總是先于優(yōu)先級(jí)低的進(jìn)程執(zhí)行。知道實(shí)時(shí)優(yōu)先級(jí)高的實(shí)時(shí)進(jìn)程無(wú)法執(zhí)行,。實(shí)時(shí)進(jìn)程總是被認(rèn)為處于活動(dòng)狀態(tài),。如果有數(shù)個(gè) 優(yōu)先級(jí)相同的實(shí)時(shí)進(jìn)程，那么系統(tǒng)就會(huì)按照進(jìn)程出現(xiàn)在隊(duì)列上的順序選擇進(jìn)程,。假設(shè)當(dāng)前CPU運(yùn)行的實(shí)時(shí)進(jìn)程A的優(yōu)先級(jí)為a,，而此時(shí)有個(gè)優(yōu)先級(jí)為b的實(shí)時(shí)進(jìn)程B進(jìn)入可運(yùn)行狀態(tài)，那么只要b<a,，系統(tǒng)將中斷A的執(zhí)行,，而優(yōu)先執(zhí)行B，直到B無(wú)法執(zhí)行（無(wú)論A,，B為何種實(shí)時(shí)進(jìn)程）,。

 　　不同調(diào)度策略的實(shí)時(shí)進(jìn)程只有在相同優(yōu)先級(jí)時(shí)才有可比性：

 　　1. 對(duì)于FIFO的進(jìn)程，意味著只有當(dāng)前進(jìn)程執(zhí)行完畢才會(huì)輪到其他進(jìn)程執(zhí)行,。由此可見(jiàn)相當(dāng)霸道,。

 　　2. 對(duì)于RR的進(jìn)程。一旦時(shí)間片消耗完畢,，則會(huì)將該進(jìn)程置于隊(duì)列的末尾,，然后運(yùn)行其他相同優(yōu)先級(jí)的進(jìn)程，如果沒(méi)有其他相同優(yōu)先級(jí)的進(jìn)程,，則該進(jìn)程會(huì)繼續(xù)執(zhí)行,。

 　　總而言之，對(duì)于實(shí)時(shí)進(jìn)程,，高優(yōu)先級(jí)的進(jìn)程就是大爺,。它執(zhí)行到?jīng)]法執(zhí)行了,，才輪到低優(yōu)先級(jí)的進(jìn)程執(zhí)行,。等級(jí)制度相當(dāng)森嚴(yán)啊。

　　重頭戲,，說(shuō)下非實(shí)時(shí)進(jìn)程調(diào)度

　　引子 

 　　言歸正傳

  　　Linux對(duì)普通的進(jìn)程,，根據(jù)動(dòng)態(tài)優(yōu)先級(jí)進(jìn)行調(diào)度。而動(dòng)態(tài)優(yōu)先級(jí)是由靜態(tài)優(yōu)先級(jí)（static_prio）調(diào)整而來(lái),。Linux下,，靜態(tài)優(yōu)先級(jí)是用戶(hù)不可見(jiàn)的，隱藏在內(nèi)核中,。而內(nèi)核提供給用戶(hù)一個(gè)可以影響靜態(tài)優(yōu)先級(jí)的接口,，那就是nice值，兩者關(guān)系如下：

　　static_prio=MAX_RT_PRIO +nice+ 20

　　nice值的范圍是-20~19,，因而靜態(tài)優(yōu)先級(jí)范圍在100~139之間,。nice數(shù)值越大就使得static_prio越大，最終進(jìn)程優(yōu)先級(jí)就越低,。

　　ps -el 命令執(zhí)行結(jié)果：NI列顯示的每個(gè)進(jìn)程的nice值,，PRI是進(jìn)程的優(yōu)先級(jí)（如果是實(shí)時(shí)進(jìn)程就是靜態(tài)優(yōu)先級(jí)，如果是非實(shí)時(shí)進(jìn)程,，就是動(dòng)態(tài)優(yōu)先級(jí)）　　

　　而進(jìn)程的時(shí)間片就是完全依賴(lài) static_prio 定制的,，見(jiàn)下圖，摘自《深入理解linux內(nèi)核》,，

 　　我們前面也說(shuō)了,，系統(tǒng)調(diào)度時(shí)，還會(huì)考慮其他因素,，因而會(huì)計(jì)算出一個(gè)叫進(jìn)程動(dòng)態(tài)優(yōu)先級(jí)的東西,，根據(jù)此來(lái)實(shí)施調(diào)度。因?yàn)?，不僅要考慮靜態(tài)優(yōu)先級(jí),，也要考慮進(jìn)程的屬性。例如如果進(jìn)程屬于交互式進(jìn)程,，那么可以適當(dāng)?shù)恼{(diào)高它的優(yōu)先級(jí),，使得界面反應(yīng)地更加迅速，從而使用戶(hù)得到更好的體驗(yàn),。Linux2.6 在這方面有了較大的提高,。Linux2.6認(rèn)為，交互式進(jìn)程可以從平均睡眠時(shí)間這樣一個(gè)measurement進(jìn)行判斷,。進(jìn)程過(guò)去的睡眠時(shí)間越多,，則越有可能屬于交互式進(jìn)程。則系統(tǒng)調(diào)度時(shí),，會(huì)給該進(jìn)程更多的獎(jiǎng)勵(lì)（bonus）,，以便該進(jìn)程有更多的機(jī)會(huì)能夠執(zhí)行,。獎(jiǎng)勵(lì)（bonus）從0到10不等。

　　系統(tǒng)會(huì)嚴(yán)格按照動(dòng)態(tài)優(yōu)先級(jí)高低的順序安排進(jìn)程執(zhí)行,。動(dòng)態(tài)優(yōu)先級(jí)高的進(jìn)程進(jìn)入非運(yùn)行狀態(tài),，或者時(shí)間片消耗完畢才會(huì)輪到動(dòng)態(tài)優(yōu)先級(jí)較低的進(jìn)程執(zhí)行。動(dòng)態(tài)優(yōu)先級(jí)的計(jì)算主要考慮兩個(gè)因素：靜態(tài)優(yōu)先級(jí),，進(jìn)程的平均睡眠時(shí)間也即bonus,。計(jì)算公式如下，

     dynamic_prio = max (100, min (static_prio - bonus + 5, 139))

　　在調(diào)度時(shí),，Linux2.6 使用了一個(gè)小小的trick,，就是算法中經(jīng)典的空間換時(shí)間的思想[還沒(méi)對(duì)照源碼確認(rèn)]，使得計(jì)算最優(yōu)進(jìn)程能夠在O(1)的時(shí)間內(nèi)完成,。

 　為什么根據(jù)睡眠和運(yùn)行時(shí)間確定獎(jiǎng)懲分?jǐn)?shù)是合理的

　　睡眠和CPU耗時(shí)反應(yīng)了進(jìn)程IO密集和CPU密集兩大瞬時(shí)特點(diǎn),，不同時(shí)期，一個(gè)進(jìn)程可能即是CPU密集型也是IO密集型進(jìn)程,。對(duì)于表現(xiàn)為IO密集的進(jìn)程,，應(yīng)該經(jīng)常運(yùn)行，但每次時(shí)間片不要太長(zhǎng),。對(duì)于表現(xiàn)為CPU密集的進(jìn)程,，CPU不應(yīng)該讓其經(jīng)常運(yùn)行，但每次運(yùn)行時(shí)間片要長(zhǎng),。交互進(jìn)程為例,，假如之前其其大部分時(shí)間在于等待CPU，這時(shí)為了調(diào)高相應(yīng)速度,，就需要增加獎(jiǎng)勵(lì)分,。另一方面，如果此進(jìn)程總是耗盡每次分配給它的時(shí)間片,，為了對(duì)其他進(jìn)程公平,，就要增加這個(gè)進(jìn)程的懲罰分?jǐn)?shù)。可以參考CFS的virtutime機(jī)制.

現(xiàn)代方法CFS

　　不再單純依靠進(jìn)程優(yōu)先級(jí)絕對(duì)值,，而是參考其絕對(duì)值,，綜合考慮所有進(jìn)程的時(shí)間，給出當(dāng)前調(diào)度時(shí)間單位內(nèi)其應(yīng)有的權(quán)重,，也就是,，每個(gè)進(jìn)程的權(quán)重X單位時(shí)間=應(yīng)獲cpu時(shí)間，但是這個(gè)應(yīng)得的cpu時(shí)間不應(yīng)太?。僭O(shè)閾值為1ms）,，否則會(huì)因?yàn)榍袚Q得不償失。但是,，當(dāng)進(jìn)程足夠多時(shí)候,，肯定有很多不同權(quán)重的進(jìn)程獲得相同的時(shí)間——最低閾值1ms，所以,，CFS只是近似完全公平,。

Linux進(jìn)程狀態(tài)機(jī)

　　進(jìn)程是通過(guò)fork系列的系統(tǒng)調(diào)用（fork、clone,、vfork）來(lái)創(chuàng)建的,，內(nèi)核（或內(nèi)核模塊）也可以通過(guò)kernel_thread函數(shù)創(chuàng)建內(nèi)核進(jìn)程。這些創(chuàng)建子進(jìn)程的函數(shù)本質(zhì)上都完成了相同的功能——將調(diào)用進(jìn)程復(fù)制一份,，得到子進(jìn)程,。（可以通過(guò)選項(xiàng)參數(shù)來(lái)決定各種資源是共享、還是私有,。）
那么既然調(diào)用進(jìn)程處于TASK_RUNNING狀態(tài)（否則,，它若不是正在運(yùn)行，又怎么進(jìn)行調(diào)用,？）,，則子進(jìn)程默認(rèn)也處于TASK_RUNNING狀態(tài)。
另外,，在系統(tǒng)調(diào)用clone和內(nèi)核函數(shù)kernel_thread也接受CLONE_STOPPED選項(xiàng),，從而將子進(jìn)程的初始狀態(tài)置為 TASK_STOPPED。

 　　進(jìn)程創(chuàng)建后,，狀態(tài)可能發(fā)生一系列的變化,，直到進(jìn)程退出。而盡管進(jìn)程狀態(tài)有好幾種,，但是進(jìn)程狀態(tài)的變遷卻只有兩個(gè)方向——從TASK_RUNNING狀態(tài)變?yōu)榉荰ASK_RUNNING狀態(tài),、或者從非TASK_RUNNING狀態(tài)變?yōu)門(mén)ASK_RUNNING狀態(tài)。總之,，TASK_RUNNING是必經(jīng)之路,，不可能兩個(gè)非RUN狀態(tài)直接轉(zhuǎn)換。

也就是說(shuō),，如果給一個(gè)TASK_INTERRUPTIBLE狀態(tài)的進(jìn)程發(fā)送SIGKILL信號(hào),，這個(gè)進(jìn)程將先被喚醒（進(jìn)入TASK_RUNNING狀態(tài)），然后再響應(yīng)SIGKILL信號(hào)而退出（變?yōu)門(mén)ASK_DEAD狀態(tài)）,。并不會(huì)從TASK_INTERRUPTIBLE狀態(tài)直接退出,。

  　　進(jìn)程從非TASK_RUNNING狀態(tài)變?yōu)門(mén)ASK_RUNNING狀態(tài)，是由別的進(jìn)程（也可能是中斷處理程序）執(zhí)行喚醒操作來(lái)實(shí)現(xiàn)的,。執(zhí)行喚醒的進(jìn)程設(shè)置被喚醒進(jìn)程的狀態(tài)為T(mén)ASK_RUNNING,，然后將其task_struct結(jié)構(gòu)加入到某個(gè)CPU的可執(zhí)行隊(duì)列中。于是被喚醒的進(jìn)程將有機(jī)會(huì)被調(diào)度執(zhí)行。

 　　而進(jìn)程從TASK_RUNNING狀態(tài)變?yōu)榉荰ASK_RUNNING狀態(tài),，則有兩種途徑：

　　1,、響應(yīng)信號(hào)而進(jìn)入TASK_STOPED狀態(tài)、或TASK_DEAD狀態(tài),；
　　2,、執(zhí)行系統(tǒng)調(diào)用主動(dòng)進(jìn)入TASK_INTERRUPTIBLE狀態(tài)（如nanosleep系統(tǒng)調(diào)用）、或TASK_DEAD狀態(tài)（如exit系統(tǒng)調(diào)用）,；或由于執(zhí)行系統(tǒng)調(diào)用需要的資源得不到滿(mǎn)　　　　 足,，而進(jìn)入TASK_INTERRUPTIBLE狀態(tài)或TASK_UNINTERRUPTIBLE狀態(tài)（如select系統(tǒng)調(diào)用）。
　　顯然,，這兩種情況都只能發(fā)生在進(jìn)程正在CPU上執(zhí)行的情況下,。

 通過(guò)ps命令我們能夠查看到系統(tǒng)中存在的進(jìn)程，以及它們的狀態(tài)：

R(TASK_RUNNING),，可執(zhí)行狀態(tài),。

只有在該狀態(tài)的進(jìn)程才可能在CPU上運(yùn)行。而同一時(shí)刻可能有多個(gè)進(jìn)程處于可執(zhí)行狀態(tài),，這些進(jìn)程的task_struct結(jié)構(gòu)（進(jìn)程控制塊）被放入對(duì)應(yīng)CPU的可執(zhí)行隊(duì)列中（一個(gè)進(jìn)程最多只能出現(xiàn)在一個(gè)CPU的可執(zhí)行隊(duì)列中）,。進(jìn)程調(diào)度器的任務(wù)就是從各個(gè)CPU的可執(zhí)行隊(duì)列中分別選擇一個(gè)進(jìn)程在該CPU上運(yùn)行。
只要可執(zhí)行隊(duì)列不為空,，其對(duì)應(yīng)的CPU就不能偷懶,，就要執(zhí)行其中某個(gè)進(jìn)程。一般稱(chēng)此時(shí)的CPU“忙碌”,。對(duì)應(yīng)的,，CPU“空閑”就是指其對(duì)應(yīng)的可執(zhí)行隊(duì)列為空，以致于CPU無(wú)事可做,。
有人問(wèn),，為什么死循環(huán)程序會(huì)導(dǎo)致CPU占用高呢？因?yàn)樗姥h(huán)程序基本上總是處于TASK_RUNNING狀態(tài)（進(jìn)程處于可執(zhí)行隊(duì)列中）,。除非一些非常極端情況（比如系統(tǒng)內(nèi)存嚴(yán)重緊缺,，導(dǎo)致進(jìn)程的某些需要使用的頁(yè)面被換出，并且在頁(yè)面需要換入時(shí)又無(wú)法分配到內(nèi)存……）,，否則這個(gè)進(jìn)程不會(huì)睡眠,。所以CPU的可執(zhí)行隊(duì)列總是不為空（至少有這么個(gè)進(jìn)程存在），CPU也就不會(huì)“空閑”,。

很多操作系統(tǒng)教科書(shū)將正在CPU上執(zhí)行的進(jìn)程定義為RUNNING狀態(tài),、而將可執(zhí)行但是尚未被調(diào)度執(zhí)行的進(jìn)程定義為READY狀態(tài)，這兩種狀態(tài)在linux下統(tǒng)一為 TASK_RUNNING狀態(tài),。

S(TASK_INTERRUPTIBLE),，可中斷的睡眠狀態(tài)。

處于這個(gè)狀態(tài)的進(jìn)程因?yàn)榈却衬呈录陌l(fā)生（比如等待socket連接、等待信號(hào)量）,，而被掛起,。這些進(jìn)程的task_struct結(jié)構(gòu)被放入對(duì)應(yīng)事件的等待隊(duì)列中。當(dāng)這些事件發(fā)生時(shí)（由外部中斷觸發(fā),、或由其他進(jìn)程觸發(fā)）,，對(duì)應(yīng)的等待隊(duì)列中的一個(gè)或多個(gè)進(jìn)程將被喚醒,。

通過(guò)ps命令我們會(huì)看到,，一般情況下，進(jìn)程列表中的絕大多數(shù)進(jìn)程都處于TASK_INTERRUPTIBLE狀態(tài)（除非機(jī)器的負(fù)載很高）,。畢竟CPU就這么一兩個(gè),，進(jìn)程動(dòng)輒幾十上百個(gè)，如果不是絕大多數(shù)進(jìn)程都在睡眠,，CPU又怎么響應(yīng)得過(guò)來(lái),。

D(TASK_UNINTERRUPTIBLE)，不可中斷的睡眠狀態(tài),。

與TASK_INTERRUPTIBLE狀態(tài)類(lèi)似,，進(jìn)程處于睡眠狀態(tài)，但是此刻進(jìn)程是不可中斷的,。不可中斷,，指的并不是CPU不響應(yīng)外部硬件的中斷，而是指進(jìn)程不響應(yīng)異步信號(hào),。
絕大多數(shù)情況下,，進(jìn)程處在睡眠狀態(tài)時(shí)，總是應(yīng)該能夠響應(yīng)異步信號(hào)的,。否則你將驚奇的發(fā)現(xiàn),，kill -9竟然殺不死一個(gè)正在睡眠的進(jìn)程了！于是我們也很好理解,，為什么ps命令看到的進(jìn)程幾乎不會(huì)出現(xiàn)TASK_UNINTERRUPTIBLE狀態(tài),，而總是TASK_INTERRUPTIBLE狀態(tài)。

而TASK_UNINTERRUPTIBLE狀態(tài)存在的意義就在于,，內(nèi)核的某些處理流程是不能被打斷的,。如果響應(yīng)異步信號(hào)，程序的執(zhí)行流程中就會(huì)被插入一段用于處理異步信號(hào)的流程（這個(gè)插入的流程可能只存在于內(nèi)核態(tài),，也可能延伸到用戶(hù)態(tài)）,，于是原有的流程就被中斷了（參見(jiàn)《linux異步信號(hào)handle淺析》）。
在進(jìn)程對(duì)某些硬件進(jìn)行操作時(shí)（比如進(jìn)程調(diào)用read系統(tǒng)調(diào)用對(duì)某個(gè)設(shè)備文件進(jìn)行讀操作,，而read系統(tǒng)調(diào)用最終執(zhí)行到對(duì)應(yīng)設(shè)備驅(qū)動(dòng)的代碼,，并與對(duì)應(yīng)的物理設(shè)備進(jìn)行交互），可能需要使用TASK_UNINTERRUPTIBLE狀態(tài)對(duì)進(jìn)程進(jìn)行保護(hù)，以避免進(jìn)程與設(shè)備交互的過(guò)程被打斷,，造成設(shè)備陷入不可控的狀態(tài),。（比如read系統(tǒng)調(diào)用觸發(fā)了一次磁盤(pán)到用戶(hù)空間的內(nèi)存的DMA，如果DMA進(jìn)行過(guò)程中,，進(jìn)程由于響應(yīng)信號(hào)而退出了,，那么DMA正在訪(fǎng)問(wèn)的內(nèi)存可能就要被釋放了。）這種情況下的TASK_UNINTERRUPTIBLE狀態(tài)總是非常短暫的,，通過(guò)ps命令基本上不可能捕捉到,。

linux系統(tǒng)中也存在容易捕捉的TASK_UNINTERRUPTIBLE狀態(tài)。執(zhí)行vfork系統(tǒng)調(diào)用后,，父進(jìn)程將進(jìn)入TASK_UNINTERRUPTIBLE狀態(tài),，直到子進(jìn)程調(diào)用exit或exec。
通過(guò)下面的代碼就能得到處于TASK_UNINTERRUPTIBLE狀態(tài)的進(jìn)程：
#include <unistd.h>
void main() {
if (!vfork()) sleep(100);
}
編譯運(yùn)行,，然后ps一下：
kouu@kouu-one:~/test$ ps -ax | grep a\.out
4371 pts/0 D+ 0:00 ./a.out
4372 pts/0 S+ 0:00 ./a.out
4374 pts/1 S+ 0:00 grep a.out
然后我們可以試驗(yàn)一下TASK_UNINTERRUPTIBLE狀態(tài)的威力,。不管kill還是kill -9，這個(gè)TASK_UNINTERRUPTIBLE狀態(tài)的父進(jìn)程依然屹立不倒,。

T(TASK_STOPPED or TASK_TRACED),，暫停狀態(tài)或跟蹤狀態(tài)。

向進(jìn)程發(fā)送一個(gè)SIGSTOP信號(hào),，它就會(huì)因響應(yīng)該信號(hào)而進(jìn)入TASK_STOPPED狀態(tài)（除非該進(jìn)程本身處于TASK_UNINTERRUPTIBLE狀態(tài)而不響應(yīng)信號(hào)）,。（SIGSTOP與SIGKILL信號(hào)一樣，是非常強(qiáng)制的,。不允許用戶(hù)進(jìn)程通過(guò)signal系列的系統(tǒng)調(diào)用重新設(shè)置對(duì)應(yīng)的信號(hào)處理函數(shù),。）
向進(jìn)程發(fā)送一個(gè)SIGCONT信號(hào)，可以讓其從TASK_STOPPED狀態(tài)恢復(fù)到TASK_RUNNING狀態(tài),。

當(dāng)進(jìn)程正在被跟蹤時(shí),，它處于TASK_TRACED這個(gè)特殊的狀態(tài)?！罢诒桓櫋敝傅氖沁M(jìn)程暫停下來(lái),，等待跟蹤它的進(jìn)程對(duì)它進(jìn)行操作。比如在gdb中對(duì)被跟蹤的進(jìn)程下一個(gè)斷點(diǎn),，進(jìn)程在斷點(diǎn)處停下來(lái)的時(shí)候就處于TASK_TRACED狀態(tài),。而在其他時(shí)候，被跟蹤的進(jìn)程還是處于前面提到的那些狀態(tài),。
對(duì)于進(jìn)程本身來(lái)說(shuō),，TASK_STOPPED和TASK_TRACED狀態(tài)很類(lèi)似，都是表示進(jìn)程暫停下來(lái),。
而TASK_TRACED狀態(tài)相當(dāng)于在TASK_STOPPED之上多了一層保護(hù),，處于TASK_TRACED狀態(tài)的進(jìn)程不能響應(yīng)SIGCONT信號(hào)而被喚醒,。只能等到調(diào)試進(jìn)程通過(guò)ptrace系統(tǒng)調(diào)用執(zhí)行PTRACE_CONT、PTRACE_DETACH等操作（通過(guò)ptrace系統(tǒng)調(diào)用的參數(shù)指定操作）,，或調(diào)試進(jìn)程退出,，被調(diào)試的進(jìn)程才能恢復(fù)TASK_RUNNING狀態(tài)。

Z(TASK_DEAD - EXIT_ZOMBIE),，退出狀態(tài),，進(jìn)程成為僵尸進(jìn)程。

進(jìn)程在退出的過(guò)程中,，處于TASK_DEAD狀態(tài),。

在這個(gè)退出過(guò)程中，進(jìn)程占有的所有資源將被回收,，除了task_struct結(jié)構(gòu)（以及少數(shù)資源）以外,。于是進(jìn)程就只剩下task_struct這么個(gè)空殼,，故稱(chēng)為僵尸,。
之所以保留task_struct，是因?yàn)閠ask_struct里面保存了進(jìn)程的退出碼,、以及一些統(tǒng)計(jì)信息,。而其父進(jìn)程很可能會(huì)關(guān)心這些信息。比如在shell中,，$?變量就保存了最后一個(gè)退出的前臺(tái)進(jìn)程的退出碼,，而這個(gè)退出碼往往被作為if語(yǔ)句的判斷條件。
當(dāng)然,，內(nèi)核也可以將這些信息保存在別的地方,，而將task_struct結(jié)構(gòu)釋放掉，以節(jié)省一些空間,。但是使用task_struct結(jié)構(gòu)更為方便,，因?yàn)樵趦?nèi)核中已經(jīng)建立了從pid到task_struct查找關(guān)系，還有進(jìn)程間的父子關(guān)系,。釋放掉task_struct,，則需要建立一些新的數(shù)據(jù)結(jié)構(gòu)，以便讓父進(jìn)程找到它的子進(jìn)程的退出信息,。

父進(jìn)程可以通過(guò)wait系列的系統(tǒng)調(diào)用（如wait4,、waitid）來(lái)等待某個(gè)或某些子進(jìn)程的退出，并獲取它的退出信息,。然后wait系列的系統(tǒng)調(diào)用會(huì)順便將子進(jìn)程的尸體（task_struct）也釋放掉,。
子進(jìn)程在退出的過(guò)程中，內(nèi)核會(huì)給其父進(jìn)程發(fā)送一個(gè)信號(hào),，通知父進(jìn)程來(lái)“收尸”,。這個(gè)信號(hào)默認(rèn)是SIGCHLD,，但是在通過(guò)clone系統(tǒng)調(diào)用創(chuàng)建子進(jìn)程時(shí)，可以設(shè)置這個(gè)信號(hào),。

通過(guò)下面的代碼能夠制造一個(gè)EXIT_ZOMBIE狀態(tài)的進(jìn)程：
#include <unistd.h>
void main() {
if (fork())
while(1) sleep(100);
}
編譯運(yùn)行,，然后ps一下：
kouu@kouu-one:~/test$ ps -ax | grep a\.out
10410 pts/0 S+ 0:00 ./a.out
10411 pts/0 Z+ 0:00 [a.out] <defunct>
10413 pts/1 S+ 0:00 grep a.out

只要父進(jìn)程不退出，這個(gè)僵尸狀態(tài)的子進(jìn)程就一直存在,。那么如果父進(jìn)程退出了呢,，誰(shuí)又來(lái)給子進(jìn)程“收尸”？
當(dāng)進(jìn)程退出的時(shí)候,，會(huì)將它的所有子進(jìn)程都托管給別的進(jìn)程（使之成為別的進(jìn)程的子進(jìn)程）,。托管給誰(shuí)呢？可能是退出進(jìn)程所在進(jìn)程組的下一個(gè)進(jìn)程（如果存在的話(huà)）,，或者是1號(hào)進(jìn)程,。所以每個(gè)進(jìn)程、每時(shí)每刻都有父進(jìn)程存在,。除非它是1號(hào)進(jìn)程,。

1號(hào)進(jìn)程，pid為1的進(jìn)程,，又稱(chēng)init進(jìn)程,。
linux系統(tǒng)啟動(dòng)后，第一個(gè)被創(chuàng)建的用戶(hù)態(tài)進(jìn)程就是init進(jìn)程,。它有兩項(xiàng)使命：
1,、執(zhí)行系統(tǒng)初始化腳本，創(chuàng)建一系列的進(jìn)程（它們都是init進(jìn)程的子孫）,；
2,、在一個(gè)死循環(huán)中等待其子進(jìn)程的退出事件，并調(diào)用waitid系統(tǒng)調(diào)用來(lái)完成“收尸”工作,；
init進(jìn)程不會(huì)被暫停,、也不會(huì)被殺死（這是由內(nèi)核來(lái)保證的）。它在等待子進(jìn)程退出的過(guò)程中處于TASK_INTERRUPTIBLE狀態(tài),，“收尸”過(guò)程中則處于TASK_RUNNING狀態(tài),。

X(TASK_DEAD - EXIT_DEAD)，退出狀態(tài),，進(jìn)程即將被銷(xiāo)毀,。

而進(jìn)程在退出過(guò)程中也可能不會(huì)保留它的task_struct。比如這個(gè)進(jìn)程是多線(xiàn)程程序中被detach過(guò)的進(jìn)程（進(jìn)程,？線(xiàn)程,？參見(jiàn)《linux線(xiàn)程淺析》）?；蛘吒高M(jìn)程通過(guò)設(shè)置SIGCHLD信號(hào)的handler為SIG_IGN,，顯式的忽略了SIGCHLD信號(hào),。（這是posix的規(guī)定，盡管子進(jìn)程的退出信號(hào)可以被設(shè)置為SIGCHLD以外的其他信號(hào),。）
此時(shí),，進(jìn)程將被置于EXIT_DEAD退出狀態(tài)，這意味著接下來(lái)的代碼立即就會(huì)將該進(jìn)程徹底釋放,。所以EXIT_DEAD狀態(tài)是非常短暫的,，幾乎不可能通過(guò)ps命令捕捉到。

一些重要的雜項(xiàng)

調(diào)度程序的效率
“優(yōu)先級(jí)”明確了哪個(gè)進(jìn)程應(yīng)該被調(diào)度執(zhí)行,，而調(diào)度程序還必須要關(guān)心效率問(wèn)題,。調(diào)度程序跟內(nèi)核中的很多過(guò)程一樣會(huì)頻繁被執(zhí)行，如果效率不濟(jì)就會(huì)浪費(fèi)很多CPU時(shí)間,，導(dǎo)致系統(tǒng)性能下降,。
在linux 2.4時(shí)，可執(zhí)行狀態(tài)的進(jìn)程被掛在一個(gè)鏈表中,。每次調(diào)度,，調(diào)度程序需要掃描整個(gè)鏈表，以找出最優(yōu)的那個(gè)進(jìn)程來(lái)運(yùn)行,。復(fù)雜度為O(n),；
在linux 2.6早期，可執(zhí)行狀態(tài)的進(jìn)程被掛在N(N=140)個(gè)鏈表中,，每一個(gè)鏈表代表一個(gè)優(yōu)先級(jí)，系統(tǒng)中支持多少個(gè)優(yōu)先級(jí)就有多少個(gè)鏈表,。每次調(diào)度,，調(diào)度程序只需要從第一個(gè)不為空的鏈表中取出位于鏈表頭的進(jìn)程即可。這樣就大大提高了調(diào)度程序的效率,，復(fù)雜度為O(1),；
在linux 2.6近期的版本中，可執(zhí)行狀態(tài)的進(jìn)程按照優(yōu)先級(jí)順序被掛在一個(gè)紅黑樹(shù)（可以想象成平衡二叉樹(shù)）中,。每次調(diào)度,，調(diào)度程序需要從樹(shù)中找出優(yōu)先級(jí)最高的進(jìn)程。復(fù)雜度為O(logN),。

那么,，為什么從linux 2.6早期到近期linux 2.6版本，調(diào)度程序選擇進(jìn)程時(shí)的復(fù)雜度反而增加了呢,？
這是因?yàn)?，與此同時(shí)，調(diào)度程序?qū)叫缘膶?shí)現(xiàn)從上面提到的第一種思路改變?yōu)榈诙N思路（通過(guò)動(dòng)態(tài)調(diào)整優(yōu)先級(jí)實(shí)現(xiàn)）,。而O(1)的算法是基于一組數(shù)目不大的鏈表來(lái)實(shí)現(xiàn)的,，按我的理解,，這使得優(yōu)先級(jí)的取值范圍很小（區(qū)分度很低）,，不能滿(mǎn)足公平性的需求,。而使用紅黑樹(shù)則對(duì)優(yōu)先級(jí)的取值沒(méi)有限制（可以用32位、64位,、或更多位來(lái)表示優(yōu)先級(jí)的值）,，并且O(logN)的復(fù)雜度也還是很高效的。

調(diào)度觸發(fā)的時(shí)機(jī)
調(diào)度的觸發(fā)主要有如下幾種情況：
1,、當(dāng)前進(jìn)程（正在CPU上運(yùn)行的進(jìn)程）狀態(tài)變?yōu)榉强蓤?zhí)行狀態(tài),。
進(jìn)程執(zhí)行系統(tǒng)調(diào)用主動(dòng)變?yōu)榉强蓤?zhí)行狀態(tài)。比如執(zhí)行nanosleep進(jìn)入睡眠,、執(zhí)行exit退出,、等等；
進(jìn)程請(qǐng)求的資源得不到滿(mǎn)足而被迫進(jìn)入睡眠狀態(tài),。比如執(zhí)行read系統(tǒng)調(diào)用時(shí),，磁盤(pán)高速緩存里沒(méi)有所需要的數(shù)據(jù)，從而睡眠等待磁盤(pán)IO,；
進(jìn)程響應(yīng)信號(hào)而變?yōu)榉强蓤?zhí)行狀態(tài),。比如響應(yīng)SIGSTOP進(jìn)入暫停狀態(tài)、響應(yīng)SIGKILL退出,、等等,；

2、搶占,。進(jìn)程運(yùn)行時(shí),，非預(yù)期地被剝奪CPU的使用權(quán)。這又分兩種情況：進(jìn)程用完了時(shí)間片,、或出現(xiàn)了優(yōu)先級(jí)更高的進(jìn)程,。
優(yōu)先級(jí)更高的進(jìn)程受正在CPU上運(yùn)行的進(jìn)程的影響而被喚醒。如發(fā)送信號(hào)主動(dòng)喚醒,，或因?yàn)獒尫呕コ鈱?duì)象（如釋放鎖）而被喚醒,；
內(nèi)核在響應(yīng)時(shí)鐘中斷的過(guò)程中，發(fā)現(xiàn)當(dāng)前進(jìn)程的時(shí)間片用完,；
內(nèi)核在響應(yīng)中斷的過(guò)程中,，發(fā)現(xiàn)優(yōu)先級(jí)更高的進(jìn)程所等待的外部資源的變?yōu)榭捎茫瑥亩鴮⑵鋯拘?。比如CPU收到網(wǎng)卡中斷,，內(nèi)核處理該中斷，發(fā)現(xiàn)某個(gè)socket可讀,，于是喚醒正在等待讀這個(gè)socket的進(jìn)程,；再比如內(nèi)核在處理時(shí)鐘中斷的過(guò)程中,，觸發(fā)了定時(shí)器，從而喚醒對(duì)應(yīng)的正在nanosleep系統(tǒng)調(diào)用中睡眠的進(jìn)程,；

內(nèi)核搶占
理想情況下,，只要滿(mǎn)足“出現(xiàn)了優(yōu)先級(jí)更高的進(jìn)程”這個(gè)條件，當(dāng)前進(jìn)程就應(yīng)該被立刻搶占,。但是,，就像多線(xiàn)程程序需要用鎖來(lái)保護(hù)臨界區(qū)資源一樣，內(nèi)核中也存在很多這樣的臨界區(qū),，不大可能隨時(shí)隨地都能接收搶占,。
linux 2.4時(shí)的設(shè)計(jì)就非常簡(jiǎn)單，內(nèi)核不支持搶占,。進(jìn)程運(yùn)行在內(nèi)核態(tài)時(shí)（比如正在執(zhí)行系統(tǒng)調(diào)用,、正處于異常處理函數(shù)中），是不允許搶占的,。必須等到返回用戶(hù)態(tài)時(shí)才會(huì)觸發(fā)調(diào)度（確切的說(shuō),，是在返回用戶(hù)態(tài)之前，內(nèi)核會(huì)專(zhuān)門(mén)檢查一下是否需要調(diào)度）,；
linux 2.6則實(shí)現(xiàn)了內(nèi)核搶占,，但是在很多地方還是為了保護(hù)臨界區(qū)資源而需要臨時(shí)性的禁用內(nèi)核搶占。

也有一些地方是出于效率考慮而禁用搶占,，比較典型的是spin_lock,。spin_lock是這樣一種鎖，如果請(qǐng)求加鎖得不到滿(mǎn)足（鎖已被別的進(jìn)程占有）,，則當(dāng)前進(jìn)程在一個(gè)死循環(huán)中不斷檢測(cè)鎖的狀態(tài),，直到鎖被釋放。
為什么要這樣忙等待呢,？因?yàn)榕R界區(qū)很小，比如只保護(hù)“i+=j++;”這么一句,。如果因?yàn)榧渔i失敗而形成“睡眠-喚醒”這么個(gè)過(guò)程,，就有些得不償失了。
那么既然當(dāng)前進(jìn)程忙等待（不睡眠）,，誰(shuí)又來(lái)釋放鎖呢,？其實(shí)已得到鎖的進(jìn)程是運(yùn)行在另一個(gè)CPU上的，并且是禁用了內(nèi)核搶占的,。這個(gè)進(jìn)程不會(huì)被其他進(jìn)程搶占,，所以等待鎖的進(jìn)程只有可能運(yùn)行在別的CPU上。（如果只有一個(gè)CPU呢,？那么就不可能存在等待鎖的進(jìn)程了,。）
而如果不禁用內(nèi)核搶占呢,？那么得到鎖的進(jìn)程將可能被搶占，于是可能很久都不會(huì)釋放鎖,。于是,，等待鎖的進(jìn)程可能就不知何年何月得償所望了。

對(duì)于一些實(shí)時(shí)性要求更高的系統(tǒng),，則不能容忍spin_lock這樣的東西,。寧可改用更費(fèi)勁的“睡眠-喚醒”過(guò)程，也不能因?yàn)榻脫屨级尭邇?yōu)先級(jí)的進(jìn)程等待,。比如,，嵌入式實(shí)時(shí)linux montavista就是這么干的。
由此可見(jiàn),，實(shí)時(shí)并不代表高效,。很多時(shí)候?yàn)榱藢?shí)現(xiàn)“實(shí)時(shí)”，還是需要對(duì)性能做一定讓步的,。

多處理器下的負(fù)載均衡
前面我們并沒(méi)有專(zhuān)門(mén)討論多處理器對(duì)調(diào)度程序的影響,，其實(shí)也沒(méi)有什么特別的，就是在同一時(shí)刻能有多個(gè)進(jìn)程并行地運(yùn)行而已,。那么,，為什么會(huì)有“多處理器負(fù)載均衡”這個(gè)事情呢？
如果系統(tǒng)中只有一個(gè)可執(zhí)行隊(duì)列,，哪個(gè)CPU空閑了就去隊(duì)列中找一個(gè)最合適的進(jìn)程來(lái)執(zhí)行,。這樣不是很好很均衡嗎？
的確如此,，但是多處理器共用一個(gè)可執(zhí)行隊(duì)列會(huì)有一些問(wèn)題,。顯然，每個(gè)CPU在執(zhí)行調(diào)度程序時(shí)都需要把隊(duì)列鎖起來(lái),，這會(huì)使得調(diào)度程序難以并行,，可能導(dǎo)致系統(tǒng)性能下降。而如果每個(gè)CPU對(duì)應(yīng)一個(gè)可執(zhí)行隊(duì)列則不存在這樣的問(wèn)題,。
另外,，多個(gè)可執(zhí)行隊(duì)列還有一個(gè)好處。這使得一個(gè)進(jìn)程在一段時(shí)間內(nèi)總是在同一個(gè)CPU上執(zhí)行,，那么很可能這個(gè)CPU的各級(jí)cache中都緩存著這個(gè)進(jìn)程的數(shù)據(jù),，很有利于系統(tǒng)性能的提升。
所以,，在linux下,，每個(gè)CPU都有著對(duì)應(yīng)的可執(zhí)行隊(duì)列，而一個(gè)可執(zhí)行狀態(tài)的進(jìn)程在同一時(shí)刻只能處于一個(gè)可執(zhí)行隊(duì)列中。

于是,，“多處理器負(fù)載均衡”這個(gè)麻煩事情就來(lái)了,。內(nèi)核需要關(guān)注各個(gè)CPU可執(zhí)行隊(duì)列中的進(jìn)程數(shù)目，在數(shù)目不均衡時(shí)做出適當(dāng)調(diào)整,。什么時(shí)候需要調(diào)整,，以多大力度進(jìn)程調(diào)整，這些都是內(nèi)核需要關(guān)心的,。當(dāng)然,，盡量不要調(diào)整最好，畢竟調(diào)整起來(lái)又要耗CPU,、又要鎖可執(zhí)行隊(duì)列,，代價(jià)還是不小的。
另外,，內(nèi)核還得關(guān)心各個(gè)CPU的關(guān)系,。兩個(gè)CPU之間，可能是相互獨(dú)立的,、可能是共享cache的,、甚至可能是由同一個(gè)物理CPU通過(guò)超線(xiàn)程技術(shù)虛擬出來(lái)的……CPU之間的關(guān)系也是實(shí)現(xiàn)負(fù)載均衡的重要依據(jù)。關(guān)系越緊密,，進(jìn)程在它們之間遷移的代價(jià)就越小,。

優(yōu)先級(jí)繼承
由于互斥，一個(gè)進(jìn)程（設(shè)為A）可能因?yàn)榈却M(jìn)入臨界區(qū)而睡眠,。直到正在占有相應(yīng)資源的進(jìn)程（設(shè)為B）退出臨界區(qū),，進(jìn)程A才被喚醒。
可能存在這樣的情況：A的優(yōu)先級(jí)非常高,，B的優(yōu)先級(jí)非常低,。B進(jìn)入了臨界區(qū)，但是卻被其他優(yōu)先級(jí)較高的進(jìn)程（設(shè)為C）搶占了,，而得不到運(yùn)行,，也就無(wú)法退出臨界區(qū)。于是A也就無(wú)法被喚醒,。
A有著很高的優(yōu)先級(jí),，但是現(xiàn)在卻淪落到跟B一起，被優(yōu)先級(jí)并不太高的C搶占,，導(dǎo)致執(zhí)行被推遲。這種現(xiàn)象就叫做優(yōu)先級(jí)反轉(zhuǎn),。

出現(xiàn)這種現(xiàn)象是很不合理的,。較好的應(yīng)對(duì)措施是：當(dāng)A開(kāi)始等待B退出臨界區(qū)時(shí)，B臨時(shí)得到A的優(yōu)先級(jí)（還是假設(shè)A的優(yōu)先級(jí)高于B），以便順利完成處理過(guò)程,，退出臨界區(qū),。之后B的優(yōu)先級(jí)恢復(fù)。這就是優(yōu)先級(jí)繼承的方法,。

中斷處理線(xiàn)程化
在linux下,，中斷處理程序運(yùn)行于一個(gè)不可調(diào)度的上下文中。從CPU響應(yīng)硬件中斷自動(dòng)跳轉(zhuǎn)到內(nèi)核設(shè)定的中斷處理程序去執(zhí)行,，到中斷處理程序退出,，整個(gè)過(guò)程是不能被搶占的。
一個(gè)進(jìn)程如果被搶占了,，可以通過(guò)保存在它的進(jìn)程控制塊（task_struct）中的信息,，在之后的某個(gè)時(shí)間恢復(fù)它的運(yùn)行。而中斷上下文則沒(méi)有task_struct,，被搶占了就沒(méi)法恢復(fù)了,。
中斷處理程序不能被搶占，也就意味著中斷處理程序的“優(yōu)先級(jí)”比任何進(jìn)程都高（必須等中斷處理程序完成了,，進(jìn)程才能被執(zhí)行）,。但是在實(shí)際的應(yīng)用場(chǎng)景中，可能某些實(shí)時(shí)進(jìn)程應(yīng)該得到比中斷處理程序更高的優(yōu)先級(jí),。
于是,，一些實(shí)時(shí)性要求更高的系統(tǒng)就給中斷處理程序賦予了task_struct以及優(yōu)先級(jí)，使得它們?cè)诒匾臅r(shí)候能夠被高優(yōu)先級(jí)的進(jìn)程搶占,。但是顯然,，做這些工作是會(huì)給系統(tǒng)造成一定開(kāi)銷(xiāo)的，這也是為了實(shí)現(xiàn)“實(shí)時(shí)”而對(duì)性能做出的一種讓步,。