最早截止期优先调度算法的改进

程 禹，赵宏伟，龙曼丽，李玉翠

（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.