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

0 引言

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

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

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

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

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

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

在uClinux操作系統中，進(jìn)程的調度策略是由task_struct結構成員policy所選擇的，它的值為下述三種之一，即SCHED_FIFO（先來(lái)先服務(wù)調度），SCHED_RR（時(shí)間片輪轉調度）

和SCHED_OTHER（非實(shí)時(shí)調度）。

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

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

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

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

3 uClinux進(jìn)程的調度時(shí)機

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

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

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

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

If( bh_active bh_mask)

{ intr_count =1；

do_bottom_half（）；

intr_count = 0；
}

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

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