linux內核設計與實現讀書筆記

 　　進程的調度程序是保證進程能有效工作的一個內核子系統。調度程序負責決定將哪個進程投入運行，何時運行以及運行多少時間。簡單的來說，調度程序就是在給一堆就緒的進程分配處理器的時間，調度程序是多任務操作系統的基礎。調度程序的原則就是最大限度的使用cpu的資源，也就是說，當系統中只要有可運行的進程，就不能讓cpu處於空閒的狀態，如果系統中沒有就緒的進程時，則cpu會運行一個idle進程。

　　1.多任務

　　多任務操作系統就是能夠同時並發的交互執行多個進程的操作系統，需要注意這裡是並發，而不是並行。如果你的計算機有兩個或者兩個以上的cpu那麼，你的計算機就可以真正同時、並行的執行多個任務。多任務操作系統可以分為兩類：搶占式多任務和非搶占式多任務。

　　搶占式多任務中，由調度程序來決定什麼時候停止一個進程的執行，這種由調度程序強行停止一個進程執行的動作稱為搶占(preemption)。進程在被搶占之前運行的時間是固定的，而且有一個專門的名字，叫做時間片(timeslice)。時間片實際上是分配給每個進程的處理器時間段。

　　而非搶占式多任務是由進程自己做出讓步，在執行了一段時間之後，主動地讓出cpu。進程主動掛起自己的操作稱為讓步(yielding)，如果某個進程懸掛起來並且拒不作出讓步的話，可能會導致操作系統崩潰。

　　所以總述上面的兩種情況，搶占式多任務就像“法律”，只要時間到了，就把你撤下來。而非搶占式卻像“道德”一樣，你要是有道德，執行了一會之後，你就自己撤下來，如果有的“人”占著茅坑不拉屎，那其他進程除了用“道德”譴責它，也沒有其他的辦法了。

　　2.linux進程調度

　　linux最初的進程調度程序是非常原始的，很難適應一些眾多的可運行進程和多處理器環境。後來從linux2.5開始，對linux的進程調度程序做了大的調整，使用了稱為O(1)的調度算法，這個算法引起算法行為而得名。O(1)調度算法雖然在數以十計的多處理器上能表現出近乎完美的特性和可擴展性，但是由於這個算法在調度交互進程的時候並沒有表現出很理想的效果。所以在linux2.6的開發初期，提出了CFS算法，即完全公平調度算法。

　　3.策略

　　(1)IO消耗型進程和處理器消耗型進程

　　IO消耗型進程指的是進程的大部分時間是用來等待IO的操作，例如圖形用戶界面(GUI)程序就屬於IO消耗型程序，這個程序需要不斷的監聽來自用戶的輸入。這樣的進程經常處於可運行的狀態，但是每次運行的時間都很短。

　　處理器消耗型進程是指進程的大部分時間用在執行代碼上，比如大型的計算程序MATLAB就屬於處理器消耗型進程。

　　還有一些應用程序雖然劃分為IO消耗型進程，但是也有處理器消耗型進程的特征。例如，字處理程序，在大多數時間可能等待來自用戶的輸入，但是在某段時間該程序又可能粘住處理器瘋狂的進行語法和拼寫錯誤的檢查。

　　調度程序需要在兩個矛盾目標中尋找平衡————進程的迅速響應和高吞吐量。unix和linux為了獲得良好的用戶響應，因此都傾向於調度IO消耗型進程。

　　(2)進程優先級

　　調度算法中最基本的一種就是基於進程優先級的調度，這是一種根據進程的價值和其對處理器的時間需求來對進程分級的一種想法。通常的做法是優先級高的進程先執行，低的後運行，相同優先級的進程按輪轉方式進行調度(一個接一個，重復進行)。在某些操作系統中，優先級高的進程的使用的時間片也長一些。調度程序總是選擇優先級高的，並且時間片尚未用盡的進程。

　　linux系統采用了兩種不同類別的優先級，第一種是使用nice值，范圍是從-20到+19，值越大表示優先級越低。這個優先級適用於一般的進程。

　　另外，linux對實時進程采用實時優先級，值從0-99，值越大代表優先級越高。實時進程的優先級都高於普通進程，因此這兩個進程優先級是處於兩個互不相交的范圍內。

　　(3)時間片

　　時間片是一個數值，他表示進程在被搶占前能夠持續運行的時間。時間片過長會導致系統對交互的響應表現欠佳，時間片過短，卻又明顯增大進程切換帶來的處理器時間消耗。所以IO消耗型進程和處理器消耗型進程的矛盾在這裡又再次顯現出來，IO消耗型進程不需要長的時間片，而處理器消耗型進程則希望時間片越長越好。

　　長時間片將導致系統的交互性表現欠佳，很多的操作系統都很重視這一點，因此將時間片設置的很短，如10ms。但是linux的CFS調度算法並沒有直接分配時間片到進程，它是將處理器的使用比分給了進程，這樣進程獲得的處理器的時間是和系統負載密切相關的。這個比例還會受到nice值的影響，nice值作為權重將調整進程使用處理器時間的使用比。具有更高nice值(低優先級)的進程將被賦予低權重，從而喪失一小部分處理器的使用比，而具有低nice值(高優先級)的進程江北賦予高權重，從而獲得更多的處理器使用比。

　　在多數的搶占式操作系統中，一個新就緒的進程能否立即執行(即搶占原來的進程)，完全取決於新進程的優先級和是否有時間片。而在linux中采用的CFS調度器，其搶占時機取決於新的進程消耗了多少處理器的使用比，如果新就緒的進程消耗的處理器使用比低於當前的進程，則新進程搶占當前進程，立即投入運行。