Cloudsim中基于智能算法的任务调度研究
宣豪骏XUAN Hao-jun；姜瑛JIANG Ying （昆明理工大学，昆明650500） （Kunming University of Science and Technology，Kunming 650500，China）
【摘 要】摘要：云计算［1］是一种基于网络的、按需获取服务资源的大型分布式计算模式。任务调度则是云计算中的关键技术之一，任务调度策略的优劣直接影响到用户提交作业的执行效率和对服务质量的满意度。针对于此，本文将几类传统任务调度算法的性能进行了比较，并在基本算法的基础上融入最优调度的思想，实验证明本文所设计的算法在一定程度上节约了任务的总调度时间，有一定的可行性。 【期刊名称】价值工程 【年(卷),期】2016(035)010 【总页数】2
【关键词】云计算；任务调度；智能算法；最优调度；cloudsim 【
文
献
来
源
】
https://www.zhangqiaokeyan.com/academic-journal-cn_value-
engineering_thesis/0201237683253.html
0 引言
云计算［2］作为一种新兴的技术和商业模式，是继个人电脑、互联网之后的第三次巨大变革。其基本思想是：通过获取和使用可通过重新配置的虚拟化［8］资源池，以一种按需付费的方式获取计算资源，并通过软件实现自动管理，无须人为参与。现有的成熟的云计算平台由于服务成本高，规模巨大等原因，通常不直接用于云计算平台的实验中。为此，澳大利亚墨尔本大学教授团队开发
了云仿真器cloudsim来模拟云环境下的任务调度与资源分配。
1 问题的描述
云计算中的任务调度是一个非确定性多项式（nondeterministic polynomical，缩写NP-hard）的问题。其调度策略的优劣对系统的整体性能有重要的影响。现有的任务调度算法大体可以分为两大类：早期传统的任务调度算法：先来先服务（First Come First Served，FCFS），有向非循环图（Directed Acyclic Graph），轮询法等。后期的启发式算法：遗传算法（Genetic Algorithm，GA），蚁群算法，粒子群算法，模拟退火算法，神经网络，禁忌搜索，免疫算法，max-max，max-min，min-min等。然而这些传统算法都存在问题包括，描述复杂，正确性不高，收敛性差，调度策略单一，并不能直接用于云计算环境中。为了提高云计算任务调度的服务质量，一些新的任务调度算法被提出。文献［3］提出了在遗传算法产生新个体的过程中引入模拟退火算子，该算法在一定程度上改善了算法的性能；文献［4］提出了一种动态规划的云任务分配算法，避免了子问题的重复计算，提高了时间复杂度；袁平鹏［5］等人依据cache中所存放的最近访问过的资源信息来减少不必要的延迟，在任务响应时间的平滑性、任务的吞吐率要比传统的算法好。
2 智能算法的研究
2.1 模拟退火算法
模拟退火算法是一种基于概率的算法，最早于1953年由N.Metropolis等人提出重要性采样法，以概率接受新状态，被称为Metropolis准则。1983年，Kirkpatrick等提出模拟退火算法，并将其应用于组合优化问题的求解。模拟退火算法起源于物理退火的过程，其基本思想是：将固体加温至非常高的温度，
再让其慢慢的冷却。加温时固体内部的粒子呈现出无序状，内能增大，而在冷却时粒子渐渐有序，每个温度都达到平衡状态，最后在常温时达到基态，俗称等温过程。最后，算法的一个重要参数叫做冷却进度表，它控制参数的初值和衰减函数对应于马尔尔科夫链的长度和终止条件，这也叫做冷却过程。而根据Metropolis准则［7］，粒子在温度T时趋于平衡的概率为e-ΔE/（KT），其中E为温度T时刻的内能，ΔE为其该变量，K为Boltzmann常数。 2.2 粒子群算法
基本粒子群算法［6］（Patricle Swarm Optimization，PSO）其根源于对鸟群觅食行为的研究。粒子群算法主要解决连续优化的问题。它的具体描述如下：设在一个n维空间中，粒子群中有X个粒子组成，每个粒子都是这n维空间中的一个可能解。每个粒子表示为：Xi=（Xi1，Xi2，…，Xiq）；每个粒子对应的速度可以表示为Vi=（Vi1，Vi2，…，Viq）；每个粒子在进行搜索时要考虑的两个因素：自己搜索到的历史最优值和全部粒子搜索到的最优值。 2.3 遗传算法
遗传算法（Genetic Algorithm）是一种模拟生物进化论中自然选择过程的计算模型，是较经典的搜索最优解的方法。在遗传算法中，首先会生成一组候选解，然后根据适应度函数计算每个候选解的适应度，并根据适应度的大小对种群进行选择操作，适应度大者生存，适应度小者被淘汰。最后，对保留的个体进行交叉、变异操作，以产生出更优的个体。传统遗传算法具有全局解空间搜索和并行性两个显著优点，同时也存在早熟等现象。
3 混合调度与最优性原理
任务的最优性是指：不论是在批处理系统还是在分时系统中，对于前面决策所
Cloudsim中基于智能算法的任务调度研究
