最晚截止期优先带宽转让算法

摘要

An algorithm named Latest Deadline First(LDF) is presented to implement the bandwidth transfer at run time in a real-time system scheduled with the Earliest Deadline First(EDF) algorithm if the remaining bandwidth of the system is not enough for new tasks’ insertion and/or current tasks acceleration. This algorithm starts from the task with the latest instance deadline so that the times of comparison can be as few as possible before the proper task is found to compress, the bandwidth transfer can be done smoothly as quickly as possible. Simulation experimental results show that the maximum time of comparison of the algorithm is 2n, only one or two comparisons are needed in many cases.%基于最早截止期优先调度的实时系统，针对有新任务插入(与/或)现行任务加速但系统带宽不足的问题，提出一种最晚截止期优先(LDF)算法，用于系统在运行时选择现行任务转让带宽。采用从最晚作业截止期任务开始判断的方法，经过尽可能少的比较次数，找到合适的受压任务，平滑地完成带宽转让。算法需要的最多比较次数为2n。仿真结果表明，该算法在大多情况下只需要比较1~2次即可完成压缩任务。