- 1、本文档共6页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
基于有向无环图的时间-费用优化调度算法.pdf
第31卷第3期 衡阳师范学院学报 No.3V01.31
20 1 of Normal
0年6月 JournalHengyangUniversity June.2010
基于有向无环图的时问一费用优化调度算法
王 樱1’2,李 琳2,王 杰2
(1.湖南大学计算机与通信学院,湖南长沙410082;
2.衡阳师范学院计算机科学系,湖南衡阳421008)
摘 要:在网格计算环境中,基于时间限制和费用最小的有向元环图(DAG)调度算法,运用了经济规律把网
格用户的任务映射到网格资源中运行。该文综合考虑时间、费用以及任务间的优先关系等诸多QoS需求,提出
了基于有向无环图的优化调度算法。通过仿真实例,论证了该算法的优越性。
关键词:有向无环图;网格计算;调度算法
中图分类号:TP301.6 文献标志码:A 文章编号:1673—0313(2010)03—0084—04
网格环境下任务间的依赖关系对传统的调度策略
0引言
提出了新的挑战。如何解决任务之间的优先关系?
在网格环境下,资源广域分布、异构、动态且有 有向无环图DAG是一个比较有用的工具。本文将
多个管理域,这些资源为不同的组织拥有,各组织 对DBC算法提出改进,用有向无环图DAG来表示
对资源的管理机制、策略、费用和目标都不尽相同。 任务问的依赖关系,同时考虑了时间、费用、任务间
传统调度只考虑系统性能,而忽视了用户的服务质 的依赖关系等因素,提出比较符合现实情况的基于
Greed—
量要求,如文献[1巧]介绍的OLB,UDA,Fast有向无环图的优化调度算法。
Y,Min—Min,Max-Min,Sufferage,GSA等,追求最
1优化调度算法
小Makespan是这些算法的主要目标。但这些资源
管理和调度算法均不能很好地满足实际网格环境。 1.1 算法基本思想
对网格用户而言,希望提交的任务在尽可能短的时 基于费用一时间优化的网格调度问题主要解
间内,以尽可能低的价格获得尽可能高安全可靠的 决在不增加总完成时间Makespan的基础上,减少
服务。而基于网格经济模型最有效的任务调度算 总的费用Cost。在网格环境中,一个网格应用T往
法是时间成本限制下的时间优化、成本优化调度算 往需要由多个任务协同完成。在一个由竹个任务构
法(DBC)[6{]。该算法可以简单表述为N个用户,
成的网格应用中,根据任务间的依赖关系可以生成
每个用户有M个任务,并且任务相互独立,无依赖 一个DAG图(图1所示),用户任务集合W={W。,
关系,可调度到任意资源上执行,同时每个用户都 Wz,…,W。}。从锄。到W。的有向边,表示任务硼。
有一定的终止时间和成本预算限制。然而网格计 和W。之间存在依赖关系,W。只有在W。执行完成
算[91中,一个大型的应用程序往往被分解为具有依 后才能执行。从图中可得到每个任务结点的入度
赖关系的多个任务。任务与任务之间可能存在着 和出度。如果结点的入度为0,出度大于0,则这个
优先运行的关系,在资源个体差异较大、广域互连的 结点称为源点;如果结点的人度大于0,出度为0,则
收稿日期:2010—03一01
基金项目:湖南省教育厅科研资助项目(07COl6)
作者简介:王樱(1970一),女,湖南龙山人,副教授,主要研究方向是网格计算.
万方数据
20lo年第3期
您可能关注的文档
- 基于无线传感器网络的电机运行状态监测系统设计.pdf
- 基于无线传感器网络的电网现场作业管理系统的设计与应用.pdf
- 基于无线传感网的变配电监控系统.pdf
- 基于无线传输的高速列车轴温集中监测系统.pdf
- 基于无线宽带城域网的城市环境监测系统结构化设计.pdf
- 基于无线射频识别(RFID)技术的肉制品安全监控系统模糊综合评价.pdf
- 基于无线异步转移模式ATM的IP技术.pdf
- 基于无线控制的小区车辆出入管理系统的设计.pdf
- 基于无线测控专网的车队监控系统及其应用研究.pdf
- 基于无线组网技术的交通信息采集方法研究.pdf
- 2023-2024学年广东省深圳市龙岗区高二(上)期末物理试卷(含答案).pdf
- 2023-2024学年贵州省贵阳市普通中学高一(下)期末物理试卷(含答案).pdf
- 21.《大自然的声音》课件(共45张PPT).pptx
- 2023年江西省吉安市吉安县小升初数学试卷(含答案).pdf
- 2024-2025学年广东省清远市九校联考高一(上)期中物理试卷(含答案).pdf
- 广东省珠海市六校联考2024-2025学年高二上学期11月期中考试语文试题.pdf
- 2024-2025学年语文六年级上册第4单元-单元素养测试(含答案).pdf
- 2024-2025学年重庆八中高三(上)月考物理试卷(10月份)(含答案).pdf
- 安徽省安庆市潜山市北片学校联考2024-2025学年七年级上学期期中生物学试题(含答案).pdf
- 贵州省部分校2024-2025学年九年级上学期期中联考数学试题(含答案).pdf
文档评论(0)