進(jìn)程調(diào)度

checl1987_EE

                                                                                                進(jìn)程調(diào)度程序可看作在可運(yùn)行態(tài)進(jìn)程之間分配有限的處理器時(shí)間資源的內(nèi)核子系統(tǒng)。在一組處于可運(yùn)行狀態(tài)的進(jìn)程中選擇一個(gè)來(lái)執(zhí)行，是調(diào)度程序所需要完成的基本工作。多任務(wù)系統(tǒng)可以劃分為兩類：非搶占式多任務(wù)和搶占式多任務(wù)模式。linux是搶占式多任務(wù)模式，在這個(gè)模式下，由調(diào)度程序來(lái)決定什么時(shí)候停止一個(gè)進(jìn)程的運(yùn)行以便其他進(jìn)程能夠得到執(zhí)行，這個(gè)強(qiáng)制掛起動(dòng)作就叫做搶占。[color="#FF0102"]進(jìn)程在被搶占之前能夠運(yùn)行的時(shí)間是被分配好的，而且有一個(gè)專門名字，叫進(jìn)程的時(shí)間片。[color="#000102"]4.1 策略[color="#000102"]非搶占式多任務(wù)模式下，除非進(jìn)程自己停止，否則會(huì)一直執(zhí)行。[color="#000102"]4.1.1 I/O消耗型和處理器消耗型的進(jìn)程[color="#000102"]進(jìn)程可以被分為I/O消耗型和處理器消耗型。前者是指進(jìn)程的大部分時(shí)間用來(lái)提交I/O請(qǐng)求或是等待I/O請(qǐng)求。這樣的進(jìn)程經(jīng)常處于可運(yùn)行狀態(tài)，通常都是運(yùn)行短短的一會(huì)。因?yàn)樗�在等待更多的I/O請(qǐng)求時(shí)候總會(huì)阻塞（這里指的是所有的I/O操作，像鍵盤活動(dòng)等都包括）。[color="#000102"]4.1.2 進(jìn)程優(yōu)先級(jí)[color="#000102"]優(yōu)先級(jí)高的進(jìn)程先運(yùn)行，優(yōu)先級(jí)低的進(jìn)程后運(yùn)行，優(yōu)先級(jí)高的進(jìn)程時(shí)間片較長(zhǎng)。[color="#000102"]linux采用動(dòng)態(tài)優(yōu)先級(jí)的調(diào)用方式，一開始先設(shè)置基本的優(yōu)先級(jí)，然后他允許調(diào)度程序根據(jù)需要來(lái)加減優(yōu)先級(jí)。如果一個(gè)進(jìn)程在I/O等待上耗費(fèi)的時(shí)間多于其運(yùn)行時(shí)間，那么該進(jìn)程明顯屬于I/O消耗型進(jìn)程。他會(huì)被動(dòng)態(tài)的提高，如果一個(gè)進(jìn)程的全部時(shí)間片一下就被耗盡，那么該進(jìn)程屬于處理器消耗型進(jìn)程，他的優(yōu)先級(jí)會(huì)被動(dòng)態(tài)的降低。[color="#000102"]linux內(nèi)核提供了兩種獨(dú)立的優(yōu)先級(jí)范圍。一種是nice值，范圍-20－－19，默認(rèn)值為0。nice值也用來(lái)決定分配給進(jìn)程的時(shí)間片的長(zhǎng)短。[color="#000102"]4.1.3 時(shí)間片[color="#000102"]調(diào)度策略必須規(guī)定一個(gè)默認(rèn)的時(shí)間片，這個(gè)時(shí)間片為20ms。[color="#000102"]進(jìn)程并不是一定非要一次就用完它所有的時(shí)間片。他可以分幾次運(yùn)行，這樣他可以保證它們盡可能長(zhǎng)時(shí)間的處于可運(yùn)行狀態(tài)。當(dāng)?shù)鹊狡渌�所有的進(jìn)程都耗盡了它們的時(shí)間片。在那個(gè)時(shí)候，所有進(jìn)程的時(shí)間片會(huì)被重新計(jì)算。[color="#000102"]4.1.4 進(jìn)程搶占[color="#000102"]linux系統(tǒng)是搶占式的，當(dāng)一個(gè)進(jìn)程進(jìn)入TASK_RUNNING狀態(tài)，[color="#FF0102"]內(nèi)核會(huì)檢查它的優(yōu)先級(jí)是否高于當(dāng)前正在執(zhí)行的進(jìn)程。如果這樣，調(diào)度程序會(huì)被喚醒，搶占當(dāng)前正在運(yùn)行的進(jìn)程并運(yùn)行新的進(jìn)程。當(dāng)一個(gè)進(jìn)程時(shí)間片為0時(shí)，它會(huì)被搶占，調(diào)度程序會(huì)被喚醒選擇一個(gè)新的進(jìn)程[color="#000102"]。[color="#000102"]4.2 linux調(diào)度算法[color="#000102"]linux的調(diào)度程序定義于kernel/sched.c中。[color="#000102"]4.2.1 可執(zhí)行隊(duì)列[color="#000102"]調(diào)度程序中最基本的數(shù)據(jù)結(jié)構(gòu)是運(yùn)行隊(duì)列（runqueue）。可執(zhí)行隊(duì)列定義于kernel/sched.c中，可執(zhí)行隊(duì)列是給定處理器上的可執(zhí)行進(jìn)程的鏈表。[color="#FF0102"]為什么是kernel/sched.c而不是kernel/sched.h，因?yàn)榘颜{(diào)度程序的代碼抽象出來(lái)而只給內(nèi)核的其余部分提供某些接口是一種理想的做法。把運(yùn)行隊(duì)列的代碼放在頭文件中會(huì)使調(diào)度程序以外的代碼也訪問(wèn)運(yùn)行隊(duì)列的代碼，這不是一種理想的做法。[color="#000102"]由于可執(zhí)行隊(duì)列是調(diào)度程序的核心數(shù)據(jù)結(jié)構(gòu)體，所以有一組宏定義用于獲取與給定處理器或進(jìn)程相關(guān)的可執(zhí)行隊(duì)列。cpu_rq(processor)宏用于返回給定處理器可執(zhí)行隊(duì)列的指針。this_rq()宏用來(lái)返回當(dāng)前處理器的可執(zhí)行隊(duì)列。宏task_rq(task)返回給定任務(wù)所在的隊(duì)列指針。[color="#000102"]在對(duì)可執(zhí)行隊(duì)列進(jìn)行操作以前，應(yīng)該先鎖住它，因?yàn)槊總�(gè)可執(zhí)行隊(duì)列唯一地對(duì)應(yīng)一個(gè)處理器，所以很少出現(xiàn)一個(gè)處理器需要鎖在其他處理器的可執(zhí)行隊(duì)列的情況。在其擁有者讀取或改寫隊(duì)列成員的時(shí)候，可執(zhí)行隊(duì)列包含的鎖用來(lái)防止隊(duì)列被其他代碼改動(dòng)，鎖住運(yùn)行隊(duì)列的最常見情況發(fā)生在你想鎖住的運(yùn)行隊(duì)列上恰巧有一個(gè)特定的任務(wù)在運(yùn)行。此時(shí)需要用到task_rq_lock()和task_rq_unlock()函數(shù)。[color="#000102"]this_rq_lock()來(lái)鎖住當(dāng)前的可執(zhí)行隊(duì)列，用rq_unlock(struct runqueue *rq)釋放給定隊(duì)列的鎖。[color="#FF0102"]為了避免死鎖，要鎖住多個(gè)運(yùn)行隊(duì)列的代碼必須總是按照同樣的順序獲取這些鎖[color="#000102"]。[color="#000102"]嵌套的鎖必須以相同的順序操作，自旋鎖用于防止多個(gè)任務(wù)同時(shí)對(duì)可執(zhí)行隊(duì)列進(jìn)行操作。[color="#000102"]例：最開始，一個(gè)任務(wù)來(lái)到門前，拿起鑰匙開了門，走進(jìn)去把門鎖上。如果這個(gè)時(shí)候第二個(gè)任務(wù)來(lái)了，沒有鑰匙，只能在門口等著，直到第一個(gè)任務(wù)走出來(lái)交出鑰匙，這個(gè)等待過(guò)程叫做[color="#FF0102"]自旋[color="#000102"]。因?yàn)閷?shí)際上任務(wù)是在不停地執(zhí)行一個(gè)循環(huán)操作來(lái)查詢鑰匙是否被交出來(lái)。[color="#000102"]如果一號(hào)任務(wù)先鎖住隊(duì)列甲，然后鎖隊(duì)列乙，而二號(hào)任務(wù)想先鎖住隊(duì)列乙，然后鎖住隊(duì)列甲，如果在一號(hào)任務(wù)鎖住隊(duì)列甲同時(shí)，二號(hào)任務(wù)鎖住了隊(duì)列乙，就是說(shuō)，鑰匙都被對(duì)方拿著，就形成了[color="#FF0102"]死鎖[color="#000102"]。如果兩個(gè)任務(wù)用相同的順序操作鎖，這種局面就不會(huì)產(chǎn)生。[color="#000102"]4.2.3 重新計(jì)算時(shí)間片[color="#000102"]linux為每個(gè)處理器維護(hù)兩個(gè)優(yōu)先級(jí)數(shù)組：活動(dòng)數(shù)組，過(guò)期數(shù)組�；顒�(dòng)數(shù)組內(nèi)的可執(zhí)行隊(duì)列上的進(jìn)程都還有時(shí)間片剩余；而過(guò)期數(shù)組內(nèi)的可執(zhí)行隊(duì)列上的進(jìn)程都耗盡了時(shí)間片。[color="#FF0102"]當(dāng)一個(gè)進(jìn)程的時(shí)間片耗盡時(shí)，它會(huì)被移至過(guò)期數(shù)組，但在此之前，時(shí)間片已經(jīng)給它重新計(jì)算好了[color="#000102"]。[color="#000102"]4.2.4 schedule()[color="#000102"]選定下一個(gè)進(jìn)程并切換到它去執(zhí)行是通過(guò)schedule()函數(shù)實(shí)現(xiàn)的。當(dāng)內(nèi)核代碼想要休眠時(shí)，會(huì)直接調(diào)用該函數(shù)，如果哪個(gè)進(jìn)程被搶占，那么該函數(shù)也會(huì)被喚起執(zhí)行。schedule()函數(shù)獨(dú)立于每個(gè)處理器運(yùn)行。因此，每個(gè)CPU都要對(duì)下一次該運(yùn)行哪個(gè)進(jìn)程做出自己的判斷。[color="#000102"]4.2.5 計(jì)算優(yōu)先級(jí)和時(shí)間片[color="#000102"]如果一個(gè)進(jìn)程的大部分時(shí)間都在休眠，那么它就是I/O消耗型的，如果一個(gè)進(jìn)程執(zhí)行的時(shí)間比休眠的時(shí)間長(zhǎng)，那它就是處理器消耗型的。當(dāng)一個(gè)任務(wù)的時(shí)間片用完之后，就要根據(jù)任務(wù)的靜態(tài)優(yōu)先級(jí)重新計(jì)算時(shí)間片。task_timeslice()函數(shù)為給定任務(wù)返回一個(gè)新的時(shí)間片。時(shí)間片的計(jì)算只需要把優(yōu)先級(jí)按比例縮放。[color="#000102"]4.2.6 睡眠和喚醒[color="#000102"]休眠（被阻塞）的進(jìn)程處于一個(gè)特殊的不可執(zhí)行狀態(tài)。進(jìn)程把自己標(biāo)記成休眠狀態(tài)，把自己從可執(zhí)行隊(duì)列移出，放入等待隊(duì)列，然后調(diào)用schedule()選擇和執(zhí)行一個(gè)其他進(jìn)程。喚醒的過(guò)程剛好相反：進(jìn)程被設(shè)置為可執(zhí)行狀態(tài)，然后再?gòu)牡却��?duì)列中移到可執(zhí)行隊(duì)列。[color="#000102"]4.2.7 負(fù)載平衡程序[color="#000102"]如果可執(zhí)行隊(duì)列間出現(xiàn)負(fù)載不均衡的情況時(shí)，比如一個(gè)處理器的隊(duì)列上有五個(gè)進(jìn)程，而另外一個(gè)處理器上只有一個(gè)進(jìn)程，該怎么處理呢？負(fù)載平衡程序會(huì)拿當(dāng)前處理器的可執(zhí)行隊(duì)列和系統(tǒng)中的其他可執(zhí)行隊(duì)列做比較，如果它發(fā)現(xiàn)了不均衡就會(huì)把相對(duì)繁忙的隊(duì)列中的進(jìn)程抽到當(dāng)前的可執(zhí)行隊(duì)列中來(lái)。負(fù)載平衡由kernel/sched.c中的函數(shù)load_balance()來(lái)實(shí)現(xiàn)。[color="#000102"]4.3 搶占和上下文切換[color="#000102"]從一個(gè)可執(zhí)行的進(jìn)程切換到另一個(gè)可執(zhí)行的進(jìn)程，由定義在kernel/sched.c中的context_switch()函數(shù)負(fù)責(zé)處理。[color="#000102"]
[color="#000102"]

               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               

本文來(lái)自ChinaUnix博客，如果查看原文請(qǐng)點(diǎn)：http://blog.chinaunix.net/u3/103763/showart_2164335.html