摘要：針對操作系統(tǒng)中進程的調度機制，依次對其調度方式、調度策略、調度時機進行了分析，并結合uClinux中進程調度實現(xiàn)的核心源代碼，剖析了uClinux中進程調度器的實現(xiàn)原理，展示了uClinux中獨具特色的進程調度機制。
關鍵詞：uClinux；調度策略；進程調度器

0. 引言

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



1. uClinux進程的調度方式[1]

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

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

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



2. uClinux進程的調度策略

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

　　和SCHED_OTHER（非實時調度）。

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

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

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

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



3. uClinux進程的調度時機

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

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

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

　　(3) 通過時鐘中斷。uClinux初始化時，設定系統(tǒng)定時器的周期為10ms。當時鐘中斷發(fā)生時，時鐘中斷服務程序timer_interrupt立即調用時鐘處理函數(shù)do_timer( )，該函數(shù)會調用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ù)

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

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

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



4. Schedule調度程序核心部分源代碼分析[3]

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

/*是的話則打印錯誤提示，退出調度器*/

BUG（）；

}

release_kernel_lock(prev, this_cpu)； /*釋放全局內核鎖和全局中斷鎖*/

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)) {

/*若處于運行隊列中的進程沒有可調度的，那么得重新分配時間片*/

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

/*重新獲得內核鎖*/

if (current->need_resched)

goto need_resched_back；

return；

}





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

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

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

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

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

5). 后期整理



5. 結束語

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

參考文獻：

[1] Claudia Salzberg Rodriguez，Gordon Fischer，Steven Smolski.The Linux Kernel Primer

[M].北京：機械工業(yè)出版社，2006www.51kaifa.com

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

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