基于任务备份的云计算容错调度算法

《基于任务备份的云计算容错调度算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

第38卷第24期计算机工程2012年12月Vol.38No.24ComputerEngineeringDecember2012·云计算专题·文章编号：1000—3428(2012)24—0017—04文献标识码：A中图分类号：TP391基于任务备份的云计算容错调度算法abb廖福蓉，王成良，陈蜀宇(重庆大学a.计算机学院；b.软件学院，重庆400030)摘要：云计算所提供的服务面向庞大的用户群，随着节点规模的扩大、任务执行时间的增长，云计算的故障率越来越高。为此，提出基于任务备份的云计算容错调度算法。将任务映射到含有该任务输入数据且负载最小的节点，根据云计算的安全等级将任务进行备份，并重新调度失败任务。仿真实验结果表明，该算法具有较好的容错性，任务调度成功率达到99%。关键词：容错；任务备份；云计算；任务调度；数据本地性Fault-tolerantSchedulingAlgorithmforCloudComputingBasedonTaskBackupabbLIAOFu-rong,WANGCheng-liang,CHENShu-yu(a.CollegeofComputerScience;b.CollegeofSoftwareEngineering,ChongqingUniversity,Chongqing400030,China)【Abstract】Theserviceofcloudcomputingfacesthehugeusergroup,withtheexpansionofnodescaleandthegrowthoftaskexecutiontime,thefailurerateofcloudcomputingisincreased.Tosolvethisproblem,thefault-tolerantschedulingalgorithmforcloudcomputingbasedontaskbackupisproposed.Itmapstasktothenodewhichcontainstheinputdataofthetaskandtheloadisthesmallest.Accordingtothelevelofcloudcomputingsecurity,itbackupsthetask,andre-schedulesforthefailuretask.Simulationexperimentalresultsshowthatthealgorithmhasgoodfaulttolerance,andthesuccessrateoftaskschedulingis99%.【Keywords】fault-tolerance;taskbackup;cloudcomputing;taskscheduling;datalocalityDOI:10.3969/j.issn.1000-3428.2012.24.0051概述2相关理论随着互联网的发展，数据量飞速增加，人们对计算机定义1(数据图)数据图由一个二部图G=(T∪N,E)表计算能力的需求也与日俱增，价格低廉且具备超级计算能示，T是任务的集合，N是计算节点(以下称为节点)的集[1]力的云计算应运而生。任务调度是云计算的重点与难合，E⊆T×S是T和S之间边的集合，边e(t,n)表示任务G点，由于资源的高度动态性和异构性，使得云计算平台较t∈T的输入数据在节点n∈N上。Ntpre()表示图G中，含传统的计算平台有更大的出错机率。为此，在云计算任务有任务t输入数据的所有节点的集合。调度过程中，必须考虑容错这一问题，以保证任务调度具定义2(分配函数)分配函数即为映射f:TN，表示有容错性。目前已知的大部分云计算任务调度算法，如将任务t分配到节点f(n)上。如果对所有任务tT,f(n)都[2][3]BAR调度算法、延迟调度(delayscheduling)算法、基存在，那么该分配函数是完全分配，否则是部分分配。[4]于最小代价流的调度模型，都只关注数据的本地性和任是一个分配函数，如果任务t是本地任务当且仅当()t存务的公平性，忽略了任务容错机制。文献[5]采用同步错位在且在数据图G中存在一条边e(t,α(t))，否则任务t是远技术分别对主任务和备份任务进行调度，但其只关注了任程任务。让l和r分别表示本地任务数量和远程任务数量。务执行成功率，没有考虑数据的本地性。由于节点间带宽定义3(任务代价)任务在节点上的执行时间和输入的限制，数据本地性是云计算任务调度必须考虑的问题之数据传输时间的总和称为任务代价。Ct(,)表示任务t在[6][2]一。本文借鉴了BAR调度算法和简单自适应备份算节点()t上的执行时间，定义为：[7]法的思想，提出一种基于任务备份的容错调度算法Ctloc是本地任务Ct(,)(1)(FT-scheduling)。该算法在兼顾数据本地性的同时，采用Crem其他任务备份来实现系统的容错。称C和C分别为本地代价和远程代价。因为本地locrem————————————基金项目：重庆市教委科学技术研究基金资助项目(KJ100506)作者简介：廖福蓉(1987－)，女，硕士研究生，主研方向：云计算，数据挖掘；王成良，教授、博士；陈蜀宇，教授收稿日期：2012-03-19修回日期：2012-05-24E-mail：liaofurong@foxmail.com 18计算机工程2012年12月20日任务读取数据的时间可以忽略，所以本地代价等于任务执Cloc为1，远程代价函数Crrem()10.1r。有2个远程任行时间，而远程代价等于执行时间与数据传输时间的总务，因此，远程代价Crem()10.121.2。由式(3)和和。为简单起见，假设所有任务的执行时间相同。对于所式(4)，节点的负载分别为：有分配，本地代价是常量，由于远程任务要竞争网络资源，Ln17.1因此远程代价随着远程任务数量增加而增加。令：Ln24.2317.2CCrem()r(2)Ln30.321+21.24.7其中，Crem()是单调递增函数；r是远程任务数量。由于n1没有分配任何任务，因此Sass是nn23,。由定义4(节点负载)节点n的负载表示在分配函数式(6)可得，makespan7.2。下，完成所有任务花费的时间，由以下定义：3FT-Scheduling调度算法inittaskLL()L()(3)nnn定义5(本地分配)是一个分配函数，在该分配下，init其中，L表示节点n的初始负载。n如果所有的任务都是本地任务，则称为本地分配。taskLC()(,)t(4)nttn:()定义6(平衡分配)数据图G=(T∪N,E)，本地花费为表示节点n完成分配给它的所有任务的时间。令：Cloc，是本地分配函数，是平衡分配，当且仅当：Snass|,tTtn()(5)tTL()()tCloc≤minGLn()(7)nSpre表示所有被分配任务的节点。对于每个节点n，如果其中，L()和L()由式(3)计算。n()tsS，那么n是活动的。在分配函数下，完成所有任ass性质是平衡分配，在该分配下，所有任务都分配务的时间定义为：给含有该任务输入数据且负载最小的节点，因此在该平衡makespanmaxL()(6)nnSass分配下，完成任务的总时间最小。基于以上定义，调度问题可以如下描述：给定一个数BAR算法[3]的主要思想为：给定数据图G，系统初始据图G=(T∪N,E)，本地代价C，远程代价C()和初始initlocrem负载L和本地代价C。对每个新到的任务t，若将其分lociinit负载L，找到一个完全分配使makespan达到最小。配给含有该任务输入数据且负载最小的节点n，负载为i数据图G如图1所示，有7个任务和3个节点，每个L()；若将其分配给所有节点中负载最小的节点n，负nij任务都有2块输入数据。载为L()，若分配给n，t属于远程任务，此时要计算njji远程代价。比较L()和L()的大小，若L()