一类特殊的非抢占式周期任务的调度方法

现实世界中针对许多任务的资源调度分配和使用具有时效性,对该类任务的调度问题目前的研究还较少.针对此类调度问题,分析其特点,明确其与已有调度模型研究问题的区别,提出新的非抢占式周期任务调度模型,并证明了该类问题为NP完全问题.在此基础上,给出了一种求解最优解的模式剪枝算法,以及一种

Computer Engineering and Applications 计算机工程与应用

2018，54（9）1引言对单处理器实时系统而言，通常存在多个不同的任务，同一时刻只能对一个任务进行处理；不同的任务有不同的开始时间、执行时间、截止时间等等约束因素；当存在多个任务时，如何通过合理安排不同任务的执行时间，使得单处理器实时系统能够对这些任务进行处理，这就是调度方法需要解决的问题[1]。周期任务调度问题是当前研究的热点问题之一[2-4]。Liu 和Layland 提出了一种通用的周期任务模型[5]，该模型假设任务之间相互独立，并根据不同的调度情况，可以将调度问题分成静态调度问题和动态调度问题。RM （Rate Monotonic ）算法[6]和EDF （Earliest Deadline First ）算法[7]分别是这两类调度算法中的典型代表。其中，EDF 算法总是优先选择截止期最早的任务进行调度，而RM 算法则根据任务的周期进行优先级调度，周期越小，优先级越高。

当任务开始执行后，如出现其他优先级更高的任务，按照是否可以替换当前正在执行任务，将调度问题划分成可抢占式（preemptive ）调度问题和非抢占式（non-preemptive ）调度问题。对可抢占式调度问题，学界已有较为充分的研究和理论成果[8]。在实际系统中，由于硬件条件的限制以及效率和性能的考虑，存在非常

多的系统并不支持可抢占式调度，如控制器局域网络（Control Area Network ，CAN ）的总线消息传递问题[9]。与可抢占式调度问题不同，非抢占式调度问题已经被证明是NP 难问题[10]，可抢占式调度问题中得到的可调度条件在非抢占式调度问题中最多也仅为必要条件[11]。学者针对不同实际场景的特点，提出了解决相应非抢占式调度问题的一系列优秀算法[12-14]。

对通常研究的周期性调度问题而言，如控制系统中一类特殊的非抢占式周期任务的调度方法

李智翔，李赟，贺亮

LI ＇hixiang,LI Yun,HE Liang

盲信号处理重点实验室，成都610041

National Key Laboratory of Science and Technology on Blind Signal Processing,Chengdu 610041,China

LI Zhixiang,LI Yun,HE Liang.Scheduling methods for special type of non-preemptive periodic http://www.77cn.com.cnputer Engineering and Applications,2018,54（9）：22-27.

Abstract ：Many actual resource schedule problems for different tasks have timeliness,but few research has been focused on this kind of problem.This paper studies the problem,discusses the difference with some models that have been studied well,then proposes a new schedule model for non-preemptive periodic tasks,and proves the problem to be NP-Complete problem.After that,this paper gives two algorithms to solve the schedule problem,one for optimal solutions called pattern pruning algorithm,and the other for approximation solutions called fast solving algorithm.The experimental result shows that the algorithms can deal the schedule problem efficiently according to different situation.

Key words ：schedule problem;periodic task;non-preemptive scheduling;schedule algorithm;pruning algorithm

摘要：现实世界中针对许多任务的资源调度分配和使用具有时效性，对该类任务的调度问题目前的研究还较少。针对此类调度问题，分析其特点，明确其与已有调度模型研究问题的区别，提出新的非抢占式周期任务调度模型，并证明了该类问题为NP 完全问题。在此基础上，给出了一种求解最优解的模式剪枝算法，以及一种求解近似解的快速求解算法。相关实验表明，提出的两种算法能够针对不同的需求场景分别对调度问题进行高效求解。

关键词：调度问题；周期任务；非抢占式调度；调度算法；剪枝算法

文献标志码：A 中图分类号：TP301doi ：10.3778/j.issn.1002-8331.1801-0270

基金项目：国家自然科学基金（No.61221063，No.61403301）。

作者简介：李智翔（1989—），男，博士生，研究领域为智能优化算法与应用，E-mail ：lzxest@http://www.77cn.com.cn ；李赟（1984—），男，博士，研究

领域为智能信息处理；贺亮（1990—），男，博士生，研究领域为内部人员检测，拓扑推断及网络测量。

收稿日期：2018-01-08修回日期：2018-03-09文章编号：1002-8331（2018）09-0022-06

22万方数据

本文来源：https://www.bwwdw.com/article/9h3m.html