兩種驅動系統運作的方式--分時的方式

引子：哪些是該負責的，哪些是不該負責的

哪些是該負責的，哪些是不該負責的，這是一個問題，hrtimer就能保證所有的timer都可以不延時的被執行嗎？不能，很簡單，如果你排入10000個timer，每一個哪怕執行1毫秒...這個問題就是使用者的使用政策問題了，不是hrtimer機制要負責的，而hrtimer要負責的是它的算法本身不能引入延遲，這也是它能保證的最後壁壘了，就好像再結實的汽車你非要開着它開下懸崖，死了之後變成鬼找到車的設計者抱怨沒能保護他的安全，這合理嗎？hrtimer用了紅黑樹資料結構，很高效的實作了timer到期後的處理，并沒有引入什麼延遲，僅僅就是一個線性出隊的時間複雜度罷了，而傳統的timer在執行的時候用了cascading算法，該算法的初衷是為了不想每次都輪詢所有的timer以檢測到期與否，但是該算法雖然減少了輪詢的時間延遲，但是算法本身的O(n)時間複雜度也是很可觀的，究其原因就在于它是基于jiffies的，而jiffies是一個基于tick的絕對單調遞增的值，除此之外别無任何政策可言，是以萬惡的tick機制才是罪魁禍首，htimer的回調函數采用了兩種觸發方式，這樣就可以讓使用者根據需求設定更多的政策，這是一個額外的優勢，于是就有了tickless。

開始：

在2.6的早期的核心以及更早的2.4核心中，時鐘周期性中斷是一個很重要的概念，因為它驅動了系統向前運作，一切的統計幾乎都是在時鐘中斷中進行的，核心中有一個jiffies全局變量，很多的機制依賴這個變量，是以如果時鐘的周期中斷停止，那麼整個系統也将停止，時鐘周期中斷的意義和心跳的意義類似，是一切的基礎，這裡面最重要的就是時鐘隻管周期性的中斷系統而不管其餘的機制如何去使用這個中斷處理，子產品分離的很不錯。但是有個問題就是時鐘中斷的周期也就成了度量時間的最基本最小的機關，這個周期就是一個tick的時間，按照配置和cpu頻率是不等的，這樣的話不管是使用者級别還是核心級别的睡眠或逾時喚醒間隔就嚴重受制于一個tick的時間間隔，如果一個tick是10ms，那麼10ms以下的睡眠就提供不了了，因為以前的timer是在時鐘中斷後的軟中斷上下文進行的，怎樣樣才能将定時機制和時鐘周期心跳機制分離呢？首先我們看看分離的必要性，時鐘周期中斷是為了推動系統前進的，程序排程等重要操作都在時鐘中斷中被驅動，而定時機制是程序或者驅動使用的一個必不可少的機制，它們二者不是太有必要綁定在一起的，是以有必要分離，并且定時機制和時鐘周期中斷分離以後必須可以提供更高的精度讓程序或者驅動使用而不是讓它們死死依賴住那個可靠但不精确的jiffies變量，于是hrtimer呼之欲出。hrtimer的出現可以說是打開了一個缺口，在哪裡打開一個缺口呢？是在驅動系統的方式上打開一個缺口，當clocksource和clock_event_device出現以後，這個缺口越來越大，最終的結果就是完全的tickless，不再需要周期的定時中斷了，這種新的驅動系統的方式就是任務驅動的，每個任務綁定一個hrtimer，然後将此hrtimer入隊後和所有的hrtimer比較，找出最小的，将其逾時時間設定為下一次的時鐘中斷時間，這樣時鐘就不會頻繁的打斷正在運作的任務了，特别是在cfs排程器成為主排程器之後，這種想法更加顯得合乎情理，因為cfs做到了一個排程周期内的公平排程，沒有驅動任務并且沒有搶占的理想情況下在一個排程周期内，tickless的系統隻需要和任務數量相等數量的時鐘中斷就可以了，固定時間内，時鐘中斷的數量和任務的數量成正比，這正是符合邏輯的，如果是原來的O(1)排程器，那麼時間片的配置設定是固定的，隻要優先級确定，同一HZ值情況下配置設定的時間片是一定的，是以同一時間段内時鐘中斷的數量和任務的數量沒有什麼關系，即使同樣都是一個程序，其優先級不同，同一時間段内發生的時鐘中斷也是不同的，這是不符合邏輯的，時鐘中斷的數量應該不能和程序優先級相關，因為程序分時排程(非搶占)是在時鐘中斷内發生的，是以為了公平，中斷的數量隻能和程序的數量相關，至于優先級的展現不能在中斷的數量上而應該在中斷的間隔上，是以cfs使tickless更加合理化，畢竟系統運作中程序排程是最重要的子產品之一。

目前的核心對tickless的實作上還是僅在cpu進入idle的時候才tickless，而正常情況下還是按照HZ進行周期的時鐘中斷，其實完全可以全局禁用周期中斷而全局改用tickless，但是需要做的就是将所有以來jiffies的機制全部用hrtimer實作，這可是一個不小的工程，另外周期中斷的另一個作用就是進行記帳，用于統計和評估，如果完全tickless的話，像那些以前基于傳統tick的timer就要同樣轉移到 hrtimer，理論上這也是很簡單的，但是實踐上可能不太适合linux的開發方式，為何說理論上簡單呢？将傳統的timer改變成每隔一個tick觸發一次的hrtimer就可以了，tick還是根據HZ計算出來，這樣我們完全可以把傳統的周期中斷的timer_interrupt中的各個不同的功能分離成不同的hrtimer，比如為每10ms統計記帳資訊的代碼提供一個hrtime，裡面就做這一件事并且它每10ms觸發一次然後再次加入 hrtimer對列，同樣負責程序排程的代碼也提供一個hrtimer，實際上核心早就這麼做了，該hrtimer就是hrtick_timer，它負責程序排程，如此一來程序的運作就不必再受到無休止的時鐘中斷打擾了，在cfs中，一個程序可以一次性運作完承諾給它的 sched_slice(cfs_rq, se)時間，在一個程序開始運作的時候，将hrtick_timer設定為到sched_slice(cfs_rq, se)之後到期豈不妙哉！cfs的代碼正是如此做的

static void hrtick_start_fair(struct rq *rq, struct task_struct *p)

{

struct sched_entity *se = &p->se;

struct cfs_rq *cfs_rq = cfs_rq_of(se);

if (hrtick_enabled(rq) && cfs_rq->nr_running > 1) {

u64 slice = sched_slice(cfs_rq, se);

u64 ran = se->sum_exec_runtime - se->prev_sum_exec_runtime;

s64 delta = slice - ran;

if (delta < 0) {

if (rq->curr == p)

resched_task(p);

return;

}

...//避免hrtimer頻繁到期的粒度最小化限制處理

hrtick_start(rq, delta); //操作hrtick_timer，排入hrtimer對列

以上函數在pick_next_task最後調用，其實就是在一個程序剛開始運作的時候調用，代碼十分容易了解。上面代碼中設定的hrtick_timer到期了以後将會調用它的回調函數，即htick，後者會用queued為1進一步調用task_tick：

static void entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)

update_curr(cfs_rq);

#ifdef CONFIG_SCHED_HRTICK

if (queued) { //如果queued為1并且設定CONFIG_SCHED_HRTICK也就是是hrtimer的情況下，直接排程，因為在程序開始運作的時候就設定該hrtimer到這個時間點到期，是以無條件排程

resched_task(rq_of(cfs_rq)->curr);

if (!sched_feat(DOUBLE_TICK) && //系統難免還保留着原來的周期中斷驅動的程序排程，但是同時也設定了程序排程的hrtimer，如此一來傳統的周期中斷就不能打擾hrtimer的行為

hrtimer_active(&rq_of(cfs_rq)->hrtick_timer))

#endif

if (cfs_rq->nr_running > 1 || !sched_feat(WAKEUP_PREEMPT))

check_preempt_tick(cfs_rq, curr);

現在稍微考慮一下搶占，如果一個程序還沒有運作完排程器承諾給它的時間就被搶占了，那怎麼辦，一切會亂掉嗎？不，在cfs上絲毫不會亂掉，另外的一個原因就是每個運作隊列隻有一個hrtick_timer，如果目前程序被搶占了，那麼可想而知它還沒有運作完它的sched_slice，剩下的時間怎麼辦，怎麼補償給它？答案就是不再顯式補償給它，而是隐式補償，靠的就是cfs的機制原理，被搶占的程序的vruntime不再向前推進，而cfs總是挑選 vruntime最小的程序運作，是以被搶占的程序在搶占它的程序運作完後會接着運作的幾率是有的，即使不接着運作它也總是會運作，而且在被搶占的這段時間内它的vruntime沒有推進，積攢的內插補點恰恰成了它的優勢。接着說搶占，由于每個運作隊列隻有一個hrtick_timer，在新程序開始運作的時候會重新hrtick_start，結果就是停掉了原來的hrtick_timer，當搶占程序運作完它的sched_slice後就會發生程序排程，可以說在cfs中不需要刻意補償被搶占的程序，所有的程序可以随意搶占，交疊搶占，嵌套搶占，cfs的原則使一切變得簡單，就是挑選vruntime最小的運作。

還是管不住自己的手，寫着寫着就拐到cfs排程器了，本來本文是要說系統的驅動方式呢，唉！以往的時鐘周期中斷機制中，時鐘是不了解目前系統的運作情況的，它隻是傻傻的周期性中斷cpu而已，核心的政策就是提供一個回調函數，該回調函數就是時鐘中斷處理函數，一切分離的那麼清晰，設計多麼好，但是它卻完全不符合我們的邏輯，設計上雖然有一些的模式，比如遵循高内聚低耦合，避免雙向通信等等，但是想想看我們的社會有這麼和諧嗎？我們不也活得很好嗎？有時候好的設計不在于多麼和諧，而是在于彼此之間能否互相适應，如果将核心和時鐘中斷規則想象成我們和社會的話，社會真的是不顧我們的需求而單獨運轉，而我們按社會的規則活着嗎？不，絕非這樣，我們和社會有一種互動，是以核心和時鐘中斷規則之間也需要一種互動，新時鐘架構的set_next_event就提供了這麼一種互動，核心可以設定下次中斷的時間了，既然這樣了，那麼核心就要盡情地和時鐘中斷規則互動，于是時鐘不再傻傻的按照周期中斷cpu了，而是聽從核心的建議，核心讓它什麼時候中斷它就什麼時候中斷，這一切由clock_event_device中的set_next_event提供機制接口，而 hrtimer最為其一個政策，它們的組合就形成了一種tickless的底層。

hrtimer的紅黑樹實作方式的巧妙展現在hrtimer入隊的時候，類似于cfs總是挑選vruntime最小的程序運作，hrtimer挑選離現在最近的設定下一個時鐘中斷時間點，在hrtimer運作完畢後或者新的hrtimer插入紅黑樹之後或者一個hrtimer從紅黑樹删除之後都可能引起最早hrtimer的改變，是以在上述三個地方都要權衡，用紅黑樹實作會非常高效。最為本文的結束，我總結一下兩種分時的方式，一種就是老式系統的固定時間片配置設定，優先級一旦确定，其時間片就确定了，這種方式在程序比較少的時候還可以，如果随着程序的增多，程序颠簸現象就會很嚴重，比如一個程序即使其優先級很高，被配置設定的時間片很大，當它活躍了一定時間後還是要等待很久，在這很久的時間内它不再活躍，給人的感覺就是程序一會很快一會很慢，注意好的排程算法隻能保證盡量的公平，但是沒有辦法縮短程序的不活躍時延；另外一種分時的方式就是動态時間片配置設定，在一個相對确定的時間段内按比例動态配置設定時間片，這樣會讓系統顯得更加的公平化，程序的不活躍時延有了最壞的保證，這就是公平，而第一種分時方式僅僅比早期的批處理任務時的一個程序運作完再讓另一個運作進步一點點，不再是讓其一次性運作完了，而是一次運作x毫秒，這難道叫排程嗎？在外部操作相同的前提下，即使是cfs，不管任何排程器，如果将一個程序的所有的運作時間都加在一起的話都是一個确定的值，是和排程器無關的，既然是為了使分時作的更好，那麼要點就不是如何讓一個程序怎麼樣高效，而是如何讓所有程序公平，使得整個機器看起來更像是多台機器，這就是多道程式設計的精髓，是以最重要的不在于排程算法，而是在于時間片的配置設定方式。

後記：作為後記，我想談一下cfs在設計上和hrtimer的相似點，這種相似展現在它們相對應前輩的優勢上，傳統的timer在cascading算法上引入了O(n)時間複雜度，而這種開銷是額外的，是timer的管理開銷，使用者如果發現自己的timer延時了，他們不會把醉過歸結到自己的timer本身，而是會說，看啊，那個該死的cascading算法浪費了那麼多時間，事實上可能不是這樣，然而使用者不會這麼想，hrtimer很自然的用到了紅黑樹，一切變得很平滑，沒有了O(n)的開銷，也就是說hrtimer的延時隻是timer本身的延時而消除了機制算法本身的延時；cfs也是一樣，說到排程算法，公平是個重要的名額，然後如果實作公平來的太貴的話，這種公平就是不值得的，其實任何排程算法都是為了公平，然而看看從前的O(n)排程器，為了優先級排程，僅在pick-next算法上就引入了O(n)的開銷，後來的O(1)算法雖然消除了pick-next的開銷，但它的意義僅在多處理器排程上，饑餓判斷，互動判斷，優先級調整等等還是帶來了很多額外的算法開銷，cfs自然地選則了紅黑樹，消除了機制算法的開銷，而hrtimer有着異曲同工之妙，這裡的要點就是，不要在機制上浪費太多，機制應該做到簡單高效，做到如果有延時，那麼99%的問題是政策問題，這才是成功的設計。機制上的開銷是額外的開銷，不應該讓使用者為之買單，機制很大意義上是帶有公益性質的，而不是收費的，想必大家都希望國家有好的福利保障體系和完善的純公益性質的機構吧，教育和醫療等機構收費太高是誰都不希望的。

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