仿真网格中一种基于匹配度的改进Min-Min调度算法  

Simulation Grid:An Improved Min-Min Algorithm Based on Matching-degree

作　　者：张霞[1] 杜丽敏[1] 

机构地区：[1]山西大学计算机与信息技术学院,太原030006

出　　处：《山西大学学报（自然科学版）》2016年第2期223-228,共6页Journal of Shanxi University(Natural Science Edition)

基　　金：国家自然科学基金(61202018)

摘　　要：分布式仿真网格是完善分布式仿真系统有效途径之一,而资源任务调度问题是提高分布式仿真网格系统效率的基础。通过对经典Min-Min和Max-Min调度算法研究学习,发现现有算法存在负载不均衡问题。针对现存问题,在考虑到任务本身优先级要求、任务大小和机器运行速度运行效率等因素的情况下,提出机器任务匹配度函数Matching-rate[i][j],将任务的预期完成时间与任务优先级进行匹配;并定义了系统负载均衡参数LBP,然后根据机器任务匹配度函数和系统负载均衡参数实现动态地调度Min-Min算法和Max-Min算法。最后通过实验,验证了此算法在总执行时间、总执行费用和机器利用率指标中有了一定改进,提高了调度性能,且达到了实现负载均衡的目的。Distributed simulation grid is one of effective ways to improve the distributed simulation system,and the grid task scheduling problem is the foundation of improving the efficiency of the distributed simulation grid system.Through the study of classics Min-Min and Max-Min scheduling algorithm,we found that there is a load imbalance question.Aimed at the existing problem,considering the task itself requirements,the size of the task priority and machine efficiency or other factors,Matching-rate[i][j]of machine is put forward.The expected completion time of the task and the task priority are be matched,and the method defines the load balance parameter（LBP）of the system.Based on the Matching-rate[i][j]and LBP,it realized the dynamic scheduling algorithm of Min-Min and Max-Min algorithm.Finally,through the experiment,the algorithm has a certain improvement in some indicators such as the total execution time,the total execution cost and the machine utilization and the performance of the scheduling,and achieves the purpose of load balancing.

关 键 词：任务调度 MIN-MIN MAX-MIN 匹配度 负载平衡 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] TP311[自动化与计算机技术—计算机科学与技术]