摘 要:PQBEDF算法是一種將優(yōu)先級(jí)和時(shí)延相結(jié)合的動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法，具有快速高效的特點(diǎn)。對(duì)PQBEDF算法進(jìn)行了研究，對(duì)其實(shí)現(xiàn)過程進(jìn)行了改進(jìn)，并給出了具體實(shí)現(xiàn)方法，同時(shí)對(duì)隊(duì)列長(zhǎng)度和優(yōu)先級(jí)之間的關(guān)系作了分析。改進(jìn)后的算法簡(jiǎn)化了操作，避免了PQBEDF算法中優(yōu)先級(jí)可能相同的不合理現(xiàn)象，提高了算法的魯棒性。另外，改進(jìn)后的算法在公平性上也有所提高，不僅滿足高優(yōu)先級(jí)業(yè)務(wù)對(duì)帶寬和時(shí)延的要求，對(duì)低優(yōu)先級(jí)業(yè)務(wù)也有一定的保障，為各業(yè)務(wù)提供既有一定保證又有所區(qū)別的服務(wù)，具有一定的公平性和合理性。

關(guān)鍵詞:PQBEDF算法; 時(shí)延; 隊(duì)列; 調(diào)度

中圖分類號(hào):TP393 文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):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 引 言

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

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

1 PQBEDF_α算法

1.1 PQBEDF_α算法介紹

在PQBEDF_α算法中，為了處理的方便也按PQBEDF算法中的方式，采用等長(zhǎng)的數(shù)據(jù)包[7-8]，各業(yè)務(wù)流按優(yōu)先級(jí)的大小進(jìn)入相應(yīng)的隊(duì)列中等待調(diào)度。對(duì)于同一隊(duì)列中的分組，它們?cè)陉?duì)列中存在一定的先后順序，并且在隊(duì)列中的等待時(shí)間也有一定聯(lián)系。只要記錄各分組的到達(dá)時(shí)間，再根據(jù)前一個(gè)分組的等待時(shí)間，就可以計(jì)算出后一個(gè)分組的等待時(shí)間，并由等待時(shí)間進(jìn)而得出相應(yīng)的優(yōu)先級(jí)。這樣就不需要象PQBEDF算法那樣為每個(gè)分組動(dòng)態(tài)設(shè)置優(yōu)先級(jí)了。

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

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

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為隊(duì)頭分組的到達(dá)時(shí)間。根據(jù)分組的等待時(shí)間和初始優(yōu)先級(jí)，由算法可以得出分組的優(yōu)先級(jí)。再假設(shè)隊(duì)頭分組的優(yōu)先級(jí)用p1表示，那么可以得出分組n的優(yōu)先級(jí)為:

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

(2)

從式(2)可以得知，只要保留隊(duì)頭分組的到達(dá)時(shí)間a1和優(yōu)先級(jí)w1，再根據(jù)各分組的到達(dá)時(shí)間，就可以得出隊(duì)列中每個(gè)分組的優(yōu)先級(jí)。

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

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

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

其實(shí)在調(diào)度過程中并不需要計(jì)算每個(gè)分組的優(yōu)先級(jí)，只需要比較各隊(duì)頭分組的優(yōu)先級(jí)，找出最大的那個(gè)分組，就是將要發(fā)送的分組。此外還要保留該分組的到達(dá)時(shí)間和優(yōu)先級(jí)，以便計(jì)算隊(duì)列中下一個(gè)分組的優(yōu)先級(jí)。若發(fā)送分組后隊(duì)列為空，則置ai1為0，pi1為pi0，以便重新開始計(jì)算。

下面是算法實(shí)現(xiàn)的一個(gè)例子，其中pi0表示flowi的初始優(yōu)先級(jí)。

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

For 每個(gè)時(shí)間片

選出最大的pi1

發(fā)送隊(duì)列i中的隊(duì)頭分組

If (隊(duì)列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//調(diào)整其他隊(duì)頭分組的優(yōu)先級(jí)

1.2 堆與動(dòng)態(tài)優(yōu)先級(jí)

下面討論如何進(jìn)行查找和比較隊(duì)頭分組的優(yōu)先級(jí)。為了便于節(jié)點(diǎn)刪除、插入等操作，將“堆”[9]用于優(yōu)先級(jí)隊(duì)列是最合適的。由于在查找過程中，不僅與優(yōu)先級(jí)的大小有關(guān)，而且也與分組所在的隊(duì)列編號(hào)有關(guān)，因此算法使用一種特殊的數(shù)據(jù)結(jié)構(gòu):雙單元堆。在一個(gè)雙單元堆中，每一個(gè)節(jié)點(diǎn)由兩個(gè)單元組成，第一個(gè)單元的內(nèi)容為優(yōu)先級(jí)，第二個(gè)單元的內(nèi)容為該優(yōu)先級(jí)所對(duì)應(yīng)的隊(duì)列編號(hào)。

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

圖1 一個(gè)雙單元堆

1.3 隊(duì)列長(zhǎng)度設(shè)置

隊(duì)列長(zhǎng)度是一個(gè)十分重要的參數(shù)。隊(duì)列長(zhǎng)度過短，將會(huì)導(dǎo)致分組大量溢出;隊(duì)列長(zhǎng)度過長(zhǎng)，又會(huì)導(dǎo)致低優(yōu)先級(jí)隊(duì)列中積壓大量分組，這些分組隨等待時(shí)間的增加，優(yōu)先級(jí)變得較高而使得初始優(yōu)先級(jí)高的分組得不到相應(yīng)的服務(wù)，出現(xiàn)PQBEDF算法中相同的問題。在PQBEDF_α算法中為了避免這種現(xiàn)象的發(fā)生，可以通過隊(duì)列長(zhǎng)度的設(shè)置來解決。

隊(duì)列的長(zhǎng)度設(shè)置為某一值，那么隊(duì)列中分組超過這一范圍時(shí)將被丟棄。當(dāng)隊(duì)列因獲得服務(wù)而出現(xiàn)空余時(shí)，新到達(dá)的分組由于優(yōu)先級(jí)較低，要獲得較高的優(yōu)先級(jí)還需要較長(zhǎng)的時(shí)間，這時(shí)高優(yōu)先級(jí)業(yè)務(wù)流就可以獲得服務(wù)。另外，高優(yōu)先級(jí)業(yè)務(wù)流的初始優(yōu)先級(jí)本身就高，它們?cè)陉?duì)列中的優(yōu)先級(jí)也隨等待時(shí)間的增加而增加，從而使高優(yōu)先級(jí)業(yè)務(wù)流獲得服務(wù)的機(jī)會(huì)要多得多。因此，只要將低優(yōu)先級(jí)業(yè)務(wù)流的隊(duì)列長(zhǎng)度設(shè)置為某一值，就可以將低優(yōu)先級(jí)業(yè)務(wù)的服務(wù)次數(shù)控制在一定范圍內(nèi)，進(jìn)而控制其帶寬，使之不影響高優(yōu)先級(jí)業(yè)務(wù)流的服務(wù)。

在PQBEDF_α算法中，隊(duì)列長(zhǎng)度的設(shè)置，不僅可以達(dá)到丟棄分組，控制分組流入網(wǎng)絡(luò)中的流量，還與分組的等待時(shí)間有關(guān)系，影響分組的優(yōu)先級(jí)。

1.4 算法性能分析

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

網(wǎng)絡(luò)仿真軟件采用OPNET Modeler[10-11]。3個(gè)源節(jié)點(diǎn)的分組生成間隔都是constant(2.8)，進(jìn)行仿真，結(jié)果如圖2所示。

圖2 仿真結(jié)果

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

2 結(jié) 語

在PQBEDF_α算法中，優(yōu)先級(jí)的設(shè)置是通過對(duì)分組的等待時(shí)間計(jì)算而得到的，不需要在每次調(diào)度后對(duì)各分組的優(yōu)先級(jí)動(dòng)態(tài)調(diào)整，大大地簡(jiǎn)化了優(yōu)先級(jí)設(shè)置操作。同時(shí)，通過合理的隊(duì)列長(zhǎng)度設(shè)置，避免了低優(yōu)先級(jí)業(yè)務(wù)流中較多分組因等待時(shí)間的原因達(dá)到高優(yōu)先級(jí)，使得高優(yōu)先級(jí)業(yè)務(wù)流得不到相應(yīng)的服務(wù)。此外，它還能保證各業(yè)務(wù)流按初始優(yōu)先級(jí)的大小獲得相應(yīng)的服務(wù)，具有較好的公平性和合理性。

參考文獻(xiàn)

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

[2]林闖.計(jì)算機(jī)網(wǎng)絡(luò)的服務(wù)質(zhì)量[M].北京:清華大學(xué)出版社，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.計(jì)算機(jī)網(wǎng)絡(luò)自頂向下方法與Internet特色[M].陳鳴，譯.北京:機(jī)械工業(yè)出版社，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]錢光明.基于業(yè)務(wù)的多優(yōu)先級(jí)隊(duì)列區(qū)別服務(wù)方案[J].計(jì)算機(jī)工程與應(yīng)用，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]梁田貴，張鵬.算法設(shè)計(jì)與分析[M].北京:冶金工業(yè)出版社，2004.

[10]陳敏.OPNET網(wǎng)絡(luò)仿真[M].北京:清華大學(xué)出版社，2002.

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