岳笑含, 劉艷秋

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

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

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

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

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

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

1.1.1 非實(shí)時(shí)進(jìn)程優(yōu)先級的計(jì)算

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

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

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

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

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

1.1.2 實(shí)時(shí)進(jìn)程優(yōu)先級的計(jì)算

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

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

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

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

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

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

1.2.1 FIFO調(diào)度策略

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

1.2.2 RR調(diào)度策略

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

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

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

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

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

2.1.1 基于EDF的改進(jìn)原理

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

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

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

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

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

2.1.2 基于EDF的算法步驟

具體的算法步驟如下:

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

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

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

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

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

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

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

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

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

2.2 Linux 2.6實(shí)時(shí)調(diào)度策略的改進(jìn)

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

#define SCHED_EDF 4

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

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

unsigned long deadline; /＊任務(wù)的截止期限 ＊/

unsigned long relate_dl;/＊任務(wù)的相對截止期,用截止期減當(dāng)前時(shí)間.＊/

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

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

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

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

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

static void enqueue_rt_task(struct task_

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

3 試驗(yàn)分析

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

試驗(yàn)環(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ù)試驗(yàn)程序,生成3個(gè)實(shí)時(shí)任務(wù) T1、T2、T3(如表1所示),這里,截止期只對EDF算法有效,對FIFO和RR不起作用.

表1 任務(wù)集Table 1 The task sets

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

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

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

4 結(jié) 語

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

[1] 欒建海,李眾立,黃曉芳.Linux2.6內(nèi)核分析[J].兵工自動(dòng)化,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].北京:機(jī)械工業(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.