一种面向BSP系统的多等待队列作业调度算法

摘要

在以往的BSP(Bulk Synchronous Parallel)系统中,作业调度都是采用基于单队列的优先级调度策略.它的优点是实现简单,但作业队列维护开销大,低优先级作业存在无限等待的问题.论文提出了面向BSP系统基于多等待队列的按优先级作业调度算法,以高响应比优先级队列为作业组织方式,并加入了作业优先级的动态调整策略,避免了低优先级作业因长期得不到执行而废弃的情况.目前,论文所提算法已成功运行于BC-BSP系统中.文中通过实验进一步证明,融合了作业优先级调整策略的基于多等待队列的作业调度算法较传统的单队列优先级调度算法在队列维护方面,能降低30％～50％的维护代价.另外,在兼顾作业的初始优先级的同时,能够减少低优先级作业的等待时间,避免低优先级作业的无限等待问题.