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

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

Abstract

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

CLC Number:

TP301.6

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.

Figures/Tables 9

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

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

Metrics

Recommended 0

No Suggested Reading articles found!

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 9

References 14

Related Articles 6

Metrics

Recommended 0

[1]	Weiqiong WANG, Haojie XU, Meng CUI, Qiong XIE. Hybrid tabu search algorithm for excellent Boolean function [J]. Journal on Communications, 2022, 43(5): 133-143.
[2]	Fang LYU,Jun BAI,Junheng HUANG,Bailing WANG. Discovering the backbone network with a novel designed ant colony algorithm [J]. Journal on Communications, 2020, 41(11): 74-85.
[3]	Daoguang DONG,Guosheng RUI,Wenbiao TIAN,Jian KANG,Ge LIU. Nonparametric Bayesian dictionary learning algorithm based on structural similarity [J]. Journal on Communications, 2019, 40(1): 43-50.
[4]	Xin-pan YUAN,Can-fei WANG,Jun LONG,Cheng-yuan ZHANG,Jun-feng MAN. FGBC-iDistance:fine-grained bit-code filter based high-dimensional index [J]. Journal on Communications, 2017, 38(Z1): 127-134.
[5]	Jing CHEN,Yun WAN. Research on label propagation algorithm based on modularity maximization in the social network [J]. Journal on Communications, 2017, 38(2): 25-33.
[6]	DONG Daoguang, RUI Guosheng, TIAN Wenbiao, KANG Jian, LIU Ge. Nonparametric Bayesian dictionary learning algorithm based on structural similarity [J]. Journal on Communications, 2018, 99(99): 1-.