基于EDF算法的嵌入式Linux實(shí)時(shí)調(diào)度策略

關(guān)斌斌，王勇

（南京郵電大學(xué) 南京 210003）

0 引言

目前市場上比較著名的嵌入式操作系統(tǒng)有Vxwork、pSOS、Windows CE和Neculeus，但這些專用操作系統(tǒng)都是商業(yè)化產(chǎn)品，其高昂的價(jià)格使許多低端產(chǎn)品的小公司望而卻步，而且，源代碼封裝性也大大限制了開發(fā)者的積極性。嵌入式Linux以其免費(fèi)、適應(yīng)于多種CPU和多種硬件平臺(tái)、性能穩(wěn)定、裁剪性能好以及開放源代碼、開發(fā)和使用都很容易等眾多特性獲得越來越多的關(guān)注。

標(biāo)準(zhǔn)Linux是一個(gè)多任務(wù)多用戶的分時(shí)操作系統(tǒng)，盡管系統(tǒng)通過為實(shí)時(shí)任務(wù)賦予較高的優(yōu)先級(jí)使得系統(tǒng)具有一定的實(shí)時(shí)性，但對于大多數(shù)時(shí)限要求較高的實(shí)時(shí)任務(wù)來說，標(biāo)準(zhǔn)Linux還遠(yuǎn)遠(yuǎn)達(dá)不到其對于時(shí)間約束的要求。常用的實(shí)時(shí)性改造方法是采用雙內(nèi)核方法[1]，這種方法的弊端在于實(shí)時(shí)任務(wù)的開發(fā)是直接面向提供精確實(shí)時(shí)服務(wù)的小實(shí)時(shí)核心的，而不是功能強(qiáng)大的常規(guī)Linux核心?；诖耍壳靶薷暮说姆椒ㄎ烁嘌芯亢烷_發(fā)人員的注意力，這種方法是基于已有Linux系統(tǒng)對于軟件開發(fā)的支持，進(jìn)行源代碼級(jí)修改而使Linux變成一個(gè)真正的實(shí)時(shí)操作系統(tǒng)。本文分析了基本Linux內(nèi)核的實(shí)時(shí)任務(wù)調(diào)度策略，基于其對實(shí)時(shí)應(yīng)用的技術(shù)障礙，提出了一種新穎的Linux內(nèi)核實(shí)時(shí)任務(wù)調(diào)度策略，并提出了以最早期限優(yōu)先動(dòng)態(tài)調(diào)度算法代替原內(nèi)核的FIFO調(diào)度算法，以增強(qiáng)Linux內(nèi)核的調(diào)度性能。

1 Linux內(nèi)核的調(diào)度策略

Linux作為一個(gè)通用操作系統(tǒng)，主要考慮的是調(diào)度的公平性和吞吐量等指標(biāo)。然而，在實(shí)時(shí)方面它還不能很好地滿足實(shí)時(shí)系統(tǒng)方面的需要，其本身僅僅提供了一些簡單的實(shí)時(shí)處理的支持，這包括支持大部分POSIX（可移植操作系統(tǒng)接口）標(biāo)準(zhǔn)中的實(shí)時(shí)功能，如支持多任務(wù)、多隊(duì)列，具有豐富的通信機(jī)制等；同時(shí)也提供了符合POSIX標(biāo)準(zhǔn)的調(diào)度策略，包括FIFO調(diào)度策略、時(shí)間片輪轉(zhuǎn)調(diào)度策略和靜態(tài)優(yōu)先級(jí)搶占式調(diào)度策略。

為了同時(shí)支持實(shí)時(shí)和非實(shí)時(shí)兩種進(jìn)程，Linux的調(diào)度策略[2]簡單講就是優(yōu)先級(jí)加上時(shí)間片。當(dāng)系統(tǒng)中有實(shí)時(shí)進(jìn)程到來時(shí)，系統(tǒng)賦予它最高的優(yōu)先級(jí)。體現(xiàn)在實(shí)時(shí)性上，Linux采用了兩種簡單的調(diào)度策略，即先來先服務(wù)調(diào)度（SCHED-FIFO）和時(shí)間片輪轉(zhuǎn)調(diào)度（SCHED-RR）。具體是將所有處于運(yùn)行狀態(tài)的任務(wù)掛接在一個(gè)run-queue 隊(duì)列中，對不同的任務(wù)，在其任務(wù)控制塊task_struct中用一個(gè)policy屬性來確定其調(diào)度策略，并將此任務(wù)分成實(shí)時(shí)和非實(shí)時(shí)任務(wù)。對實(shí)時(shí)性要求較嚴(yán)的實(shí)時(shí)任務(wù)采用SCHED-FIFO調(diào)度，使之在一次調(diào)度后運(yùn)行完畢。對普通非實(shí)時(shí)進(jìn)程，Linux采用基于優(yōu)先級(jí)的輪轉(zhuǎn)策略。盡管Linux本身提供了一些支持實(shí)時(shí)性的機(jī)制，由于缺乏有效的實(shí)時(shí)任務(wù)調(diào)度策略和調(diào)度算法，實(shí)時(shí)性問題仍然是將Linux應(yīng)用于實(shí)時(shí)應(yīng)用中一大障礙。

2 EDF動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法

動(dòng)態(tài)優(yōu)先級(jí)可以防止優(yōu)先級(jí)高的進(jìn)程不停的執(zhí)行，例如可以在每一個(gè)時(shí)鐘中斷時(shí)降低正在運(yùn)行著的進(jìn)程優(yōu)先級(jí)。這樣該進(jìn)程必然在某個(gè)時(shí)刻優(yōu)先級(jí)低于其他進(jìn)程，從而被切換掉。系統(tǒng)還可以通過動(dòng)態(tài)確定優(yōu)先級(jí)，以使某些特定的進(jìn)程得以優(yōu)先執(zhí)行。最著名的動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法就是最早期限優(yōu)先調(diào)度算法EDF[3]，按照任務(wù)的最終響應(yīng)期限來調(diào)度。哪個(gè)任務(wù)的期限最早，就是最緊急的任務(wù)，就會(huì)被賦予高優(yōu)先級(jí)，得到優(yōu)先調(diào)度。EDF是可搶占的調(diào)度算法，通常周期任務(wù)的最終期限是它下一個(gè)周期開始的時(shí)刻。Liu和Layland證明，如果存在某一種調(diào)度能夠滿足所有的時(shí)限要求，那么每一次總是執(zhí)行當(dāng)前具有最早時(shí)限的未完成任務(wù)就可以滿足所有時(shí)限的要求，并證明了對于一個(gè)n個(gè)周期任務(wù)的任務(wù)集T= {t1，t2，……，tn}可以被EDF所調(diào)度，當(dāng)且僅當(dāng)： ≤1

EDF表示時(shí)限最早的任務(wù)優(yōu)先調(diào)度，是調(diào)度理論中一個(gè)很重要的動(dòng)態(tài)調(diào)度算法，對于同步周期任務(wù)組是佳調(diào)度算法。

在EDF算法中，任務(wù)調(diào)度優(yōu)先級(jí)定義為：di(t)-t，di(t)是任務(wù)時(shí)限，t是當(dāng)前時(shí)間，兩者的差值就表示任務(wù)的緊迫程度。這種調(diào)度優(yōu)先級(jí)定義方式，表明在每個(gè)時(shí)刻，都要計(jì)算下個(gè)時(shí)刻系統(tǒng)中哪個(gè)任務(wù)的時(shí)限最小，從而決定了系統(tǒng)在下個(gè)時(shí)刻應(yīng)該調(diào)度哪個(gè)任務(wù)。系統(tǒng)下個(gè)時(shí)刻調(diào)度的任務(wù)的不確定性，使得系統(tǒng)的適應(yīng)性比較好。

根據(jù)EDF算法，處理器將分配給當(dāng)前距離絕對時(shí)限最近的任務(wù)。EDF算法是動(dòng)態(tài)調(diào)度算法，任務(wù)的優(yōu)先級(jí)不是固定的，而是根據(jù)各任務(wù)距離其絕對時(shí)限的接近程度決定。

在FIFO調(diào)度算法中，進(jìn)程一旦占用CPU則一直運(yùn)行，直到有更高優(yōu)先級(jí)任務(wù)到達(dá)或自己放棄，因此靈活性差。EDF調(diào)度算法最大的優(yōu)點(diǎn)是：對于突發(fā)實(shí)時(shí)事件的實(shí)時(shí)處理能力強(qiáng)，系統(tǒng)調(diào)度靈活，同時(shí)CPU的利用率較高，可以達(dá)到100%的利用率。最大缺點(diǎn)在于系統(tǒng)的開銷較大，在超載的情況下，系統(tǒng)不可能保證所有的任務(wù)都能夠滿足截止期。

3 基于EDF算法的實(shí)時(shí)任務(wù)調(diào)度策略

該調(diào)度策略吸取了EDF算法的優(yōu)點(diǎn)，又保證了內(nèi)核可以在任何時(shí)間被搶占，它主要取決于以下三個(gè)問題的解決，臨界區(qū)的保護(hù)、優(yōu)先級(jí)的確定、快速查找將調(diào)度實(shí)時(shí)進(jìn)程，下面就這三個(gè)問題的解決方法進(jìn)行說明。

3.1 臨界區(qū)的保護(hù)

主要保護(hù)措施如下：

(1)在臨界區(qū)上使用搶占鎖。系統(tǒng)維護(hù)一個(gè)全局變量，使用臨界區(qū)前設(shè)置該變量，使用完畢清除該變量。當(dāng)該變量被設(shè)置時(shí)說明有進(jìn)程使用臨界區(qū)，不允許搶占。如果此時(shí)發(fā)生中斷，在執(zhí)行完中斷處理程序后將恢復(fù)被中斷的進(jìn)程，不會(huì)進(jìn)行調(diào)度。當(dāng)獲得搶占鎖的進(jìn)程使用完臨界區(qū)釋放鎖，并檢查是否有高優(yōu)先級(jí)進(jìn)程就緒，如果有則執(zhí)行上下文切換。

(2)使用互斥鎖保護(hù)執(zhí)行時(shí)間較長的臨界段。利用信號(hào)量，進(jìn)程使用臨界區(qū)前進(jìn)行P操作,使用完畢進(jìn)行V操作。

(3)中斷處理過程的修改。在中斷返回時(shí)進(jìn)行搶占性判斷。

下面詳細(xì)說明每種保護(hù)措施的具體實(shí)現(xiàn)方法。

3.1.1 搶占鎖實(shí)現(xiàn)方法

為了實(shí)現(xiàn)搶占鎖[4],需要在Linux的進(jìn)程結(jié)構(gòu)taskstruct中增加一項(xiàng)搶占計(jì)數(shù)器atomic_preempt_count。當(dāng)進(jìn)程執(zhí)行搶占鎖時(shí)搶占計(jì)數(shù)器加1，當(dāng)進(jìn)程釋放搶占鎖時(shí)搶占計(jì)數(shù)器減1；如果進(jìn)程的搶占計(jì)數(shù)器值為0，則該進(jìn)程在內(nèi)核態(tài)下執(zhí)行時(shí)可以被搶占。搶占鎖屬于一種遞歸鎖，對于己經(jīng)擁有鎖的進(jìn)程可以再次獲得搶占鎖，也就是允許嵌套使用臨界段。

為了在搶占式內(nèi)核的實(shí)現(xiàn)中保持原來使用的自旋鎖，在禁止搶占之后設(shè)置自旋鎖。將原來對自旋鎖的實(shí)現(xiàn)函數(shù)改名為pre_ spin_ lock()和pre_spin_unlock ()，用搶占鎖的加鎖和解鎖代替原來的自旋鎖實(shí)現(xiàn)函數(shù)spin_lock()和spin_unlock()。新的搶占鎖加鎖操作為:先禁止搶占，再執(zhí)行pre_ sp in_lock()：解鎖操作為：先執(zhí)行pre_spin_unlock()，再解除搶占。這樣就由搶占鎖代替了自旋鎖對臨界區(qū)提供保護(hù)，同時(shí)也保持了原來定義的自旋鎖，代碼修改盡量少。

3.1.2 互斥鎖的實(shí)現(xiàn)方法

為了減少由于搶占鎖長時(shí)間鎖定臨界段而可能帶來的延遲，使用互斥鎖來保護(hù)執(zhí)行時(shí)間較長的臨界段?；コ怄i的實(shí)現(xiàn)利用了Linux內(nèi)核中的二元信號(hào)量。信號(hào)量[5]使用兩個(gè)原子操作P操作和V操作，進(jìn)入臨界段之前執(zhí)行P操作，離開臨界段后執(zhí)行V操作。P操作減少信號(hào)量，并當(dāng)信號(hào)量的新值為0時(shí)被阻塞；V操作增加信號(hào)量，若信號(hào)量的新值小于等于0時(shí)，如果存在阻塞于該信號(hào)量的進(jìn)程則將之喚醒。如果信號(hào)量的初值為1，也就是由信號(hào)量保護(hù)的資源數(shù)目為1，稱之為二元信號(hào)量。內(nèi)核必須保證對信號(hào)量的操作是原子的。Linux對信號(hào)量的數(shù)據(jù)結(jié)構(gòu)的定義在include/rim-i386/semaphore.h中，在內(nèi)核信號(hào)量的實(shí)現(xiàn)中，與P操作和V操作相對應(yīng)的內(nèi)核例程分別是downQ和upQ?？梢灾苯永肔inux的信號(hào)量原語down()和up()來實(shí)現(xiàn)互斥鎖，其定義添加在頭文件nclude/rim-i386/semaphore.h中。

3.1.3 中斷的處理方法

Linux中斷處理的流程[6]是：中斷產(chǎn)生源→中斷向量表→中斷入口程序→中斷處理程序→中斷返回。為了實(shí)現(xiàn)搶占式的Linux內(nèi)核，必須對中斷的處理過程進(jìn)行修改。其要點(diǎn)是在中斷返回進(jìn)行搶占性判斷時(shí)，如果進(jìn)程在內(nèi)核態(tài)下運(yùn)行，還必須要判斷是否可以對內(nèi)核搶占，即判斷進(jìn)程搶占計(jì)數(shù)器的值是否為0。修改后的中斷處理流程如圖1所示。

圖1 修改后的中斷處理流程

3.2 優(yōu)先級(jí)的確定

每次內(nèi)核搶占時(shí)，從就緒進(jìn)程中選出優(yōu)先級(jí)最高的進(jìn)程進(jìn)行調(diào)度?？紤]到EDF算法采用動(dòng)態(tài)優(yōu)先級(jí)，盡管CPU利用率高，但會(huì)增大系統(tǒng)開銷，而且嵌入式系統(tǒng)資源又有限，因此這里以任務(wù)的截止期限作為任務(wù)調(diào)度的首選指標(biāo)，當(dāng)兩個(gè)任務(wù)的截止期限在允許的范圍內(nèi)時(shí)，根據(jù)任務(wù)的靜態(tài)優(yōu)先級(jí)來決定要運(yùn)行的任務(wù)，在一定程度上增強(qiáng)了算法的可控性，保證實(shí)時(shí)任務(wù)得到確定的響應(yīng)時(shí)間。確定任務(wù)的靜態(tài)優(yōu)先級(jí)，主要依據(jù)以下參數(shù)。

1）任務(wù)緊迫程度：根據(jù)任務(wù)的緊急程度，人為安排任務(wù)的優(yōu)先級(jí)。任務(wù)越緊急，靜態(tài)優(yōu)先級(jí)越高；

2）任務(wù)周期：任務(wù)周期越短，靜態(tài)優(yōu)先級(jí)越高；3）執(zhí)行時(shí)間：執(zhí)行時(shí)間越短 ，靜態(tài)優(yōu)先級(jí)越高。將以上三個(gè)參數(shù)的和作為靜態(tài)優(yōu)先級(jí)，如果任務(wù)的靜態(tài)優(yōu)先級(jí)相同則放在同一個(gè)就緒隊(duì)列的隊(duì)首，同一就緒隊(duì)列中的任務(wù)被分時(shí)調(diào)度，這樣可以保證在下次調(diào)度發(fā)生時(shí)被優(yōu)先調(diào)度。

3.3 快速查找將調(diào)度實(shí)時(shí)進(jìn)程的方法

在搶占式內(nèi)核中，調(diào)度發(fā)生前，如何快速找到優(yōu)先級(jí)最高的就緒實(shí)時(shí)任務(wù)是內(nèi)核所要解決的一個(gè)首要問題。目前發(fā)布的Linux內(nèi)核都是把實(shí)時(shí)進(jìn)程看作活動(dòng)進(jìn)程，放在就緒隊(duì)列中,按先進(jìn)先出策略進(jìn)行調(diào)度。這種方法沒有考慮實(shí)時(shí)進(jìn)程的緊迫性,很有可能延誤實(shí)時(shí)進(jìn)程,從而使嵌入式系統(tǒng)出現(xiàn)嚴(yán)重故障。本文在查表法及文獻(xiàn)[7]的基礎(chǔ)上，給出了快速查找將調(diào)度實(shí)時(shí)進(jìn)程的方法。

在本調(diào)度策略中優(yōu)先級(jí)由3.2部分介紹的方法確定，一個(gè)優(yōu)先級(jí)對應(yīng)著一個(gè)任務(wù)隊(duì)列，不同的任務(wù)可以具有相同的優(yōu)先級(jí)，但必需具有唯一的任務(wù)ID號(hào)。應(yīng)用查表法首先要解決的問題是建立查找表，考慮到目前發(fā)布的Linux內(nèi)核中實(shí)時(shí)優(yōu)先權(quán)的范圍是從1到99及內(nèi)核實(shí)時(shí)功能擴(kuò)充的需要，查找表可以看作一個(gè)預(yù)先設(shè)計(jì)好的常量數(shù)組ST[]，數(shù)組有65536個(gè)元素,從ST[0]到ST[65535]，本策略使用前8192個(gè)元素，各個(gè)元素的值通過計(jì)算得到。這樣每次可對一個(gè)13位數(shù)進(jìn)行查表，確定最高優(yōu)先級(jí)任務(wù)所在位置。ST[]表的設(shè)計(jì)方法為首先把數(shù)組下標(biāo)用16位二進(jìn)制數(shù)來表示(最低位為第0位,最高位為第15位)，再看為1的最低位在第幾位，然后把該值填入到數(shù)組下標(biāo)所指定的元素中。例如ST[80]，其下標(biāo)為80，轉(zhuǎn)換成二進(jìn)制為01010000，為1的最低位在第1位，所以ST[80]=4。系統(tǒng)最多可支持128個(gè)優(yōu)先級(jí)，把這128個(gè)優(yōu)先級(jí)分為16組，每組8個(gè)，通過兩次查表即可獲得當(dāng)前表中的最高優(yōu)先級(jí)的任務(wù)。用RRG中的位來指示任務(wù)的優(yōu)先級(jí)組，RRG的定義為 INT16U RRG(INT16U為無符號(hào)的16位整數(shù))。數(shù)組RRPT[]用來指示優(yōu)先級(jí)，RRPT[]的定義為INT8U RRPT[8] (INT8U為無符號(hào)的8位整數(shù))。RRPT[]里的元素只要不為0則RRG對應(yīng)位置1。

調(diào)度任務(wù)時(shí)，先依據(jù)RRG的值與ST[]表中的下標(biāo)對應(yīng)，該值記為k，ST[k]即是找到最高任務(wù)優(yōu)先級(jí)所在的組，假設(shè)查到的值為i，再用RRPT[i]值查表找到任務(wù)所在組里的位置，假設(shè)查到的值為j，即可得到最高優(yōu)先級(jí)為i×16+j，該優(yōu)先級(jí)對應(yīng)的就緒隊(duì)列中的第一任務(wù)就是將被調(diào)度的任務(wù)。

4 實(shí)時(shí)性能測試

常用的嵌入式實(shí)時(shí)操作系統(tǒng)性能測試方法包括：Rhealstone方法、進(jìn)程分配延遲時(shí)間（PDLT）法和三維表示法[8]，本文使用PDLT法測試改進(jìn)內(nèi)核的性能。進(jìn)程分派延遲時(shí)間定義為從中斷的產(chǎn)生到由中斷激活的實(shí)時(shí)任務(wù)開始執(zhí)行之間的時(shí)間間隔，這段間隔由幾部分時(shí)間組成，如圖2所示。這里的進(jìn)程分配延遲時(shí)間可以理解為任務(wù)響應(yīng)時(shí)間。

圖2 進(jìn)程分配時(shí)間延遲

4.1 測試環(huán)境

硬件平臺(tái)CPU為3G，內(nèi)存為512MB，軟件環(huán)境為redhat9.0，采用裁減的Linux2.6內(nèi)核以及基于裁減的Linux2.6進(jìn)行本文所述調(diào)度策略修改后的內(nèi)核，測試方法為PDLT方法，測試工具為Linux Trace ToolKit。

4.2 測試結(jié)果

通過LTT對裁減的Linux（嵌入式Linux）和基于裁減Linux按本文所述策略修改后的內(nèi)核進(jìn)行跟蹤測試，對比它們的任務(wù)響應(yīng)時(shí)間，前者為32ms，后者為407μs。測試結(jié)果表明，修改后的內(nèi)核在任務(wù)響應(yīng)方面有所改進(jìn)，較好的解決了嵌入式Linux在實(shí)時(shí)方面的不足。

5 結(jié)論

本文介紹了基本Linux內(nèi)核的調(diào)度策略，針對其缺乏有效的實(shí)時(shí)任務(wù)調(diào)度機(jī)制和調(diào)度算法而導(dǎo)致實(shí)時(shí)性效差的問題，提出了一種增加Linux內(nèi)核調(diào)度性能的調(diào)度算法和調(diào)度策略，經(jīng)測試，修改后的內(nèi)核在實(shí)時(shí)調(diào)度方面有所提高。

[1] 王長安.一種嵌入式Linux實(shí)時(shí)實(shí)現(xiàn)[J].科學(xué)技術(shù)與工程，2007(15):3940-3942.

[2] 姚君蘭.增強(qiáng)Linux內(nèi)核實(shí)時(shí)任務(wù)調(diào)度性能的研究[J].微計(jì)算機(jī)信息， 2006(5):42-44.

[3] 洪艷偉,賴娟,楊斌.其于EDF算法的可行性判定及實(shí)現(xiàn)[J].計(jì)算機(jī)技術(shù)與發(fā)展，2006(11):257-261.

[4] 王海珍,廉佐政.一種實(shí)時(shí)的嵌入式Linux調(diào)度策略[J].科學(xué)技術(shù)與工程，2009(14):4197-4201.

[5] 徐宗元.操作系統(tǒng)[M]. 北京：高等教育出版社,2005.

[6] 楊黎,楊琳芳.嵌入式Linux的實(shí)時(shí)性分析與研究[J].儀表技術(shù)，2009(7):58-61.

[7] 王新政,程小輝.實(shí)時(shí)操作系統(tǒng)任務(wù)調(diào)度策略策略的研究與設(shè)計(jì)[J].微計(jì)算機(jī)信息，2007(23):57-58.

[8] 李慶誠,顧健.嵌入式實(shí)時(shí)操作系統(tǒng)性能測試方法研究[J].單片機(jī)與嵌入式系統(tǒng)應(yīng)用，2005(8):19-21.