岳笑含, 劉艷秋

(沈陽工業(yè)大學,遼寧沈陽110023)

由于Linux是開源的操作系統(tǒng),它擁有眾多的開發(fā)和維護者,并且將其運用在各種不同的領域里,發(fā)揮了極好的作用.并且Linux的速度或效率都表現(xiàn)得非常好,只是在一些情況下,這樣的速度還不能滿足某些需求.有時需要的是在特定的容差范圍內(nèi)確定性地滿足調(diào)度期限的能力.故此,本文將從Linux 2.6調(diào)度器的實時性分析入手,針對EDF實時調(diào)度算法進行討論,并對內(nèi)核進行相應的改進,以便更加適合實時進程(任務)的執(zhí)行.

1 Linux 2.6進程調(diào)度系統(tǒng)的實時性分析

Linux 2.6加入了內(nèi)核搶占并實現(xiàn)了調(diào)度算法時間復雜度為O(1),Linux 2.6的實時性得到了加強,對于O(1)調(diào)度算法和內(nèi)核搶占,有很多資料對其進行了詳細的闡述[1],本節(jié)只介紹Linux 2.6優(yōu)先級的計算和Linux 2.6的實時調(diào)度策略.

1.1 進程的優(yōu)先級計算

由于Linux 2.6調(diào)度器調(diào)度進程是依據(jù)優(yōu)先級的大小(prio值),所以優(yōu)先級的計算是人們所關心的,進程優(yōu)先級的計算分為普通進程優(yōu)先級的計算和實時進程優(yōu)先級的計算.

1.1.1 非實時進程優(yōu)先級的計算

非實時優(yōu)先級的計算,一般通過2個函數(shù)來實現(xiàn):effective_prio()和recalc_task_prio()[2],首先介紹recalc_task_prio()函數(shù).

recalc_task_prio()函數(shù)的調(diào)用時機一般是當執(zhí)行schedule()或active_task()系統(tǒng)調(diào)用,并且主要用于schedule()系統(tǒng)調(diào)用時,用于計算非實時進程的優(yōu)先級.它首先通過計算并對當前進程(主要是對交互式進程)的平均睡眠時間做相應的調(diào)整;然后調(diào)用effective_prio()函數(shù).

effective_prio()函數(shù)并不是只被 recalc_ task_prio()所調(diào)用,它還主要被調(diào)用在scheduler_tick()時鐘中斷程序、sched_fork()、wake_ up_new_task()等函數(shù)里.它用于計算進程的動態(tài)優(yōu)先級(prio),同時也包括實時進程的動態(tài)優(yōu)先級.對于非實時進程的計算它是通過該進程的平均睡眠時間(sleep_avg)和靜態(tài)優(yōu)先級(static_ prio等同于nice)2個因素來確定的,在i386結(jié)構體系中,其計算公式如下:(其中sleep_avg值類型為Jiffies)

prio=max(100,min((p-＞static_prio-(sleep_avg/10+5)),139))

其中(sleep_avg/10-5)計算出來的值作為對該進程的獎勵/懲罰值,范圍在(-5,+5)之間,那么就可以看出,當一個進程睡眠時間比較長的話,它就會得到+5的獎勵,如果沒有睡眠的話,那么它將得到-5的懲罰.

1.1.2 實時進程優(yōu)先級的計算

實時進程優(yōu)先級的計算,是通過effective_ prio()函數(shù),但與實時進程的平均睡眠時間以及靜態(tài)優(yōu)先級無關,與計算有關的是rt_priority變量.這個變量通過sys_sched_setparam()來設置和改變,并且該值不會動態(tài)地修改,即內(nèi)核不為實時進程計算動態(tài)優(yōu)先級,那么就使得實時進程的調(diào)度單純依賴于一個固定的值.其優(yōu)先級的計算公式如下:

prio=MAX_RT_PRIO-1-p-＞rt_priority其中,MAX_RT_PRIO=100.

由此可見,rt_priority值越大,實時進程的優(yōu)先級越高,該值的取值范圍是0～99.

對于實時進程,固定的優(yōu)先級表示了該進程的關鍵程度,越關鍵的實時進程,它對系統(tǒng)的貢獻作用也越大,但是僅僅考慮任務的關鍵性對于實時進程是不夠的,實時進程的最大特點就是具有截止期的特征.

1.2 Linux 2.6的實時調(diào)度策略

Linux 2.6的調(diào)度策略比較簡單,分為4種: NORMAL、BA TCH、FIFO和RR.本節(jié)只討論FIFO和RR兩種實時調(diào)度策略,這兩種調(diào)度策略為軟實時調(diào)度策略[3].

1.2.1 FIFO調(diào)度策略

FIFO是先進先出的一種調(diào)度算法.它實現(xiàn)了一種簡單的、先入先出的調(diào)度算法,它不使用時間片.FIFO級的進程會比任何NORMAL級的進程都先得到調(diào)度,一旦一個FIFO級進程處于可執(zhí)行狀態(tài),就會一直執(zhí)行,直道它自己受阻塞或顯式地釋放處理器為止;它不基于時間片,可以一直執(zhí)行下去.只有較高優(yōu)先級的FIFO或RR級進程才能搶占FIFO進程,而NORMAL級進程將不會被調(diào)用.

1.2.2 RR調(diào)度策略

RR調(diào)度策略,與FIFO大體相同,只是RR級的進程在耗盡事先分配給它的時間片后就不能再接著執(zhí)行了,即RR是帶有時間片的FIFO,這是一種實時的輪回調(diào)度算法.當RR級進程耗完自己的時間片后,將其插入到同等優(yōu)先級進程隊列的末尾,并與同等優(yōu)先級進程一起輪流調(diào)度,時間片只用來重新調(diào)度同一優(yōu)先級的進程.

對于實時進程優(yōu)先級的計算方法,體現(xiàn)的是“靜態(tài)優(yōu)先級”,即將任務的關鍵性作為衡量實時進程優(yōu)先級標準的唯一途徑.這對于實時調(diào)度策略是比較簡單和片面的,容易導致具有同樣關鍵性進程的截止期不被滿足或系統(tǒng)資源得不到充分利用而夭折.針對這些缺點,下面將引入EDF調(diào)度算法對Linux 2.6內(nèi)核進行有針對性的改進和實施.

2 EDF調(diào)度策略在Linux 2.6上的改進

EDF調(diào)度算法,是最著名的基于截止期優(yōu)先的實時調(diào)度算法,它按照任務的相對截止期進行由小到大的排序[4].

2.1 EDF調(diào)度策略在Linux 2.6上的實現(xiàn)方案

2.1.1 基于EDF的改進原理

EDF算法是截止時間驅(qū)動調(diào)度算法,是一種動態(tài)的調(diào)度算法.EDF指在調(diào)度時,進程的優(yōu)先級根據(jù)進程的截止時間動態(tài)分配.截止時間越短,優(yōu)先級越高,EDF調(diào)度算法是在進程執(zhí)行期間,根據(jù)它的啟動時間改變優(yōu)先級;并以最后期限的順序指定優(yōu)先級.優(yōu)先級最高的進程是距離最后期限最近的進程,優(yōu)先級最低的進程是距離最后期限最遠的進程.并且,EDF調(diào)度算法已被證明是動態(tài)最優(yōu)調(diào)度,而且是充要條件,處理器的利用率最大可達 100%.將 EDF引入到Linux調(diào)度器中,可以采取如下策略:

①進程的優(yōu)先級越大,越先得到調(diào)度;

②如果優(yōu)先級相同,那么進程相對截止期越小越先得到調(diào)度;

可見,相對截止期在具有同等優(yōu)先級的進程隊列里得到了表現(xiàn),根據(jù)以上原則,可以得到運行隊列,如圖1所示.

圖1 基于EDF的實時進程調(diào)度Fig.1 Real-time process schedule based on EDF

2.1.2 基于EDF的算法步驟

具體的算法步驟如下:

(1)確定實時進程所在優(yōu)先級隊列,并按相對截止期的大小在同一優(yōu)先級隊列里進行由小到大的排序;

(2)如果有中斷產(chǎn)生,都要重新計算各個隊列的相對截止期,并查看是否有實時進程錯失截止期,并將錯失截止期的進程夭折;

(3)對新到達的任務將其送入到相應的優(yōu)先級任務隊列中,并按相對截止期大小入隊;

(4)如果當前沒有任務占用CPU,則從等待任務隊列中選擇優(yōu)先級等級最高、截止期最早的任務調(diào)度執(zhí)行,如上一節(jié),即是該優(yōu)先級隊列的隊首任務;

(5)如果當前有任務 Ti在執(zhí)行并假設其實時優(yōu)先等級為rpi,那么:

①如果有更高優(yōu)先級的任務 Tj存在,即rpj＞rpi,則 Tj搶占 Ti;

②如果沒有更高優(yōu)先等級的任務,但有相同優(yōu)先等級且相對截止期更小的任務存在,即rpj=rpi,且 dj＜di,則 Tj搶占 Ti;

③如果沒有前兩種情況發(fā)生時,Ti繼續(xù)執(zhí)行.

(6)轉(zhuǎn)到步驟2,循環(huán)反復直到實驗結(jié)束.

2.2 Linux 2.6實時調(diào)度策略的改進

由于篇幅所限,這一節(jié)只給出主要數(shù)據(jù)結(jié)構以及函數(shù)的改進.并且值得說明的是,在修改中,增加了EDF調(diào)度算法,即:

#define SCHED_EDF 4

2.2.1 數(shù)據(jù)結(jié)構的修改

調(diào)度策略由于采用EDF的調(diào)度原理,所以必須增加幾個由CDF實時進程相關信息組成的隊列,以便于優(yōu)先級的計算.修改在task_struct中,如下:

unsigned long deadline; /＊任務的截止期限 ＊/

unsigned long relate_dl;/＊任務的相對截止期,用截止期減當前時間.＊/

當一個實時進程被創(chuàng)建時,把該進程的相關信息保存在此數(shù)據(jù)結(jié)構中;當該進程結(jié)束時,就從該鏈表中刪除.

2.2.2 相關函數(shù)的修改

主要修改兩個調(diào)度函數(shù):scheduler_tick()和enqueue_rt_task().

scheduler_tick()的修改,增加了對實時進程的相對截止期進行更新以及過截止期進程的夭折:

enqueue_rt_task()是添加的一個函數(shù),與enqueue_task()類似,不過在這里的入隊方式是按截止期大小排列的.

static void enqueue_rt_task(struct task_

綜上所述,首先提出了 EDF在Linux 2.6中的改進原理,并提出了相應的算法步驟,最后落實到了內(nèi)核代碼的修改上面,那么接下來進行試驗分析.

3 試驗分析

試驗分析比較的是各個調(diào)度算法平均執(zhí)行性能.這一指標根據(jù)的是截止期滿足率,如果系統(tǒng)能夠保證實時進程的運行在其截止期內(nèi)完成,則稱該進程在此運行時的截止期限得到滿足;試驗讓幾個實時進程有周期地多次運行,并根據(jù)每次運行得到的滿足次數(shù)以及運行次數(shù)加以比較,即截止期滿足率[5](用百分比表示),以此來對不同實時調(diào)度策略的性能加以區(qū)分.

試驗環(huán)境:操作系統(tǒng) FC6;內(nèi)核 2.6.20; CPU為Pentium Ⅳ/3.0 GHz,內(nèi)存512 MB.

測試工具:systemtap0.96.

FIFO、RR和EDF調(diào)度策略的比較:

根據(jù)試驗程序,生成3個實時任務 T1、T2、T3(如表1所示),這里,截止期只對EDF算法有效,對FIFO和RR不起作用.

表1 任務集Table 1 The task sets

3個任務分別運行在FIFO、RR、EDF調(diào)度策略下,運行結(jié)果如圖2所示.

圖2 測試結(jié)果Fig.2 The experimental results

通過試驗表明,基于EDF調(diào)度算法的進程調(diào)度系統(tǒng)具有較好的實時任務處理能力,能夠基本保證任務的截止期錯失率.

4 結(jié) 語

剖析了Linux 2.6進程優(yōu)先級的計算,并分析了Linux 2.6實時調(diào)度策略在實時性以及實時進程處理上所存在的不足.基于以上兩點,引入了基于進程截止期的EDF算法,并進行了詳細的說明,更進一步地在Linux 2.6.20內(nèi)核里進行了相應的修改和完善,最終根據(jù)試驗結(jié)果,證明了該調(diào)度策略具備更強的關鍵性實時進程的調(diào)度能力,從而提高了Linux硬實時性以及處理關鍵性進程的能力.

[1] 欒建海,李眾立,黃曉芳.Linux2.6內(nèi)核分析[J].兵工自動化,2005,24(2):89-90,92.

[2] Rodriguez Claudia Salzberg, Fischer Gordon, Smolski Steven.The Linux Kernel Primer:A Topdown Approach for X86and PowerPC Architectures[M].北京:機械工業(yè)出版社,2006:78-79.

[3] Bovet Daniel P,Cesati Marco.Understanding the Linux Kernel[M].陳莉君,等譯.北京:中國電力出版社,2007:258-289.

[4] Buttazzo G C.Rate Monotonic vs.EDF:Judgment day[J].J ournal of Real-Time Systems,2005,29 (1):5-26.

[5] Stankovic J A,Spuri M,Ramanritham K,et al. Deadline Scheduling for Real-time Systems:EDF and Related Algorithms[M].Boston:Kluwer Academic Publisher,1991:144-147.