基于优先级的抢占式并行调度算法设计与分析

Design and Analysis of Prority-based Preemtiv Parallel Scheduling Algorithm

并行作业调度系统负责对高性能计算系统中作业队列的管理。其核心功能是在每次调度发生时,选择下一个被执行的作业。最简单的调度算法是先来先服务(FCFS)。但这种方法的缺点是资源利用率很低。解决这个问题,目前常用的算法有EASY Backfilling。但EASY算法也存在两个缺陷:要求用户估计作业运行时间和偏爱小作业。针对这两个问题,本文设计了一种新的调度方法:基于优先级的抢占式并行调度(Priority-based Preemptive Schedu-ling),并实现了两种算法的模拟系统,从性能和公平性两个角度对PPS算法和EASY算法进行了比较分析,表明了PPS算法的有效性。

Parallel job scheduler is important to High Performance Computing system. The kernel function is to choose a job to execute whenever a scheduling event happens. The simplest policy is FCFS. This approach suffers from low system utilization. EASY Backfilling was p oposed to improve system utilization and has been implemented in several production schedulers. The main problem with EASY is that it requires estimates of job runtimes to be available. Another problem is that it moves forwards as many smaller jobs as possible. It is unfair to the larger ones. To attack these problems, we propose a new method, Priority-based Preemptive Scheduling.