最早截止期優(yōu)先調(diào)度算法的改進(jìn)

程 禹，趙宏偉，龍曼麗，李玉翠

（1.吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，長(zhǎng)春 130012；2.吉林大學(xué) 公共外語教育學(xué)院，長(zhǎng)春 130012）

網(wǎng)絡(luò)服務(wù)質(zhì)量可以由許多參數(shù)來評(píng)定，這些參數(shù)主要包括網(wǎng)絡(luò)帶寬、網(wǎng)絡(luò)延時(shí)和延時(shí)抖動(dòng)等，其中網(wǎng)絡(luò)延時(shí)是評(píng)價(jià)一個(gè)網(wǎng)絡(luò)服務(wù)質(zhì)量的重要參數(shù)。很多應(yīng)用諸如視頻通話，在線直播等都需要良好的實(shí)時(shí)性支持，調(diào)度算法的使用能夠很好地保障多種網(wǎng)絡(luò)服務(wù)的實(shí)時(shí)性。EDF調(diào)度算法是一種基于最早截止時(shí)間優(yōu)先調(diào)度的算法，可以有效保證延時(shí)。在實(shí)際應(yīng)用中，EDF算法的調(diào)度分為搶占式的EDF算法和非搶占式的EDF算法。在非搶占式的EDF算法中，一段時(shí)間內(nèi)只能完成一個(gè)任務(wù)，在一個(gè)任務(wù)未完成之前不能調(diào)度其他任務(wù)執(zhí)行，這樣就無法保證動(dòng)態(tài)到來的分組對(duì)延時(shí)的要求。搶占式的EDF算法可以動(dòng)態(tài)地調(diào)用延時(shí)最小的分組，但是在搶占式EDF算法中，搶占會(huì)占用系統(tǒng)的許多資源，而且這些搶占對(duì)于嵌入式系統(tǒng)來說影響很大，是不可忽略的。本文主要針對(duì)以上EDF算法的優(yōu)缺點(diǎn)提出了一些改進(jìn)，并在IEEE8021.6d協(xié)議中驗(yàn)證了改進(jìn)后的EDF算法的優(yōu)越性。

1 非搶占式EDF算法

EDF算法中的分組是以到達(dá)時(shí)間和分組的延時(shí)之和來做參數(shù)插入隊(duì)列的，在EDF算法選擇分組調(diào)度時(shí)選擇到達(dá)時(shí)間和分組的延時(shí)之和最小的分組［1］。每一個(gè)服務(wù)流的QoS中都會(huì)有一個(gè)時(shí)延參數(shù)，假設(shè)這個(gè)參數(shù)為Tdelay，分組到達(dá)的時(shí)間為Tarrive，分組的截止時(shí)間為Tdeadline，有

非搶占式EDF算法比搶占式EDF調(diào)度算法的復(fù)雜度低。非搶占式EDF調(diào)度算法在單一的處理器中，只要開始調(diào)度一個(gè)任務(wù)，則在這個(gè)任務(wù)執(zhí)行完畢之前不能被其他的任務(wù)搶占。這種調(diào)度方式使得搶占的次數(shù)為零，直到任務(wù)執(zhí)行完畢才進(jìn)行線程的轉(zhuǎn)換，所以相對(duì)于搶占式EDF算法來說，這種非搶占式EDF算法的運(yùn)作系統(tǒng)資源消耗比較少。但是，由于非搶占式EDF算法一次只能執(zhí)行一個(gè)任務(wù)，并且直到這個(gè)任務(wù)執(zhí)行完才能調(diào)度下一個(gè)任務(wù)，因此不能保證隨時(shí)到來的最高優(yōu)先級(jí)的分組最先被調(diào)度。本文的EDF算法應(yīng)用的對(duì)象為調(diào)度IEEE802.16d協(xié)議中的RTPS服務(wù)流，RTPS服務(wù)流是一種周期性的服務(wù)流，本文討論的非搶占式EDF算法的可調(diào)度性主要基于服務(wù)流的截止時(shí)間等于周期，對(duì)截止時(shí)間小于周期的服務(wù)流不做詳細(xì)的討論［2］?；诜?wù)流的截止時(shí)間等于周期這個(gè)假設(shè)條件，非搶占式EDF算法的可調(diào)度性的充分必要條件是：假設(shè)一個(gè)任務(wù)集有n個(gè)任務(wù)，ei是任務(wù)i的最壞執(zhí)行時(shí)間，pi是任務(wù)i的執(zhí)行周期，任務(wù)是按照周期非遞減的方式排列的。如果下面兩式成立，則說明任務(wù)i在非搶占式EDF方式下的調(diào)度是允許的［3］。

非搶占式EDF算法實(shí)現(xiàn)了搶占次數(shù)的減少，但是卻無法保證最高優(yōu)先級(jí)的服務(wù)流首先被服務(wù)，因此，本文改進(jìn)EDF算法的主要方向就是在非搶占式EDF算法和搶占式EDF算法之間取得一個(gè)折中。

2 搶占式EDF算法

搶占式EDF算法的運(yùn)作也是基于一些理想的假設(shè)條件，例如搶占時(shí)搶占的代價(jià)是可以忽略不計(jì)的。在這種理想的運(yùn)行狀況下，搶占式EDF算法是單一處理器調(diào)度算法中最優(yōu)的調(diào)度算法。但是，在實(shí)際的實(shí)時(shí)處理器系統(tǒng)中，該算法運(yùn)行的效果比理想的狀況下差很多。特別是對(duì)一些系統(tǒng)資源比較緊張的實(shí)時(shí)系統(tǒng)來說，系統(tǒng)資源尤其珍貴，搶占式EDF算法發(fā)生搶占時(shí)所占用的資源是無法忽略不計(jì)的，在這種情況下，搶占資源占用系統(tǒng)資源比例大，可能會(huì)影響系統(tǒng)的性能，降低系統(tǒng)的運(yùn)行速率。因此，搶占式EDF算法能夠調(diào)度的條件是與系統(tǒng)的處理器的利用率有關(guān)的，要視運(yùn)行搶占式EDF算法時(shí)所用資源占系統(tǒng)資源的比例多少而定［4］。

搶占式EDF算法是根據(jù)數(shù)據(jù)流的最小延時(shí)來排列分組的，具體的計(jì)算方式如式（1）所示。每次都是調(diào)用Tdeadline最小的分組n發(fā)送，當(dāng)在發(fā)送過程中有新的分組j到來時(shí)，一樣按式（1）計(jì)算Tdeadline，如果新來的服務(wù)流j的Tdeadline小于正在發(fā)送的分組n的Tdeadline，則發(fā)生搶占，這也就是所謂的動(dòng)態(tài)優(yōu)先級(jí)調(diào)度。這樣EDF算法才能保證在數(shù)據(jù)流分組的截止日期到來之前發(fā)送該數(shù)據(jù)流。對(duì)于可調(diào)度的周期性任務(wù)來說，搶占式EDF算法的可調(diào)度性應(yīng)該滿足：式中：n為任務(wù)集中所有的任務(wù)個(gè)數(shù)［5］。

式（4）是搶占式EDF算法可調(diào)度性的充分必要條件。從式（4）可以看出，只要所有任務(wù)的執(zhí)行時(shí)間之和不大于所有周期時(shí)間之和，即處理器的利用率不超過百分之百，則搶占式EDF算法就是可調(diào)度的［6］。因此，搶占式EDF算法可以很好地滿足服務(wù)流的延時(shí)需要，保證實(shí)時(shí)系統(tǒng)的正常運(yùn)行。但是其搶占時(shí)所耗費(fèi)的時(shí)間和資源也是不可忽視的，特別是在資源緊張的實(shí)時(shí)系統(tǒng)中，所以對(duì)于搶占式EDF算法要改進(jìn)，必須從搶占時(shí)所消耗的系統(tǒng)資源來入手。

3 EDF算法的改進(jìn)

在搶占式EDF算法中，系統(tǒng)資源的利用率很高，而且能保證高優(yōu)先級(jí)的服務(wù)流分組得到最先發(fā)送，但是如果實(shí)時(shí)系統(tǒng)使用搶占EDF算法時(shí)，發(fā)生搶占的次數(shù)太頻繁，這樣的消耗對(duì)實(shí)時(shí)系統(tǒng)來說又是很難承受的［7］。非搶占式EDF算法沒有搶占式EDF算法對(duì)系統(tǒng)資源的消耗大，但同時(shí)也無法保證高優(yōu)先級(jí)的服務(wù)流分組的最先發(fā)送。所以對(duì)EDF算法的改進(jìn)主要從這兩個(gè)方面綜合考慮。原算法的分組是按截止時(shí)間從小到大的順序排隊(duì)，改進(jìn)后考慮服務(wù)流的其他特性，從不同的方面更詳細(xì)地描述服務(wù)流分組的調(diào)度方式，把服務(wù)流的各種特性應(yīng)用到EDF算法的調(diào)度中去，既使得在服務(wù)流分組中的高優(yōu)先級(jí)服務(wù)流優(yōu)先得到服務(wù)，同時(shí)又要對(duì)系統(tǒng)的資源消耗有所降低。

由于在網(wǎng)絡(luò)應(yīng)用中傳輸?shù)姆?wù)流的類型具有多樣性，可以讓更多的因素來影響EDF算法調(diào)度的決策，例如，數(shù)據(jù)分組的重要性、數(shù)據(jù)包的剩余時(shí)間、數(shù)據(jù)包的緊迫程度等。在充分考慮分組截止時(shí)間的基礎(chǔ)上，綜合以上各種因素來實(shí)現(xiàn)新的EDF算法的改進(jìn)［8］。改進(jìn)的EDF算法主要涵蓋以下幾個(gè)方面：

（1）時(shí)間特性。原來的EDF算法對(duì)到來的分組插入隊(duì)列的處理都是以截止時(shí)間為參數(shù)，按照從小到大的順序把分組插入到隊(duì)列當(dāng)中，調(diào)用時(shí)首先調(diào)用排在前面的分組。而在搶占式EDF中，因?yàn)榭赡艽嬖诒粨屨嫉姆纸M，所以可以考慮將分組剩余的要執(zhí)行時(shí)間作為參數(shù)來選擇分組發(fā)送，剩余時(shí)間小的優(yōu)先［9-10］。

（2）重要性特性。因?yàn)閿?shù)據(jù)流的特性不同，在一種傳輸中可能有些信息比較重要，例如，控制信息、掉電信息等。如果一些比較重要的信息的截止時(shí)間大，則得不到優(yōu)先服務(wù)，因此，有必要把信息的重要性也考慮到EDF算法調(diào)用中［11］。

（3）順序參考。嚴(yán)格來說，在一個(gè)時(shí)刻同時(shí)到達(dá)多個(gè)服務(wù)流的概率很小，但是可以把微小的一段時(shí)間到達(dá)的服務(wù)流分組看成是同一時(shí)間到達(dá)。所以到來的順序也可以作為EDF算法調(diào)度的一個(gè)參數(shù)之一［12］。

對(duì)于傳統(tǒng)的EDF算法的改進(jìn)要從多方面考慮，綜合選擇參考因素，從以上3個(gè)方面可以把EDF算法調(diào)度的參數(shù)綜合為

本文根據(jù)所調(diào)度服務(wù)流的特性，也對(duì)EDF算法進(jìn)行了合適的改動(dòng)。在本文應(yīng)用IEEE802.16d協(xié)議覆蓋的測(cè)試網(wǎng)絡(luò)中，各個(gè)SS站和BS站之間傳送的數(shù)據(jù)服務(wù)流類型幾乎都是一樣的。傳送主要是以MEPG視頻信息為主，但是每個(gè)SS站和BS站相距的距離是不同的，所以每個(gè)服務(wù)流分組的QoS（服務(wù)質(zhì)量保證）參數(shù)中的延時(shí)項(xiàng)可能設(shè)置相同，但是其傳送的距離是各不相同的。因此，可以把BS站和SS站之間的傳輸距離作為EDF算法調(diào)度的一個(gè)參數(shù)。距離越遠(yuǎn)的服務(wù)流分組，其重要性越大。這樣就可以把分組簡(jiǎn)化為

調(diào)度參數(shù)＝重要性／截止期限 （6）式（6）中的重要性是根據(jù)BS站和SS站之間的距離來確定的，距離越遠(yuǎn)的數(shù)據(jù)流分組越重要。這樣在改進(jìn)的EDF算法中，參與調(diào)度的有兩個(gè)參數(shù)。改進(jìn)后的EDF算法稱為半搶占式EDF算法。半搶占式EDF算法的具體操作過程如下。

（1）在半搶占式EDF算法中，新到的服務(wù)流分組根據(jù)被分配的試驗(yàn)參數(shù)Tdelay以及該分組的到達(dá)時(shí)間Tarrive按照式（1）計(jì)算Tdeadline，根據(jù)分組中Tdeadline的大小，如果當(dāng)前沒有正在處理的分組，則按照Tdeadline由小到大的順序?qū)⑿碌椒纸M插入隊(duì)列當(dāng)中。優(yōu)先調(diào)用Tdeanline最小的分組，即最早達(dá)到截止期限的分組，該調(diào)度過程類似于非搶占式EDF算法，調(diào)度過程不發(fā)生搶占。

（2）如果在一個(gè)分組i處理的過程中，新到來一個(gè)服務(wù)流分組j，則首先計(jì)算服務(wù)流分組j的，比較和的大小，如果≥，則把服務(wù)流分組j按的順序插入隊(duì)列。如果＜區(qū)別于搶占式EDF調(diào)度算法立刻發(fā)生搶占的調(diào)度方式，增加一步根據(jù)重要性對(duì)是否搶占進(jìn)行的二次判斷，即在分組當(dāng)中，根據(jù)目標(biāo)BS站和SS站之間的距離來設(shè)置重要性這個(gè)參數(shù)的值V，按照式（6）分別計(jì)算服務(wù)流分組i和j的調(diào)度參數(shù)，再次比較服務(wù)流分組j的重要性參數(shù)Vj和服務(wù)流分組i的重要性參數(shù)Vi的值的大小。如果Vj＞Vi，則服務(wù)流分組j搶占服務(wù)流分組i，否則，把服務(wù)流分組j按Tjdeadline的值插入隊(duì)列，等待當(dāng)前正在處理的服務(wù)流i完成后執(zhí)行。

從半搶占式EDF算法的執(zhí)行過程可以看出，通過在搶占之前對(duì)服務(wù)流分組做了一次比較，使得一部分按照搶占式EDF算法必然發(fā)生的搶占，因?yàn)橹匾詤?shù)的比較而被拒絕搶占，在減少搶占次數(shù)的同時(shí)也保證了比較重要的服務(wù)流分組得到優(yōu)先傳送。這里比較重要的數(shù)據(jù)流分組是指?jìng)鬏斁嚯x比較遠(yuǎn)的服務(wù)流分組。在面對(duì)不同調(diào)度業(yè)務(wù)時(shí)，可根據(jù)業(yè)務(wù)流的特點(diǎn)，按照式（5）調(diào)整調(diào)度參數(shù)的計(jì)算方法。按照本文所支持的RTPS業(yè)務(wù)流調(diào)度方式對(duì)重要性參數(shù)的設(shè)置，可保證離BS較遠(yuǎn)的SS站服務(wù)流分組的延時(shí)不會(huì)過長(zhǎng)［13-14］。

4 實(shí) 驗(yàn)

IEEE802.16協(xié)議是一種重要的第三代無線網(wǎng)絡(luò)接入標(biāo)準(zhǔn)，廣泛支持寬帶固定及移動(dòng)無線接入系統(tǒng)，具有一定的代表性。因此本文基于IEEE802.16協(xié)議對(duì)改進(jìn)后的半搶占式EDF算法進(jìn)行了實(shí)驗(yàn)［15］。

在IEEE802.16中有4種不同的服務(wù)流，UGS、RTPS、NRTPS和BE服務(wù)流，每種服務(wù)流都有自己的Qos參數(shù)和特點(diǎn)，根據(jù)不同的服務(wù)流特點(diǎn)可以選擇不同的調(diào)度方法來滿足每種服務(wù)流的Qos參數(shù)的要求。RTPS服務(wù)流是一種周期性的、傳送速率可變的服務(wù)流，并且要求的延時(shí)性特別高。為此本文為RTPS服務(wù)流使用了改進(jìn)后的EDF算法來調(diào)度。具體的實(shí)驗(yàn)結(jié)果如圖1所示。

圖1中g(shù)edf.txt為改進(jìn)后的EDF算法應(yīng)用在調(diào)度RTPS服務(wù)流上的平均延時(shí)；nedf.txt為非搶占式的EDF算法應(yīng)用在調(diào)度RTPS服務(wù)流上的平均延時(shí)；zedf.txt為搶占式EDF算法應(yīng)用在調(diào)度服務(wù)流RTPS上的平均延時(shí)。

在仿真實(shí)驗(yàn)的對(duì)比結(jié)果中，改進(jìn)后的半搶占式EDF算法延時(shí)為0.31～0.33μs，而非搶占式EDF算法的延時(shí)為0.21～0.7μs，未改進(jìn)的搶占式EDF算法延時(shí)在0.24μs至0.67μs之間，搶占式EDF算法平均延時(shí)要略小于非搶占式EDF算法，而改進(jìn)后的半搶占式EDF算法平均延時(shí)要遠(yuǎn)小于前兩者，且從仿真結(jié)果看，改進(jìn)后的半搶占式EDF算法延時(shí)隨數(shù)據(jù)傳輸變化很小，基本維持在0.32μs。

圖1 RTPS的平均延時(shí)Fig.1 Average delay of RTPS

5 結(jié)束語

通過改進(jìn)基于最早截止時(shí)間優(yōu)先調(diào)度算法（EDF），有效解決了EDF算法保證優(yōu)先級(jí)較高的服務(wù)流優(yōu)先調(diào)度和執(zhí)行搶占算法占用系統(tǒng)資源較多的矛盾，實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的半搶占EDF算法在調(diào)度RTPS服務(wù)時(shí)的平均延時(shí)較改進(jìn)前的EDF算法有一定縮短，且占用的資源較搶占式EDF算法要少，在提高數(shù)據(jù)傳輸?shù)膶?shí)時(shí)性方面有一定的意義。

［1］IEEE P802.16H／D10－2009.IEEE standard for local and metropolitan area networks Part 16：air interface for fixed broadband wireless access systems［S］.

［2］Chen Jian－feng，Jiao Wen－h(huán)ua，Wang Hong－xi.A service flow management strategy for IEEE 802.16 broadband wireless access systems in TDD mode［C］∥2005IEEE International Conference on Communications.Seoul，Kerea：Institute of Electrical and E－lectronics Engineers Inc，2005.

［3］Ng T S E，Stoica Ion，Zhang Hui.Packet fair queueing algorithms for wireless networks with location－dependent errors［C］∥ Proceedings of the 199817th Annual IEEE Conference on Computer Communications，INFOCOM.Part 1 （of 3）.San Francisco，CA，USA：IEEE，Piscataway，NJ，U－nited States，1998.

［4］Sayenko Alexander，Alanen Olli，Karhula Juha，et al.Ensuring the QoS requirements in 802.16scheduling［C］∥Proceedings of the 9th ACM Symposium on Modeling，Analysis and Simulation of Wireless and Mobile Systems.Malaga，Spain：Association for Computing Machinery，2006.

［5］胡軍.基于IEEE802.16的 MAC層協(xié)議分析及QoS技術(shù)研究［D］.重慶：重慶大學(xué)通信工程學(xué)院，2008.Hu Jun.MAC protocol analysis and QoS technology research based on IEEE802.16［D］.Chongqing：Collage of Communication Engineering，Chongqing U－niversity，2008.

［6］陳永銳，栗欣，樂正友.基于預(yù)留的802.16MAC層資源調(diào)度算法［J］.微電子學(xué)與計(jì)算機(jī)，2008，25（1）：62－65.Chen Yong－rui，Li Xin，Le Zheng－you.A fair scheduling algorithm based on resource reservation［J］.Micro Electronics ＆ Computer，2008，25（1）：62－65.

［7］Zhang Gang，Liu Chun－gui，Wang Feng，et al.Quality of service scheduling based on GPSS in IEEE 802.16WiMax networks［C］∥2008International Conference on Wireless Communications，Networking and Mobile Computing，WiCOM 2008，Dalian，China，2008.

［8］Gakhar Kamal，Achir Mounir，Gravey Annie.Dynamic resource reservation in IEEE 802.16broadband wireless networks［C］∥2006Fourteenth International Workshop on Quality of Service，IWQoS 2006.New Haven，CT，United States：Institute of Electrical and Electronics Engineers Inc，2006.

［9］Wongthavarawat Kitti，Ganz Aura.Packet scheduling for QoS support in IEEE 802.16broadbandwireless access systems［J］.International Journal of Communication Systems，2003，16：81－96.

［10］Dusit Niyato，Ekram Hossain.QoS－aware bandwidth allocation and admission control in IEEE 802.16broadband wireless access networks：A non－cooperative game theoretic approach［J］.Computer Networks，2007，51（11）：3305－3321.

［11］Cristian Vasar，Octavian Prostean，Ioan Filip，et al.Markov models for wireless sensor network reliability［C］∥2009IEEE 5th International Conference on Intelligent Computer Communication and Processing.Cluj－Napoca，Romania：IEEE Computer Society，2009.

［12］Cristian Vasar，Octavian Prostean，Ioan Filip，et al.A reliability analysis for wireless sensor networks in a wind farm［C］∥22nd International Symposium on Information，Communication and Automation Technologies，Sarajevo，Bosnia and Herzegovina：IEEE Computer Society，2009.

［13］Chen Yun－xia，Zhao Qing.On the lifetime of wireless sensor networks［J］.IEEE Communications Letters，2005，9（11）：976－978.

［14］Roberto Verdone，Chiara Buratti.Modelling for wireless sensor network protocol design［C］∥Wreless AD－HOC Networks.International Workshop.King＇s College London，UK：Curran Associates，Inc，2005.

［15］闞君滿，秦俊，趙宏偉，等.基于累計(jì)價(jià)值的最早最終截止期優(yōu)先調(diào)度策略［J］.吉林大學(xué)學(xué)報(bào)：理學(xué)版，2012，50（2）：315－319.Kan Jun－man，Qin Jun，Zhao Hong－wei，et al.First priority schedule strategy based on accumulated value earliest deadline［J］.Journal of Jilin University（Science Edition），2012，50（2）：315－319.