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

A Job Scheduling Algorithm Based on Multi-Waiting-Queue in BSP System

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

In most of the BSP（Bulk Synchronous Parallel） system, job scheduling is based on single job waiting queue, which is proved of simplicity in implementation. However, it demands more cost in maintenance of the dynamic queue, and jobs with lower priority may stay waiting indefinitely. In this paper, we propose a strategy of multi-waiting-queue for job scheduling in BSP. In our method, we maintain five job waiting queues, and each queue contains the jobs with the same priority. Jobs in one queue are in order of Response Ratio（RR）. Multiple queues can reduce maintenance costdramatically. Besides, we integrate priority adjustment into our method. It can avoid the situation that jobs with relatively lower priority keep waiting endlessly. The scheduling method proposed in this paper is successfully deployed in BC-BSP. In this paper, comprehensive experiments with synthetic dataset are conducted to validate the efficiency of our proposed method. It proves that the proposed method of multi-waiting-queuescheduling not only can achieve 30% to 50% performance improvement in maintenance, but also can reduce the overall waiting time of jobs.