uClinux進(jìn)程調(diào)度器的實現(xiàn)分析

0 引言

uClinux是針對控制領(lǐng)域的嵌入式Linux操作系統(tǒng)，它從Linux 2.0/2.4內(nèi)核派生而來，沿襲了Linux的絕大部分特性，適合不具備內(nèi)存管理單元(MMU)的微處理器或微控制器，現(xiàn)已經(jīng)廣泛應(yīng)用于各種不同的微處理器平臺上。因此，對uClinux操作系統(tǒng)核心模塊的設(shè)計進(jìn)行分析對于應(yīng)用系統(tǒng)設(shè)計具有重要的現(xiàn)實意義。uClinux作為支持多任務(wù)的操作系統(tǒng)，進(jìn)程調(diào)度是其重要的組成部分，本文就uClinux進(jìn)程調(diào)度器的設(shè)計實現(xiàn)進(jìn)行分析。重點討論了uClinux的進(jìn)程調(diào)度機(jī)制，主要包括調(diào)度方式、調(diào)度策略、調(diào)度時機(jī)、調(diào)度算法這四個方面。

1 uClinux進(jìn)程的調(diào)度方式[1]

uClinux中每個進(jìn)程的task_struct結(jié)構(gòu)中有四項：policy、priority、counter、rt_priority，

它們是調(diào)度程序運行時在所有可運行狀態(tài)的進(jìn)程中選擇調(diào)度的依據(jù)。其中，policy是進(jìn)程調(diào)度策略，用來區(qū)分實時進(jìn)程和非實時進(jìn)程;priority是進(jìn)程(包括實時進(jìn)程和非實時進(jìn)程)的靜態(tài)優(yōu)先級;counter是進(jìn)程剩余的時間片，它的起始值就是priority的值，另外 counter還以看作是進(jìn)程的動態(tài)優(yōu)先級，用于計算處于可運行狀態(tài)的進(jìn)程值得運行的程度goodness;rt_priority是實時進(jìn)程特有的，用于實時進(jìn)程間的選擇。[1]

其進(jìn)程調(diào)度過程可簡要概述如下：首先，uClinux根據(jù)policy從整體上區(qū)分實時進(jìn)程和非實時進(jìn)程，其中，實時進(jìn)程先于非實時進(jìn)程運行，對于同一類型的不同進(jìn)程，采用不同的標(biāo)準(zhǔn)來選擇，對于非實時進(jìn)程，uClinux根據(jù)進(jìn)程counter的大小采用動態(tài)優(yōu)先調(diào)度;對于實時進(jìn)程，uClinux采用先來先服務(wù)調(diào)度(FIFO)和時間片輪轉(zhuǎn)調(diào)度(RR)兩種調(diào)度方法。

2 uClinux進(jìn)程的調(diào)度策略

在uClinux操作系統(tǒng)中，進(jìn)程的調(diào)度策略是由task_struct結(jié)構(gòu)成員policy所選擇的，它的值為下述三種之一，即SCHED_FIFO(先來先服務(wù)調(diào)度)，SCHED_RR(時間片輪轉(zhuǎn)調(diào)度)

和SCHED_OTHER(非實時調(diào)度)。

SCHED_FIFO遵循POSIX1.b標(biāo)準(zhǔn)的調(diào)度規(guī)則：CPU一直運行，直到有一個進(jìn)程因I/O阻塞，或者主動釋放CPU，或者是CPU被另一個更高rt_priority的實時進(jìn)程搶占，進(jìn)程只有當(dāng)時間片用完時才能被迫釋放CPU。

SCHED_RR也遵循POSIX1.b標(biāo)準(zhǔn)的調(diào)度規(guī)則：與SCHED_FIFO類似，當(dāng)進(jìn)程的時間片用完后，調(diào)度程序就將其加到SCHED_RR 隊列的末尾。對于該調(diào)度策略只要系統(tǒng)中有一個實時進(jìn)程在運行，則任何SCHED_OTHER進(jìn)程都不能在任何CPU上運行。一個進(jìn)程從創(chuàng)建到任務(wù)完成后終止，可能需要經(jīng)歷多次反饋循環(huán)。

SCHED_OTHER是傳統(tǒng)的unix調(diào)度策略，適合于交互式的分時進(jìn)程。這類非實時進(jìn)程的優(yōu)先權(quán)取決于兩個因素：一個因素是進(jìn)程剩余時間配額，如果進(jìn)程用完了配給的時間，則相應(yīng)優(yōu)先權(quán)為0;如果進(jìn)程未用完時間片，則剩余時間參與其動態(tài)優(yōu)先級的計算。另一個因素是進(jìn)程的優(yōu)先數(shù)nice，即優(yōu)先數(shù)越小，優(yōu)先級越高。

如果系統(tǒng)中有實時進(jìn)程處于就緒狀態(tài)，則非實時進(jìn)程就不能被調(diào)度運行，直至所有實時進(jìn)程都完成了，非實時進(jìn)程才有機(jī)會占用CPU。

3 uClinux進(jìn)程的調(diào)度時機(jī)

通過分析進(jìn)程調(diào)度器的源代碼，可以發(fā)現(xiàn)uCLinux以五種方式轉(zhuǎn)入到schedule()處理函數(shù)進(jìn)行進(jìn)程調(diào)度[2]。

(1)進(jìn)程狀態(tài)轉(zhuǎn)換時。當(dāng)進(jìn)程要調(diào)用sleep( )或pause( )等函數(shù)使進(jìn)程狀態(tài)發(fā)生改變時，這些函數(shù)會主動調(diào)用schedule()轉(zhuǎn)入進(jìn)程調(diào)度。

(2)進(jìn)程終止時，永久放棄對CPU的使用。

(3)通過時鐘中斷。uClinux初始化時，設(shè)定系統(tǒng)定時器的周期為10ms。當(dāng)時鐘中斷發(fā)生時，時鐘中斷服務(wù)程序 timer_interrupt立即調(diào)用時鐘處理函數(shù)do_timer( )，該函數(shù)會調(diào)用mark_bh，將bh_active標(biāo)志的TIMER_BH置1，接著uClinux會在時鐘中斷服務(wù)程序中通過代碼片段

If( bh_active & bh_mask)

{ intr_count =1;

do_bottom_half();

intr_count = 0;

}

來判斷此時是否有bottom_half服務(wù)要處理，若有則執(zhí)行do_bottom_half()。該函數(shù)

會調(diào)用時鐘響應(yīng)函數(shù)timer_bh( )，分別由updates_times( )、run_old_timers( )和run_timer_list( )檢查、執(zhí)行調(diào)用服務(wù)。Update_times( )又調(diào)用update_process_times( )函數(shù)調(diào)整進(jìn)程的時間片，當(dāng)時間片小于0時，need_resched( 需要重調(diào)度)標(biāo)志會被置位。當(dāng)時鐘中斷處理完畢后，系統(tǒng)會返回到入口ret_from_intr，ret_with_reschedule處，判斷 need_resched 標(biāo)志是否置位，若是則轉(zhuǎn)入執(zhí)行schedule( )。

(4)當(dāng)喚醒一個睡眠進(jìn)程時，發(fā)現(xiàn)被喚醒的進(jìn)程比當(dāng)前進(jìn)程優(yōu)先級更高。www.51kaifa.com

(5)一個進(jìn)程通過執(zhí)行系統(tǒng)調(diào)用來改變調(diào)度策略或降低自身的優(yōu)先級，從而引起調(diào)度。

4 Schedule調(diào)度程序核心部分源代碼分析[3]

該調(diào)度程序的目標(biāo)是選擇下一個要執(zhí)行的進(jìn)程：首先對所有進(jìn)程進(jìn)行檢測，喚醒任何一個得到信號的進(jìn)程，即改變進(jìn)程的state屬性;然后根據(jù)時間片和優(yōu)先級調(diào)度機(jī)制來計算處于就緒隊列中每個進(jìn)程的綜合優(yōu)先級，其計算方法由goodness( )函數(shù)實現(xiàn);接著選擇綜合優(yōu)先級最高的進(jìn)程作為隨后要執(zhí)行的進(jìn)程，若就緒隊列中沒有可調(diào)度的，則重新分配時間片，即改變進(jìn)程的counter屬性值，并利用switch_to( )函數(shù)進(jìn)行進(jìn)程切換。

asmlinkage void schedule(void){

struct schedule_data * sched_data;

/*描述進(jìn)程的數(shù)據(jù)結(jié)構(gòu)，

包含指向所運行CPU的屬性。*/

struct task_struct *prev, *next, *p;

struct list_head *tmp;

int this_cpu, c;

spin_lock_prefetch(&runqueue_lock);

need_resched_back:

prev = current;

this_cpu = prev->processor;

if (unlikely(in_interrupt())) {

/*判斷是否在中斷服務(wù)程序中*/

printk("Scheduling in interrupt\\n"); www.51kaifa.com

/*是的話則打印錯誤提示，退出調(diào)度器*/

BUG();

}

release_kernel_lock(prev, this_cpu); /*釋放全局內(nèi)核鎖和全局中斷鎖*/

sched_data=&aligned_data[this_cpu].schedule_data;

if (unlikely(prev->policy == SCHED_RR))

if (!prev->counter) {

prev->counter= NICE_TO_TICKS(prev->nice);

move_last_runqueue(prev);

}

switch (prev->state) {

case TASK_INTERRUPTIBLE:

/*此狀態(tài)表明進(jìn)程可以被信號中斷*/

if (signal_pending(prev)) {

/*如果該進(jìn)程有未處理的信號*/

prev->state= TASK_RUNNING; break;

}

default:

del_from_runqueue(prev);

case TASK_RUNNING:;

}

prev->need_resched = 0;

repeat_schedule: /*缺省選擇空閑進(jìn)程*/

next = idle_task(this_cpu);

c = -1000;

list_for_each(tmp, &runqueue_head) {

p = list_entry(tmp, struct task_struct, run_list);

if (can_schedule(p, this_cpu)) {

/*尋找優(yōu)先級最高的那個進(jìn)程*/

int weight=

goodness(p, this_cpu, prev->active_mm);

if (weight > c)

c = weight, next = p;

}

}

if (unlikely(!c)) {

/*若處于運行隊列中的進(jìn)程沒有可調(diào)度的，那么得重新分配時間片*/

struct task_struct *p;

for_each_task(p)

p->counter = (p->counter >> 1) + NICE_TO_TICKS(p->nice);

goto repeat_schedule;

}

sched_data->curr = next;

task_set_cpu(next, this_cpu); www.51kaifa.com

if (unlikely(prev == next)){

/*如果選中的進(jìn)程和原來運行的進(jìn)程是同一個*/

prev->policy &= ~SCHED_YIELD;

goto same_process;

}

kstat.context_swtch++;

/*全局統(tǒng)計進(jìn)程上下文切換次數(shù)*/

prepare_to_switch();

/*準(zhǔn)備進(jìn)行進(jìn)程切換*/

{

……/*進(jìn)程的頁表處理，代碼略*/

}

switch_to(prev, next, prev); www.51kaifa.com

/*切換到選中的進(jìn)程中*/

__schedule_tail(prev);

/*考慮將當(dāng)前被切換下來的進(jìn)程，放到別的CPU上運行*/

same_process:

reacquire_kernel_lock(current);www.51kaifa.com

/*重新獲得內(nèi)核鎖*/

if (current->need_resched)

goto need_resched_back;

return;

}

整個schedule()的工作流程可以概述成以下幾步：

1). 清理當(dāng)前運行中的進(jìn)程

2). 選擇下一個投入運行的進(jìn)程

3). 設(shè)置新進(jìn)程的運行環(huán)境www.51kaifa.com

4). 執(zhí)行進(jìn)程上下文切換

5). 后期整理

5 結(jié)束語

uClinux的進(jìn)程調(diào)度有其獨有的特征，比如為了將三種調(diào)度策略協(xié)調(diào)一致同時不增加程序復(fù)雜度，uClinux為每一個進(jìn)程設(shè)置相應(yīng)的調(diào)度策略，并設(shè)置實時進(jìn)程的優(yōu)先級遠(yuǎn)高于非實時進(jìn)程，使得在調(diào)度過程中不必去區(qū)分實時進(jìn)程和非實時進(jìn)程，從而獲得最佳響應(yīng)時間。同時，uClinux操作系統(tǒng)采用底半部分處理策略，將中斷處理服務(wù)程序分割成兩部分，提高了響應(yīng)時間。另外，被暫時掛起的中斷處理程序及任務(wù)隊列，都要放在schedule( )中去處理，并優(yōu)于其它進(jìn)程調(diào)度，形成了uClinux獨具特色的調(diào)度風(fēng)格。

參考文獻(xiàn)：

[1] Claudia Salzberg Rodriguez，Gordon Fischer，Steven Smolski.The Linux Kernel Primer[M].北京：機(jī)械工業(yè)出版社，2006www.51kaifa.com

[2] 鄒治鋒，張曦煌.Linux 2.6進(jìn)程調(diào)度[J].微計算機(jī)信息.2006，1-2：77-79

[3] uClinux官方網(wǎng)站源碼下載. http://www.uclinux.org/pub/uClinux/dist/.2007