计算机工程

• 体系结构与软件技术 • 上一篇    下一篇

一种高回报的最小空闲时间优先实时调度改进算法

张晶,孙少杰,范洪博,肖智斌   

  1. (昆明理工大学 信息工程与自动化学院,昆明 650500)
  • 收稿日期:2016-01-22 出版日期:2017-03-15 发布日期:2017-03-15
  • 作者简介:张晶(1974—),男,教授、博士,主研方向为实时嵌入式软件;孙少杰,硕士研究生;范洪博(通信作者),博士;肖智斌,硕士研究生。
  • 基金项目:
    国家自然科学基金(61562051);云南省应用基础研究计划重点项目(2014FA029)。

An Improved Least Slack First Real-time Scheduling Algorithm with High Return

ZHANG Jing,SUN Shaojie,FAN Hongbo,XIAO Zhibin   

  1. (Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650500,China)
  • Received:2016-01-22 Online:2017-03-15 Published:2017-03-15

摘要: 信号任务调度算法是提高信息物理系统执行效能的关键,而最小空闲时间优先算法(LSF)、最早截止时间优先算法(EDF)和最大价值优先算法(HVF)在系统满载的情况下无法很好地完成任务调度并且系统能耗很高。为此,提出一种改进型调度算法。将任务能耗、任务完成价值和任务紧迫程度相结合,通过引入任务调度优先级和任务实际调度优先级的形式,实现任务的动态调度。实验结果表明,对于同一个任务集,在完成相同调度任务数量的情况下,改进算法的系统能耗小于采用LSF算法和EDF算法的系统能耗。系统满载时,在完成任务总价值相同的情况下,采用改进算法的系统所需要的能耗比HVF算法更少。

关键词: 最小空闲时间优先算法, 高回报最小空闲时间优先算法, 任务能耗, 任务价值, 动态调度

Abstract: Signal task scheduling algorithm is the key to the effectiveness of the implementation of Cyber Physical System(CPS).When the system is fully loaded,the Least Slack First(LSF) algorithm,Earliest Deadline First(EDF) algorithm or Highest Value First(HVF) algorithm cannot finish the task scheduling perfectly and the system energy consumption is higher than normal condition.Therefore,this paper proposes an improved scheduling algorithm.The algorithm can schedule system task dynamically by introducing task scheduling priority and actual task scheduling priority with combining task energy consumption,task completion value and task urgency.Experimental results show that for the same task set and the same number of tasks,the system energy consumption of the improved algorithm is less than that of LSF algorithm and EDF algorithm.When the system is fully loaded,compared with HVF algorithm,the improved algorithm can use less energy consumption to achieve the same total tasks’ value.

Key words: Least Slack First(LSF) algorithm, High Return Least Slack First(HRLSF) algorithm, task energy consumption, task value, dynamic scheduling

中图分类号: