基于Backfilling调度算法的'扩履适足'改进算法

摘要

在众多的并行作业调度算法中,Backfilling通常被广泛认为是有效提高CPU利用率的一种算法.该算法是在FCFS算法的基础上,将队列中较小的作业回填(Backfill)到空闲CPU,以提高CPU利用率.但是,当空闲CPU数量仍然无法满足Backfilling算法中小作业的回填要求时,系统仍有部分CPU闲置,因而也难以达到更好地提高CPU利用率的目的.对于共享内存体系结构的并行计算机系统,本文提出了基于Backfilling算法的"扩履适足"的改进算法.该算法以正在运行的作业的CPU利用率为依据,通过动态调整正在运行作业的CPU数,扩大可供回填(backfill)的CPU空间,使得Backfilling算法无法回填的作业得到运行,弥补了Backfilling算法的不足,大大提高了共享内存体系结构并行计算机系统的CPU利用率.