基于负载均衡和任务超时率的任务调度研究

摘要

最近几年，在学术界和工业界的大力推动下，云计算技术得到了迅速的发展。云计算技术的实现除了依靠分布式计算、网格计算等技术外，还要依靠一项重要的技术手段—负载均衡技术。如何实现资源访问的负载均衡以提高系统的整体处理能力是云计算的关键问题之一。保证任务不超时是用户对云计算服务的最基本要求，如何通过合理的调度和资源管理，降低任务超时率也是云计算研究的重要目标之一。随着云计算系统规模的不断扩大，云计算的运行成本和能量消耗越来越受到关注，提高功耗效率，实现绿色计算，是云计算技术发展的潮流和方向。因此，本文将负载均衡、任务超时率和系统能耗作为任务调度的三个优化目标，并做了以下的研究工作:
　　(1)介绍了云计算任务调度的特点和目标，研究比较了多种经典任务调度模型的优缺点，并以此为基础建立了本文所用的任务模型、系统模型、负载均衡模型和系统能耗模型。接着简单介绍了几种云计算任务调度的经典算法，为之后算法的分析比较与改进提供了理论基础。
　　(2)本文重点研究了集中式批处理任务调度模型。在此模型基础上，针对基于周转时间的服务器速度优化方案任务超时率较高的缺点，本文对比研究了基于截止时间的速度优化改进方案。在任务与资源异构环境下，针对基于任务数的负载均衡方法无法准确反映服务器的负载状况，本文分析比较了基于预执行时间的负载均衡方法，该方法提高了系统的负载均衡性能。遗传算法易陷入局部最优解，本文利用模拟退火算法的Metropolis准则来改进遗传算法，有效提高了遗传算法的全局搜索能力。同时采用双适应度函数来分别优化负载均衡和系统能耗，使种群向着负载均衡性能良好且系统低能耗的方向进化发展。
　　(3)集中式批处理任务调度模型只有唯一的调度器用于任务调度，规模庞大且复杂的云计算环境容易造成调度系统失效。模拟退火遗传算法的运行时间较长，无法保证任务执行的实时性要求。针对以上不足，本文对比研究了一种分层式实时调度模型，并在此模型基础上设计了LTS（Load Balancing负载均衡，Task Overtime Rate任务超时率，System Energy Consumption系统能耗）算法。仿真结果表明，与模拟退火遗传算法相比，LTS算法在降低任务超时率上具有一定的优势。同时LTS算法还具有较好的负载均衡性能，能够较好地降低系统的能耗。

目录

声明

摘要

第1章 绪论

1．1 云计算任务调度研究背景及意义

1．2 国内外研究现状

1．2．1 负载均衡研究现状

1．2．2 实时调度研究现状

1．2．3 服务器节能研究现状

1．3 本文的工作

第2章 任务调度理论基础与模型分析

2．1 任务调度理论基础

2．1．1 任务调度概述

2．1．2 云计算任务调度的特点

2．1．3 云计算任务调度的目标

2．1．4 云计算任务调度的经典算法

2．2 任务调度模型分析

2．2．1 经典任务调度模型

2．2．2 云环境下任务模型

2．2．3 云环境下系统模型

2．2．4 云环境下负载均衡模型

2．2．5 云环境下系统能耗模型

第3章 基于模拟退火遗传算法的任务调度研究

3．1 任务调度模型

3．2 最小化能耗的服务器速度优化

3．2．1 基于周转时间的速度优化

3．2．2 基于截止时间的速度优化

3．3 基于模拟退火遗传算法的任务调度研究

3．3．1 模拟退火算法简介

3．3．2 遗传算法简介

3．3．3 模拟退火遗传算法设计

3．4 仿真实验及结果分析

3．5 本章小结

第4章 基于分层式实时调度系统的任务调度研究

4．1 任务调度模型

4．2 调度算法设计

4．2．1 负载均衡算法

4．2．2 任务超时率算法

4．3．3 系统能耗算法

4．3 仿真实验及结果分析

4．4 本章小结

总结与展望

致谢

参考文献

攻读硕士学位期间发表的论文