1 進程狀態(tài)模型
在操作系統(tǒng)中，進程的狀態(tài)模型一般可以用進程五狀態(tài)模型來概括簸喂，其他模型只是在五狀態(tài)模型上的增刪难菌。
1.1 state域狀態(tài)
對于Linux內(nèi)核而言，進程的狀態(tài)描述沿用了五狀態(tài)模型柜去，進程狀態(tài)在進程描述符（task_struct）的state域（類似于C++類中成員變量的概念）中進行描述灰嫉，該域有五種狀態(tài)標(biāo)志：
（1）TASK_RUNNING：被標(biāo)記為該值的進程是可運行的，包括正在運行和在運行隊列中等待執(zhí)行的進程诡蜓。對應(yīng)進程五狀態(tài)模型中的運行和就緒兩種狀態(tài)熬甫。
（2）TASK_INTERRUPTIBLE：被標(biāo)記為該值的進程是被阻塞的，即進程在某些條件的滿足后，才能投入運行椿肩，對應(yīng)進程無狀態(tài)模型中的阻塞狀態(tài)瞻颂。
（3）TASK_UNINTERRUPTIBLE：被標(biāo)記為該值的進程同樣是被阻塞的，但是和被標(biāo)記為TASK_INTERRUPTIBLE的進程不同郑象，被標(biāo)記為該值的進程是不可中斷的贡这，對外部信號不會做任何響應(yīng)。所以該值標(biāo)記的進程必須是在等待時不受干擾厂榛，或者等待時間很快發(fā)生時才使用盖矫。 該狀態(tài)同樣對應(yīng)于進程無狀態(tài)模型中的阻塞狀態(tài)。
（4）__TASK_TRACED：被標(biāo)記為該值的進程是被其他進程跟蹤的击奶。在五狀態(tài)模型中沒有對應(yīng)的狀態(tài)辈双。
（5）__TASK_STOPPED：被標(biāo)記為該值的進程是停止執(zhí)行的，進程沒有投入運行柜砾，也不能投入運行湃望。在五狀態(tài)模型中沒有對應(yīng)的狀態(tài)。雖然該狀態(tài)可以勉強歸為退出態(tài)痰驱，但是這種描述并不準(zhǔn)確证芭。
需要注意的是，在Linux操作系統(tǒng)上使用ps命令查看進程狀態(tài)時担映，往往看到的進程狀態(tài)為以下幾種：
（1）D ：不可中斷的深度睡眠废士，一般由IO引起，同步IO在做讀或?qū)懖僮鲿r蝇完，此進程不能做其它事情官硝，只能等待，這時進程處于這種狀態(tài)四敞，如果程序采用異步IO泛源，這種狀態(tài)應(yīng)該就很少見到了
（2）R：進程處于運行或就緒狀態(tài)
（3）S： 可接收信號的睡眠狀態(tài)
（4）T：被ctrl+z中斷或被trace
（5）W：2.6的系統(tǒng)版本之后已不在使用
（6）X：進程已經(jīng)完全死掉，此狀態(tài)不可見
（7）Z： 進程已經(jīng)終止忿危，但是其父進程尚未對其進行處理
這些通過ps命令可以查詢到的標(biāo)志位达箍，其實都是內(nèi)核進程狀態(tài)的一種反映，他們和內(nèi)核進程的state域不能混為一談铺厨。
2 Linux進程調(diào)度
2.1 進程種類和調(diào)度算法演變
編寫高效的進程調(diào)度程序就需要對進程的種類有所了解缎玫，進程由于其執(zhí)行操作類別執(zhí)行時間等被分為了兩種類型，一種為I/O消耗型解滓，另一種為處理器消耗型（有時又被稱為I/O密集型和處理器密集型）赃磨。所謂I/O消耗型指進程的大部分時間都用來提交和等待I/O請求，所以進程經(jīng)常需要運行洼裤，但是由于I/O的原因邻辉，又會經(jīng)常被阻塞，但是運行時間很短；而處理器消耗型則是指進程把大部分時間用在代碼的執(zhí)行上值骇。
但是實際上進程的類型時復(fù)雜的莹菱，進程有時候可能會同時擁有I/O消耗型和處理器消耗型的特性；而又有一些進程在一段時間內(nèi)是I/O消耗型吱瘩，而在另外一段時間又是處理器消耗型道伟。所以調(diào)度程序需要能動態(tài)地對進程進行合法的調(diào)度，來提高系統(tǒng)運行的效率使碾。
調(diào)度程序的目標(biāo)一般有兩個,進程響應(yīng)速度和最大系統(tǒng)利用率蜜徽，這兩個目標(biāo)其實是互相矛盾的，所以進程調(diào)度程序需要在二者之中取得平衡票摇。為了追求更高的性能拘鞋，進程調(diào)度程序在Linux內(nèi)核的2.5版本中引入了O(1)調(diào)度器來取代之前的調(diào)度程序，為了提高系統(tǒng)的響應(yīng)性矢门，內(nèi)核開發(fā)者又在2.6版本時诀黍，引入了反轉(zhuǎn)樓梯最后期限調(diào)度算法（Rotating Staircase Deadline Scheduler）(RSDL)焙格，RSDL后來又演變?yōu)椤?strong>完全公平調(diào)度算法”角虫，簡稱CFS印机，并在2.6.23內(nèi)核版本中取代了O(1)調(diào)度算法如绸。
2.2 傳統(tǒng)進程調(diào)度算法
進程調(diào)度算法一般來說可以分為兩種蝶押，優(yōu)先級調(diào)度算法和時間片調(diào)度算法昼激，這兩種調(diào)度算法大多數(shù)操作系統(tǒng)都進行結(jié)合使用拖陆。優(yōu)先級調(diào)度根據(jù)進程價值和進程對處理器需求來對進程的優(yōu)先級進行劃分障本，高優(yōu)先級先執(zhí)行教届，低優(yōu)先級后執(zhí)行，然后不斷輪轉(zhuǎn)驾霜。而時間片調(diào)度算法則是為每一個可執(zhí)行的進程分配一個時間片（有時也被稱為量子或者處理器片）案训，這個時間片就是在一段時間內(nèi)可供進程執(zhí)行的時間（更專業(yè)的說法是時間片表示的是進程在被搶占前所能持續(xù)運行的時間），當(dāng)進程時間片用完之后粪糙，就會從處理器中換出强霎，而另外一個時間片沒有用完的進程就會被換入處理器中開始執(zhí)行。Linux操作系統(tǒng)中的CFS也使用了優(yōu)先級和時間片這兩個概念蓉冈，但是其實現(xiàn)方式有其特殊之處城舞。
Linux內(nèi)核規(guī)定了兩種優(yōu)先級，第一種為nice值寞酿，第二種為實時優(yōu)先級（該值的設(shè)置意味這進程為實時進程家夺，先不進行分析）。nice值的范圍在-20到+19之間伐弹，默認為0拉馋，nice值越大優(yōu)先級越低。在傳統(tǒng)的Unix或者在CFS（完全公平調(diào)度算法）之前，nice值和時間片的映射關(guān)系為簡單映射煌茴，例如nice值為0時随闺，對應(yīng)的時間片為100ms，nice為+19時就對應(yīng)5ms景馁，所以nice直接決定了時間片的大邪遄场（又被稱為絕對時間片分配，或者nice值對時間片進行算數(shù)加權(quán)）合住。
2.3 傳統(tǒng)調(diào)度算法主要問題
（1）進程切換過于頻繁：假設(shè)nice為0的時間片為100ms绰精，那么nice值為+19的時間片就為5ms，毫無疑問透葛，當(dāng)兩個nice值為19的進程存在時笨使，系統(tǒng)每過5ms就要進行一次進程調(diào)度，導(dǎo)致進程切換十分頻繁僚害，大量時間被進程切換所消耗硫椰。
（2）nice值的不同導(dǎo)致時間片大小相差過大：假設(shè)nice值為0時的時間片為100ms，那么nice值為18的時間片為10ms萨蚕，nice值為19的時間片為5ms靶草，而18和19nice值僅僅只是相差1，但是時間片卻相差了兩倍岳遥，這明顯是不合理的奕翔。
（3）最小時間片無法實現(xiàn)：由于系統(tǒng)限制，要求所有時間片必須為定時器節(jié)拍的整數(shù)倍（先行記下再說）浩蓉，那么就導(dǎo)致最小時間片也是定時器節(jié)拍的整數(shù)倍派继；系統(tǒng)定時器限制了兩個時間片的差異；時間片會隨著定時器節(jié)拍改變捻艳。（這個和后面的定時器有關(guān)驾窟，但是這一點的確是CFS被采用的主要原因）
（4）無法進行公平調(diào)度：為了使有些進程能夠更快地投入運行，該進程的優(yōu)先級可能會被提高认轨，即使該進程時間片用盡绅络，這樣就會導(dǎo)致時間片分配的問題，使得某些進程可以獲得更多處理器時間嘁字，損害其他進程的利益昨稼。
2.4 CFS完全公平調(diào)度算法
完全公平調(diào)度算法CFS將進程獲取的處理器時間進行了重新的劃分，時間片和nice值之間的關(guān)系不再是絕對的拳锚，而是一種相對的劃分方式假栓。CFS希望進程調(diào)度的效果和一個具有理想完美多任務(wù)處理器的系統(tǒng)相同。在這種系統(tǒng)中霍掺，若有n個進程匾荆，那么每個進程將被分配到1/n的處理器時間拌蜘。CFS就是在這樣的理想模型下，考慮了在現(xiàn)實中進程的切換的代價所設(shè)計的牙丽。CFS允許每個進程運行一段時間简卧、循環(huán)輪轉(zhuǎn)、選擇運行最少的進程最為下一個運行進程烤芦，然后將nice值的概念重新定義举娩，不在像之前一樣，將nice值和時間片進行絕對映射构罗，而是將nice值作為進程獲得處理器運行比的權(quán)重铜涉，越高的nice值獲得的處理器運行比權(quán)重越低。每個進程都按照權(quán)重遂唧，獲取自身在全部可運行進程所占比例的時間片運行芙代。
為了更加精確計算框出時間的可運行時間，CFS又引入了目標(biāo)延遲——完美多任務(wù)中的無限小調(diào)度周期近似值盖彭。為了更直觀的說明問題纹烹，可以使用代數(shù)式來進行表達。假設(shè)目標(biāo)延遲為T召边，系統(tǒng)中有三個nice值分別為0铺呵，+10，+15的進程隧熙，而nice值0所對應(yīng)的權(quán)重值為Q_0陪蜻，nice值10對應(yīng)的權(quán)重值為Q_10，nice值15對應(yīng)的權(quán)重值為Q_15,那么三個進程時間片就分別為如下所示：
t_0=Q_0/(Q_0+Q_10+Q_15 ) T
t_10=Q_10/(Q_0+Q_10+Q_15 ) T
t_15=Q_15/(Q_0+Q_10+Q_15 ) T
贱鼻！注意，在CFS中所指的時間片一般都是進程在目標(biāo)延遲內(nèi)的可運行時間滋将，而有一些書里會提到"CFS不再有時間片概念"（例如《Linux內(nèi)核設(shè)計與實現(xiàn)》）邻悬，其實是指絕對時間片的分配
這樣的劃分方式又重新引入了一個問題，那就是當(dāng)可運行的任務(wù)數(shù)量趨于無限時随闽，每個進程所獲得的處理器使用比和時間片都會趨于0父丰，這樣將會導(dǎo)致系統(tǒng)不斷進行進程切換，造成系統(tǒng)資源的巨大損耗掘宪。為了解決這個問題蛾扇，CFS特意引入了另外一個概念——最小粒度，最小粒度為每個進程可以獲得的時間片最小值魏滚，這個值在默認情況下為1ms镀首。采用最小粒度之后，即便有可運行進程數(shù)量趨于無限鼠次，每個進程也能獲得最小粒度的執(zhí)行時間更哄。
CFS對于nice值的重新定義芋齿，解決了之前絕對映射的問題。
首先成翩，當(dāng)只有兩個nice值相同但是都很大的進程在系統(tǒng)中運行時觅捆，其所占據(jù)的時間片都為目標(biāo)延遲的二分之一，而不是之前很小的值麻敌，這樣就解決了兩個高nice值進程運行導(dǎo)致的進程頻繁切換問題栅炒；
其次，當(dāng)只有兩個高nice值术羔，但是兩個nice值并不相同的進程在系統(tǒng)中運行時赢赊，由于將nice值原來和時間片的絕對映射改為了相對映射，所以不會出現(xiàn)nice值相差很小聂示，但是時間片倍數(shù)相差的情況域携；
然后，引入處理器使用比的方法鱼喉，解決分配絕對時間片引發(fā)的時間片會隨著時鐘節(jié)拍修改的問題秀鞭，進程運行的時間片也不再是一個絕對值；
最后扛禽，對時間片分配方式進行了重新設(shè)計锋边，處理器使用比的分配不會出現(xiàn)固定的進程切換頻率問題，更好地進行公平調(diào)度编曼。
但是在采用CFS的系統(tǒng)中豆巨，如果出現(xiàn)大量可運行進程，由于最小粒度的存在掐场，將會導(dǎo)致一個問題往扔，那么就是nice值的大小，對于進程所獲取到的時間片大小沒有影響熊户，所有進程的時間片都將為最小粒度萍膛，導(dǎo)致進程調(diào)度公平性問題。這一問題的出現(xiàn)本質(zhì)上是為了保證系統(tǒng)進程不會出現(xiàn)頻繁切換所做出的必要犧牲嚷堡，這是一個進程調(diào)度程序設(shè)計過程中的取舍蝗罗，而且在設(shè)計中也盡量去規(guī)避這個問題，所以當(dāng)系統(tǒng)中可運行進程數(shù)量在只有幾百個時（通常情況下系統(tǒng)中的可運行進程數(shù)目）蝌戒，CFS的公平性是可以可以保證的串塑。
2.5 CFS進程選擇
進程選擇（選擇下一個執(zhí)行的進程）是進程調(diào)度中另一個重要的方面。在CFS中其實現(xiàn)方法如下：
首先北苟，CFS為每一個進程維護了一個實際運行時間和理想運行時間
其次桩匪，周期性地按照權(quán)重對進程的實際運行時間進行計算（和CFS時間片計算相同）
最后，在進行進程選擇的時候友鼻，比較實際運行時間和理想運行時間吸祟，選擇二者相差最大的進程投入運行
可以注意到瑟慈，CFS通過實際運行時間和理想運行時間來進行進程選擇。這樣做的好處就是可以將I/O消耗型進程和處理器消耗型進程進行區(qū)分調(diào)度屋匕。一般來說I/O消耗型進程追求響應(yīng)速度葛碧，而處理器消耗型進程追求系統(tǒng)利用率。
從CFS中的進程選擇設(shè)計中可以看出过吻，若每一個進程都擁有一個理想運行時間进泼，那么由于I/O消耗型進程一直在等待I/O事件的完成所以其實際運行時間必然很小，而處理器消耗型進程一直運行纤虽，所以其實際運行時間很大乳绕，所以在CFS調(diào)度算法在面對都可運行的I/O消耗型進程和處理器消耗型進程時，會更加傾向于去調(diào)用I/O消耗型進程逼纸，因此解決了系統(tǒng)反應(yīng)速度的問題洋措。
這是個人在閱讀《Linux內(nèi)核設(shè)計與實現(xiàn)》時候的一點心得，里面加入了一些自己關(guān)于操作系統(tǒng)的理解杰刽，對自己的現(xiàn)有的知識進行梳理菠发，如有錯誤敬請指正。
