調(diào)度？咋這熟悉，我們是不是常在哪里聽(tīng)到。沒(méi)錯(cuò)，是的，調(diào)度我們時(shí)常聽(tīng)過(guò)，比如交通管制調(diào)度啦等。這不，夏天這熱， 標(biāo)語(yǔ)貼的好：相應(yīng)國(guó)電電力調(diào)度，做文明市民,好別扭啊!不管了。你要是還是不懂，再啰嗦講個(gè)事，過(guò)年回家，和漂亮的GF回家，為了張普通的硬座票還要排老久對(duì)，甚至還可能被坑拿到黃牛票，這時(shí)你嘴里咧咧的啥：XX,啥火車(chē)站，做的啥春運(yùn)調(diào)度?。“?，這次你說(shuō)到點(diǎn)上了。
總結(jié)一下：調(diào)度就是通過(guò)調(diào)度程序的合理調(diào)度，實(shí)現(xiàn)系統(tǒng)資源的最大限度發(fā)揮作用。多進(jìn)程的并發(fā)正是這樣的效果。其實(shí)原理一點(diǎn)也不復(fù)雜，道理也一樣簡(jiǎn)單：只要又可以執(zhí)行的進(jìn)程，那么就總是會(huì)有進(jìn)程正在執(zhí)行。但簡(jiǎn)單的問(wèn)題也會(huì)復(fù)雜化，比如：我們買(mǎi)票為啥抱怨調(diào)度，歸根接地感謝當(dāng)年的人海戰(zhàn)術(shù)(多說(shuō)一句，其實(shí)現(xiàn)實(shí)的很多問(wèn)題，一個(gè)人海戰(zhàn)術(shù)解決所有，這戰(zhàn)術(shù)中國(guó)人用起來(lái)最得心應(yīng)手)。好么，一般系統(tǒng)中進(jìn)程的數(shù)目總會(huì)比處理器的個(gè)數(shù)多，所以競(jìng)爭(zhēng)在所難免，調(diào)度的問(wèn)題就集中在解決競(jìng)爭(zhēng)的問(wèn)題。
種類問(wèn)題不多說(shuō)：搶占和非搶占。linux提供了搶占式的多任務(wù)模式，下一階段誰(shuí)得到CPU的執(zhí)行時(shí)間由調(diào)度程序決定。這怎么決定，是不是請(qǐng)個(gè)客，喝個(gè)酒啥的。對(duì)不起，linux無(wú)情的說(shuō)，我是開(kāi)源的，對(duì)所有人公平，哥不吃這一套。我有自己的一套原則(策略，這個(gè)我們待會(huì)兒再講)。接著來(lái)術(shù)語(yǔ)，上面的過(guò)程叫做搶占，進(jìn)程得到CPU的執(zhí)行機(jī)會(huì)這段時(shí)間叫時(shí)間片，是由系統(tǒng)定義好的。后面我們會(huì)看到，linux調(diào)度程序采用動(dòng)態(tài)方法計(jì)算時(shí)間片。說(shuō)了搶占，再說(shuō)說(shuō)非搶占，就是說(shuō)沒(méi)人跟你搶，除非自己放棄，否則你自己運(yùn)行下去吧。進(jìn)程主動(dòng)放棄掛起自己的行為叫讓步。這種機(jī)制看似很和諧(不要被和諧哦)，但問(wèn)題挺多，比如系統(tǒng)不知道每個(gè)進(jìn)程執(zhí)行多長(zhǎng)時(shí)間。而且一旦一個(gè)懸掛進(jìn)程不愿意或者忘了做出讓步，那系統(tǒng)崩了咋辦，我的money，我的future，我的lover，從此一去不復(fù)返。
說(shuō)了那多，開(kāi)始正題。原則，一切都有原則，linux的原則。開(kāi)始原則以前，再來(lái)認(rèn)識(shí)一下我們前邊說(shuō)過(guò)的進(jìn)程，其實(shí)進(jìn)程遠(yuǎn)不如以前那樣簡(jiǎn)單。進(jìn)程也有種類的，至少分為IO型和CPU型。IO型指那種大部分時(shí)間用來(lái)提交I/O請(qǐng)求或是等待I/O請(qǐng)求的進(jìn)程。這樣的進(jìn)程挺討人厭的，他通常都是運(yùn)行一小小會(huì)兒，因?yàn)樗偸窃诘却嗟腎/O請(qǐng)求時(shí)最后總會(huì)阻塞。與之對(duì)應(yīng)的則是CPU型進(jìn)程。這樣的進(jìn)程把時(shí)間大多放在執(zhí)行代碼上，除非被搶占，他們就一直貪得無(wú)厭的運(yùn)行。因?yàn)樗鼈儧](méi)有太多的IO請(qǐng)求。由于它們不是IO驅(qū)動(dòng)類型，也就不存在用戶交互的問(wèn)題(IO驅(qū)動(dòng)不僅僅指磁盤(pán)，還指鍵盤(pán)鼠標(biāo)等)，所有從系統(tǒng)交互響應(yīng)速度而言，調(diào)度器不應(yīng)該經(jīng)常讓他們運(yùn)行。即降低它們的運(yùn)行頻率，而將它們的運(yùn)行時(shí)間拖長(zhǎng)一些。這里所說(shuō)的原則就是：調(diào)度策略要在進(jìn)程響應(yīng)迅速(相應(yīng)時(shí)間短)和進(jìn)程吞吐量高之間做出艱難的決定。這個(gè)原則有時(shí)不公平，很殘酷。殘酷的讓人不懂，不懂低優(yōu)先級(jí)的有時(shí)不能公平對(duì)待。由于交互式進(jìn)程屬于IO型進(jìn)程，所以linux為了保證交互式應(yīng)用，所以調(diào)度策略會(huì)向IO型進(jìn)行傾斜。
上面提到優(yōu)先級(jí)，調(diào)度算法中最基本的一類當(dāng)然就是基于優(yōu)先級(jí)的調(diào)度。挺簡(jiǎn)單：優(yōu)先級(jí)高的先運(yùn)行，相同優(yōu)先級(jí)的按輪轉(zhuǎn)式進(jìn)行調(diào)度。優(yōu)先級(jí)高的進(jìn)程使用的時(shí)間片也長(zhǎng)。調(diào)度程序總是選擇時(shí)間片未用盡且優(yōu)先級(jí)最高的進(jìn)程運(yùn)行。這句話就是說(shuō)用戶和系統(tǒng)可以通過(guò)設(shè)置進(jìn)程的優(yōu)先級(jí)來(lái)響應(yīng)系統(tǒng)的調(diào)度。基于此，linux設(shè)計(jì)上一套動(dòng)態(tài)優(yōu)先級(jí)的調(diào)度方法。一開(kāi)始，先為進(jìn)程設(shè)置一個(gè)基本的優(yōu)先級(jí)，然而它允許調(diào)度程序根據(jù)需要來(lái)加減優(yōu)先級(jí)。linux內(nèi)核提供了兩組獨(dú)立的優(yōu)先級(jí)范圍。第一種是nice值，范圍從-20到19，默認(rèn)為0.nice值越大優(yōu)先級(jí)越小。另外nice值也用來(lái)決定分配給進(jìn)程時(shí)間片的長(zhǎng)短。第二種范圍是實(shí)時(shí)優(yōu)先級(jí)。默認(rèn)范圍是從0到99.任何實(shí)時(shí)的優(yōu)先級(jí)都高于普通優(yōu)先級(jí)。這個(gè)我們后面再說(shuō)。
說(shuō)了那么多的時(shí)間片，說(shuō)起來(lái)不費(fèi)勁，做起來(lái)那不是一個(gè)麻煩可以說(shuō)清楚的。時(shí)間片就是一個(gè)數(shù)值，它表明進(jìn)程在被搶占前所能持續(xù)運(yùn)行的時(shí)間。默認(rèn)的時(shí)間片是20ms，很短。linux調(diào)度程序還能根據(jù)進(jìn)程的優(yōu)先級(jí)動(dòng)態(tài)調(diào)整分配給他的時(shí)間片。特別說(shuō)明的是，進(jìn)程不一定要一次用完所有分配給它的時(shí)間片。一旦進(jìn)程的時(shí)間片耗盡后，就認(rèn)為進(jìn)程到期了。沒(méi)有時(shí)間片的進(jìn)程不會(huì)再投入運(yùn)行。除非等到其他的進(jìn)程都耗盡了它們的時(shí)間片，這時(shí)，所有進(jìn)程的時(shí)間片就會(huì)被重新計(jì)算。
前邊講到了搶占的話題，當(dāng)一個(gè)進(jìn)程進(jìn)入TASK_RUNNING狀態(tài)時(shí)，內(nèi)核就會(huì)檢測(cè)它的優(yōu)先級(jí)是否高于當(dāng)前正在執(zhí)行的進(jìn)程。如果是，則調(diào)度程序會(huì)被喚醒，重新選擇新的進(jìn)程執(zhí)行(套用書(shū)上的話， 應(yīng)該是剛剛進(jìn)入可運(yùn)行狀態(tài)的這個(gè)進(jìn)程)。此外，當(dāng)一個(gè)進(jìn)程的時(shí)間片變?yōu)?時(shí)，它會(huì)被搶占，調(diào)度程序被喚醒以選擇一個(gè)新的進(jìn)程。(具體的例子大家可以看看參考書(shū)籍的p28頁(yè)3.1.5)
linux的調(diào)度程序定義于kernel/sched.c中，在2.6內(nèi)核中的調(diào)度程序和以前有了很大的差別，體現(xiàn)在下面：
1.充分實(shí)現(xiàn)O(1)調(diào)度.這個(gè)應(yīng)該懂得，可以懂的
2.在多核處理器的今天，linux也不落伍，全面實(shí)現(xiàn)SMP的擴(kuò)展性。每個(gè)處理器擁有自己的鎖和自己的可執(zhí)行隊(duì)列
3.強(qiáng)化SMP的親和力。這是有關(guān)多核CPU親和力的說(shuō)明，我目前正在研究這個(gè)，后面我會(huì)專門(mén)在一篇博文中詳細(xì)說(shuō)明。
4.加強(qiáng)交互能力。
5.保證公平。
6.雖然最常見(jiàn)的優(yōu)化情況是系統(tǒng)中只有1~2個(gè)可運(yùn)行進(jìn)程，但是優(yōu)化也完全有能力擴(kuò)展到具有多處理器且每個(gè)處理器上運(yùn)行多個(gè)進(jìn)程的系統(tǒng)中。
上面第二條可執(zhí)行隊(duì)列，它是調(diào)度程序中最基本的數(shù)據(jù)結(jié)構(gòu)，定義于kernel/sched.c中，由結(jié)構(gòu)runquene表示。它是給定處理器上的可執(zhí)行進(jìn)程的鏈表，每個(gè)處理器維護(hù)一個(gè)。每個(gè)可投入運(yùn)行得進(jìn)程都唯一的歸屬于一個(gè)可執(zhí)行隊(duì)列。此外，可執(zhí)行隊(duì)列中還包含每個(gè)處理器的調(diào)度信息。具體的結(jié)構(gòu)這里就不給了，自己要有看源代碼的能力哦。宏cpu_rq(processor)用于返回給定處理器可執(zhí)行隊(duì)列的指針，this_rq()用于來(lái)返回當(dāng)前處理器的可執(zhí)行隊(duì)列，task_rq(task)返回給定任務(wù)所在的隊(duì)列指針。
在其擁有者讀取或改寫(xiě)其隊(duì)列成員的時(shí)候，可執(zhí)行隊(duì)列包含的鎖用來(lái)防止隊(duì)列被其他代碼改動(dòng)，由于每個(gè)可執(zhí)行隊(duì)列唯一地對(duì)應(yīng)一個(gè)處理器，所以很少出現(xiàn)一個(gè)處理器需要鎖其他處理器的可執(zhí)行隊(duì)列的情況，但這種情況是事實(shí)存在的。最常見(jiàn)的情況是發(fā)生在一個(gè)特定的任務(wù)在運(yùn)行隊(duì)列上執(zhí)行時(shí)。此時(shí)需要用到task_rq_lock()和task_rq_unlock()函數(shù)，或者可以用this_rq_lock()來(lái)鎖住當(dāng)前的可執(zhí)行隊(duì)列，用rq_unlock(struct runqueue *rq)釋放給定隊(duì)列上的鎖。關(guān)于鎖的操作，我們?cè)俅物h過(guò)，為啥？一方面，這超出了本節(jié)的重點(diǎn)，二者我在linux驅(qū)動(dòng)理論帖中對(duì)加解鎖做了詳細(xì)說(shuō)明，三者，我后面可能還會(huì)詳細(xì)說(shuō)。所以，那句話真是太真理了：暫時(shí)的放下，是再次的拿起。
從運(yùn)行隊(duì)列的結(jié)構(gòu)中，我們發(fā)現(xiàn)了兩個(gè)有關(guān)優(yōu)先級(jí)的數(shù)組(定義在kernel/sched.c中，名字叫prio_array,具體自己去看吧)：活躍的和過(guò)去的。這兩個(gè)數(shù)組是實(shí)現(xiàn)O(1)級(jí)算法的數(shù)據(jù)結(jié)構(gòu)。優(yōu)先級(jí)數(shù)組使可運(yùn)行處理器的每一種優(yōu)先級(jí)都包含一個(gè)相應(yīng)的隊(duì)列，而這些隊(duì)列包含對(duì)應(yīng)優(yōu)先級(jí)上的可執(zhí)行進(jìn)程鏈表。結(jié)構(gòu)中的優(yōu)先級(jí)位圖主要是為了幫助提高查找當(dāng)前系統(tǒng)內(nèi)擁有最高優(yōu)先級(jí)的可執(zhí)行進(jìn)程的效率而設(shè)計(jì)的。關(guān)于結(jié)構(gòu)中的定義常量，MAX_PRIO定義了系統(tǒng)擁有的優(yōu)先級(jí)個(gè)數(shù)，默認(rèn)值是140，BITMAP_SIZE是優(yōu)先級(jí)位圖數(shù)組的大小，值是5，這個(gè)是可以計(jì)算出來(lái)的。比如：位圖數(shù)組的類型是unsigned long類型，長(zhǎng)是32位，假定每一位代表一個(gè)優(yōu)先級(jí)(4*32 = 128<140),就需要5個(gè)這樣的長(zhǎng)整型才能表示。所以，bitmap就正好含有5個(gè)數(shù)組項(xiàng)。
開(kāi)始時(shí)，位圖成員的所有位都被清0，當(dāng)某一優(yōu)先級(jí)的進(jìn)程開(kāi)始準(zhǔn)備執(zhí)行時(shí)，位圖中對(duì)應(yīng)的位就置1，這樣，查找系統(tǒng)中最高的優(yōu)先級(jí)就變成了查找位圖中被設(shè)置的第一位。鑒于優(yōu)先級(jí)個(gè)數(shù)的定值性，查找的時(shí)間就不受系統(tǒng)到底有多少可執(zhí)行進(jìn)程的影響，是個(gè)定值。關(guān)于對(duì)位圖的快速查找算法對(duì)應(yīng)的函數(shù)是sched_find_first_bit().
優(yōu)先級(jí)數(shù)組的list_head隊(duì)列是一個(gè)鏈表，這個(gè)鏈表包含了該處理器上相應(yīng)優(yōu)先級(jí)的全部可運(yùn)行線程。要找到下一個(gè)要運(yùn)行的任務(wù)，直接從該鏈表中選擇下一個(gè)元素。對(duì)于給定的優(yōu)先級(jí)，按輪轉(zhuǎn)方式調(diào)度任務(wù)。優(yōu)先級(jí)數(shù)組的計(jì)數(shù)器nr_active,它保存了該優(yōu)先級(jí)數(shù)組內(nèi)可執(zhí)行進(jìn)程的數(shù)目。
下一話題，我前邊反復(fù)提到時(shí)間片的話題，一旦所有進(jìn)程的時(shí)間片都用完會(huì)怎樣了，總不能系統(tǒng)宕掉吧，好在操作系統(tǒng)提供了一種顯式的方法來(lái)重新計(jì)算每個(gè)進(jìn)程的時(shí)間片。典型就是循環(huán)訪問(wèn)每個(gè)進(jìn)程。借用書(shū)上的一個(gè)例子：
for (系統(tǒng)中的每個(gè)任務(wù))｛
重新計(jì)算優(yōu)先級(jí)
重新計(jì)算時(shí)間片
｝
這種方法簡(jiǎn)單，但弊端很多：
1.可能耗費(fèi)相當(dāng)長(zhǎng)的時(shí)間。
2.為了保護(hù)任務(wù)隊(duì)列和每個(gè)進(jìn)程的描述符，必要要用到鎖的機(jī)制。這樣做很明顯會(huì)加劇對(duì)鎖的爭(zhēng)用，影響系統(tǒng)性能。
3.重算時(shí)間片的時(shí)機(jī)不確定。
4.實(shí)現(xiàn)顯得很粗糙。
現(xiàn)在采用的是新的調(diào)度方法，每個(gè)處理器擁有上面提到的兩個(gè)優(yōu)先級(jí)數(shù)組，活動(dòng)數(shù)組上的進(jìn)程都有時(shí)間片剩余，而過(guò)期數(shù)組中的進(jìn)程都耗盡了時(shí)間片，當(dāng)一個(gè)進(jìn)程的時(shí)間片耗盡時(shí)，它會(huì)移至過(guò)期數(shù)組，但在此之前，時(shí)間片已經(jīng)給它重新計(jì)算好了，重新計(jì)算時(shí)間片現(xiàn)在變的非常簡(jiǎn)單，只要在活動(dòng)和過(guò)期數(shù)組之間來(lái)回切換就可以了。又因?yàn)閿?shù)組是通過(guò)指針進(jìn)行訪問(wèn)的，所以交換它們用的時(shí)間就是交換指針需要的時(shí)間。這個(gè)動(dòng)作由schedule()完成：
struct prio_array *array = rq->active;
if(!array->nr_active){
rq->active = rq->expired;
rq->expired = array;
}
這種交換是O(1)級(jí)調(diào)度程序的核心。O(1)級(jí)調(diào)度程序根本不需要從頭到尾都忙著重新計(jì)算時(shí)間片，它只要完成一個(gè)兩個(gè)步驟就能實(shí)現(xiàn)數(shù)組的切換，這種實(shí)現(xiàn)完美地解決了前面列舉的所有弊端。linux的調(diào)度程序是在schedule()函數(shù)實(shí)現(xiàn)的。當(dāng)內(nèi)核代碼想要休眠時(shí)，會(huì)直接調(diào)用該函數(shù)，如果哪個(gè)進(jìn)程將被搶占，也會(huì)被喚起執(zhí)行。調(diào)度的第一步是判斷誰(shuí)是優(yōu)先級(jí)最高的進(jìn)程：
struct task_struct *prev, *next;
struct list_head *queue;
struct prio_array array;
int idx;
prev = current;
array = rq->active;
idx = sched_find_first_bit(array->bitmpa);
queue = array->queue + idx;
next = list_entry(queue->next, struct task_struct, run_list);
分析上面這段代碼，首先在活動(dòng)優(yōu)先級(jí)數(shù)組中找到第一個(gè)被設(shè)置的bit位，該位對(duì)應(yīng)著最高的可執(zhí)行進(jìn)程。然后，調(diào)度程序選擇這個(gè)級(jí)別鏈表里的頭一個(gè)進(jìn)程。這個(gè)進(jìn)程就是系統(tǒng)中優(yōu)先級(jí)最高的可執(zhí)行程序，也是馬上就會(huì)被調(diào)度執(zhí)行的進(jìn)程。上面中的prev和next不等，說(shuō)明被選中的進(jìn)程不是當(dāng)前進(jìn)程，這時(shí)就要調(diào)用context_switch來(lái)進(jìn)程切換。最后強(qiáng)調(diào)一點(diǎn)，不存在任何影響schedule()時(shí)間長(zhǎng)短的因素，因?yàn)榍斑呎f(shuō)過(guò)，所用的時(shí)間是恒定的。
前邊多次說(shuō)過(guò)：調(diào)度程序是利用優(yōu)先級(jí)和時(shí)間片來(lái)做出決定的。下邊看看實(shí)際代碼的實(shí)現(xiàn)方式。進(jìn)程結(jié)構(gòu)體告訴我們進(jìn)程擁有一個(gè)初始的優(yōu)先級(jí)，叫做nice值，最低是19，最高是20，結(jié)構(gòu)體的static_prio域就存放這個(gè)值，static就是說(shuō)這個(gè)一開(kāi)始就由用戶指定好了，不能改變。調(diào)度程序要用的動(dòng)態(tài)優(yōu)先級(jí)用prio域表示，兩者的關(guān)系在于通過(guò)一個(gè)關(guān)于靜態(tài)優(yōu)先級(jí)和進(jìn)程交互性的函數(shù)計(jì)算而來(lái)。啥叫進(jìn)程交互性？這是個(gè)新詞，第一次提到，這樣說(shuō)吧，我們前邊說(shuō)過(guò)I/O消耗性和CPU消耗性的進(jìn)程區(qū)別，進(jìn)程交互性就是指IO消耗性的，因?yàn)楹陀脩暨M(jìn)行交互就是電腦IO和用戶交互，像鼠標(biāo)鍵盤(pán)等。但我們?cè)趺创_定一個(gè)進(jìn)程的交互性的強(qiáng)弱呢？最明顯的標(biāo)準(zhǔn)莫過(guò)于通過(guò)計(jì)算進(jìn)程休眠的時(shí)間長(zhǎng)短來(lái)做預(yù)測(cè)了。大部分時(shí)間都在休眠的進(jìn)程當(dāng)然是IO消耗型的，如果一個(gè)進(jìn)程把所有的時(shí)間幾乎都放在了CPU執(zhí)行處理上，那..不說(shuō)了。在linux中，用值tast_struct中的sleep_avg域記錄了一個(gè)進(jìn)程用于休眠和用于執(zhí)行的時(shí)間，范圍為0~MAX_SLEEP_AVG,默認(rèn)值是10ms。當(dāng)一個(gè)進(jìn)程從休眠狀態(tài)恢復(fù)到執(zhí)行狀態(tài)時(shí)，sleep_avg會(huì)根據(jù)它休眠時(shí)間的長(zhǎng)短而增長(zhǎng)直到最大。相反，進(jìn)程沒(méi)運(yùn)行一個(gè)時(shí)鐘節(jié)拍，sleep_avg就做相應(yīng)的遞減，到0為止。這種方法不僅會(huì)獎(jiǎng)勵(lì)交互性強(qiáng)的進(jìn)程，還會(huì)懲罰處理器耗時(shí)量的進(jìn)程。再加之獎(jiǎng)勵(lì)和處罰都是建立在作為基數(shù)的nice值上，所有用戶仍然能夠通過(guò)改變nice指來(lái)調(diào)整程序的調(diào)度。effective_prio()函數(shù)可以返回一個(gè)進(jìn)程的動(dòng)態(tài)優(yōu)先數(shù)，該函數(shù)以nice值為基數(shù)，再加上我們上面提到的從-5到+5的進(jìn)程交互性型獎(jiǎng)勵(lì)處罰分。
一旦有了上面的動(dòng)態(tài)優(yōu)先級(jí)，再來(lái)重新計(jì)算時(shí)間片就方便多了。另外，當(dāng)一個(gè)進(jìn)程創(chuàng)建的時(shí)候，新建的子進(jìn)程和父進(jìn)程均分父進(jìn)程剩余的時(shí)間片。這樣的分配很平均并且防止用戶通過(guò)不斷的創(chuàng)建新進(jìn)程來(lái)不斷攫取時(shí)間片。task_timeslice()函數(shù)為給定任務(wù)返回一個(gè)新的時(shí)間片，時(shí)間片的計(jì)算只需要把優(yōu)先級(jí)按比例縮放，使其符合時(shí)間片的數(shù)值范圍要求就可以了。優(yōu)先級(jí)最高的進(jìn)程能獲得的最大時(shí)間片長(zhǎng)度(MAX_TIMESLICE)是200ms，最短時(shí)間片(MIN_TIMESLICE)是10ms。默認(rèn)優(yōu)先級(jí)(nice值為0，沒(méi)有交互性獎(jiǎng)罰分)的進(jìn)程得到的時(shí)間片長(zhǎng)度為100ms。上面我們也提到過(guò)，活動(dòng)數(shù)組內(nèi)的可執(zhí)行隊(duì)列上的進(jìn)程的時(shí)間片耗盡時(shí)，它就會(huì)移植到過(guò)期數(shù)組。但是，如果一個(gè)進(jìn)程的交互性很強(qiáng)，特別特別強(qiáng)，那么調(diào)度程序支持另外一種機(jī)制來(lái)支持這種交互進(jìn)程：當(dāng)時(shí)間片用完后，它會(huì)被再放置到活動(dòng)數(shù)組而不是過(guò)期數(shù)組中?；貞浺幌律厦鍻(1)調(diào)度器的實(shí)現(xiàn)機(jī)制：進(jìn)程用盡其時(shí)間片后，都會(huì)被移動(dòng)到過(guò)期數(shù)組，當(dāng)活動(dòng)數(shù)組中沒(méi)有剩余進(jìn)程的時(shí)候，這個(gè)時(shí)候兩個(gè)數(shù)組就會(huì)被交換。但是在發(fā)生這種交換以前，交互性很強(qiáng)的一個(gè)進(jìn)程有可能已經(jīng)處于過(guò)期數(shù)組中了，當(dāng)他需要交互的時(shí)候，這時(shí)可能數(shù)組交互還沒(méi)有發(fā)生，所以交互也就無(wú)法進(jìn)行，這時(shí)對(duì)于這種交互特別特別強(qiáng)的進(jìn)程重新插入到活動(dòng)數(shù)組就可以避免這種問(wèn)題。注意，雖然被放回到活動(dòng)數(shù)組，但不會(huì)立即就運(yùn)行，它還要和其他具有相同優(yōu)先級(jí)的進(jìn)程輪流運(yùn)行。該邏輯在scheduler_tick()中實(shí)現(xiàn)，該函數(shù)會(huì)被定時(shí)器中斷調(diào)用。看下面的實(shí)現(xiàn)代碼：
struct task_struct *task = current;
struct runqueue *rq = this_rq();
if(!—task->time_slice){
if(!TASK_INTERACTIVE(task) || (EXPIRED_STARVING(rq)))
enqueue_task(task, rq->expired);
else
enqueue_task(task, rq->active);
}
這段代碼先減少進(jìn)程時(shí)間片的值。宏TASK_INTERACTIVE主要是基于進(jìn)程的nice值來(lái)查看這個(gè)進(jìn)程是否是交互性很強(qiáng)的進(jìn)程。宏EXPIRED_STARVING負(fù)責(zé)檢查過(guò)期數(shù)組內(nèi)的進(jìn)程是否處于饑餓狀態(tài)，是否有相當(dāng)長(zhǎng)的時(shí)間沒(méi)有發(fā)生數(shù)組交換了。如果最近一直沒(méi)有發(fā)生切換，那么再把當(dāng)前的進(jìn)程放置到活動(dòng)數(shù)組會(huì)進(jìn)一步拖延切換--過(guò)期數(shù)組內(nèi)的進(jìn)程會(huì)來(lái)越來(lái)越餓.只要不發(fā)生這種情況，進(jìn)程就會(huì)被重新設(shè)置在活動(dòng)數(shù)組里，否則，進(jìn)程會(huì)被放入過(guò)期數(shù)組里。
有關(guān)休眠我就不用多講了。內(nèi)核對(duì)休眠的處理都相同：進(jìn)程把自己標(biāo)記成休眠狀態(tài)，然后將自己從可執(zhí)行隊(duì)列移出，放入等待隊(duì)列，然后調(diào)用schedule()選擇和執(zhí)行一個(gè)其他進(jìn)程，喚醒的過(guò)程剛好相反。要明白一點(diǎn)就是：即使休眠也有兩種進(jìn)程狀態(tài)，TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE.前者如果接收到一個(gè)信號(hào)會(huì)被提前喚醒并響應(yīng)該信號(hào)，后者會(huì)忽略信號(hào)。這兩種進(jìn)程位于同一等待隊(duì)列(wake_queue_head_t)上，等待某些事情，不能夠運(yùn)行。有關(guān)等待隊(duì)列的知識(shí)，跳過(guò)(我已經(jīng)在Linux驅(qū)動(dòng)開(kāi)發(fā)理論帖里講過(guò)，自己去看吧)現(xiàn)在，在內(nèi)核中進(jìn)行休眠的推薦操作相比較以前而言復(fù)雜了很多，但更安全：
1.調(diào)用DECLARE_WAITQUEUE() 創(chuàng)建一個(gè)等待隊(duì)列的項(xiàng)。
2.調(diào)用add_wait_queue()把自己加入到等帶對(duì)列中。
3.將進(jìn)程的狀態(tài)變更為T(mén)ASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE.
4.檢查條件是否為真，如果是的話，就沒(méi)必要休眠了。不為真，就調(diào)用schedule().
5.當(dāng)進(jìn)程被喚醒的時(shí)候，它會(huì)再次檢查條件是否為真。如果是，它就退出循環(huán)，如果不是，它再次調(diào)用schedule()并一直重復(fù)這步操作。
6.當(dāng)條件滿足后，進(jìn)程將自己設(shè)置為T(mén)ASK_RUNNING并調(diào)用remove_wait_queue把自己移出等待隊(duì)列。
如果在進(jìn)程開(kāi)始休眠之前條件就已經(jīng)達(dá)成了，那么循環(huán)會(huì)退出，進(jìn)程不會(huì)存在錯(cuò)誤的進(jìn)入休眠的傾向。有休眠就有喚醒，喚醒是通過(guò)wake_up()進(jìn)行。她喚醒指定的等待隊(duì)列上的所有進(jìn)程。它調(diào)用try_to_wake_up,該函數(shù)負(fù)責(zé)將進(jìn)程設(shè)置為T(mén)ASK_RUNNING狀態(tài)，調(diào)用active_task()將此進(jìn)程放入可執(zhí)行隊(duì)列，如果被喚醒進(jìn)程的優(yōu)先級(jí)比當(dāng)前正在執(zhí)行的進(jìn)程的優(yōu)先級(jí)高，還要設(shè)置need_resched標(biāo)志。編程的技巧，通常哪段代碼促使等待條件達(dá)成，它就要負(fù)責(zé)隨后調(diào)用wake_up函數(shù)。說(shuō)明：存在虛假的喚醒，有時(shí)候進(jìn)程被喚醒并不是因?yàn)樗却臈l件達(dá)成了，所以才需要用一個(gè)循環(huán)處理來(lái)保證它等待的條件真正到達(dá)。
開(kāi)始新的問(wèn)題，現(xiàn)在市場(chǎng)上，你說(shuō)單核CPU，你都沒(méi)臉見(jiàn)人，現(xiàn)在是啥時(shí)代，多核的時(shí)代，瞧，我這都酷睿i7了(四核)，我用的服務(wù)器實(shí)驗(yàn)平臺(tái)是8核心的。和我有啥關(guān)系，和我今天講的有啥關(guān)系。關(guān)系大了去了。前邊提到過(guò)，linux的調(diào)度程序?yàn)閷?duì)稱多處理器系統(tǒng)的每個(gè)處理器準(zhǔn)備了單獨(dú)的可執(zhí)行隊(duì)列和鎖，出于效率的考慮，整個(gè)調(diào)度系統(tǒng)從每個(gè)處理器來(lái)看都是獨(dú)立的。那么這樣的情況咋辦呢？一個(gè)處理器上有5個(gè)進(jìn)程，另外一個(gè)處理器的隊(duì)列上只有一個(gè)進(jìn)程，這時(shí)很明顯出現(xiàn)了系統(tǒng)負(fù)載不均衡的情況。這時(shí)咋辦呢？由負(fù)載均衡程序來(lái)解決(kernel/sched.c的load_balance來(lái)實(shí)現(xiàn))。它有兩種調(diào)用方法，在schedule執(zhí)行的時(shí)候，只要當(dāng)前的可執(zhí)行對(duì)列為空，它就會(huì)被調(diào)用。此外，它也會(huì)被定時(shí)器調(diào)用，系統(tǒng)空閑時(shí)每隔1ms調(diào)用一次或者在其他情況下每隔200ms調(diào)用一次。單系統(tǒng)中，它不會(huì)被調(diào)用，甚至不會(huì)被編譯進(jìn)內(nèi)核，因?yàn)槟抢镞呏挥幸粋€(gè)可執(zhí)行隊(duì)列，根本沒(méi)有平衡負(fù)載的必要。load_balances調(diào)用時(shí)需要鎖住當(dāng)前處理器的可執(zhí)行隊(duì)列并且屏蔽中斷，以避免可執(zhí)行隊(duì)列被并發(fā)的訪問(wèn)，所完成的操作步驟如下所示：
1.load_balance()調(diào)用find_busiest_queue(),找到最繁忙的可執(zhí)行隊(duì)列(進(jìn)程數(shù)目最多)并返回該隊(duì)列。如果沒(méi)有哪個(gè)可執(zhí)行隊(duì)列中進(jìn)程的數(shù)
目比當(dāng)前隊(duì)列中的數(shù)目多25%或25%以上。它就返回NULL,同時(shí)load_balance也返回。
2.load_balance從最繁忙的運(yùn)行隊(duì)列中選擇一個(gè)優(yōu)先級(jí)數(shù)組以便抽取進(jìn)程。最好是過(guò)期數(shù)組，如果過(guò)期數(shù)組為空，那就只能選活動(dòng)數(shù)組。
3.load_balance尋找到含有進(jìn)程并且優(yōu)先級(jí)最高的鏈表，因?yàn)榘褍?yōu)先級(jí)高的進(jìn)程分散開(kāi)來(lái)才是最重要的。
4.分析找到的所有這些優(yōu)先級(jí)相同的進(jìn)程，這樣一個(gè)不是正在執(zhí)行，也不會(huì)因?yàn)樘幚砥飨嚓P(guān)性而不可移動(dòng)，并且不在高速緩存中的進(jìn)程。如
果有，就調(diào)用pull_task將其從最繁忙的隊(duì)列中抽取到當(dāng)前隊(duì)列
5.只要可執(zhí)行隊(duì)列之間仍然不平衡，就重復(fù)上面兩個(gè)步驟，這最終會(huì)消除不平衡。然后解除對(duì)當(dāng)前運(yùn)行隊(duì)列進(jìn)行的鎖定，從load_balance返
回。
我們后面會(huì)提到的上下文切換，就是從一個(gè)可執(zhí)行進(jìn)程切換到另一個(gè)可執(zhí)行進(jìn)程，由定義在kernel/sched.c的context_switch函數(shù)負(fù)責(zé)處理。每當(dāng)一個(gè)新的進(jìn)程被選出來(lái)準(zhǔn)備投入運(yùn)行的時(shí)候，schedule就會(huì)調(diào)用該函數(shù)。它主要完成如下兩個(gè)工作：
1.調(diào)用定義在include/asm/mmu_context.h中的switch_mm().該函數(shù)負(fù)責(zé)把虛擬內(nèi)存從上一個(gè)進(jìn)程映射切換到新進(jìn)程中。
2.調(diào)用定義在include/asm/system.h的switch_to(),該函數(shù)負(fù)責(zé)從上一個(gè)進(jìn)程的處理器狀態(tài)切換到新進(jìn)程的處理器狀態(tài)，這包括保存，恢復(fù)
棧信息和寄存器信息。
內(nèi)核也必須知道什么時(shí)候調(diào)用schedule(),單靠用戶代碼顯示調(diào)用schedule(),他們可能就會(huì)永遠(yuǎn)地執(zhí)行下去，相反，內(nèi)核提供了一個(gè)need_resched標(biāo)志來(lái)表明是否需要重新執(zhí)行一次調(diào)度。當(dāng)某個(gè)進(jìn)程耗盡它的時(shí)間片時(shí)，scheduler_tick()就會(huì)設(shè)置這個(gè)標(biāo)志，當(dāng)一個(gè)優(yōu)先級(jí)高的進(jìn)程進(jìn)入可執(zhí)行狀態(tài)的時(shí)候，try_to_wake_up()也會(huì)設(shè)置這個(gè)標(biāo)志。下表給出了用于訪問(wèn)和操作need_resched的函數(shù)。
函數(shù)
說(shuō)明
set_tsk_need_resched(task) 設(shè)置指定進(jìn)程中的need_resched標(biāo)志
clear_tsk_need_resched(task) 清除指定進(jìn)程中的nedd_resched標(biāo)志
need_resched() 檢查need_resched標(biāo)志的值，如果被設(shè)置就返回真，否則返回假
再返回用戶空間以及從中斷返回的時(shí)候，內(nèi)核也會(huì)檢查need_resched標(biāo)志，如果已被設(shè)置，內(nèi)核會(huì)在繼續(xù)執(zhí)行之前調(diào)用該調(diào)度程序。最后，每個(gè)進(jìn)程都包含一個(gè)need_resched標(biāo)志，這是因?yàn)樵L問(wèn)進(jìn)程描述符內(nèi)的數(shù)值要比訪問(wèn)一個(gè)全局變量要快(因?yàn)閏urrent宏速度很快并且描述符通常都在高速緩存中)。在2.6內(nèi)核中，他被移到了thread_info結(jié)構(gòu)體里，這是和以前不同的。
搶占，還是搶占！我們總是逃不了搶占的話題。內(nèi)核放回到用戶空間的時(shí)候，如果need_resched標(biāo)志被設(shè)置，就會(huì)導(dǎo)致schedule()被調(diào)用。簡(jiǎn)兒言之，用戶搶占在以下情況下發(fā)生：從系統(tǒng)調(diào)用返回到用戶空間和從中斷處理程序返回用戶空間。
在linux2.6內(nèi)核中，內(nèi)核引入了搶占內(nèi)力。為了支持內(nèi)核搶占所做的第一個(gè)變動(dòng)就是為每個(gè)進(jìn)程的thread_info引入preempt_count計(jì)數(shù)器，該計(jì)數(shù)器初始為0，每當(dāng)使用鎖的時(shí)候，該值減1。當(dāng)為0的時(shí)候，內(nèi)核就可執(zhí)行搶占。從中斷返回內(nèi)核空間的時(shí)候，內(nèi)核會(huì)檢查need_resched和preempt_count的值，如果need_resched被設(shè)置，并且preempt_count為0的時(shí)候，這說(shuō)明有一個(gè)更重要的任務(wù)需要執(zhí)行并且安全地?fù)屨迹藭r(shí)，調(diào)度程序就會(huì)被調(diào)度。如果，preempt_count不為0，說(shuō)明當(dāng)前任務(wù)持有鎖，這時(shí)搶占是不安全的。這時(shí)，就會(huì)想通常那樣直接從中斷返回當(dāng)前執(zhí)行進(jìn)程。如果當(dāng)前進(jìn)程持有的鎖都被釋放了，那么preempt_count就會(huì)重新為0。此時(shí)，釋放鎖的代碼會(huì)檢查need_sheduled是否被設(shè)置，如果是的話，就會(huì)調(diào)用調(diào)度程序，有些內(nèi)核需要允許或禁止內(nèi)核搶占，這個(gè)后面具體問(wèn)題具體分析。如果內(nèi)核中的進(jìn)程阻塞了，或它顯示地調(diào)用了schedule(),內(nèi)核搶占也會(huì)顯示地發(fā)生，這種形式的內(nèi)核搶占從來(lái)都是支持的，因?yàn)楦緹o(wú)需額外的邏輯來(lái)保證內(nèi)核可以安全地被搶占，如果代碼顯示的調(diào)用了schedule(),那么它清楚自己是可以安全地被強(qiáng)化的。
我們前邊講的是普通的，非實(shí)時(shí)的調(diào)度策略(SCHED_OTHER),Linux也支持兩種實(shí)時(shí)調(diào)度策略(SCHED_FIFO和SCHED_RR).SCHED_FIFO從名字中我們也知道，就不說(shuō)了。它不使用時(shí)間片。該級(jí)的進(jìn)程會(huì)比任何SCHED_OTHER級(jí)的進(jìn)程都先得到調(diào)度。一旦一個(gè)SCHED_FIFO級(jí)進(jìn)程處理可執(zhí)行狀態(tài)，就會(huì)一直執(zhí)行，直到它自己被阻塞或是顯示地釋放處理器為止。由于不基于時(shí)間片，所以它會(huì)一直執(zhí)行下去。多個(gè)SCHED_FIFO級(jí)進(jìn)程存在時(shí)，他們會(huì)輪流執(zhí)行。而且只要有SCHED_FIFO級(jí)的進(jìn)程存在，普通級(jí)進(jìn)程級(jí)只能等待它結(jié)束后才有機(jī)會(huì)執(zhí)行。SCHED_RR是一種帶有時(shí)間片的SCHED_FIFO。以上兩種實(shí)時(shí)調(diào)度算法實(shí)現(xiàn)都是靜態(tài)優(yōu)先級(jí)的。內(nèi)核不為實(shí)時(shí)進(jìn)程計(jì)算動(dòng)態(tài)優(yōu)先級(jí)。這樣就能保證給定優(yōu)先級(jí)級(jí)別的實(shí)時(shí)進(jìn)程總能搶占優(yōu)先級(jí)比它低的進(jìn)程。
linux的實(shí)時(shí)調(diào)度算法分為軟實(shí)時(shí)和硬實(shí)時(shí)。軟實(shí)時(shí)的含義是，內(nèi)核調(diào)度進(jìn)程盡可能使進(jìn)程在它的限定時(shí)間到來(lái)前執(zhí)行，但內(nèi)核不會(huì)拍著胸脯說(shuō)：我一定能保證。對(duì)應(yīng)地，硬實(shí)時(shí)會(huì)這樣哥們義氣哦。linux下的實(shí)時(shí)調(diào)度不做任何保證，只保證只要實(shí)時(shí)進(jìn)程可執(zhí)行，就盡量去執(zhí)行它。現(xiàn)在開(kāi)來(lái)，效果還是不錯(cuò)的。
實(shí)時(shí)優(yōu)先級(jí)范圍從0~MAX_RT_PRIO-1.默認(rèn)情況下，MAX_RT_PRIO為100.SCHED_OTHER級(jí)進(jìn)程的nice值共享了這個(gè)取值空間。它的取值范圍是從MAX_RT_PRIO到MAX_RT_PRIO+40.也就是說(shuō)，nice值從-20到+19對(duì)應(yīng)的是從100到140的實(shí)時(shí)優(yōu)先級(jí)范圍。
最后，是一些關(guān)于和調(diào)度有關(guān)的系統(tǒng)調(diào)用，這個(gè)我就不說(shuō)了，感覺(jué)就是函數(shù)調(diào)用，說(shuō)了沒(méi)啥意思，自己看吧。反正就是一書(shū)在手，萬(wàn)事不愁啊..呵呵
