队头阻塞优化的EDF可重构任务调度算法  

Head-of-line Blocking Optimization EDF Scheduling Algorithm for Reconfigurable Tasks

作　　者：韩晓亚[1] 汪斌强[1] 黄万伟[1] 王保进[1] 

机构地区：[1]国家数字交换系统工程技术研究中心,郑州450002

出　　处：《计算机辅助设计与图形学学报》2011年第9期1567-1575,共9页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家"八六三"高技术研究发展计划(2009AA01A334;2009AA012201;2008AA01A323;2008AA01A325;2008AA01A326)

摘　　要：针对最早截止时刻优先(earliest deadline first,EDF)调度算法队头阻塞任务导致资源利用率和配置端口复用率低下的问题,提出一种队头阻塞优化的EDF实时调度算法.通过定义无效阻塞任务并引入无效阻塞任务丢弃策略,提前判定和丢弃无法调度成功的任务,以利于后续任务调度;通过定义队头阻塞任务最早布局成功时刻,引入匹配任务提前配置策略和次队头任务提前配置策略,使阻塞过程中的部分空闲可重构资源和空闲配置端口得到有效利用.仿真结果表明,与EDF调度算法相比,采用文中调度算法有效地提高了调度成功率和可重构资源利用率.Concerning the head-of-line blocking task in earliest deadline first（EDF） scheduling algorithm led to low resource utilization rate and low configuration port multiplexing rate,a head-of-line blocking optimization EDF real-time scheduling algorithm for reconfigurable tasks is presented.By defining the invalid blocking task,The invalid blocking task drop strategy is introduced to drop the task that can＇t be scheduled successfully in advance,in order to facilitate the follow-up tasks scheduling;the Matching task configuration bring forward strategy and the second head task configuration bring forward strategy is introduced by defining the earliest placement success time of head-of-line blocking task,so that part of the free reconfigurable resource and free configuration port in head-of-line blocking process can be used by other tasks.Experimental results show that,compared to the EDF scheduling algorithm,this scheduling algorithm can gains a considerable improvement both in the scheduling success rate and the reconfigurable resource using rate.

关 键 词：可重构任务 实时调度 队头阻塞 最早截至时刻优先 调度成功率 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]