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

摘 要: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相吻合。……