Portioned EDF-based scheduling on multiprocessors
Portioned EDF-based scheduling on multiprocessors
复制标题
DOI：
10.1145/1450058.1450078
复制
发表时间：
2008-10
期刊：
影响因子：
--
通讯作者：
S. Kato;N. Yamasaki
中科院分区：
文献类型：
--
作者：
S. Kato;N. Yamasaki
提出了一种基于EDF的递归实时任务调度算法--最早截止期延迟部分算法(EDDP)。EDDP的设计基于分段调度技术，将每个任务分为固定任务和可迁移任务。在没有迁移的情况下，在专用处理器上调度固定任务。同时允许可迁移任务在特定的两个处理器之间迁移。为了控制任务迁移的开销，EDDP在M个处理器上最多可迁移M-1个任务。调度分析得出给定任务集是可调度的条件。还证明，如果系统利用率不超过65%，任何任务都不会错过最后期限。在理论分析的基础上，通过仿真研究对EDDP的有效性进行了评估。仿真结果表明，与传统的基于EDF的算法相比，EDDP具有较高的系统利用率和较少的抢占次数。
This paper presents an EDF-based algorithm, called Earliest Deadline Deferrable Portion (EDDP), for efficient scheduling of recurrent real-time tasks on multiprocessor systems. The design of EDDP is based on the portioned scheduling technique which classifies each task into a fixed task or a migratable task. A fixed task is scheduled on the dedicated processor without migrations. A migratable task is meanwhile permitted to migrate between the particular two processors. In order to curb the cost of task migrations, EDDP makes at most M -- 1 migratable tasks on M processors. The scheduling analysis derives the condition for a given task set to be schedulable. It is also proven that no tasks ever miss deadlines, if the system utilization does not exceed 65%. Beyond the theoretical analysis, the effectiveness of EDDP is evaluated through simulation studies. Simulation results show that EDDP achieves high system utilization with a small number of preemptions, compared with the traditional EDF-based algorithms.