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

0 引言

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

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

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

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

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

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

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

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

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

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

3 uClinux進(jìn)程的調(diào)度時(shí)機(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)換時(shí)。當(dāng)進(jìn)程要調(diào)用sleep( )或pause( )等函數(shù)使進(jìn)程狀態(tài)發(fā)生改變時(shí)，這些函數(shù)會(huì)主動(dòng)調(diào)用schedule()轉(zhuǎn)入進(jìn)程調(diào)度。

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

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

If( bh_active & bh_mask)

{ intr_count =1;

do_bottom_half();

intr_count = 0;

}

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

會(huì)調(diào)用時(shí)鐘響應(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)程的時(shí)間片，當(dāng)時(shí)間片小于0時(shí)，need_resched( 需要重調(diào)度)標(biāo)志會(huì)被置位。當(dāng)時(shí)鐘中斷處理完畢后，系統(tǒng)會(huì)返回到入口ret_from_intr，ret_with_reschedule處，判斷 need_resched 標(biāo)志是否置位，若是則轉(zhuǎn)入執(zhí)行schedule( )。

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

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

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

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

包含指向所運(yùn)行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

/*是的話則打印錯(cuò)誤提示，退出調(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)程可以被信號(hào)中斷*/

if (signal_pending(prev)) {

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

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í)最高的那個(gè)進(jìn)程*/

int weight=

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

if (weight > c)

c = weight, next = p;

}

}

if (unlikely(!c)) {

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

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)程和原來運(yùn)行的進(jìn)程是同一個(gè)*/

prev->policy &= ~SCHED_YIELD;

goto same_process;

}

kstat.context_swtch++;

/*全局統(tǒng)計(jì)進(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上運(yùn)行*/

same_process:

reacquire_kernel_lock(current);www.51kaifa.com

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

if (current->need_resched)

goto need_resched_back;

return;

}

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

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

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

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

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

5). 后期整理

5 結(jié)束語

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

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