一種改進(jìn)的進(jìn)程調(diào)度算法在機(jī)頂盒上的設(shè)計(jì)與實(shí)現(xiàn)

王銘偉, 呂華

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

0 引言

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

1 最小裕度算法的改進(jìn)與分析

1.1 最小裕度算法的改進(jìn)

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

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

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

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

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

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

圖2 改進(jìn)后的schedule流程圖

圖3 LSF改進(jìn)算法

1.2 搶占閾值的確定

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

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

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

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

根據(jù)上面的設(shè)計(jì)，本文對(duì)Linux 2.6算法在原來(lái)算法的基礎(chǔ)之上改進(jìn)，在下面兩個(gè)函數(shù)中進(jìn)行了修改。

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

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

3 驗(yàn)證與負(fù)面影響分析

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

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

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

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

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

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

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

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

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

表1 實(shí)驗(yàn)數(shù)據(jù)

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

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

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

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

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

3.3 改進(jìn)的負(fù)面影響

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

[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] 金宏，王強(qiáng)，王宏安，等.基于動(dòng)態(tài)搶占閾值的實(shí)時(shí)調(diào)度[J].計(jì)算機(jī)研究與發(fā)展，2004(3)：393-398.

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

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

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