王銘偉, 呂華

（重慶郵電大學 通信與信息系統(tǒng)學院 重慶 400065）

0 引言

目前，大多機頂盒系統(tǒng)使用的Linux2.6內(nèi)核中采用的是0（1）調(diào)度算法，此算法相對于Linux2.4核心的0（n）算法有了很大的改進。但由于在2.6內(nèi)核中，仍然使用源自2.4核心的SCHED_FIFO（先入先出）和SCHED_RR（時間片輪轉(zhuǎn)）作為對實時線程的調(diào)用的主要策略，對實時進程的調(diào)用效率上沒有大的提升。在0（1）調(diào)度算法中，由于任務的優(yōu)先級及搶占閾值都采用的是固定的整數(shù)[3]，并且等待任務的空閑時間遵循嚴格遞減的規(guī)律[4]，造成了在任務執(zhí)行過程中無法動態(tài)地分配CPU資源導致的實時性能降低?；谝陨显蛟S多嵌入式系統(tǒng)中的Linux都引入了最小裕度算法，以期能達到動態(tài)分配優(yōu)先級進而優(yōu)化Linux2.6核心的實時調(diào)度性能的目的。不過，最小裕度算法也存在問題，若有兩個優(yōu)先級相近的進程同時運行，會出現(xiàn)兩個線程間的頻繁切換現(xiàn)象[5]。針對這一最小裕度算法的缺點，本文通過對其增加二級優(yōu)先級進行了改進，使之能在一定程度下減小頻繁切換造成的系統(tǒng)資源浪費[6]，并通過將之運用到機頂盒產(chǎn)品中，證明了該算法對于增強機頂盒系統(tǒng)實時性能方面的有效性。

1 最小裕度算法的改進與分析

1.1 最小裕度算法的改進

作為實時系統(tǒng)中較為常用的動態(tài)優(yōu)先級調(diào)度算法，最小裕度優(yōu)先(Least Slack First)調(diào)度算法是對最早截止期優(yōu)先EDF算法的改進，根據(jù)任務所剩余的裕度（即剩余時間）的多少來分配優(yōu)先級。裕度越少，任務就越緊急，就為之分配更高的優(yōu)先級，以此保證緊急任務能夠得到優(yōu)先執(zhí)行。但是由于等待任務的裕度是嚴格隨時間遞減的，在系統(tǒng)執(zhí)行過程中，等待執(zhí)行的任務可能會由于緊急程度的提高而又搶占當前執(zhí)行的任務，從而造成兩個任務之間的頻繁切換（又稱為顛簸），使系統(tǒng)性能下降。通過引入搶占閾值的調(diào)度策略，控制不必要的任務搶占，可降低由于任務搶占引起的系統(tǒng)開銷和過多的上下文切換。需要注意的是過于復雜的調(diào)度算法也會消耗太多的系統(tǒng)資源，反而會降低系統(tǒng)的調(diào)度性能。在調(diào)度算法的開銷與系統(tǒng)的調(diào)度性能之間需要找到一個平衡點，為了找到這個平衡點，需要找到最合適的優(yōu)先級和搶占閾值。

設T時刻，X為任務剩余部分的執(zhí)行時間，截止期限(絕對)為G，則該任務的空閑時間(裕度)S定義如下：

在裕度相同時，G（截止期限）靠前的任務的優(yōu)先級高；當S≥0時任務才會被調(diào)度，否則進入下一個周期。這種算法存在一個問題：當系統(tǒng)中有1個以上(假設有3個，分別為T1、T2、T3)最小裕度相近或相等的任務，且系統(tǒng)中沒有比這3個任務裕度更小的任務了。由于正在執(zhí)行的任務裕度不變(假設為T1)，這時在等待隊列上等待的任務(T2、T3)的裕度隨著時間的推移而減小，從而使它們的優(yōu)先級動態(tài)地發(fā)生變化。隨著調(diào)度的執(zhí)行，T2（或T3）就會因裕度變得足夠小而搶占CPU。經(jīng)過任務切換后，同樣的道理，在T2（T3）執(zhí)行一段時間后，T3（或T2）也會搶占CPU，然后T1因裕度減小也會加入搶占的隊伍中，如此反復進行。這種頻繁的任務切換即稱為顛簸現(xiàn)象。如圖1就是3個任務下的顛簸現(xiàn)象。可見其中在完成這3個任務中，總共進行了多達10次切換。

圖1 LSF算法的顛簸現(xiàn)象

為了減少顛簸現(xiàn)象造成的系統(tǒng)資源浪費，本文對LSF算法進行了如下改進：每個任務除了按裕度分配優(yōu)先級外，還有一個搶占閾值，從而構(gòu)成一個雙優(yōu)先級系統(tǒng)。一旦任務得到CPU，其優(yōu)先級就提升到其搶占閾值的水平，直到它的執(zhí)行結(jié)束或被其他任務搶占后再回復到其原先的優(yōu)先級。設定任務的優(yōu)先級值越大，其優(yōu)先級越高，任務的搶占閾值大于其優(yōu)先級值。改進后的schedule（）函數(shù)的流程圖如圖2所示。

通過引入搶占閾值，可以有效地減少顛簸現(xiàn)象的發(fā)生?，F(xiàn)在還是假設有3個任務，分別為T1、T2、T3，它們的最小裕度相近或相等。T1的裕度(優(yōu)先級值)和搶占閾值分別為S1、P1，T2的裕度和搶占閾值S2、P2，T3的裕度和搶占閾值S3、P3。T1開始執(zhí)行，T2、T3則等待。隨著時間的推移，S2、S3不斷增大，S1保持不變。當S2（或S3）>S1時，并不進行搶占，而是讓T1繼續(xù)運行。直到S2（或S3）>P1時，T2（或T3）才可以搶占T1。于是，在前述3個任務的情況下，改進后的調(diào)度算法就減少了顛簸現(xiàn)象。3個任務下的模擬情況如圖3所示?？梢郧逦乜吹?，3個任務完成總共跳轉(zhuǎn)兩次，用時也大大減少。

圖2 改進后的schedule流程圖

圖3 LSF改進算法

1.2 搶占閾值的確定

這種改進的LSF算法的關鍵在于搶占閾值的確定,它直接影響到任務截止期的錯失率,也影響到任務切換的頻率,還影響到CPU的有效利用率。根據(jù)前面關于優(yōu)先值越大,任務的優(yōu)先級就越高的假設,任務的搶占閾值需要大于或等于（h≥p）相應的優(yōu)先級。如果 h≥≥pmax,則調(diào)度策略變?yōu)榉菗屨寄Ｐ?因此在新LSF算法中,搶占閾值的取值范圍為 p≤≤h≤≤pmax；在任務空閑時間不為0時,排除完全搶占和非搶占模式,則搶占閾值的取值范圍為p＜h＜pmax。由于任務的優(yōu)先級p是隨其空閑時間變化而變化的,因此,任務的搶占閾值不能事先確定(或者無條件預知),需要隨著任務優(yōu)先級值的變化而變化,因此,現(xiàn)有的關于搶占閾值的取值方法在這里都是不可行的。我們這里需要根據(jù)搶占閾值的取值范圍以及優(yōu)先級值確定閾值的計算公式,本文采用以下方法確定搶占閾值。

當pmax=0時, h = c e i l ( ? p ) ,其中比例系數(shù)0＜ ＜1為給定常數(shù),函數(shù)ceil( x)表示取大于x的最小的整數(shù).

此種方法較簡單，且能達到總體性能優(yōu)化的目的，避免了過于復雜的閾值計算。在確保改進可操作性與提高系統(tǒng)效能的角度來說是非常有利的。

2 改進后的最小裕度算法在機頂盒中的實現(xiàn)

根據(jù)上面的設計，本文對Linux 2.6算法在原來算法的基礎之上改進，在下面兩個函數(shù)中進行了修改。

首先，在schduler_tick函數(shù)中，需要更新當前線程的剩余執(zhí)行時間，而后更新實時線程的裕度值與實時線程優(yōu)先權范圍的部分，遍歷完成后需加回裕度值。具體代碼如下：

以上是在schduler_tick()函數(shù)中加入更新實時進程的裕度值與最低限度值，另外還有一些進程狀態(tài)信息，例如，裕度值、時間片、是否可以搶占等等，在更新這些狀態(tài)后，將檢測是否允許搶占，然后發(fā)生搶占，并檢測當前進程的時間片是否就位，并且確定截止點是否就位，如上述內(nèi)容到了，就剔除現(xiàn)進程，接著運行一個進程。這些交由schedule函數(shù)判斷執(zhí)行。

3 驗證與負面影響分析

3.1 調(diào)試環(huán)境

本方案的主要調(diào)試、開發(fā)等功能均是在宿主機上完成的（Linux環(huán)境PC或安裝了虛擬機的Windows PC）。開發(fā)和編譯時使用宿主機上的編譯工具來生成目標板（機頂盒實驗板）上的上運行的二進制代碼，然后通過打包，并將打好的升級包通過網(wǎng)線傳輸至目標板中燒包。在燒包成功后重啟即可對改進的系統(tǒng)進行驗證。驗證中，通過對串口的打印信息進行監(jiān)控和調(diào)試，也可通過串口通信程序輸入一些命令以測試我們的調(diào)度改進。調(diào)試環(huán)境如圖4所示。

圖4 調(diào)試環(huán)境

3.2 驗證結(jié)果及分析

在完成了代碼的整改后，分別對原版的最小裕度2.6.16內(nèi)核與改進了最小裕度優(yōu)先級算法的內(nèi)核進行了測試。測試中通過模擬兩個實時線程進入競態(tài)，并通過在schedule（）中添加調(diào)用打印函數(shù)，確定調(diào)用中的切換時間，線程運行時間等重要信息。具體實驗中使用了兩種線程，一種的CPU資源消耗較少，在原版的最小裕度內(nèi)核中只通過單優(yōu)先級判斷容易造成線程間切換；另一種線程的CPU資源消耗較多，在原版的最小裕度內(nèi)核中會出現(xiàn)多次切換的情況。通過兩種類型線程的不同組合，可以模擬出3種情況。

(1) 兩個或多個需要CPU資源較少的線程發(fā)生競態(tài)的情況。

(2) 兩個需要CPU資源較多的線程發(fā)生競態(tài)的情況。

(3) 一個需要CPU資源較多的與一個需要CPU資源較少的線程發(fā)生竟態(tài)的情況。

經(jīng)過3次實驗后得到了如表1所示的數(shù)據(jù)。

表1 實驗數(shù)據(jù)

通過對上面數(shù)據(jù)的分析，可以得出如下結(jié)果：

(1) 在兩個或多個需要CPU資源較少的線程發(fā)生競態(tài)的情況下，系統(tǒng)在完成兩個占用CPU資源并不多的兩個線程間仍然出現(xiàn)了一次線程的切換，在總的時間上相對于只作出了一次切換的改進后系統(tǒng)處于劣勢，較改進后的系統(tǒng)，在總時間上多了近10%。

(2) 兩個需要CPU資源較多的線程發(fā)生競態(tài)的情況下，由于采取兩重有限級判斷的策略，改進后的系統(tǒng)中切換次數(shù)較未改進之前有了較大的減少，在運行的總時間上站有很大的優(yōu)勢，較改進前的系統(tǒng)，在總時間上提高了近10%的效率。

(3) 一個需要CPU資源較多的與一個需要CPU資源較少的線程發(fā)生竟態(tài)的情況下，由于此情況下在所占資源較少的線程實行中只作出了一次多余的切換，在整個運行過程中，一次切換所占的時間比例很小，所以改進后的核心在此與原系統(tǒng)沒有太大出入。

通過以上的實驗，得到以下結(jié)論。通過在線程調(diào)度優(yōu)先級的計算中引入最小裕度算法，動態(tài)地獲得線程的優(yōu)先級，使得Linux 2.6的實時性得到了一定的提高，特別是在線程所需CPU資源較多和多線程的情況下對系統(tǒng)的提升較大，在這兩種情況下，平均能得到10%左右的性能提升。

3.3 改進的負面影響

在使用了動態(tài)的優(yōu)先級計算后，每次時鐘中斷都必須對實時任務的裕度值進行計算，而每次計算都必須遍歷整個實時任務鏈表。這在應用中必然加重對系統(tǒng)的負擔，但是由于機頂盒系統(tǒng)的實時線程并發(fā)量并不大，實時任務鏈表相對較小，此弊端并不會對系統(tǒng)造成較大的影響。相對于改進后對系統(tǒng)的提升來說，是可以接受的。

[1] Liu C L，Lay,J W.Scheduling algorithms for multiprograrrmaing in a hard real-time environment[J]. The Association for Computing Machinery，1973，20(1)：46-61.

[2] Hildebrandt J，Golatowski F，Timmermann D. Scheduling Coprocessor for Enhanced Least-Laxity-First Scheduling in Hard Real-Time Systems // Proc.of the llth Euromicro Conf.011. Real-Time Systems[M].Los Alamitos：IEEE Computer Society Press，2002：208-215.

[3] Jackson LE, Rouskas GN. Deterministic preemptive scheduling of real-time tasks[J]. Computer, 2002,35(1):72-79.

[4] Terrasa A，Garcia-Fomes A，Botti VJ.Flexible Real—Time Linux：A FIexible Hard Real-Time Environment[J].Real-Time Systems，2004，22(2)：151-173.

[5] 金宏，王強，王宏安，等.基于動態(tài)搶占閾值的實時調(diào)度[J].計算機研究與發(fā)展，2004(3)：393-398.

[6] 許占文，李歆. Linux2. 6 內(nèi)核的實時調(diào)度的研究與改進[J] . 沈陽工業(yè)大學學報,2006 (8) :4382441.

[7] 關斌斌，王勇 基于EDF算法的嵌入式Linux實時調(diào)度策略[J]. 電子測量，2010（3）：27-31.

[8] 王剛，余兆Linux 2.6內(nèi)核進程調(diào)度分析[J].計算機應用與軟件，2007，24(9)：162-164.