基于QoS约束的云工作流任务调度模型与算法研究
发布时间:2024-08-29
发布时间:2024-08-29
中国科学技术大学
硕士学位论又基于QoS约束的云工作流任务
调度模型与算法研究
作者姓名:刘文娟
学科专业:计算机系统结构
导师姓名:陈华平教授完成时间:二。一二年四月十九日
l帅帅舢哪哪咖删哪帅删
Y2125672
ofChinaandofScienceTechnologyUniversity
Adissertationformaster’SdegreeResearchonthecloudworkflow
taskschedulingModel
andAlgorithmwhich
basedontheQoSconstraintsAu曲or’sName:WenjuanLiu
Specialty:ComputerSystemStructureS—。upervi。sor:Prof.HuapingChenFinishedtime:April19伽,2012
中国科学技术大学学位论文原创性声明
本人声明所呈交的学位论文,是本人在导师指导下进行研究工作所取得的成果。除己特别加以标注和致谢的地方外,论文中不包含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确的说明。
作者签名:.弛复蝎签字同期:垫12,皇,叠
中国科学技术大学学位论文授权使用声明
作为申请学位的条件之一,学位论文著作权拥有者授权中国科学技术大学拥保密的学位论文在解密后也遵守此规定。
电仫开口保密(——年)
作者签名:皇11室安马导师签名:
签字F|期:21121皇!翌签字同期:有学位论文的部分使用权,即:学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借阅,可以将学位论文编入《中国学位论文全文数据库》等有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。
摘要
摘要
云计算是近些年新出的一个热门名词,它从提出到现在一直受到了各大企业、高校以及政府的重视并很快成为众多厂商竞相研究的技术。随着云技术的同益成熟,越来越多的云产品开始问世并正式为用户服务。在云产品被大家广泛使用的同时,云技术也遭受到了更严峻的考验,一些诸如安全、效率、兼容性等诸多问题都开始显现出来。而其中一个亟待解决的问题就是云计算中的调度问题,它贯穿了云计算中从底层资源到上层服务的整个过程,在云计算中占有很重要的地位。
目前在云计算中广泛使用的是一些智能调度算法,它们性能比较好但是丌销太大,而传统的简单调度算法虽然效率较高但调度效果差强人意,所以它们都不太适合在云计算系统中运用。为了解决云计算中的这些调度问题,本文对现有的调度模型和调度算法进行了详细的调研和总结,并且通过对不同调度模型优缺点和适用环境的分析,得出结论:云计算中高效的调度模型应该是结合了分布式和层次式模型的动态调度模型。基于此本文提出了一种基于QoS约束的智能云调度模型和一个满足用户截止时间的银行家调度算法。
本文所提出的智能云调度模型主要由预处理器模块、主调度器模块和本地调度器模块三个重要部分组成,还包括划分策略库、云任务特征信息库、云空闲资源信息和本地云资源信息四个存储部分。当工作流任务被提交后,首先预处理器会将其划分为一系列的元任务并对元任务做出相应的需求分析和特性判断,而后主调度器根据元任务的特性将它们分别分配到相应的本地调度器上进行最终调度,最后本地调度器根据特定的调度算法使元任务得到调度并在本地资源上得以执行。云系统中用户最关心的问题就是能否满足任务的截止时问,针对此本文提出了一种银行家调度算法供本地调度器使用,它借助操作系统中经典银行家算法中“试分配”和“安全序列”的思想来保证使每个任务满足其截止时问。
本文在最后对银行家调度算法在云计算仿真平台CloudSim环境下进行了仿真实验。实验将本文调度算法与传统的Min.Min及Min—Max算法做了比较,结果表明本文调度算法在满足任务截止时间、减少费用和提高系统性能等方面比传统的任务调度算法更加优秀。
关键字:云计算CloudSim平台智能云调度模型银行家调度算法QoS标准截I匕时间
摘要
Abstract
ABSTRACT
Cloudcomputingwhichisverypopularfromitsproposinguptonowhassoondrawnmostcompanies,universitiesandevengovernments’attentionsandthenbecameonekindofmajormanufacturerscompetingresearchtechnologies.Withcloudtechnologies’development,moreandmorecloudproductshaveemergedandbegantoserviceforcustomers.Whilecloudproductsarewidelyused,thecloudtechnologieshavetofaceseverertests,suchassecurity,efficiencyandcompatibilitypi'oblems.Onemosturgentandimportantproblemistheschedulingprobleminthecloudcomputing,whichexiststhroughtheunderlyingcloudresourcestotheupperservices.
Intelligentschedulingalgorithmisoftenusedincloudcomputingwhichhasgoodperformancebutcoststoolongtime,whilethesimpleschedulingalgorithmcostlesstimebutresultisnotSOgood,SOboththeyarenotsuitableforreal—timecloudcomputingsystems.Inordertobettersolvetheschedulingproblem,adetailsurveyontheadvantagesandapplicabilityoftheexistingschedulingmodelsandschedulingalgorithmshasbeencarriedout.Theconclusionshowsthattheschedulingmodelinthecloudcomputingshouldbeadynamicschedulingmodelwhichcombinesdistributedandhierarchicalschedulingmodel.Consequently,thearticleproposesanintelligentcloudschedulingmodelwhichbasedontheQoSconstraintsandabanker’Sschedulingalgorithmwhichcansatisfytasks’deadline.
Theintelligentcloudschedulingmodelincludesthreeprocessingpartswhicharethepre—processormodule,themainschedulingmoduleandthelocalschedulingmoduleandfourstoragepartswhicharethepartitioningstrategieslibrary,thecloudtaskcharacteristicslibrary,theidlecloudresourcesinformationlibraryandthelocalcloudresourcesinformationlibrary.Whenaworkflowtaskispresented,thepre-processorwilldivideitintoaseriesofmeta-tasksandjudgetheirneedsandcharacteristics.Then,themainschedulerrespectivelyassignedthemeta—taskstothelocalscheduleraccordingtotheircharacteristics.Becausecloudusersaremainlyconcernedwithsatisfyingthetasks’deadline,anovelstrategythatnamedbanker’SschedulingalgorithmusedonthelocalschedulerisproposedtoaddressthisissueThisalgorithmusesthe“trialdistribution”and‘‘securitysequence”ideasoftheclassicbanker。SalgorithmintheoperatingsystemtoensurethateachtaskcouldIII
Abstract
satisfyitsdeadline
Finally,computationalexperimentsareperformedintheCloudSimenvironmenttotesttheeffectivenessofthebanker’sschedulingalgorithm.TheexperimentoftheschedulingalgorithmiscomparedwiththetraditionalMin—MinandMin‘Maxalgorithm.Theresultsshowthatthebanker’sschedulingalgorithmoutperformsthetwotraditionalalgorithmsintermsofmeetingdeadline,min。i。mi‘zin‘gcostandimprovingsystemperformance.
Key’words:Cloudcomputing,CloudSimplatform,IntelligentCloudscheduling
model,Banker。sschedulingalgorithm,QoS,deadlineIV
目录
目录
第l章绪论………………一…………………………….11.1研究背景………………………………………………11.1.1云计算概述………………………….……………………..11.1.2云调度及其重要性…………………………………….….….31.1.3QoS标准简介………………………………………….…...31.2研究现状………………………………………………41.2.1国内外研究成果………………………….…….…….……..41.2.2当前研究存在的问题……………………………...….………51.3研究内容………………………………………………61。4论文结构…………………………....………………..7第2章云平台下的调度算法研究………………..……..92.1云平台简介…....……………...……………………...92.1.1Google的云计算平台……。...….......…..……........…...…92.1.2Amazon的弹性计算云.…....…......…..…....……..….…...102.1.3IBM“蓝云”计算平台.….…..…........….…….....…..…...102.2云工作流任务...………......……...………..…...…..1l2.2.i工作流任务概述……….………………….…….….……...112.2.2云工作流任务…………………….………………….…….122.3云任务调度算法...………….....………………………132.3.1调度算法概述…….…………,…………….….…….….…..132.3.2常用调度算法简介.………………………….….…….…….132.4本章小结.…….....………...……...一…....... . … lb第3章基于QoS约束的智能云调度模型…………………173.1调度模型分类………………………………………….173.1.1集中式调度模型…………….….…….….…………….…..173.1.2分布式调度模型…….………………….………….……….183.1.3层次式调度模型…….….….…………….….…….……….19V
目录
3.1.4静态和动态调度模型.....…........................................203.2智能云调度模型的提出…….…………………………….203.2.1智能云的提出…………….…….….……...…...…..…….203.2.2智能云调度框架..…....….…….…….….….....…....……2l3.2.3智能云调度思想.……………-……………………….……..223.3智能云调度模型详解.……………………………一…….243.3.i预处理器模块….……………………….…….……..…….243.3.2主调度器模块……….……………..……….….………….253.3.3本地调度器模块….……………….…………….………….273.4智能云调度模型的特点……………………...…………..283.5本章小结.......….……..……...’…………….……….29第4章满足任务截止时间的银行家调度算法.…...….……314.1银行家调度算法的由来...…...........…….......…….....3l4.1.I调度算法思考………………………………………………314.1.2经典银行家算法简介…….……………….……..…………..324.2调度问题模型……….……………………...…………334.2.1问题描述........…....….…..…………................……334.2.2基本定义...............….....….………......……...….…344.3本文调度算法……....…..…...………….......…..….354.3.I算法思想…….….…………………………....………….354.3.2算法伪码.......…....…..…...….…….....…...…......…384.3.3算法特点….…….......…….…….…....……..………...404.4本章小结….................….………….......…....….40第5章CloudSim仿真实验.一…...……….………....435.1实验环境......…......….…………….……..……….435.i.1CloudSim介绍......…....…........….…....…….....…....435.1.2实验配置........….............…….............….....…....445.2实验结果与分析…….………………………...……….455.2.I性能指标………..………….……………...…………….455.2.2实验结果比较……………….…....…………………….…455.3本章小结....….…..…...…........…………......…..47VT
目录
第6章结论与未来工作.………………….......……496.1本文总结..……….……..…………………….….….496。2未来工作……………………………………………..49参考文献………………………………………………….51致谢…………………………………………………….55个人简历、在读期间发表的论文及研究成果……………………….57VII
VIII
第1章绪论
第1章绪论
云计算是目前IT界最热门的词汇之一,而云技术也被各大IT厂商竟相研究。随着各种云产品的推出和盛行,云计算中的调度问题也显得越来越重要了。该问题,即按照某种次序为云任务分配到最合适它的云资源,从而使任务得以执行。调度算法是否能按最合理的次序找到最合适的资源,将会直接影响云任务的执行效率和云资源的负载平衡,进而影响到云用户的认可度和云系统的性能。调度的好坏可以使用国际公认的QoS标准来衡量,本文所研究的主要内容就是基于满足QoS标准的调度模型和调度算法。在详细介绍本文内容之前,先在本章介绍了该研究课题所处的现实背景和当前状况,再在此基础上阐明本文将要研究的主要内容,并在最后给出了本文的组织结构。
1.1研究背景
本节讲述了云计算的由来、概念以及其服务给社会各方面所带来的变革,进而阐述了云计算中的调度问题及其重要性。此外,由于本文是基于QoS标准提出的调度模型和算法,所以本节在最后着重介绍了该标准。
1.1.1云计算概述
近些年,“云计算”可谓炙手可热。那么“云计算”是怎么来的,究竟什么是“云计算"呢?MichaelAeta1.(2010)在《云计算之上:伯克利对云计算的展望》这篇报告中指出:云计算一直以来都作为--300效用计算的新名词,最近以一种商业现实的形式涌现。云计算是既指通过Internet作为服务发布的应用程序,也指提供这些服务的数据中心中的软硬件。这些服务一直以来都被称为SaaS(SoftwareaSaService),而数据中心的软硬件就是我们称之为云。另外,云还可以分为公有云和私有云,其中公有云销售的服务是效用计算,用户可以以即用即付费的方式使用,而私有云通常用来描述一个商业或其他机构对外不可用的内部数据中心。
以上可以看出,云计算并不是凭空出来的新技术,它是在“saas”、“效用计算”等原有技术的基础上发展而来的。实际中,“云计算”中的“云”就是云资源,主要是指大型数据中心的服务器集群,该资源可以分为硬件资源(如计算机、I/O设备等)和软件资源(如开发平台、应用程序等)。云用户仅需要在门户网站
第1章绪论
上将任务提交到云系统上,任务便被分配资源执行并很快得到结果。“云计算”可以根据其提供服务范围不同有广义和狭义之分:广义的“云计算”为用户提供的是云服务的交付和使用。其中,云服务包括基础设施、软件和互联网的相关使用,或者是其他服务。而狭义的“云计算”是仅为用户提供基础设施的交付和使用,提供的服务种类相对较少。无论广义还是狭义,“云计算”目的都是为用户提供按需可扩展的服务,由于云资源是大量用网络连接的主机,所以为用户提供服务的前提对其进行统一管理和调度。
总的来说,“云计算”可以为我们提供三种服务(中国云计算网,2010)。分别是:
软件即服务(SaaS):SaaS服务提供商在公司内部的服务器上对软件进行统一部署、升级和管理,用户可以通过网络向厂商购买所需软件服务,厂商将根据用户所需软件的种类、使用的时间等因素进行其进行收费和提供相应服务。目前,Salesforce.corn公司提供这类服务是很有名的,GoogleDoc,GoogleApps和ZohoOffice等也都是这类服务。
平台即服务(PaaS):PaaS(PlatformasaService)是一种分布式平台服务,它把开发平台作为一种服务提供给应用开发者使用。厂商提供了硬件资源和开发环境,用户便可以在此平台上开发、部署和运营自己的应用程序,也可以将开发好的应用任务提交到该平台上执行。谷歌的AppEngine、Salesforce的force.corn平台等都很受用户欢迎。
基础设施即服务(IaaS):IaaS(InfrastructureasaService)是指厂商将自己数据中心中的服务器集群构成云计算的基础设施,再将其作为服务提供给用户。它将内存、带宽、存储和计算能力虚拟化为统一的资源池为用户提供其所需的存储和计算资源等服务。用户付费使用厂商的硬件资源,相关的IT部门可付费使用IaaS服务来构建部门服务器,从而节省成本。目前有亚马逊的Web服务和IBM的“蓝云”等都是提供IaaS服务。
云计算确实给IT行业带来了很大的变革:首先,对于开发者们来说,不再需要大型的专有硬件来部署他们的应用,同时也不用花费大量的人力成本来管理它们。而是可以直接在现有云平台上开发、部署和运营他们的应用程序,完全不需要考虑程序以外的事情。需要时,云平台会根据应用程序的实际客流情况,来为其增加或减少资源,从而实现即用即付费的弹性收费制度。这不仅缩短了开发时间,而且大大降低了成本。其次,也会给云提供商带来很大收益。例如,亚马逊在线商城,它们为了满足网上购物高峰,购买了大量的服务器来扩大数据中心。可是,这些主机在大部分时间是空闲的,不仅用不到,而且会浪费水费电费和厂房等费用。现在,他们可以利用“云计算”技术,把数据中心中闲置的资源构成2
上一篇:电池保护板系列规格参数(1)
下一篇:校园网混合组建设计方案