Computer Engineering and Applications ›› 2018, Vol. 54 ›› Issue (9): 22-27.DOI: 10.3778/j.issn.1002-8331.1801-0270

Previous Articles     Next Articles

Scheduling methods for special type of non-preemptive periodic tasks

LI Zhixiang, LI Yun, HE Liang   

  1. National Key Laboratory of Science and Technology on Blind Signal Processing, Chengdu 610041, China
  • Online:2018-05-01 Published:2018-05-15

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

李智翔,李  赟,贺  亮   

  1. 盲信号处理重点实验室,成都 610041

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完全问题。在此基础上,给出了一种求解最优解的模式剪枝算法,以及一种求解近似解的快速求解算法。相关实验表明,提出的两种算法能够针对不同的需求场景分别对调度问题进行高效求解。

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