基于Linux 2.6進程調度系統的實時性研究

岳笑含, 劉艷秋

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

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

1 Linux 2.6進程調度系統的實時性分析

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

1.1 進程的優先級計算

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

1.1.1 非實時進程優先級的計算

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

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

effective_prio()函數并不是只被 recalc_ task_prio()所調用,它還主要被調用在scheduler_tick()時鐘中斷程序、sched_fork()、wake_ up_new_task()等函數里.它用于計算進程的動態優先級(prio),同時也包括實時進程的動態優先級.對于非實時進程的計算它是通過該進程的平均睡眠時間(sleep_avg)和靜態優先級(static_ prio等同于nice)2個因素來確定的,在i386結構體系中,其計算公式如下:(其中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 實時進程優先級的計算

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

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

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

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

1.2 Linux 2.6的實時調度策略

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

1.2.1 FIFO調度策略

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

1.2.2 RR調度策略

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

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

2 EDF調度策略在Linux 2.6上的改進

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

2.1 EDF調度策略在Linux 2.6上的實現方案

2.1.1 基于EDF的改進原理

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

①進程的優先級越大,越先得到調度;

②如果優先級相同,那么進程相對截止期越小越先得到調度;

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

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

2.1.2 基于EDF的算法步驟

具體的算法步驟如下:

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

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

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

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

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

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

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

③如果沒有前兩種情況發生時,Ti繼續執行.

(6)轉到步驟2,循環反復直到實驗結束.

2.2 Linux 2.6實時調度策略的改進

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

#define SCHED_EDF 4

2.2.1 數據結構的修改

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

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

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

當一個實時進程被創建時,把該進程的相關信息保存在此數據結構中;當該進程結束時,就從該鏈表中刪除.

2.2.2 相關函數的修改

主要修改兩個調度函數:scheduler_tick()和enqueue_rt_task().

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

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

static void enqueue_rt_task(struct task_

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

3 試驗分析

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

試驗環境:操作系統 FC6;內核 2.6.20; CPU為Pentium Ⅳ/3.0 GHz,內存512 MB.

測試工具:systemtap0.96.

FIFO、RR和EDF調度策略的比較:

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

表1 任務集Table 1 The task sets

3個任務分別運行在FIFO、RR、EDF調度策略下,運行結果如圖2所示.

圖2 測試結果Fig.2 The experimental results

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

4 結 語

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

[1] 欒建海,李眾立,黃曉芳.Linux2.6內核分析[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].北京:機械工業出版社,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.