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

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

1、第38卷第24期计算机工程2012年12月Vol.38No.24ComputerEngineeringDecember2012·云计算专题·文章编号：1000—3428(2012)24—0017—04文献标识码：A中图分类号：TP391基于任务备份的云计算容错调度算法abb廖福蓉，王成良，陈蜀宇(重庆大学a.计算机学院；b.软件学院，重庆400030)摘要：云计算所提供的服务面向庞大的用户群，随着节点规模的扩大、任务执行时间的增长，云计算的故障率越来越高。为此，提出基于任务备份的云计算容错调度算法。将任务映射到含有该任务输入数据且负载最小的节点，根据

2、云计算的安全等级将任务进行备份，并重新调度失败任务。仿真实验结果表明，该算法具有较好的容错性，任务调度成功率达到99%。关键词：容错；任务备份；云计算；任务调度；数据本地性Fault-tolerantSchedulingAlgorithmforCloudComputingBasedonTaskBackupabbLIAOFu-rong,WANGCheng-liang,CHENShu-yu(a.CollegeofComputerScience;b.CollegeofSoftwareEngineering,ChongqingUniversity,Chong

3、qing400030,China)【Abstract】Theserviceofcloudcomputingfacesthehugeusergroup,withtheexpansionofnodescaleandthegrowthoftaskexecutiontime,thefailurerateofcloudcomputingisincreased.Tosolvethisproblem,thefault-tolerantschedulingalgorithmforcloudcomputingbasedontaskbackupisproposed.It

4、mapstasktothenodewhichcontainstheinputdataofthetaskandtheloadisthesmallest.Accordingtothelevelofcloudcomputingsecurity,itbackupsthetask,andre-schedulesforthefailuretask.Simulationexperimentalresultsshowthatthealgorithmhasgoodfaulttolerance,andthesuccessrateoftaskschedulingis99%

5、.【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,

6、n)表示任务G点，由于资源的高度动态性和异构性，使得云计算平台较t∈T的输入数据在节点n∈N上。Ntpre()表示图G中，含传统的计算平台有更大的出错机率。为此，在云计算任务有任务t输入数据的所有节点的集合。调度过程中，必须考虑容错这一问题，以保证任务调度具定义2(分配函数)分配函数即为映射f:TN，表示有容错性。目前已知的大部分云计算任务调度算法，如将任务t分配到节点f(n)上。如果对所有任务tT,f(n)都[2][3]BAR调度算法、延迟调度(delayscheduling)算法、基存在，那么该分配函数是完全分配，否则是部分分配。[4]于最

7、小代价流的调度模型，都只关注数据的本地性和任是一个分配函数，如果任务t是本地任务当且仅当()t存务的公平性，忽略了任务容错机制。文献[5]采用同步错位在且在数据图G中存在一条边e(t,α(t))，否则任务t是远技术分别对主任务和备份任务进行调度，但其只关注了任程任务。让l和r分别表示本地任务数量和远程任务数量。务执行成功率，没有考虑数据的本地性。由于节点间带宽定义3(任务代价)任务在节点上的执行时间和输入的限制，数据本地性是云计算任务调度必须考虑的问题之数据传输时间的总和称为任务代价。Ct(,)表示任务t在[6][2]一。本文借鉴了BAR调度算法

8、和简单自适应备份算节点()t上的执行时间，定义为：[7]法的思想，提出一种基于任务备份的容错调度算法C