• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

计算机工程与科学

• 论文 • 上一篇    下一篇

基于改进型统一调度算法改善任务集的可调度性

李蕊,李志泽   

  1. (湖南大学信息科学与工程学院,湖南 长沙 410082)
  • 收稿日期:2015-12-07 修回日期:2016-03-04 出版日期:2017-06-25 发布日期:2017-06-25
  • 基金资助:

    国家自然科学基金(61202102);湖南省科技计划(2015GK3010)

Improving the feasibility of task-sets based on
modified generalized scheduling algorithm

LI Rui,LI Zhi-ze   

  1. (College of Computer Science and Electronic Engineering,Hunan University,Changsha 410082,China)
  • Received:2015-12-07 Revised:2016-03-04 Online:2017-06-25 Published:2017-06-25

摘要:

实时系统要求任务在最差情况下能在其截止时间前获得结果,若超过了其截止时间,也会认为是错误的行为,所以改进任务可调度性分析、提高任务集可调度性尤其重要。统一调度能结合固定优先级调度的优点,防止不必要的抢占,降低资源额外销耗,能够提高任务集合的可调度性;但其任务的可调度性分析方法过于粗糙,影响任务最差响应时间分析的结果,降低了任务集的可调度性。针对存在的问题,基于统一调度,增加任务运行阶段数,重新建立任务模型,并提出通过分配任务抢占阈值、调整运行阶段的抢占阈值与长度,优化任务可容忍阻塞,改善任务集可调度性的算法。最后,实验表明,与统一调度算法及其他算法相比,所提出的调度算法能够有效改善任务集的可调度性。

关键词: 固定优先级, 抢占阈值, 运行阶段, 改进型统一调度, 可调

Abstract:

Real-time systems require the task to get the correct results before its deadline in the worst-case. If the deadline is exceeded, the task is considered a wrong behavior. Improvement in task scheduling analysis and the task-sets schedulability is particularly important. Generalized scheduling can integrate the advantages of fixed priority scheduling, prevent tasks from unnecessary preemption, reduce additional memory usage, and improve the schedulability of task-sets. But the method of task schedulability analysis is too rough, which can impact worst-case response time analysis of the task and reduce the task-sets' schedulibility. For these problems, we re-establish a task model based on generalized scheduling by increasing the number of task's running stage and propose a method for improving the schedulability by assigning task's preemption threshold, adjusting preemption thresholdand length of task running stage and optimizing the block tolerance of the task. Finally, experimental results show that the proposed scheduling algorithm can effectively improve the feasibility of the task-sets.

Key words: fixed-priority, preemption threshold, running stage, improved generalized scheduling, feasibility