最早截止期優先調度算法的改進

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

（1.吉林大學 計算機科學與技術學院，長春 130012；2.吉林大學 公共外語教育學院，長春 130012）

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

1 非搶占式EDF算法

EDF算法中的分組是以到達時間和分組的延時之和來做參數插入隊列的，在EDF算法選擇分組調度時選擇到達時間和分組的延時之和最小的分組［1］。每一個服務流的QoS中都會有一個時延參數，假設這個參數為Tdelay，分組到達的時間為Tarrive，分組的截止時間為Tdeadline，有

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

非搶占式EDF算法實現了搶占次數的減少，但是卻無法保證最高優先級的服務流首先被服務，因此，本文改進EDF算法的主要方向就是在非搶占式EDF算法和搶占式EDF算法之間取得一個折中。

2 搶占式EDF算法

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

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

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

3 EDF算法的改進

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

由于在網絡應用中傳輸的服務流的類型具有多樣性，可以讓更多的因素來影響EDF算法調度的決策，例如，數據分組的重要性、數據包的剩余時間、數據包的緊迫程度等。在充分考慮分組截止時間的基礎上，綜合以上各種因素來實現新的EDF算法的改進［8］。改進的EDF算法主要涵蓋以下幾個方面：

（1）時間特性。原來的EDF算法對到來的分組插入隊列的處理都是以截止時間為參數，按照從小到大的順序把分組插入到隊列當中，調用時首先調用排在前面的分組。而在搶占式EDF中，因為可能存在被搶占的分組，所以可以考慮將分組剩余的要執行時間作為參數來選擇分組發送，剩余時間小的優先［9-10］。

（2）重要性特性。因為數據流的特性不同，在一種傳輸中可能有些信息比較重要，例如，控制信息、掉電信息等。如果一些比較重要的信息的截止時間大，則得不到優先服務，因此，有必要把信息的重要性也考慮到EDF算法調用中［11］。

（3）順序參考。嚴格來說，在一個時刻同時到達多個服務流的概率很小，但是可以把微小的一段時間到達的服務流分組看成是同一時間到達。所以到來的順序也可以作為EDF算法調度的一個參數之一［12］。

對于傳統的EDF算法的改進要從多方面考慮，綜合選擇參考因素，從以上3個方面可以把EDF算法調度的參數綜合為

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

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

（1）在半搶占式EDF算法中，新到的服務流分組根據被分配的試驗參數Tdelay以及該分組的到達時間Tarrive按照式（1）計算Tdeadline，根據分組中Tdeadline的大小，如果當前沒有正在處理的分組，則按照Tdeadline由小到大的順序將新到分組插入隊列當中。優先調用Tdeanline最小的分組，即最早達到截止期限的分組，該調度過程類似于非搶占式EDF算法，調度過程不發生搶占。

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

從半搶占式EDF算法的執行過程可以看出，通過在搶占之前對服務流分組做了一次比較，使得一部分按照搶占式EDF算法必然發生的搶占，因為重要性參數的比較而被拒絕搶占，在減少搶占次數的同時也保證了比較重要的服務流分組得到優先傳送。這里比較重要的數據流分組是指傳輸距離比較遠的服務流分組。在面對不同調度業務時，可根據業務流的特點，按照式（5）調整調度參數的計算方法。按照本文所支持的RTPS業務流調度方式對重要性參數的設置，可保證離BS較遠的SS站服務流分組的延時不會過長［13-14］。

4 實 驗

IEEE802.16協議是一種重要的第三代無線網絡接入標準，廣泛支持寬帶固定及移動無線接入系統，具有一定的代表性。因此本文基于IEEE802.16協議對改進后的半搶占式EDF算法進行了實驗［15］。

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

圖1中gedf.txt為改進后的EDF算法應用在調度RTPS服務流上的平均延時；nedf.txt為非搶占式的EDF算法應用在調度RTPS服務流上的平均延時；zedf.txt為搶占式EDF算法應用在調度服務流RTPS上的平均延時。

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

圖1 RTPS的平均延時Fig.1 Average delay of RTPS

5 結束語

通過改進基于最早截止時間優先調度算法（EDF），有效解決了EDF算法保證優先級較高的服務流優先調度和執行搶占算法占用系統資源較多的矛盾，實驗結果表明，改進后的半搶占EDF算法在調度RTPS服務時的平均延時較改進前的EDF算法有一定縮短，且占用的資源較搶占式EDF算法要少，在提高數據傳輸的實時性方面有一定的意義。

［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－hua，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層協議分析及QoS技術研究［D］.重慶：重慶大學通信工程學院，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］陳永銳，栗欣，樂正友.基于預留的802.16MAC層資源調度算法［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］.吉林大學學報：理學版，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.