基于动态优先级策略的最优软非周期任务调度算法

An Optimal Scheduling Algorithm for Soft Aperiodic Tasks

周期任务与非周期任务的混合调度是实时调度研究的一个重要方向 通过定义“调度”和“逆调度” ,对实时周期任务集在使用EDF算法调度时的可挪用时间进行分析 ,求出了周期任务集在使用EDF调度时的最大可挪用时间 在此基础上 ,提出用于缩短非周期任务响应时间和周转时间的调度算法———ISA(idlestealingalgorithm) ISA算法充分使用最大可挪用时间 ,在保证周期任务满足最后期限的同时能取得非周期任务的最优响应时间和周转时间 证明了ISA算法的最优性 。

The problem of hybrid scheduling of hard period task and soft aperiodic task is important part of the research of real-time scheduling. To analysis the idle and movable time of period task set scheduled by earliest deadline first scheduling algorithm, two definitions scheduling and converse scheduling are given. These two definitions are used to calculate the max movable time of period task set. Using the max movable time, an algorithm named idle stealing algorithm (ISA) is given to decrease the response time of aperiodic task. ISA makes full use of the max movable time of period task set. It can largely decrease the response time of aperiodic tasks while guaranteeing the deadline of period tasks. The ISA algorithm provides the shortest response time of aperiodic task and is proved to be optimal by experiments.