引子：哪些是該負(fù)責(zé)的，哪些是不該負(fù)責(zé)的

哪些是該負(fù)責(zé)的，哪些是不該負(fù)責(zé)的，這是一個(gè)問(wèn)題，hrtimer就能保證所有的timer都可以不延時(shí)的被執(zhí)行嗎？不能，很簡(jiǎn)單，如果你排入10000個(gè)timer，每一個(gè)哪怕執(zhí)行1毫秒...這個(gè)問(wèn)題就是用戶的使用策略問(wèn)題了，不是hrtimer機(jī)制要負(fù)責(zé)的，而hrtimer要負(fù)責(zé)的是它的算法本身不能引入延遲，這也是它能保證的最后壁壘了，就好像再結(jié)實(shí)的汽車(chē)你非要開(kāi)著它開(kāi)下懸崖，死了之后變成鬼找到車(chē)的設(shè)計(jì)者抱怨沒(méi)能保護(hù)他的安全，這合理嗎？hrtimer用了紅黑樹(shù)數(shù)據(jù)結(jié)構(gòu)，很高效的實(shí)現(xiàn)了timer到期后的處理，并沒(méi)有引入什么延遲，僅僅就是一個(gè)線性出隊(duì)的時(shí)間復(fù)雜度罷了，而傳統(tǒng)的timer在執(zhí)行的時(shí)候用了cascading算法，該算法的初衷是為了不想每次都輪詢所有的timer以檢測(cè)到期與否，但是該算法雖然減少了輪詢的時(shí)間延遲，但是算法本身的O(n)時(shí)間復(fù)雜度也是很可觀的，究其原因就在于它是基于jiffies的，而jiffies是一個(gè)基于tick的絕對(duì)單調(diào)遞增的值，除此之外別無(wú)任何策略可言，因此萬(wàn)惡的tick機(jī)制才是罪魁禍?zhǔn)?#xff0c;htimer的回調(diào)函數(shù)采用了兩種觸發(fā)方式，這樣就可以讓用戶根據(jù)需求設(shè)置更多的策略，這是一個(gè)額外的優(yōu)勢(shì)，于是就有了tickless。

開(kāi)始：

在2.6的早期的內(nèi)核以及更早的2.4內(nèi)核中，時(shí)鐘周期性中斷是一個(gè)很重要的概念，因?yàn)樗?qū)動(dòng)了系統(tǒng)向前運(yùn)行，一切的統(tǒng)計(jì)幾乎都是在時(shí)鐘中斷中進(jìn)行的，內(nèi)核中有一個(gè)jiffies全局變量，很多的機(jī)制依賴這個(gè)變量，因此如果時(shí)鐘的周期中斷停止，那么整個(gè)系統(tǒng)也將停止，時(shí)鐘周期中斷的意義和心跳的意義類(lèi)似，是一切的基礎(chǔ)，這里面最重要的就是時(shí)鐘只管周期性的中斷系統(tǒng)而不管其余的機(jī)制如何去使用這個(gè)中斷處理，模塊分離的很不錯(cuò)。但是有個(gè)問(wèn)題就是時(shí)鐘中斷的周期也就成了度量時(shí)間的最基本最小的單位，這個(gè)周期就是一個(gè)tick的時(shí)間，按照配置和cpu頻率是不等的，這樣的話不管是用戶級(jí)別還是內(nèi)核級(jí)別的睡眠或超時(shí)喚醒間隔就嚴(yán)重受制于一個(gè)tick的時(shí)間間隔，如果一個(gè)tick是10ms，那么10ms以下的睡眠就提供不了了，因?yàn)橐郧暗膖imer是在時(shí)鐘中斷后的軟中斷上下文進(jìn)行的，怎樣樣才能將定時(shí)機(jī)制和時(shí)鐘周期心跳機(jī)制分離呢？首先我們看看分離的必要性，時(shí)鐘周期中斷是為了推動(dòng)系統(tǒng)前進(jìn)的，進(jìn)程調(diào)度等重要操作都在時(shí)鐘中斷中被驅(qū)動(dòng)，而定時(shí)機(jī)制是進(jìn)程或者驅(qū)動(dòng)使用的一個(gè)必不可少的機(jī)制，它們二者不是太有必要綁定在一起的，因此有必要分離，并且定時(shí)機(jī)制和時(shí)鐘周期中斷分離以后必須可以提供更高的精度讓進(jìn)程或者驅(qū)動(dòng)使用而不是讓它們死死依賴住那個(gè)可靠但不精確的jiffies變量，于是hrtimer呼之欲出。hrtimer的出現(xiàn)可以說(shuō)是打開(kāi)了一個(gè)缺口，在哪里打開(kāi)一個(gè)缺口呢？是在驅(qū)動(dòng)系統(tǒng)的方式上打開(kāi)一個(gè)缺口，當(dāng)clocksource和clock_event_device出現(xiàn)以后，這個(gè)缺口越來(lái)越大，最終的結(jié)果就是完全的tickless，不再需要周期的定時(shí)中斷了，這種新的驅(qū)動(dòng)系統(tǒng)的方式就是任務(wù)驅(qū)動(dòng)的，每個(gè)任務(wù)綁定一個(gè)hrtimer，然后將此hrtimer入隊(duì)后和所有的hrtimer比較，找出最小的，將其超時(shí)時(shí)間設(shè)置為下一次的時(shí)鐘中斷時(shí)間，這樣時(shí)鐘就不會(huì)頻繁的打斷正在運(yùn)行的任務(wù)了，特別是在cfs調(diào)度器成為主調(diào)度器之后，這種想法更加顯得合乎情理，因?yàn)閏fs做到了一個(gè)調(diào)度周期內(nèi)的公平調(diào)度，沒(méi)有驅(qū)動(dòng)任務(wù)并且沒(méi)有搶占的理想情況下在一個(gè)調(diào)度周期內(nèi)，tickless的系統(tǒng)只需要和任務(wù)數(shù)量相等數(shù)量的時(shí)鐘中斷就可以了，固定時(shí)間內(nèi)，時(shí)鐘中斷的數(shù)量和任務(wù)的數(shù)量成正比，這正是符合邏輯的，如果是原來(lái)的O(1)調(diào)度器，那么時(shí)間片的分配是固定的，只要優(yōu)先級(jí)確定，同一HZ值情況下分配的時(shí)間片是一定的，因此同一時(shí)間段內(nèi)時(shí)鐘中斷的數(shù)量和任務(wù)的數(shù)量沒(méi)有什么關(guān)系，即使同樣都是一個(gè)進(jìn)程，其優(yōu)先級(jí)不同，同一時(shí)間段內(nèi)發(fā)生的時(shí)鐘中斷也是不同的，這是不符合邏輯的，時(shí)鐘中斷的數(shù)量應(yīng)該不能和進(jìn)程優(yōu)先級(jí)相關(guān)，因?yàn)檫M(jìn)程分時(shí)調(diào)度(非搶占)是在時(shí)鐘中斷內(nèi)發(fā)生的，因此為了公平，中斷的數(shù)量只能和進(jìn)程的數(shù)量相關(guān)，至于優(yōu)先級(jí)的體現(xiàn)不能在中斷的數(shù)量上而應(yīng)該在中斷的間隔上，因此cfs使tickless更加合理化，畢竟系統(tǒng)運(yùn)行中進(jìn)程調(diào)度是最重要的模塊之一。

目前的內(nèi)核對(duì)tickless的實(shí)現(xiàn)上還是僅在cpu進(jìn)入idle的時(shí)候才tickless，而正常情況下還是按照HZ進(jìn)行周期的時(shí)鐘中斷，其實(shí)完全可以全局禁用周期中斷而全局改用tickless，但是需要做的就是將所有以來(lái)jiffies的機(jī)制全部用hrtimer實(shí)現(xiàn)，這可是一個(gè)不小的工程，另外周期中斷的另一個(gè)作用就是進(jìn)行記帳，用于統(tǒng)計(jì)和評(píng)估，如果完全tickless的話，像那些以前基于傳統(tǒng)tick的timer就要同樣轉(zhuǎn)移到 hrtimer，理論上這也是很簡(jiǎn)單的，但是實(shí)踐上可能不太適合linux的開(kāi)發(fā)方式，為何說(shuō)理論上簡(jiǎn)單呢？將傳統(tǒng)的timer改變成每隔一個(gè)tick觸發(fā)一次的hrtimer就可以了，tick還是根據(jù)HZ計(jì)算出來(lái)，這樣我們完全可以把傳統(tǒng)的周期中斷的timer_interrupt中的各個(gè)不同的功能分離成不同的hrtimer，比如為每10ms統(tǒng)計(jì)記帳信息的代碼提供一個(gè)hrtime，里面就做這一件事并且它每10ms觸發(fā)一次然后再次加入 hrtimer對(duì)列，同樣負(fù)責(zé)進(jìn)程調(diào)度的代碼也提供一個(gè)hrtimer，實(shí)際上內(nèi)核早就這么做了，該hrtimer就是hrtick_timer，它負(fù)責(zé)進(jìn)程調(diào)度，如此一來(lái)進(jìn)程的運(yùn)行就不必再受到無(wú)休止的時(shí)鐘中斷打擾了，在cfs中，一個(gè)進(jìn)程可以一次性運(yùn)行完承諾給它的 sched_slice(cfs_rq, se)時(shí)間，在一個(gè)進(jìn)程開(kāi)始運(yùn)行的時(shí)候，將hrtick_timer設(shè)置為到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對(duì)列

}

}

以上函數(shù)在pick_next_task最后調(diào)用，其實(shí)就是在一個(gè)進(jìn)程剛開(kāi)始運(yùn)行的時(shí)候調(diào)用，代碼十分容易理解。上面代碼中設(shè)置的hrtick_timer到期了以后將會(huì)調(diào)用它的回調(diào)函數(shù)，即htick，后者會(huì)用queued為1進(jìn)一步調(diào)用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并且設(shè)置CONFIG_SCHED_HRTICK也就是是hrtimer的情況下，直接調(diào)度，因?yàn)樵谶M(jìn)程開(kāi)始運(yùn)行的時(shí)候就設(shè)置該hrtimer到這個(gè)時(shí)間點(diǎn)到期，因此無(wú)條件調(diào)度

resched_task(rq_of(cfs_rq)->curr);

return;

}

if (!sched_feat(DOUBLE_TICK) && //系統(tǒng)難免還保留著原來(lái)的周期中斷驅(qū)動(dòng)的進(jìn)程調(diào)度，但是同時(shí)也設(shè)置了進(jìn)程調(diào)度的hrtimer，如此一來(lái)傳統(tǒng)的周期中斷就不能打擾hrtimer的行為

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

return;

#endif

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

check_preempt_tick(cfs_rq, curr);

}

現(xiàn)在稍微考慮一下?lián)屨?#xff0c;如果一個(gè)進(jìn)程還沒(méi)有運(yùn)行完調(diào)度器承諾給它的時(shí)間就被搶占了，那怎么辦，一切會(huì)亂掉嗎？不，在cfs上絲毫不會(huì)亂掉，另外的一個(gè)原因就是每個(gè)運(yùn)行隊(duì)列只有一個(gè)hrtick_timer，如果當(dāng)前進(jìn)程被搶占了，那么可想而知它還沒(méi)有運(yùn)行完它的sched_slice，剩下的時(shí)間怎么辦，怎么補(bǔ)償給它？答案就是不再顯式補(bǔ)償給它，而是隱式補(bǔ)償，靠的就是cfs的機(jī)制原理，被搶占的進(jìn)程的vruntime不再向前推進(jìn)，而cfs總是挑選 vruntime最小的進(jìn)程運(yùn)行，因此被搶占的進(jìn)程在搶占它的進(jìn)程運(yùn)行完后會(huì)接著運(yùn)行的幾率是有的，即使不接著運(yùn)行它也總是會(huì)運(yùn)行，而且在被搶占的這段時(shí)間內(nèi)它的vruntime沒(méi)有推進(jìn)，積攢的差值恰恰成了它的優(yōu)勢(shì)。接著說(shuō)搶占，由于每個(gè)運(yùn)行隊(duì)列只有一個(gè)hrtick_timer，在新進(jìn)程開(kāi)始運(yùn)行的時(shí)候會(huì)重新hrtick_start，結(jié)果就是停掉了原來(lái)的hrtick_timer，當(dāng)搶占進(jìn)程運(yùn)行完它的sched_slice后就會(huì)發(fā)生進(jìn)程調(diào)度，可以說(shuō)在cfs中不需要刻意補(bǔ)償被搶占的進(jìn)程，所有的進(jìn)程可以隨意搶占，交疊搶占，嵌套搶占，cfs的原則使一切變得簡(jiǎn)單，就是挑選vruntime最小的運(yùn)行。

還是管不住自己的手，寫(xiě)著寫(xiě)著就拐到cfs調(diào)度器了，本來(lái)本文是要說(shuō)系統(tǒng)的驅(qū)動(dòng)方式呢，唉！以往的時(shí)鐘周期中斷機(jī)制中，時(shí)鐘是不了解當(dāng)前系統(tǒng)的運(yùn)行情況的，它只是傻傻的周期性中斷cpu而已，內(nèi)核的策略就是提供一個(gè)回調(diào)函數(shù)，該回調(diào)函數(shù)就是時(shí)鐘中斷處理函數(shù)，一切分離的那么清晰，設(shè)計(jì)多么好，但是它卻完全不符合我們的邏輯，設(shè)計(jì)上雖然有一些的模式，比如遵循高內(nèi)聚低耦合，避免雙向通信等等，但是想想看我們的社會(huì)有這么和諧嗎？我們不也活得很好嗎？有時(shí)候好的設(shè)計(jì)不在于多么和諧，而是在于彼此之間能否相互適應(yīng)，如果將內(nèi)核和時(shí)鐘中斷規(guī)則想象成我們和社會(huì)的話，社會(huì)真的是不顧我們的需求而單獨(dú)運(yùn)轉(zhuǎn)，而我們按社會(huì)的規(guī)則活著嗎？不，絕非這樣，我們和社會(huì)有一種互動(dòng)，因此內(nèi)核和時(shí)鐘中斷規(guī)則之間也需要一種互動(dòng)，新時(shí)鐘架構(gòu)的set_next_event就提供了這么一種互動(dòng)，內(nèi)核可以設(shè)置下次中斷的時(shí)間了，既然這樣了，那么內(nèi)核就要盡情地和時(shí)鐘中斷規(guī)則互動(dòng)，于是時(shí)鐘不再傻傻的按照周期中斷cpu了，而是聽(tīng)從內(nèi)核的建議，內(nèi)核讓它什么時(shí)候中斷它就什么時(shí)候中斷，這一切由clock_event_device中的set_next_event提供機(jī)制接口，而 hrtimer最為其一個(gè)策略，它們的組合就形成了一種tickless的底層。

hrtimer的紅黑樹(shù)實(shí)現(xiàn)方式的巧妙體現(xiàn)在hrtimer入隊(duì)的時(shí)候，類(lèi)似于cfs總是挑選vruntime最小的進(jìn)程運(yùn)行，hrtimer挑選離現(xiàn)在最近的設(shè)置下一個(gè)時(shí)鐘中斷時(shí)間點(diǎn)，在hrtimer運(yùn)行完畢后或者新的hrtimer插入紅黑樹(shù)之后或者一個(gè)hrtimer從紅黑樹(shù)刪除之后都可能引起最早hrtimer的改變，因此在上述三個(gè)地方都要權(quán)衡，用紅黑樹(shù)實(shí)現(xiàn)會(huì)非常高效。最為本文的結(jié)束，我總結(jié)一下兩種分時(shí)的方式，一種就是老式系統(tǒng)的固定時(shí)間片分配，優(yōu)先級(jí)一旦確定，其時(shí)間片就確定了，這種方式在進(jìn)程比較少的時(shí)候還可以，如果隨著進(jìn)程的增多，進(jìn)程顛簸現(xiàn)象就會(huì)很?chē)?yán)重，比如一個(gè)進(jìn)程即使其優(yōu)先級(jí)很高，被分配的時(shí)間片很大，當(dāng)它活躍了一定時(shí)間后還是要等待很久，在這很久的時(shí)間內(nèi)它不再活躍，給人的感覺(jué)就是進(jìn)程一會(huì)很快一會(huì)很慢，注意好的調(diào)度算法只能保證盡量的公平，但是沒(méi)有辦法縮短進(jìn)程的不活躍時(shí)延；另外一種分時(shí)的方式就是動(dòng)態(tài)時(shí)間片分配，在一個(gè)相對(duì)確定的時(shí)間段內(nèi)按比例動(dòng)態(tài)分配時(shí)間片，這樣會(huì)讓系統(tǒng)顯得更加的公平化，進(jìn)程的不活躍時(shí)延有了最壞的保證，這就是公平，而第一種分時(shí)方式僅僅比早期的批處理任務(wù)時(shí)的一個(gè)進(jìn)程運(yùn)行完再讓另一個(gè)運(yùn)行進(jìn)步一點(diǎn)點(diǎn)，不再是讓其一次性運(yùn)行完了，而是一次運(yùn)行x毫秒，這難道叫調(diào)度嗎？在外部操作相同的前提下，即使是cfs，不管任何調(diào)度器，如果將一個(gè)進(jìn)程的所有的運(yùn)行時(shí)間都加在一起的話都是一個(gè)確定的值，是和調(diào)度器無(wú)關(guān)的，既然是為了使分時(shí)作的更好，那么要點(diǎn)就不是如何讓一個(gè)進(jìn)程怎么樣高效，而是如何讓所有進(jìn)程公平，使得整個(gè)機(jī)器看起來(lái)更像是多臺(tái)機(jī)器，這就是多道程序設(shè)計(jì)的精髓，因此最重要的不在于調(diào)度算法，而是在于時(shí)間片的分配方式。

后記：作為后記，我想談一下cfs在設(shè)計(jì)上和hrtimer的相似點(diǎn)，這種相似體現(xiàn)在它們相對(duì)應(yīng)前輩的優(yōu)勢(shì)上，傳統(tǒng)的timer在cascading算法上引入了O(n)時(shí)間復(fù)雜度，而這種開(kāi)銷(xiāo)是額外的，是timer的管理開(kāi)銷(xiāo)，用戶如果發(fā)現(xiàn)自己的timer延時(shí)了，他們不會(huì)把醉過(guò)歸結(jié)到自己的timer本身，而是會(huì)說(shuō)，看啊，那個(gè)該死的cascading算法浪費(fèi)了那么多時(shí)間，事實(shí)上可能不是這樣，然而用戶不會(huì)這么想，hrtimer很自然的用到了紅黑樹(shù)，一切變得很平滑，沒(méi)有了O(n)的開(kāi)銷(xiāo)，也就是說(shuō)hrtimer的延時(shí)只是timer本身的延時(shí)而消除了機(jī)制算法本身的延時(shí)；cfs也是一樣，說(shuō)到調(diào)度算法，公平是個(gè)重要的指標(biāo)，然后如果實(shí)現(xiàn)公平來(lái)的太貴的話，這種公平就是不值得的，其實(shí)任何調(diào)度算法都是為了公平，然而看看從前的O(n)調(diào)度器，為了優(yōu)先級(jí)調(diào)度，僅在pick-next算法上就引入了O(n)的開(kāi)銷(xiāo)，后來(lái)的O(1)算法雖然消除了pick-next的開(kāi)銷(xiāo)，但它的意義僅在多處理器調(diào)度上，饑餓判斷，交互判斷，優(yōu)先級(jí)調(diào)整等等還是帶來(lái)了很多額外的算法開(kāi)銷(xiāo)，cfs自然地選則了紅黑樹(shù)，消除了機(jī)制算法的開(kāi)銷(xiāo)，而hrtimer有著異曲同工之妙，這里的要點(diǎn)就是，不要在機(jī)制上浪費(fèi)太多，機(jī)制應(yīng)該做到簡(jiǎn)單高效，做到如果有延時(shí)，那么99%的問(wèn)題是策略問(wèn)題，這才是成功的設(shè)計(jì)。機(jī)制上的開(kāi)銷(xiāo)是額外的開(kāi)銷(xiāo)，不應(yīng)該讓用戶為之買(mǎi)單，機(jī)制很大意義上是帶有公益性質(zhì)的，而不是收費(fèi)的，想必大家都希望國(guó)家有好的福利保障體系和完善的純公益性質(zhì)的機(jī)構(gòu)吧，教育和醫(yī)療等機(jī)構(gòu)收費(fèi)太高是誰(shuí)都不希望的。

?本文轉(zhuǎn)自 dog250 51CTO博客，原文鏈接:http://blog.51cto.com/dog250/1274128

總結(jié)

以上是生活随笔為你收集整理的两种驱动系统运行的方式--分时的方式的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。