Author Login Editor-in-Chief Peer Review Editor Work Office Work

Computer Engineering

Previous Articles     Next Articles

Research on Bandwidth Transfer of Task Pair Based on Earliest Deadline First Algorithm

QIAN Guangming,ZHOU Yinyu   

  1. (College of Mathematics and Computer Science,Hunan Normal University,Changsha 410081,China)
  • Received:2015-03-04 Online:2016-04-15 Published:2016-04-15

基于最早截止期优先算法的任务对带宽转让研究

钱光明,周垠宇   

  1. (湖南师范大学数学与计算机科学学院,长沙 410081)
  • 作者简介:钱光明(1963-),男,教授,主研方向为网络嵌入式系统、实时系统;周垠宇,硕士研究生。
  • 基金资助:
    长沙市科技局基金资助项目(K11ZD014-13,K15ZD053-43)。

Abstract: Based on the real-time task set scheduled by the Earliest Deadline First(EDF)algorithm,the bandwidth transfer caused by the request of inserting a new task or accelerating the current task is studied.The bandwidth transfer mode of a task pair is presented,that is,a curent running task frees part of its bandwidth for the insertion of a new task.A time point is proved from which on the insertion of the new task of the pair is smooth,and it means no deadline missing will be caused in the system.The theorem in the paper shows that this time point can be evaluated on a simple expression and is very applicable to the applications at run-time,if the period and the execution amount of each task in the pair are available and the remaining execution time of the one that frees bandwidth can be gotten in current period.Assuming the remaining bandwidth(the bandwidth of the system minus the one used by the task pair) must totally be reserved for other tasks during certain stages,then this time point is the earliest feasible time for the new task.The correctness of the theorem is verified by a simulation example.

Key words: task pair, bandwidth transfer, aligning, further delaying, earliest feasible time

摘要: 针对最早截止期优先算法调度的实时任务集,研究新任务插入或现行任务加速引起的带宽转让问题。提出任务对带宽转让模式,使一个正在运行的任务出让带宽来满足另一个新任务的插入。证明在某个时间点,任务对中的新任务从该点开始的插入是平滑的,不会引起任何任务的截止期丢失。提出的定理显示,只要已知任务对中2个任务各自的周期和执行量,以及出让带宽的任务在当前周期的剩余执行量,用一个简单的代数式即可求得该时间点。假定减去任务对所用带宽后,系统的剩余带宽需要为其他任务完全保留,则该时间点就是新任务插入的最早可行时刻。仿真实例验证了该定理的正确性。

关键词: 任务对, 带宽转让, 对齐, 再延迟, 最早可行时刻

CLC Number: