作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2012, Vol. 38 ›› Issue (20): 282-285. doi: 10.3969/j.issn.1000-3428.2012.20.073

• 开发研究与设计技术 • 上一篇    下一篇

面向抖动优化的任务静态优先级指派算法

檀 明 1,2,魏 臻 2,韩江洪 2   

  1. (1. 合肥学院网络与智能信息处理重点实验室,合肥 230601;2. 合肥工业大学计算机与信息学院,合肥 230009)
  • 收稿日期:2011-11-29 修回日期:2012-02-13 出版日期:2012-10-20 发布日期:2012-10-17
  • 作者简介:檀 明(1974-),男,副教授、博士,主研方向:实时系统;魏 臻,教授、博士、博士生导师;韩江洪,教授、博士生导师
  • 基金资助:
    国家自然科学基金资助项目(60873003, 60873195);安徽省教育厅自然科学基金资助项目(KJ2011B139)

Static Priority Assignment Algorithm to Reduce Output Jitter of Real-time Tasks

TAN Ming 1,2, WEI Zhen 2, HAN Jiang-hong 2   

  1. (1. Key Laboratory of Network and Intelligent Information Processing, Hefei University, Hefei 230601, China;2. School of Computer and Information, Hefei University of Technology, Hefei 230009, China)
  • Received:2011-11-29 Revised:2012-02-13 Online:2012-10-20 Published:2012-10-17

摘要: 对任务相对截止时限进行优化设置是一种减少输出抖动的有效方法,但现有方法均是针对最早时限优先调度算法,不能适用于任务集采用静态优先级调度算法的场合。为此,提出通过优化优先级指派实现任务集的整体抖动最小化,并给出一种启发式的优先级指派算法。根据单调速率调度算法确定任务的初始优先级,以最小化局部抖动方式依次对任务的优先级进行再调整,从而得到近似最优的优先级指派。仿真实验结果表明,该算法能有效减少任务集的整体输出抖动。

关键词: 输出抖动, 静态优先级调度, 最大响应时间, 相对截止时限, 周期性任务集, 可调度性分析

Abstract: Current deadline assignment schemes which adjust relative deadlines to reduce the output jitter of periodic real-time tasks are all under EDF(Earliest Deadline First) scheduling algorithm. In this paper, a static priority assignment problem to minimize the total output jitter of a set of real-time tasks is proposed. A heuristics algorithm is presented to solve this problem. It assigns the initial priority to each task according to RM(Rate Monotonic) algorithm, and adjusts the priority of each task one by one in terms of minimizing the sum of local output jitter, until a near optimal solution to the static priority assignment problem is found. Simulation results show the advantages of the algorithm in terms of reducing the total output jitter of a set of tasks and computing complexity.

Key words: output jitter, static priority scheduling, maximum response time, relative deadline, periodic task set, schedulability analysis

中图分类号: