基于多特征动态优先级的网络实时调度算法

doi:10.11959/j.issn.1000-436x.2020091

通信学报 ›› 2020, Vol. 41 ›› Issue (5): 159-167.doi: 10.11959/j.issn.1000-436x.2020091

基于多特征动态优先级的网络实时调度算法

苏洵¹,李艳芳²,宗宁¹,魏巍³,李娟¹,丁莹¹

¹ 61623部队，北京 100036
² 61516部队，北京 100074
³ 北京航空航天大学机械工程及自动化学院，北京 100088

修回日期:2020-04-14 出版日期:2020-05-25 发布日期:2020-05-30
作者简介:苏洵（1965- ），女，北京人，61623 部队正高级工程师，主要研究方向为数据通信、计算机网络建设规划、运维管理及性能优化、数据中心建设规划及运维管理等|李艳芳（1973- ），女，湖北武汉人，61516部队高级工程师，主要研究方向为计算机网络运维管理、网络性能优化、信息服务|宗宁（1980- ），女，山东济宁人，61623部队高级工程师，主要研究方向为计算机网络运维、网络性能优化、信息服务等|魏巍（1982- ），男，辽宁沈阳人，博士，北京航空航天大学副教授、博士生导师，主要研究方向为智能制造技术及应用|李娟（1979- ），女，河北固安人，61623部队工程师，主要研究方向为计算机网络运维管理、网络性能优化、信息服务、物联网等|丁莹（1981- ），女，山东沾化人，61623部队工程师，主要研究方向为计算机网络运维、网络性能优化、信息服务等

Network real-time scheduling algorithm based on multi-feature dynamic priority

Xun SU¹,Yanfang LI²,Ning ZONG¹,Wei WEI³,Juan LI¹,Ying DING¹

¹ 61623 PLA Troops,Beijing 100036,China
² 61516 PLA Troops,Beijing 100074,China
³ College of Command Automation Beijing University of Aeronautics and Astronautics,Beijing 100088,China

Revised:2020-04-14 Online:2020-05-25 Published:2020-05-30

摘要/Abstract

摘要：

针对网络实时调度问题，提出实时调度系统体系结构与任务模型。综合考虑任务截止期、执行时间及间隔时间等属性，定义任务迫切度；根据不同任务的重要程度，提出基于服务质量的任务松紧度。通过迫切度和松紧度对优先级的动态调节，得到防止任务频繁切换的颠簸限度，保证了任务执行成功率与客户端资源利用率。仿真实验结果表明，与调度尽力交付（BE）算法、最早截止时间优先（EDF）算法相比，基于多特征动态优先级的网络实时调度算法提高了任务调度成功率，缩短了平均响应时间。

关键词: 多特征动态优先级, 迫切度, 松紧度, 颠簸限度

Abstract:

Real-time task scheduling system structure and task model were proposed aiming at the network real-time scheduling problem.The task degree of urgency was defined by considering the deadline of task,execution time and interval time between works.The task degree of tightness was proposed based on service-level assurance,according to functional importance of different tasks in the real-time task scheduling system.The thrashing limit for avoiding task switching frequently was acquired through dynamic regulation to task priorities by degree of urgency and degree of tightness,which guaranteed the success rate of tasks execution and utilization ratio of client execution.Test simulation results suggest that the multi-feature dynamic priority scheduling strategy improves the success rate of task scheduling and shorten the average response time,which suggests it has obvious superiority compared with BE and EDF scheduling algorithm.

Key words: multi-feature dynamic priority, degree of urgency, degree of tightness, thrashing limit

中图分类号:

TP301.6

苏洵,李艳芳,宗宁,魏巍,李娟,丁莹. 基于多特征动态优先级的网络实时调度算法[J]. 通信学报, 2020, 41(5): 159-167.

Xun SU,Yanfang LI,Ning ZONG,Wei WEI,Juan LI,Ying DING. Network real-time scheduling algorithm based on multi-feature dynamic priority[J]. Journal on Communications, 2020, 41(5): 159-167.

图/表 9

图1

图2

表1

实时任务调度算法的性能测量指标"

性能测量指标	定义	特性
调度成功率	在截止期内成功完成的任务执行进度占总任务执行进度的比率	$μ = \frac{已完成执行进度}{总执行进度} \times 1 00%$
切换次数	任务执行状态下切换的总次数	作业切换次数越少，系统的开销越小
客户端资源利用率	任务的执行时间与任务连续2个作业间最小时间间隔的比率，如式(1)和式(2)所示	客户端资源利用率越大越好

表1

图3

图4

图5

图6

图7

图8

参考文献 14

[1]	SEMGHOUNI S , AMANTON L , SADE B ,et al. On new scheduling policy for the improvement of firm RTDBSs performances[J]. Data ＆Knowledge Engineering, 2007,63(2): 414-432.
[2]	MUHURI P K , SHUKLA K K . Real-time scheduling of periodic tasks with processing times and deadlines as parametric fuzzy numbers[J]. Applied Soft Computing, 2009,9(3): 936-946.
[3]	NASSER N , NIDAL K , LUTFUL T ,et al. Dynamic multilevel priority packet scheduling scheme for wireless sensor network[J]. IEEE Transactions on Wireless Communications, 2013,12(4): 1448-1459.
[4]	BENITEZ P H , BENITEZ P A , ORTEGA A J ,et al. Networked control systems design considering scheduling restrictions and local faults[J]. International Journal of Innovative Computing Information and Control, 2012,8(12): 8515-8526.
[5]	洪雪玉, 张凌, 袁华 . Linux下的实时调度算法[J]. 华南理工大学学报, 2008,36(4): 104-109.
	HONG X Y , ZHANG L , YUAN H . Real-time scheduling algorithm of Linux[J]. Journal of South China University of Technology, 2008,36(4): 104-109.
[6]	王永炎, 王强, 王宏安 ,等. 基于优先级表的实时调度算法及其实现[J]. 软件学报, 2004,15(3): 360-370.
	WANG Y Y , WANG Q , WANG H A ,et al. A real-time scheduling algorithm on priority table and its implementation[J]. Journal of Software, 2004,15(3): 360-370.
[7]	陈辉 . 实时任务优先级动态分配策略[J]. 小型微型计算机系统, 2010,31(7): 1385-1388.
	CHEN H . Dynamic priority assignment strategy for real-time task[J]. Journal of Chinese Computer Systems, 2010,31(7): 1385-1388.
[8]	陈佐瓒, 徐胜超 . 面向互联网计算资源共享的自适应调度模型[J]. 计算机工程与应用, 2010,46(21): 86-89.
	CHEN Z Z ， XU S C . Adaptive-parallelism scheduling for Internet-based volunteer computing system[J]. Computer Engineering and Applications, 2010,46(21): 86-89.
[9]	巴巍 . 实时系统动态优先级任务调度算法的研究[D]. 大连:大连理工大学, 2010.
	BA W . Research of real-time system dynamic priority assignment scheduling algorithm[D]. Dalian:Dalian University of Technology, 2010.
[10]	BAURAH S , FISHER N . The partitioned dynamic-priority scheduling of sporadic task systems[J]. Real-Time Systems, 2007,36: 199-226.
[11]	HARITSA J R , LIVNY M , CAREY M J . Earliest deadline scheduling for real-time database systems[C]// Proceedings of the 12th IEEE Real-Time Systems Symposium. Piscataway:IEEE Press, 1991: 232-243.
[12]	夏家莉, 陈辉, 杨兵 . 一种动态优先级实时任务调度算法[J]. 计算机学报, 2012,35(12): 2685-2695.
	XIA J L , CHEN H , YANG B . A real-time tasks scheduling algorithm based on dynamic priority[J]. Journal of Computer, 2012,35(12): 2685-2695.
[13]	金宏, 王宏安, 王强 ,等. 改进的最小空闲时间优先调度算法[J]. 软件学报, 2004,15(8): 1116-1123.
	JIN H , WANG H A , WANG Q ,et al. An improved least-slack-first scheduling algorithm[J]. Journal of Software, 2004,15(8): 1116-1123.
[14]	萧伟, 冯治宝, 应启戛 ,等. 改进型EDF调度算法的研究与实现[J]. 计算机工程, 2009,35(18): 231-233.
	XIAO W , FENG Z B , YING Q G ,et al. Research and implementation of improved earliest deadline first schedule algorithm[J]. Computer Engineering, 2009,35(18): 231-233.

基于多特征动态优先级的网络实时调度算法

Network real-time scheduling algorithm based on multi-feature dynamic priority

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 14

相关文章 6

Metrics

推荐阅读 0

[1]	王维琼, 许豪杰, 崔萌, 谢琼. 优良布尔函数的混合禁忌搜索算法[J]. 通信学报, 2022, 43(5): 133-143.
[2]	吕芳,柏军,黄俊恒,王佰玲. 基于蚁群算法的骨干网络发现[J]. 通信学报, 2020, 41(11): 74-85.
[3]	董道广,芮国胜,田文飚,康健,刘歌. 基于结构相似性的非参数贝叶斯字典学习算法[J]. 通信学报, 2019, 40(1): 43-50.
[4]	袁鑫攀,汪灿飞,龙军,章成源,满君丰. FGBC-iDistance:细粒度位码过滤的高维索引[J]. 通信学报, 2017, 38(Z1): 127-134.
[5]	陈晶,万云. 社交网络中基于模块度最大化的标签传播算法的研究[J]. 通信学报, 2017, 38(2): 25-33.
[6]	董道广, 芮国胜, 田文飚, 康健, 刘歌. 基于结构相似性的非参数贝叶斯字典学习算法[J]. 通信学报, 2018, 99(99): 1-.