一種基于延遲的隊列調度實現

摘 要:PQBEDF算法是一種將優先級和時延相結合的動態優先級調度算法，具有快速高效的特點。對PQBEDF算法進行了研究，對其實現過程進行了改進，并給出了具體實現方法，同時對隊列長度和優先級之間的關系作了分析。改進后的算法簡化了操作，避免了PQBEDF算法中優先級可能相同的不合理現象，提高了算法的魯棒性。另外，改進后的算法在公平性上也有所提高，不僅滿足高優先級業務對帶寬和時延的要求，對低優先級業務也有一定的保障，為各業務提供既有一定保證又有所區別的服務，具有一定的公平性和合理性。

關鍵詞:PQBEDF算法; 時延; 隊列; 調度

中圖分類號:TP393 文獻標識碼:A

文章編號:1004-373X(2010)13-0073-03

Realization of Queue Scheduling Based on Delay

JIANG Wei-cheng

(Engineering Technical College， Chengdu University of Technology， Leshan 614000， China)

Abstract: PQBEDF(priority queue based on EDF) algorithm is a dynamic priority scheduling algorithm combined priority with time delay， and it is fast and efficient. PQBEDF algorithm is discussed， a new way of implementation process is improved， the relation between queue length and priority is analyzed. The improved algorithm simplifies the operation and avoids the phenomenon of priorities being identical in PQBEDF algorithm sometimes， the robustness of the algorithm is improved. Besides， the improved algorithm can guarantee the bandwidth and latency requirements not only for high-priority business but also for low-priority business to certain extent. It guarantees the quality of service for various different businesses， and is fair and reasonable.

Keywords: PQBEDF algorithm; time delay; queue; scheduling

0 引 言

隨著網絡技術的發展，各種新應用的出現，它們要求計算機網絡在帶寬和延時[1]等方面能提供一定的保證，特別是多媒體應用對網絡服務質量(QoS)[2-3]的需求更是與日俱增。優先級算法(PQ)[4]根據各業務對帶寬和延時的要求設置優先級，但PQ算法中優先級的設置是靜態的，不能滿足具體變化的需要，另外PQ算法中存在“餓死”現象，公平性差。EDF算法[5]是基于時延的調度算法，它根據任務的截止期(Deadline)大小對任務的優先級進行分配，但EDF算法中延時的計算復雜。文獻[6]提出了PQBEDF(Priority Queue Based on EDF)算法，基于EDF的思想，對分組的優先級進行設置。每過一個時間片，每一分組的優先級加1;每次挑選優先級最高的分組轉發。截止期是一個時間點，隨著時間的流逝而越來越靠近，進而優先級也隨時間的流逝而提高，這一點與EDF相吻合。

在PQBEDF算法中，初始優先級低的業務流因等待時間的增加，優先級提高而獲得服務，具有一定的公平性，但是如果出現大量這樣的分組，那么將使得初始優先級高的業務得不到相應的服務，延遲增加，帶寬得不到保證。此外，PQBEDF算法中要記錄每個分組的優先級，每次調度后還要對其優先級進行設置，也比較麻煩。為此，本文對PQBEDF算法進行了修改，提出PQBEDF_α算法。

1 PQBEDF_α算法

1.1 PQBEDF_α算法介紹

在PQBEDF_α算法中，為了處理的方便也按PQBEDF算法中的方式，采用等長的數據包[7-8]，各業務流按優先級的大小進入相應的隊列中等待調度。對于同一隊列中的分組，它們在隊列中存在一定的先后順序，并且在隊列中的等待時間也有一定聯系。只要記錄各分組的到達時間，再根據前一個分組的等待時間，就可以計算出后一個分組的等待時間，并由等待時間進而得出相應的優先級。這樣就不需要象PQBEDF算法那樣為每個分組動態設置優先級了。

在PQBEDF_α算法中，優先級的增加仍按PQBEDF算法的方式，分組在隊列中每過一個時間片，優先級增加1，由于優先級是通過計算得到的，因此只需設置隊頭分組的優先級就行了。此外還可將初始優先級設置成階梯值，如10，25，40等。這樣方便處理，同時也能防止優先級增加過快。

下面對一個隊列中的分組進行分析。如果分組i的到達時間用ai表示，等待時間用wi表示，假設各分組都恰好在每個時間片的開始時刻到達，且每個時間片只到達一個分組。那么不難得出如下關系式:

w2=w1-(a2-a1)

w3=w2-(a3-a2)

…

wn=wn-1-(an-an-1)

由w2+w3+…+wn可得:

wn=w1-(an-a1)

(1)

式中:a1為隊頭分組的到達時間。根據分組的等待時間和初始優先級，由算法可以得出分組的優先級。再假設隊頭分組的優先級用p1表示，那么可以得出分組n的優先級為:

pn=p1+wn=p1+ w1-(an-a1)

(2)

從式(2)可以得知，只要保留隊頭分組的到達時間a1和優先級w1，再根據各分組的到達時間，就可以得出隊列中每個分組的優先級。

一般地，分組并不是按上面假設的情況達到，而是隨意到達的。如果取分組到達時刻所在時間段的整數部分，如3.4和5.7時間片到達的分組，取它們到達的時間分別為3和5，那么在這種情況下，式(2)仍然成立。

下面來討論調度算法的具體實現。在系統中維持一個時鐘，用于對各分組的到達時間進行計時。數據流flowi中第j個分組的到達時間用aij表示，隊頭分組用ai1表示。那么flowi中第j個分組相對隊頭分組的等待時間之差為aij-ai1。再假設pi1表示隊頭分組的優先級，那么由式(2)可得隊列中任一分組的優先級pij為:

pij=pi1+ wi1-(aij-ai1)

其實在調度過程中并不需要計算每個分組的優先級，只需要比較各隊頭分組的優先級，找出最大的那個分組，就是將要發送的分組。此外還要保留該分組的到達時間和優先級，以便計算隊列中下一個分組的優先級。若發送分組后隊列為空，則置ai1為0，pi1為pi0，以便重新開始計算。

下面是算法實現的一個例子，其中pi0表示flowi的初始優先級。

pi1 =p i0(i=1，2，3， …，n)

For 每個時間片

選出最大的pi1

發送隊列i中的隊頭分組

If (隊列i為空)

ai1=0

pi1=pi0

Else

pi1 =pi1-(ai2-ai1)

For(j=1， j

If(i≠j)

pj1= pj1+1//調整其他隊頭分組的優先級

1.2 堆與動態優先級

下面討論如何進行查找和比較隊頭分組的優先級。為了便于節點刪除、插入等操作，將“堆”[9]用于優先級隊列是最合適的。由于在查找過程中，不僅與優先級的大小有關，而且也與分組所在的隊列編號有關，因此算法使用一種特殊的數據結構:雙單元堆。在一個雙單元堆中，每一個節點由兩個單元組成，第一個單元的內容為優先級，第二個單元的內容為該優先級所對應的隊列編號。

首先，按第一單元的內容采用堆排序的方式對隊列中的優先級進行建堆和排序，再由第二個單元的內容找到相應的隊列，選出隊頭分組進行發送。堆總是從堆頭刪除(最高優先級先得到服務)，如圖1中的“20”，且無論刪除或插入，其時間復雜度均只有O(log N)。

圖1 一個雙單元堆

1.3 隊列長度設置

隊列長度是一個十分重要的參數。隊列長度過短，將會導致分組大量溢出;隊列長度過長，又會導致低優先級隊列中積壓大量分組，這些分組隨等待時間的增加，優先級變得較高而使得初始優先級高的分組得不到相應的服務，出現PQBEDF算法中相同的問題。在PQBEDF_α算法中為了避免這種現象的發生，可以通過隊列長度的設置來解決。

隊列的長度設置為某一值，那么隊列中分組超過這一范圍時將被丟棄。當隊列因獲得服務而出現空余時，新到達的分組由于優先級較低，要獲得較高的優先級還需要較長的時間，這時高優先級業務流就可以獲得服務。另外，高優先級業務流的初始優先級本身就高，它們在隊列中的優先級也隨等待時間的增加而增加，從而使高優先級業務流獲得服務的機會要多得多。因此，只要將低優先級業務流的隊列長度設置為某一值，就可以將低優先級業務的服務次數控制在一定范圍內，進而控制其帶寬，使之不影響高優先級業務流的服務。

在PQBEDF_α算法中，隊列長度的設置，不僅可以達到丟棄分組，控制分組流入網絡中的流量，還與分組的等待時間有關系，影響分組的優先級。

1.4 算法性能分析

PQBEDF_α算法中，初始優先級低的業務流由于隨等待時間的增加，優先級增大而獲得一定的服務，但隊列的長度是一定的，超過某一范圍，分組將被丟棄。在獲得一定服務后，新到達的分組又將因優先級低而需等待較長時間才能獲得服務。對于高優先級業務，其初始優先級本身就高，并且它在隊列中也隨等待時間的增加而增加，不難看出，初始優先級高的業務流比初始優先級低的業務流的平均優先級要高得多。因此，其獲得服務的概率也就更大。PQBEDF_α算法從總體上保證了各業務流按初始優先級的大小獲得相應的服務。

網絡仿真軟件采用OPNET Modeler[10-11]。3個源節點的分組生成間隔都是constant(2.8)，進行仿真，結果如圖2所示。

圖2 仿真結果

sink_3表示的是初始優先級較高的業務流在一段時間內獲得的平均服務情況，sink_2表示的是初始優先級為中等的業務流在一段時間內獲得的平均服務情況，sink_1表示的是初始優先級較低的業務流在一段時間內獲得的平均服務情況。從仿真結果可以看出初始優先級高的業務流獲得的服務最多，初始優先級中等的業務流次之，初始優先級低的業務流最少，但還是獲得了一定的服務。仿真結果表明，PQBEDF_α算法不僅滿足高優先級業務流對帶寬和延時的要求，對低優先級業務流也有一定保障，各業務流按初始優先級的大小獲得相應比例的服務，具有良好的公平性。

2 結 語

在PQBEDF_α算法中，優先級的設置是通過對分組的等待時間計算而得到的，不需要在每次調度后對各分組的優先級動態調整，大大地簡化了優先級設置操作。同時，通過合理的隊列長度設置，避免了低優先級業務流中較多分組因等待時間的原因達到高優先級，使得高優先級業務流得不到相應的服務。此外，它還能保證各業務流按初始優先級的大小獲得相應的服務，具有較好的公平性和合理性。

參考文獻

[1]SHENKER S， PARTRIDGE C， GUERIN R. RFC2212 Specification of guaranteed quality of service[S/OL]. [ 2001-08-07] . http://China-pub.com.

[2]林闖.計算機網絡的服務質量[M].北京:清華大學出版社，2004.

[3]CHARIKAR M， NAOR J， SCHIEBER B. Resource optimization in QoS multicast routing of real-time multimedia[J]. IEEE/ACM Trans.on Networking，2004，12(2):340-348.

[4]KUROSE J F， ROSSK W.計算機網絡自頂向下方法與Internet特色[M].陳鳴，譯.北京:機械工業出版社，2005.

[5]BAKER T P. An analysis of EDF schedulability on a multiprocessor[J].IEEE Trans.on Parallel and Distributed Systems， 2005， 16(8): 760-768.

[6]錢光明.基于業務的多優先級隊列區別服務方案[J].計算機工程與應用，2006，42(10):118-120.

[7]MCKEOWN N. The iSLIP scheduling algorithm for input-queued switches[J]. IEEE/ACM Trans. on Networking，1999， 7(2): 188-201.

[8]MARSAN M A， BIANCO A， GIACCONE P， et al. Packet-mode scheduling in input-queued cell-based switches[J]. IEEE/ACM Trans.on Networking， 2002， 10(5): 666-678.

[9]梁田貴，張鵬.算法設計與分析[M].北京:冶金工業出版社，2004.

[10]陳敏.OPNET網絡仿真[M].北京:清華大學出版社，2002.

[11]OPNET Technologies Inc.. OPNET Modeler[M]. Version 80. Washington DC: OPNET Technologies Inc.， 2001.