吉林大学学报(工学版) ›› 2013, Vol. 43 ›› Issue (05): 1338-1342.doi: 10.7964/jdxbgxb201305031

• 论文 • 上一篇    下一篇

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

程禹1, 赵宏伟1, 龙曼丽2, 李玉翠1   

  1. 1. 吉林大学 计算机科学与技术学院, 长春 130012;
    2. 吉林大学 公共外语教育学院, 长春 130012
  • 收稿日期:2012-06-15 出版日期:2013-09-01 发布日期:2013-09-01
  • 通讯作者: 龙曼丽(1977- ),女,工程师.研究方向:智能信息系统.E-mail:Longml@jlu.edu.cn E-mail:Longml@jlu.edu.cn
  • 作者简介:程禹(1982- ),男,工程师,博士研究生.研究方向:智能信息系统与嵌入式技术.E-mail:unplug2007@163.com
  • 基金资助:

    吉林省自然科学基金项目(20101504);吉林省教育厅科学基金项目(2009605).

Improvement of earliest deadline first scheduling algorithm

CHENG Yu1, ZHAO Hong-wei1, LONG Man-li2, LI Yu-cui1   

  1. 1. College of Computer Science and Technology, Jilin University, Changchun, 130012, China;
    2. School of Foreign Language Education, Jilin University, Changchun 130012, China
  • Received:2012-06-15 Online:2013-09-01 Published:2013-09-01

RICH HTML

0   

PDF (PC)

287

摘要：

在基于IEEE802.16d协议的服务流调度过程中,为了保证优先级较高的任务优先得到服务,并尽量将调度过程对系统资源的消耗控制在可承受的范围内,在分析已有的非抢占式及抢占式两种方案的最早截止期优先(EDF)算法优缺点的基础上,重点考虑时间特性、重要性特性、顺序参考三方面作为调节参数,同时兼顾传输距离,对已有的EDF算法进行改进。提出了基于重要性因素抢占的半抢占式EDF算法。通过仿真实验,把改进后的EDF算法应用到IEEE802.16d协议的实时轮询业务(RTPS)服务流调度中。结果表明,改进后的EDF算法较好地平衡了抢占及非抢占式EDF算法的优缺点,具备较前两者更小且更稳定的延时。

关键词: 计算机应用, 最早截止期优先算法, 平均延时, 截止时间, 时间特性, 抢占

Abstract:

In the process of service flow scheduling based on IEEE802.16d agreement, a good scheduling algorithm should ensure that higher priority tasks get priority service;meanwhile, the occupation of system resources during the scheduling process should be minimized. The advantages and disadvantages of two kinds of existing Earliest Deadline First (EDF) algorithms, i.e. the non-preemptive EDF algorithm and preemptive EDF algorithm, are analyzed in depth. Then an improved semi-preemptive EDF algorithm based on the importance of factors is proposed. In this algorithm the time characteristics, the importance characteristics and the order of reference are taken as the adjustable parameters, and the transmission distance is also taken into account. By simulation, the improved EDF algorithm is applied to the Real-Time Polling Service (RTPS) service flow scheduling of IEEE802.16d agreement. The experimental results show that the improved EDF algorithm has a better balance between advantages and disadvantages than non-preemptive and preemptive EDF algorithms, with smaller and more stable delay.

Key words: computer applications, earliest deadline first, delay time, deadline time, time characteristics, preempt

中图分类号: 

  • TP393

[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]//2005 IEEE International Conference on Communications. Seoul, Kerea: Institute of Electrical and Electronics 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 1998 17th Annual IEEE Conference on Computer Communications, INFOCOM. Part 1 (of 3). San Francisco, CA, USA: IEEE, Piscataway, NJ, United States, 1998.

[4] Sayenko Alexander, Alanen Olli, Karhula Juha, et al. Ensuring the QoS requirements in 802.16 scheduling[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 University,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.16 WiMax networks[C]//2008 International 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.16 broadband wireless networks[C]//2006 Fourteenth 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.16 broadband wireless 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.16 broadband 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 [C]2009 IEEE 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.
[1] 刘富,宗宇轩,康冰,张益萌,林彩霞,赵宏伟. 基于优化纹理特征的手背静脉识别系统[J]. 吉林大学学报(工学版), 2018, 48(6): 1844-1850.
[2] 王利民,刘洋,孙铭会,李美慧. 基于Markov blanket的无约束型K阶贝叶斯集成分类模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1851-1858.
[3] 金顺福,王宝帅,郝闪闪,贾晓光,霍占强. 基于备用虚拟机同步休眠的云数据中心节能策略及性能[J]. 吉林大学学报(工学版), 2018, 48(6): 1859-1866.
[4] 赵东,孙明玉,朱金龙,于繁华,刘光洁,陈慧灵. 结合粒子群和单纯形的改进飞蛾优化算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1867-1872.
[5] 刘恩泽,吴文福. 基于机器视觉的农作物表面多特征决策融合病变判断算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1873-1878.
[6] 欧阳丹彤, 范琪. 子句级别语境感知的开放信息抽取方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1563-1570.
[7] 刘富, 兰旭腾, 侯涛, 康冰, 刘云, 林彩霞. 基于优化k-mer频率的宏基因组聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1593-1599.
[8] 桂春, 黄旺星. 基于改进的标签传播算法的网络聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1600-1605.
[9] 刘元宁, 刘帅, 朱晓冬, 陈一浩, 郑少阁, 沈椿壮. 基于高斯拉普拉斯算子与自适应优化伽柏滤波的虹膜识别[J]. 吉林大学学报(工学版), 2018, 48(5): 1606-1613.
[10] 车翔玖, 王利, 郭晓新. 基于多尺度特征融合的边界检测算法[J]. 吉林大学学报(工学版), 2018, 48(5): 1621-1628.
[11] 赵宏伟, 刘宇琦, 董立岩, 王玉, 刘陪. 智能交通混合动态路径优化算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[12] 黄辉, 冯西安, 魏燕, 许驰, 陈慧灵. 基于增强核极限学习机的专业选择智能系统[J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[13] 傅文博, 张杰, 陈永乐. 物联网环境下抵抗路由欺骗攻击的网络拓扑发现算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
[14] 曹洁, 苏哲, 李晓旭. 基于Corr-LDA模型的图像标注方法[J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243.
[15] 侯永宏, 王利伟, 邢家明. 基于HTTP的动态自适应流媒体传输算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1244-1253.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 《吉林大学学报(工学版)》编辑部
地址：长春市人民大街5988号　电话：+86-431-85095297　传真：+86-431-85094074　E-mail: xbgxb@jlu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发