多特征协调的实时调度算法

计算机与现代化

多特征协调的实时调度算法

1.红塔辽宁烟草有限责任公司营口卷烟厂,辽宁营口115002;2.中国科学院沈阳自动化研究所,辽宁沈阳110016

收稿日期:2014-10-10 出版日期:2015-02-28 发布日期:2015-03-06
作者简介:满立(1969),男,吉林抚余人,红塔辽宁烟草有限责任公司营口卷烟厂工程师,本科,研究方向:计算机科学与技术,信息管理系统应用,生产调度系统应用; 朱瑞龙(1984),男，黑龙江哈尔滨人,中国科学院沈阳自动化研究所助理研究员,硕士,研究方向:生产运作与管理。
基金资助:
基金项目：国家重大科技专项项目(2011ZX02507006); 辽宁省科技攻关项目(2011216008)

Realtime Scheduling Algorithm Based on Multifeatures Synthesis

1. Yingkou Cigarette Factory of Hongta Liaoning Tobacco Industry Limited Liability Company, Yingkou 115002, China;

2. Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang 110016, China

Received:2014-10-10 Online:2015-02-28 Published:2015-03-06

摘要/Abstract

摘要： 目前大多数实时调度算法都依据单一的特征参数确定任务优先级，本文提出一种基于多特征协调的实时调度算法，对特定高优先级任务优先处理，并且对其他任务的调度不产生任何影响。同时，在系统超载的时候，有效避免了EDF算法性能的急剧下降。实验结果表明，该算法有效地保证了特定任务的调度优先级，相对于EDF算法性能有明显改进。

关键词: 实时系统, 任务调度, 最早截止期优先, 优先级

Abstract: Currently, most of the realtime scheduling algorithms define the priority of task based on a single characteristic parameter. This paper presents a realtime scheduling algorithm based on the synthesis of multifeatures. It processes the specific highpriority task and does not have any impact on the scheduling of other tasks. When system overload it can effectively avoid the sharp decline of the EDF (Earliest Deadline First) algorithm performance. Experimental results show that the algorithm effectively guarantee the priority of specific task scheduling, and the performance has significantly been improved compared with EDF algorithm.

Key words: realtime system, task scheduling, earliest deadline first, priority

中图分类号:

TP274

满立1,朱瑞龙2. 多特征协调的实时调度算法[J]. 计算机与现代化.

MAN Li1, ZHU Ruilong 2. Realtime Scheduling Algorithm Based on Multifeatures Synthesis[J]. Computer and Modernization.

参考文献

［1］
Burchard A, Liebeherr J, Oh Y F, et al. New strategies for assigning realtime tasks to multiprocessor systems［J］. IEEE Transactions on Computers, 1995,44(12):14291442.
［2］Kieckhafer R M, Walter C J, Finn A M, et al. The MAFT architecture for distributed fault tolerance［J］. IEEE Transactions on Computers, 1988,37(4):398405.
［3］庞丽萍. 操作系统原理［M］. 第3版. 武汉:华中科技大学出版社， 2000:110150.
［4］Gopalan K. RealTime Support in General Purpose Operating Systems［R］. ECSL Technical Report TR92, State University of New York at Stony Brook, 2001:6371.
［5］韩忠华,史海波,刘昶,等. 客车生产中可重入倒排产应用研究［J］. 沈阳建筑大学学报(自然科学版), 2010,26(6):12191224.
［6］Isovic D, Fohler G. Efficient scheduling of sporadic, aperiodic, and periodic tasks with complex constraints［C］// Proceedings of the 21st IEEE RealTime Systems Symposium. Florida, USA, 2000:11531161.
［7］Liu C L, Layland J W. Scheduling algorithms for multiprogramming in a hardrealtime environment［J］. Journal of ACM, 1973,20(1):4661.
［8］刘怀,费树岷. 基于EDF的分布式控制系统容错调度算法［J］. 软件学报， 2003,14(8):13711378.
［9］张拥军,张怡,彭宇行,等. 一种基于多处理机的容错实时任务调度算法［J］. 计算机研究与发展， 2000,37(4):425429.
［10］Hamdaoui M, Ramanathan P. A dynamic priority assignment technique for streams with (m,k)firm deadlines［J］. IEEE Transactions on Computers, 1995,44(12):14431451.
［11］Cen Shanwei, Pu C, Staehli R, et al. A distributed realtime MPEG video audio player［C］// Proceedings of the 5th International Workshop on Network and Operating System Support of Digital Audio and Video. Durham, New Hampshire, USA, 1995,1018:142153.
［12］Yau D K Y, Lam S S. Adaptive ratecontrolled scheduling for multimedia applications［J］. IEEE/ACM Transactions on Networking, 1997,5(4):475488.
［13］Nieh J, Lam M S. Integrated processor scheduling for multimedia［C］// Proceedings of the 5th International Workshop on Network and Operating System Support for Digital Audio and Video. 1995:215218.
［14］何军,孙玉方. 提高软非周期任务相应性能的调度算法［J］. 软件学报, 1998,9(10):721727.
［15］涂刚,阳富明,卢炎生. 基于动态优先级策略的最优软非周期任务调度算法［J］. 计算机研究与发展, 2004,41(11):20262034.
［16］Bernat G, Burns A. Combining (n,m)hard deadlines with dual priority scheduling［C］// Proceedings of the 18th IEEE RealTime Systems Symposium. San Francisco USA, 1997:4657.
［17］Guillem Bernat Nicolau. Specification and Analysis of Weakly Hard RealTime Systems［D］. Universitat de les Illes Balears, Spain, 1998.
［18］Damir Isovic. Handling Sporadic Tasks in Realtime SystemsCombinedOffline and Online Approach［D］. Malardalen University, Sweden, 2001.

[1]	赵然1,2，郭志川1,2,朱小勇1,2. 一种基于Levy飞行的改进蝗虫优化算法[J]. 计算机与现代化, 2020, 0(01): 104-.
[2]	姜凯. 基于混沌人工蜂群的云计算任务调度算法[J]. 计算机与现代化, 2016, 0(6): 7-11.
[3]	毛良文1，徐亮2,3. 基于SMT的PTACTL限界模型检测方法[J]. 计算机与现代化, 2016, 0(3): 41-45.
[4]	黄国兵1，蔺元2，金勇1. 基于现场适应性策略的自动抄表任务调度算法[J]. 计算机与现代化, 2015, 0(11): 36-39+46.
[5]	魏成巍，裴毅，刘东升，王卫平. 基于PSO的多无人机协同任务目标分配方法[J]. 计算机与现代化, 2015, 0(11): 32-35.
[6]	马亮;李晓. 基于改进粒子群算法的云计算任务调度策略[J]. 计算机与现代化, 2013, 1(9): 78-81,1.
[7]	王朋. 云计算环境下任务调度策略研究[J]. 计算机与现代化, 2013, 1(7): 22-025.
[8]	陈春雷. 一种GPU集群任务调度中间件的设计与实现[J]. 计算机与现代化, 2013, 1(2): 130-133.
[9]	贺智明,杨书金 . 基于DPSO的云工作流任务自适应调度策略[J]. 计算机与现代化, 2013, 12(12): 125-129.
[10]	任海铭;朱江. 多参数综合调度算法[J]. 计算机与现代化, 2012, 208(12): 16-18.
[11]	李慧敏;张金辉. 基于改进DPSO的网格资源调度算法[J]. 计算机与现代化, 2012, 1(03): 30-33.
[12]	邓树强;刘波;庞雄文. 改进的Min-Min算法研究[J]. 计算机与现代化, 2011, 1(6): 76-4.
[13]	徐攀;冯径;黄立威. 支持队列公平和安全策略的调度算法研究[J]. 计算机与现代化, 2010, 1(6): 9-0012.
[14]	李慧敏;蒋秀凤. 基于QoS效益函数的网格任务调度算法 [J]. 计算机与现代化, 2009, 169(9): 12-14.