基于累計(jì)價(jià)值的最小松弛度優(yōu)先算法

范凱胤，王學(xué)奇，譚小虎，胡陽光，石偉文

（空軍工程大學(xué)航空航天工程學(xué)院，西安 710038）

0 引言

現(xiàn)如今所有的網(wǎng)絡(luò)都滿足實(shí)時(shí)性，這就決定了實(shí)時(shí)調(diào)度被廣泛應(yīng)用在眾多的領(lǐng)域中，這些調(diào)度策略中常采用各種基于任務(wù)某個(gè)參數(shù)或特征的方法來群定任務(wù)的優(yōu)先級(jí)［1-3］。而在設(shè)計(jì)和實(shí)現(xiàn)實(shí)時(shí)軟件的過程中，搶占多任務(wù)是一個(gè)普遍使用的結(jié)構(gòu)，在滿足任務(wù)實(shí)時(shí)調(diào)度的同時(shí)，搶占多任務(wù)也帶來了CPU資源的浪費(fèi)和增加內(nèi)存的總開銷［4］。因此，在保證調(diào)度質(zhì)量的條件下，減少任務(wù)頻繁切換是選擇調(diào)度算法要考慮的。

最低松弛度優(yōu)先（Least Laxity First，LLF）［5］調(diào)度算法屬于動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法，也是一種截止時(shí)間驅(qū)動(dòng)的調(diào)度算法。根據(jù)任務(wù)松弛度的大小分配優(yōu)先級(jí)［6］，松弛度越小，優(yōu)先級(jí)越高，每次調(diào)度時(shí)都選取松弛度最小的任務(wù)來執(zhí)行。但是LLF在調(diào)度時(shí)會(huì)引起大量的任務(wù)切換，并且在有兩個(gè)任務(wù)的松弛度一樣的情況下會(huì)產(chǎn)生松弛環(huán)，造成系統(tǒng)死鎖。系統(tǒng)將在這兩個(gè)任務(wù)之間不停地切換直到松弛環(huán)解除。這些原因使得LLF算法并不實(shí)用，應(yīng)用較少。為此，文獻(xiàn)［7］針對(duì)LLF算法和HVDF（價(jià)值密度最大優(yōu)先）算法的缺陷，綜合了松弛度和價(jià)值密度這兩種調(diào)度考量指標(biāo)來設(shè)計(jì)優(yōu)先級(jí)分配策略，提出了LVDF算法；文獻(xiàn)［8］基于搶占閾值的思想，提出基于獎(jiǎng)賞因子的改進(jìn)最小松弛度算法，動(dòng)態(tài)地給每個(gè)任務(wù)配置搶占閾值。它們都在一定程度上改善了LLF算法的性能。

基于以上分析，本文通過將HVF（最大完成價(jià)值優(yōu)先）算法和LLF算法相結(jié)合的方式，提出基于累計(jì)價(jià)值的LLF算法，有效地減少LLF中不必要的切換，降低顛簸現(xiàn)象的發(fā)生。

1 基于累計(jì)價(jià)值的LLF算法

1.1 系統(tǒng)的可調(diào)度性

在一個(gè)實(shí)時(shí)系統(tǒng)中，需要調(diào)度的任務(wù)很多，如果處理器的處理能力不夠，就會(huì)導(dǎo)致很多實(shí)時(shí)任務(wù)不被處理或者延遲處理，從而給系統(tǒng)造成難以預(yù)料的后果。

在一個(gè)單處理器的系統(tǒng)中，如果系統(tǒng)包含m個(gè)周期性的硬實(shí)時(shí)任務(wù)，每個(gè)任務(wù)的執(zhí)行時(shí)間為Ci，周期時(shí)間為Ti，1≤i≤m，為保證所有的周期任務(wù)都可以得到實(shí)時(shí)調(diào)度，必須滿足下面的限制條件［9］。

在多處理器調(diào)度系統(tǒng)中，則要滿足下面的條件，該系統(tǒng)才可認(rèn)為是可調(diào)度的。

1.2 HVF算法

該算法是從為每個(gè)任務(wù)定義價(jià)值函數(shù)的角度出發(fā)，然后根據(jù)函數(shù)值確定任務(wù)的優(yōu)先等級(jí)并進(jìn)行排序，相應(yīng)價(jià)值函數(shù)大任務(wù)的優(yōu)先級(jí)就越高。和EDF算法一樣，HVF算法［10-11］在處理器資源有限的系統(tǒng)中的表現(xiàn)也是不如人意，同時(shí)在過載情況下，性能下降更加明顯。

在以價(jià)值函數(shù)的累計(jì)值來判定系統(tǒng)任務(wù)的優(yōu)先級(jí)，這就決定了價(jià)值函數(shù)的選取對(duì)算法性能的影響有著決定作用，這是該算法要解決的主要問題。

1.3 LLF算法松弛度的計(jì)算

LLF算法是根據(jù)任務(wù)的關(guān)鍵程度來賦予相應(yīng)的優(yōu)先級(jí)。其中用來衡量任務(wù)關(guān)鍵程度的一個(gè)重要指標(biāo)就是松弛度，記任務(wù)的松弛度為Li，當(dāng)前到達(dá)時(shí)間為Ri，任務(wù)的剩余執(zhí)行時(shí)間為Bi，則對(duì)于周期性任務(wù)i，假設(shè)在其到達(dá)之前或者介于第j個(gè)周期執(zhí)行完畢等待第j+1個(gè)周期到來的這段時(shí)間其松弛度為無窮大。而在j個(gè)周期的執(zhí)行過程中，任意時(shí)刻任務(wù)的松弛度為：

式中，Li（t）不能小于0，否則任務(wù)在截止期內(nèi)將無法完成調(diào)度，在每個(gè)周期的初始時(shí)刻任務(wù)的松弛度為：

在任務(wù)的調(diào)度過程中，每次都選擇松弛度最小的任務(wù)執(zhí)行。但是任務(wù)的松弛度會(huì)隨著執(zhí)行時(shí)間的增加而減小，當(dāng)某個(gè)任務(wù)的松弛度減小到比當(dāng)前處理器正在執(zhí)行任務(wù)的松弛度小時(shí)，任務(wù)必須進(jìn)行切換，轉(zhuǎn)而執(zhí)行該任務(wù)。

1.4 LLF算法的顛簸現(xiàn)象

為方便分析，定義任務(wù)的優(yōu)先級(jí)為p，任務(wù)的絕對(duì)截止期限為Di，任務(wù)的價(jià)值為v。假設(shè)任務(wù)的優(yōu)先級(jí)由松弛度單一決定，當(dāng)Li≥0時(shí)，任務(wù)才能被調(diào)度。當(dāng)系統(tǒng)中有3個(gè)空閑時(shí)間相近的任務(wù)、、，其初始狀態(tài)為：；；。由于任務(wù)的裕度最小，所以其得到最先執(zhí)行，同時(shí)在執(zhí)行過程中其裕度保持不變，這時(shí)任務(wù)處于等待狀態(tài)，伴隨的執(zhí)行，任務(wù)、的裕度不斷減少，也就是優(yōu)先級(jí)在增加。所以當(dāng)任務(wù)、的裕度小于任務(wù)時(shí)將發(fā)生一次搶占，由3個(gè)任務(wù)的初始狀態(tài)可得，任務(wù)被搶占，然后被搶占，這樣不斷循環(huán)，頻繁發(fā)生任務(wù)的切換，在3個(gè)任務(wù)都執(zhí)行完畢后，切換才會(huì)停止。圖1表示了3個(gè)任務(wù)由于裕度相近，在調(diào)度過程中產(chǎn)生了嚴(yán)重的顛簸現(xiàn)象。

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

2 LLF算法改進(jìn)

由以上的分析可以知道，對(duì)LLF算法的改進(jìn)是為了減少不必要的資源浪費(fèi)，但這樣也不能簡單地采用不可搶占的方式來實(shí)現(xiàn)，這是因?yàn)槿蝿?wù)的松弛度會(huì)隨著時(shí)間的進(jìn)行而減少，非搶占的方式容易使任務(wù)錯(cuò)過截至期。所以針對(duì)LLF算法的缺點(diǎn)以及非搶占模型的不足，為每個(gè)任務(wù)按松弛度大小分配一個(gè)優(yōu)先級(jí)的同時(shí)，還賦予一個(gè)動(dòng)態(tài)的累計(jì)價(jià)值，在松弛度相同的情況下，將任務(wù)的累計(jì)價(jià)值作為優(yōu)先級(jí)的比較對(duì)象。這樣就成為一個(gè)具有雙優(yōu)先級(jí)的評(píng)判方式。在任務(wù)按價(jià)值調(diào)整優(yōu)先級(jí)執(zhí)行完畢后，恢復(fù)原有的優(yōu)先級(jí)。假設(shè)一個(gè)實(shí)時(shí)任務(wù)i的優(yōu)先級(jí)是Pi，累計(jì)價(jià)值為 Vi，另一個(gè)任務(wù)j的優(yōu)先級(jí)為 Pj，累計(jì)價(jià)值為Vj，在以松弛度作為優(yōu)先級(jí)評(píng)定標(biāo)準(zhǔn)時(shí)，值越小相應(yīng)優(yōu)先級(jí)越高。任務(wù)剛進(jìn)入系統(tǒng)時(shí)，價(jià)值Vi=0，伴隨著任務(wù)的運(yùn)行，Vi的值都會(huì)有不同程度的增加，隨著任務(wù)越接近截止期，它所增加的價(jià)值也就越大，這樣被其他任務(wù)搶占的可能性就越小。繼續(xù)利用上面的例子進(jìn)行分析，任務(wù)最先得到執(zhí)行，伴隨著該任務(wù)的執(zhí)行，任務(wù)和的松弛度逐漸減小，那么相應(yīng)的優(yōu)先級(jí)P1和P2逐漸增大，當(dāng)P1＞P0或者 P2＞P0時(shí)，按照 LLF 算法，任務(wù)將發(fā)生切換，任務(wù)或者搶占執(zhí)行，經(jīng)過采用累計(jì)價(jià)值策略后，任務(wù)的優(yōu)先級(jí)已經(jīng)提升到V0的水平，這樣只有 V1＞V0或者 V2＞V0時(shí)，才可以搶占。但是隨著時(shí)間的運(yùn)行，任務(wù)的累計(jì)價(jià)值最大，這就導(dǎo)致任務(wù)和無法發(fā)生搶占，這樣3個(gè)任務(wù)就相繼執(zhí)行了，有效地減少了顛簸現(xiàn)象。具體的過程如圖2所示。

圖2 基于累計(jì)價(jià)值的LLF算法

相應(yīng)算法執(zhí)行流程如圖3所示。

2.1 算法可行性分析

圖3 算法執(zhí)行流程圖

那么就有

由以上分析可得任務(wù)Ai的最差相應(yīng)時(shí)間Ri為：

以上分析可知，改進(jìn)的LLF算法滿足調(diào)度所要求的調(diào)度準(zhǔn)則。最小松弛度算法是基于搶占閾值的搶占和非搶占模型的演化，但是可調(diào)度性較兩者好。在現(xiàn)實(shí)中要準(zhǔn)確判定任務(wù)的可調(diào)度性，還必須要考慮算法動(dòng)態(tài)特性和算法所帶來的顛簸問題以及一些不確定的內(nèi)在因素。

3 實(shí)驗(yàn)結(jié)果分析

采用傳統(tǒng)LLF算法和基于累計(jì)時(shí)間價(jià)值的LLF算法來測(cè)試下頁表1中任務(wù)的前后切換次數(shù)。對(duì)于價(jià)值函數(shù)，在任務(wù)首次進(jìn)入系統(tǒng)時(shí)，Vi=0，它的值隨著任務(wù)的每次執(zhí)行而有著不同程度的增加，越接近截至期任務(wù)的累計(jì)價(jià)值也就越大，這樣就可以防止任務(wù)被打斷，在實(shí)驗(yàn)中選擇價(jià)值函數(shù)為：

表1 受測(cè)任務(wù)集合

仿真結(jié)果如圖4所示，通過改進(jìn)LLF算法，可以相對(duì)減少任務(wù)間的搶占次數(shù)。很好地降低了處理器的開銷，節(jié)約CPU資源。從結(jié)果可以看出，對(duì)于周期較長的任務(wù)4和任務(wù)5在執(zhí)行過程中受到的搶占次數(shù)較多，所以隨著測(cè)試時(shí)間的增加，周期較長的任務(wù)執(zhí)行的次數(shù)就越多，被搶占的減少比率越接近25%。

圖4 原LLF算法和改進(jìn)的LLF算法搶占次數(shù)的比較

4 結(jié)論

本文通過對(duì)LLF算法的深入研究，針對(duì)其在實(shí)時(shí)任務(wù)裕度相近或相同情況下，存在任務(wù)間的頻繁搶占，一方面浪費(fèi)了處理器資源，一方面加大了開銷的問題，通過引入一個(gè)累計(jì)價(jià)值函數(shù)，構(gòu)成雙評(píng)價(jià)系統(tǒng)，在裕度相同情況下，采用價(jià)值來重新評(píng)定優(yōu)先級(jí)，判定是否搶占當(dāng)前執(zhí)行的任務(wù)，同時(shí)在執(zhí)行完成后又恢復(fù)原來優(yōu)先級(jí)的解決策略，來達(dá)到減少任務(wù)間頻繁的上下文切換，有效避免顛簸現(xiàn)象。仿真結(jié)果表明，這種方法有效減少了任務(wù)間不必要的切換，節(jié)約了CPU資源。

［1］張海濤，艾云峰.基于Petri網(wǎng)的分布式實(shí)時(shí)嵌入式系統(tǒng)的調(diào)度分析［J］.吉林大學(xué)學(xué)報(bào)，2007，37（3）：616-620.

［2］萬加富，李迪，葉峰，等.提高混合實(shí)時(shí)任務(wù)確定性的兩級(jí)調(diào)度算法［J］.吉林大學(xué)學(xué)報(bào)，2009，39（3）：753-758.

［3］張國斌，潘金貴.基于優(yōu)先級(jí)的搶占式并行調(diào)度算法設(shè)計(jì)與分析［J］.計(jì)算機(jī)科學(xué)，2007，34（7）：279-281.

［4］SAKSENA M，WANG Y.Scalable real-time system design using preemption thresholds［C］//Proceeding of the Twelfth IEEE Real-Time System Symposium.Orlando，NY：IEEE，2000：25-34.

［5］湯小丹，梁紅兵，哲鳳屏，等.計(jì)算機(jī)操作系統(tǒng)［M］.西安：西安電子科技大學(xué)出版社，2007.

［6］DERTOUZOS M L.Control Robotics：the procedural control of physical processes ［C］//IFIP Congress，Chicago，1974：807-813.

［7］高峰，呂廣申.CAN總線調(diào)度算法的改進(jìn)［J］.佳木斯大學(xué)學(xué)報(bào)，2011，29（2）：213-214.

［8］王斌，王遵彤.基于獎(jiǎng)賞因子的改進(jìn)最小松弛度算法［J］.電子測(cè)量技術(shù)，2011，34（10）：27-29.

［9］KRILHI R，JOHN A.Scheduling algorithms and operating systems support for real-timesystem ［J］.Proceeding of the IEEE，1994，83（1）：55-67.

［10］翟鴻鳴.單處理器系統(tǒng)的實(shí)時(shí)調(diào)度算法研究［J］.微機(jī)發(fā)展，2003，13（10）：99-101.

［11］李琦，巴巍.兩種改進(jìn)的EDF軟實(shí)時(shí)動(dòng)態(tài)調(diào)度算法［J］.計(jì)算機(jī)學(xué)報(bào)，2011，34（5）：943-950.