一种基于延迟的队列调度实现

摘 要: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的到达时间用ai表示,等待时间用wi表示,Ъ偕韪鞣肿槎记『迷诿扛鍪奔淦的开始时刻到达,且每个时间片只到达一个分组。那么不难得出如下关系式:

w2=w1-(a2-a1)

w3=w2-(a3-a2)

…

wn=wn-1-(an-an-1)

由w2+w3+…+wnЭ傻:

wn=w1-(an-a1)

(1)

式中:a1为队头分组的到达时间。根据分组的等待时间和初始优先级,由算法可以得出分组的优先级。再假设队头分组的优先级用p1表示,那么可以得出分组n的优先级为:

pn=p1+wn=p1+ w1-(an-a1)

(2)

从式(2)可以得知,е灰保留队头分组的到达时间a1和优先级w1,г俑据各分组的到达时间,就可以得出队列中每个分组的优先级。

一般地,分组并不是按上面假设的情况达到,而是随意到达的。如果取分组到达时刻所在时间段的整数部分,如3.4和5.7时间片到达的分组,取它们到达的时间分别为3和5,那么在这种情况下,式(2)仍然成立。

下面来讨论调度算法的具体实现。在系统中维持一个时钟,用于对各分组的到达时间进行计时。数据流flowi中第j个分组的到达时间用aij表示,队头分组用ai1表示。那么flowi中第j个分组相对队头分组的等待时间之差为aij-ai1。再假设pi1表示队头分组的优先级,那么由式(2)可得队列中任一分组的优先级pij为:

pij=pi1+ wi1-(aij-ai1)

其实在调度过程中并不需要计算每个分组的优先级,只需要比较各队头分组的优先级,找出最大的那个分组,就是将要发送的分组。此外还要保留该分组的到达时间和优先级,以便计算队列中下一个分组的优先级。若发送分组后队列为空,则置ai1为0,pi1为pi0,以便重新开始计算。

下面是算法实现的一个例子,其中pi0表示flowi的初始优先级。

pi1 =p i0(i=1,2,3, …,n)

For 每个时间片

选出最大的pi1

发送队列i中的队头分组

If (队列i为空)

ai1=0

pi1=pi0

Else

pi1 =pi1-(ai2-ai1)

For(j=1, j

If(i≠j)

pj1= pj1+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] . .

[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 80. Washington DC: OPNET Technologies Inc., 2001.