面积最大优先调度的预约回填算法

传统backfilling算法是在先来先服务基础上,将小作业回填到空闲CPU,以提高CPU利用率。该算法偏向小作业,大作业也会因为长期等待出现饥饿现象。当空闲CPU数无法满足算法中小作业回填要求时,系统仍有部分CPU闲置,难以更好地提高CPU利用率。本文中提出的算法以作业所需CPU数及预估运行时间构成的二维面积作为优先调度的条件,引入二级优先级和预约算法消除大作业的饥饿现象,减少回填作业CPU数,相应增加预估运行时间,更好提高CPU利用率。实验证明,该算法比传统backfilling算法在保证用户公平性,缩短作业平均响应时间及CPU利用率方面有所提高。

An Algorithm for Reservation-Backfilling Based on Largest Area First

The traditional backfilling algorithm based on FCFS backfills small jobs to idle CPUs to enhance CPU utilization.It prefers to the smaller jobs,and the bigger jobs will be hunger because of a long time waiting.When the idle CPUs can not meet the requirements of the smaller jobs backfilled,there are still idle CPUs,and the CPU utilization can not be better enhanced.This paper proposed an algorithm for reservation-backfilling based on largest area first to solve these problems.The large area jobs first scheduled improves the fairness of jobs.Pulling in the second priority and Reservation Algorithm will eliminate the hunger of the bigger jobs.Reducing the CPU number and extending the running time the job required enhances CPU utilization.The result of experiment shows that this algorithm can better improve the fairness of jobs,the utilization of the CPU and the average response time than the traditional backfilling algorithm.