關于linux的cfs排程器的宏觀了解

今天重讀了cfs排程器，使我忍不住再寫一篇關于cfs的文章，cfs排程器的運作時間是0(logN)，而以前的排程器的運作時間是O(1)，這是不是就是說cfs的效率比O(1)的更差呢？并不是那樣，我們知道cfs排程器下的運作隊列是基于紅黑樹組織的，找出下一個程序就是截下左下角的節點，固定時間完成，所謂的O(logN)指的是插入時間，可是紅黑樹的統計性能是不錯的，沒有多大機率真的用得了那麼多時間，因為紅節點和黑節點的特殊排列方式既保證了樹的一定程度的平衡，又不至于花太多的時間來維持這種平衡，插入操作大多數情況下都可以很快的完成，特别是對于組織得相當好的資料。實際上cfs之是以能進入核心并不是因為它能提供多好的性能，因為在一個事物的一種架構下，性能的提升肯定有個極限，不能一味的朝一個方向走，比如cpu的流水線在設計之初被認為是好的，可是intel的NetBurst架構一味的加長流水線，以為流水線越長性能越高，吞吐量越大，可是工程學中永遠沒有一直單調遞增的函數，總會有一個拐點的。

cfs的精髓在于它改變了核心看待程序排程的方式，時間片越細越好嗎？搶占點越多越好嗎？如果是的話，那麼很抱歉，到了2.6.17左右的核心，時間片已經很精細了，而且搶占點也不能再多了，如果這個推理正确的話，那豈不是說排程器不能繼續發展了嗎，linux絕對不是這樣的性格，O(1)排程器的設計者有破有立，提供了另外一種截然不同的排程方式，這就是cfs，抛棄了時間片，抛棄了複雜的算法，從一個新的起點開始了排程器的新時代，最開始的2.6.23版本核心的cfs是很簡單的，思想十分明确。cfs的本質思想就是提供一個虛拟的時鐘，所有程序複用這個虛拟時鐘的時間，cfs将時鐘的概念從底層體系相關的硬體中抽象出來，程序排程子產品直接和這個虛拟的時鐘接口而不必再為硬體時鐘操作而操心，如此一來，整個程序排程子產品就完整了，從時鐘到排程算法，到不同程序的不同政策，全部都由虛拟系統提供，也正是在這個新的核心，引入了排程類。是以新的排程器就是不同特性的程序在統一的虛拟時鐘下按照不同的政策被排程。我們看一下這樣做有什麼好處，cfs抛棄了時間片，采用了平滑的機制，用互相追趕的方式促使所有的程序一起向前走，那麼怎麼區分不同優先級的程序呢？總不能所有程序以相同的速度往前走吧，顯然不能！我們都相信，用互相追趕的方式是最好的方式，就好像競争一樣有益，我中中學的時候，老師就教導我們要互相追趕，雖然那個時候老師的意思就是大家都追趕我！既然相信互相追趕時最好的方式，那麼下一步就是怎麼實作互相追趕，如果在傳統的排程體系下，用硬時鐘，那麼很難實作不同程序的不同優先級的管理，于是提出虛拟時鐘的概念，每個程序都有一個虛拟時鐘，然後整個系統有一個虛拟時鐘，系統虛拟時鐘以固定的步調前進，而各個程序的虛拟時鐘的前進步調卻因為其優先級不同而不同，比如優先級低的程序其虛拟時鐘的步調比較快，而優先級高的步調比較慢，這一點用硬體時鐘是很難做到的，如果用硬體時鐘，我們就要維護每一個程序的狀态，然後将這個每個程序的狀态設定為一個全局的變量，可想而知，這個變量應該是個連結清單或者數組，每當硬體時鐘中斷的時候都要查找這個連結清單進行查找，删除，選舉等操作，十分繁瑣，不說時間，空間上占用的記憶體都無法接受。cfs提出的虛拟時鐘概念使得互相追趕更為容易實作，基于時間片的排程機制中，程序排程是被動的，排程子產品不得不想辦法探知每個程序的特點并且根據不同的特性設定給它們不同的政策，然後依據這些不同的政策配置設定給它們不同的時間片，這樣必然會出現變态級的預測算法，很複雜，讓學究們看來可以為我們賣弄一把，可是這個世界不喜歡複雜，是以學究們必須退讓；現在看看cfs排程器，程序有自己的優先級，并且映射到權值，每個權值的程序的虛拟時鐘步調不同，大家都按照自己的虛拟時鐘往前走就是了，排程子產品會選擇最落後于系統虛拟時鐘的程序來執行，這就是公平的含義，那麼在O(1)排程器中對互動程序的預測算法在cfs中怎麼展現呢？其實完全沒有必要考慮這個問題，因為在O(1）排程器中，之是以要區分互動程序是因為O（1）排程器完全是基于優先級來排程的，其它所有的排程依據都需要動态預測，而動态預測就必然需要複雜的算法，在cfs排程器中，不單單有優先級作為排程依據了，其實優先級映射到了程序權值，然後各個程序互相追趕，這樣可以保證任何程序都不會被耽擱太久，互動程序的問題就解決了，O(1)排程器不能這樣的原因就是因為程序們不能自己互相追趕。舉個例子，就是在O（1）中，一個互動程序和一個非互動程序的優先級都是p，排程器僅僅根據它們的優先級來進行排程，别的什麼也不知道，隻有靠探測它們的睡眠時間來進行程序類别的判斷，通過判斷如果一個程序是互動程序，那麼就暫且不把它放到過期隊列而是繼續運作用來補償它過多的睡眠，而在cfs排程器中就不會這樣，即使一個互動程序和一個非互動程序都被映射到了一個權值，互動程序随便睡眠，隻要它醒來，它就可以以不太大的（也不會太小，按照它自己的權值和目前的系統虛拟時鐘決定）key被加到紅黑樹，随着系統繼續運作，很公平的它就會運作。之是以O（1）中如果不預測互動程序會導緻互動程序的延遲是有原因的，另起一段吧，這一段太長了。

O（1）中導緻互動程序延遲響應的原因就是兩個數組存在，一個運作隊列一個過期隊列，按照一般道理，系統依據程序優先級來配置設定時間片，隻要時間片完畢就會被放到過期隊列，問題就出在這個過期隊列，按照道理，隻有所有優先級的所有程序都放到了過期隊列，也就是所有優先級的所有程序都運作完畢了，才會交換過期隊列和運作隊列，如果不進行區分的話，系統内運作的程序越多，互動程序看起來響應越遲鈍，是以O(1)中用睡眠時間區分了互動程序和非互動程序，可見在O(1)中，互動程序的延遲主要在所有程序的數量，其實這對于伺服器是無所謂的，但是對于互動程序就不行，因為伺服器程序強調優先級下的公平性，而互動程序強調響應性，對于公平性而言，要等隻要大家一起等就沒有問題，對于互動程序就根本不允許等待太久，不管怎樣，O(1)排程器都不是很令人滿意，在運作隊列的程序可以看到公平和高效，可是對于過期隊列的程序，面臨卻是無期的等待...在爽完了以後，雖然很多人都喜歡休息一會，但是我相信更多的人喜歡在不久的将來再爽一次。這麼說的話，O(1)的排程周期的粒度就是所有的程序的運作時間之和，這個算法雖然可以保證運作隊列程序的公平性卻無法保證全局的公平性，任何一個程序在運作了不管多久之後，都必須等待很長一段時間，在一個程序的整個生命周期看來是斷斷續續的，在cfs中，任何一個程序的執行都将是連續的，這就是cfs的進步，以前的排程器必須以硬體時鐘為準，是以不能太靈活，cfs以虛拟時鐘為準，靈活性很随意。

在2.6.23核心中，剛剛實作的cfs排程器顯得很淳樸，每次的時鐘滴答中都會将目前程序先出隊，推進其虛拟時鐘和系統虛拟時鐘後再入隊，然後判斷紅黑樹的左下角的程序是否還是目前程序而抉擇是否要排程，這種排程器的key的計算是用目前的虛拟時鐘減去待計算程序的等待時間，如果該計算程序在運作，那麼其等待時間就是負值，這樣，等待越長的程序key越小，進而越容易被選中投入運作；在2.6.25核心以後實作了一種更為簡單的方式，就是設定一個運作隊列的虛拟時鐘，它單調增長并且跟蹤該隊列的最小虛拟時鐘的程序，key值由程序的vruntime和隊列的虛拟時鐘的內插補點計算，這種方式就是真正的追趕，比2.6.23實作的簡單，但是很巧妙，不必在每次時鐘滴答中都将目前程序出隊，入隊，而是根據目前程序實際運作的時間和理想應該運作的時間判斷是否應該排程。

 本文轉自 dog250 51CTO部落格，原文連結:http://blog.51cto.com/dog250/1274147