0 引言

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

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

uClinux中每個進程的task_struct結構中有四項：policy、priority、counter、rt_priority，

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

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

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

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

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

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

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

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

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

3 uClinux進程的調(diào)度時機

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

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

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

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

If( bh_active & bh_mask)

{ intr_count =1;

do_bottom_half();

intr_count = 0;

}

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

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

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

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

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

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

asmlinkage void schedule(void){

struct schedule_data * sched_data;

/*描述進程的數(shù)據(jù)結構，

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

/*判斷是否在中斷服務程序中*/

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)表明進程可以被信號中斷*/

if (signal_pending(prev)) {

/*如果該進程有未處理的信號*/

prev->state= TASK_RUNNING; break;

}

default:

del_from_runqueue(prev);

case TASK_RUNNING:;

}

prev->need_resched = 0;

repeat_schedule: /*缺省選擇空閑進程*/

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)先級最高的那個進程*/

int weight=

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

if (weight > c)

c = weight, next = p;

}

}

if (unlikely(!c)) {

/*若處于運行隊列中的進程沒有可調(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)){

/*如果選中的進程和原來運行的進程是同一個*/

prev->policy &= ~SCHED_YIELD;

goto same_process;

}

kstat.context_swtch++;

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

prepare_to_switch();

/*準備進行進程切換*/

{

……/*進程的頁表處理，代碼略*/

}

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

/*切換到選中的進程中*/

__schedule_tail(prev);

/*考慮將當前被切換下來的進程，放到別的CPU上運行*/

same_process:

reacquire_kernel_lock(current);www.51kaifa.com

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

if (current->need_resched)

goto need_resched_back;

return;

}

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

1). 清理當前運行中的進程

2). 選擇下一個投入運行的進程

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

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

5). 后期整理

5 結束語

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

參考文獻：

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

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

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