基于多服务质量属性联合效用函数的网格资源调度

D01:10.13374j.isml00103x2006.11.019 第28卷第11期 北京科技大学学报 Vol.28 No.11 2006年11月 Journal of University of Science and Technology Beijing Now.2006 基于多服务质量属性联合效用函数的网格资源调度 刘 丽)杨 扬) 刘美佳到陶丽红) 1)北京科技大学信息工程学院.北京1000832)北京起重运输机械研究所，北京100007 摘要基于经济模型研究网格服务质量(QS)控制的资源分配问题，给出了多QS属性多任务 的资源分配优化的效用模型.该效用模型描述了网格任务的动态需求和偏好.以效用最大化为目 标计算了需要提供OS的资源分配.设计了时间和预算限制条件下基于多0S属性的联合效用 函数调度算法，并与其他经济的和非经济的算法进行比较，验证了该算法的有效性. 关键词网格：服务质量效用模型：资源调度 分类号TP311 网格技术已经成为当前国内外研究的热点和 tual applicat ion service,.VAS)的体系结构可来管 前沿领域，而服务质量(quality of service,QoS)作 理计算网格中的QS:VAS是扩展了的网格服 为网格资源管理研究的重要内容之一，逐渐成为 务，主要目标是使有特定最终期限约束的实时服 网格研究的焦点.Foster等提出判断网格的三个 务更易得到执行.文献[刀引入市场经济学的理 准则之一就是“提供非凡的服务质量”川，面向服 论方法研究了分布式系统调度问题在Nim rod/. 务的体系结构是网格的典型结构.新一代开放网 G系统中给出了经济的调度算法：该算法只考虑 格体系结构(open grid service architecture, 了时间最优化或服务费用最优，没有综合反映出 OGSA)的目标就是通过跨分布式异构平台管理 应用和任务对不同QS的偏好和效用 资源来交付高质量的服务.在面向服务网格环境 中，用户关心的服务质量包括很多重要因素，而且 2 网格QoS控制的效用模型 不同应用需要不同级别的Q$,因此需要灵活的 基于经济的网格QS控制模型把提供QoS 网格调度策略.目前多数网格作业管理系统是从 保障的网格服务看作服务市场，QS的生产者是 传统的批作业管理的角度出发，研究重点放在系 网格服务提供者代理QoS的消费者是用户或应 统级调度策略或算法的优化方面，缺乏针对服务 用的需求代理，交易对象是具有一定QoS级别的 网格应用需求变化的有效支持.本文在QS相关 服务，由网格服务提供者以资源为生产要素生产 研究基础上，针对Q0S管理和控制问题并结合经 出不同级别的QoS产品.用户或应用对QoS的 济学生产一消费模型，建立了网格资源分配的 偏好由效用函数确定，优化目标是通过资源分配 效用模型，研究如何根据用户或应用描述的服务 提供给用户QoS保障使得整体效用最大化. 级效用函数来指导动态资源调度，以效用最大化 21QoS需求模型 为目标设计了多QS属性调度算法. 假设对于任务集合中的一个任务i,都有 1 相关研究 QoS需求集合Q:={Qi1,,Qd,}(1≤i≤n, d,=Q),同时用效用函数表示用户从完成任 网格QS研究还处于基础研究阶段，且主要 务中获得的QS满意程度，效用函数u:·Q:→ 是针对网格QS体系结构的研究，代表性研究包 R,R为非负实数空间.任务集中所有任务或 括基于Globus的预留和分配体系结构 (GARA)I4以及网格QoS管理体系结构(G一 应用的总效用为∑“(Q系统优化目标是最 QoSM).Keahey等提出了虚拟应用服务(vir 大化总效用，表示为：max (0,s.t 收稿日期：2005-09-06修回日期：200603-27 i=1 基金项目：国家自然科学基金资助项目(Na.90412012) pQ≤w,其中w表示第i个请求代理的预算 作者简介：刘丽(1968一)，女，副教授：杨扬(1955一)，男，教 授牌O20 China admou ero Pu用表不思对获得的C的满意程度用之ki.net

基于多服务质量属性联合效用函数的网格资源调度 刘 丽1) 杨 扬1) 刘美佳2) 陶丽红1) 1) 北京科技大学信息工程学院, 北京 100083 2) 北京起重运输机械研究所, 北京 100007 摘 要 基于经济模型研究网格服务质量( QoS) 控制的资源分配问题, 给出了多 QoS 属性多任务 的资源分配优化的效用模型.该效用模型描述了网格任务的动态需求和偏好, 以效用最大化为目 标计算了需要提供 QoS 的资源分配.设计了时间和预算限制条件下基于多 QoS 属性的联合效用 函数调度算法, 并与其他经济的和非经济的算法进行比较, 验证了该算法的有效性. 关键词 网格;服务质量;效用模型;资源调度 分类号 TP311 收稿日期:2005 09 06 修回日期:2006 03 27 基金项目:国家自然科学基金资助项目( No .90412012) 作者简介:刘 丽( 1968—) , 女, 副教授;杨 扬( 1955—) , 男, 教 授, 博士生导师 网格技术已经成为当前国内外研究的热点和 前沿领域, 而服务质量( quality of service, QoS) 作 为网格资源管理研究的重要内容之一, 逐渐成为 网格研究的焦点.Foster 等提出判断网格的三个 准则之一就是“提供非凡的服务质量” [ 1] , 面向服 务的体系结构是网格的典型结构 .新一代开放网 格体 系 结 构 ( open g rid service architecture, OGSA) 的目标就是通过跨分布式异构平台管理 资源来交付高质量的服务 .在面向服务网格环境 中, 用户关心的服务质量包括很多重要因素, 而且 不同应用需要不同级别的 QoS, 因此需要灵活的 网格调度策略.目前多数网格作业管理系统是从 传统的批作业管理的角度出发, 研究重点放在系 统级调度策略或算法的优化方面, 缺乏针对服务 网格应用需求变化的有效支持 .本文在 QoS 相关 研究基础上, 针对 QoS 管理和控制问题并结合经 济学生产-消费模型[ 2-3] , 建立了网格资源分配的 效用模型, 研究如何根据用户或应用描述的服务 级效用函数来指导动态资源调度, 以效用最大化 为目标设计了多 QoS 属性调度算法. 1 相关研究 网格 QoS 研究还处于基础研究阶段, 且主要 是针对网格 QoS 体系结构的研究, 代表性研究包 括 基 于 Globus 的 预 留 和 分 配 体 系 结 构 (GARA) [ 4] 以及网格 QoS 管理体系结构( G - QoSM) [ 5] .Keahey 等提出了虚拟应用服务( vir￾tual application service, VAS) 的体系结构[ 6] 来管 理计算网格中的 QoS ;VAS 是扩展了的网格服 务, 主要目标是使有特定最终期限约束的实时服 务更易得到执行.文献[ 7] 引入市场经济学的理 论方法研究了分布式系统调度问题, 在 Nimrod/ G 系统中给出了经济的调度算法;该算法只考虑 了时间最优化或服务费用最优, 没有综合反映出 应用和任务对不同 QoS 的偏好和效用 . 2 网格 QoS控制的效用模型 基于经济的网格 QoS 控制模型把提供 QoS 保障的网格服务看作服务市场, QoS 的生产者是 网格服务提供者代理, QoS 的消费者是用户或应 用的需求代理, 交易对象是具有一定 QoS 级别的 服务, 由网格服务提供者以资源为生产要素生产 出不同级别的 QoS 产品.用户或应用对 QoS 的 偏好由效用函数确定 .优化目标是通过资源分配 提供给用户 QoS 保障, 使得整体效用最大化. 2.1 QoS 需求模型 假设对于任务集合中的一个任务 ti , 都有 QoS 需求集合 Qi ={Qi 1, …, Qid i}( 1 ≤i ≤n, di = Qi ), 同时用效用函数表示用户从完成任 务中获得的 QoS 满意程度, 效用函数 ui ∶Qi ※ R +, R +为非负实数空间.任务集中所有任务或 应用的总效用为 ∑ n i =1 ui( Qi ), 系统优化目标是最 大化总 效用, 表示 为:max ∑ n i =1 ui ( Qi ), s .t . piQi ≤w i , 其中 w i 表示第 i 个请求代理的预算. 用 uij 表示用户对获得的 Qij 的满意程度, 用户 i 第 28 卷 第 11 期 2006 年 11 月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol.28 No.11 Nov.2006 DOI :10.13374/j .issn1001 -053x.2006.11.019

。1088· 北京科技大学学报 2006年第11期 在时间、花费和可用性三方面属性中，时间和 的总效用表示为山= w4(Q,其中ωwg为 花费为成本型属性，即数值越低对用户越有利：而 任务的不同QS属性的权重. 可用性为效益型属性，即数值越高对用户越有利， 2.2QoS生产模型 故可对矩阵A进行如下规范化处理从而得到规 服务提供者根据计算能力、用户对服务质量 范化矩阵R=(r)m×3. 的需求和偏好以及服务成本来组织和调度资源. min(ak) 对某个任务的资源分配是服务提供者的生产要 ak,j=L,;m,k=1,2: 素，以一定的生产函数生产Q$产品，服务的成 k 本决定于需要的资源、使用的时间、服务等级.该 max(a)j=L,“;m,k=3 k三 生产函数将资源分配和QoS联系在一起，描述了 假设属性权重向量为ω=(1,2,3)，并满 系统的性能模型.定义服务提供者为任务提供 第k个Q$级别的服务所需要的资源分配为r: 足单位化约束条件 户暖=1，则表示对服务提 =(rk1,;rkm),定义生产函数h:r:→Q,表示 供者选择方案的综合评价的效用函数可定义为： 给定资源组合，可以提供什么级别的服务.又根 U防()= 据Q:和效用的关系，得到资源分配和效用的关 wu(FTij)+w2u2(Cij)+w3u3(Avi). 系，表示为h:(r)={q∈Dil arg max u(q),资 本文运用离差最大化进行多属性决策和排 源分配、QoS和效用三者的关系如图1所示.从 序，即若所有的服务提供者在属性k下的属性值 图1中可以反映出，给定一组资源，生产者可以提 差异越小，则说明该属性对方案的选择与排序所 供一定级别的服务，通过获得服务，实际用户或应 起的作用越小：反之，如果属性k能使所有服务 用可以获得完成任务的效用. 提供者的属性值有较大的差异，则说明其对排序 hAr) 比较将起重要的作用.因此从对各方案进行排 序的角度考虑属性值偏差越大的属性应该赋予 越大的权重.将属性权重求解后代入U(ω) =∑，可求出相应的U(,利用其对各 方案进行排序便可求出最适合的服务提供者，从 图1资源分配，Q6和效用关系示意图 而完成服务选择和资源分配 Fig.1 Relation among resource allocation,QoS and utility 4 基于多QoS属性联合效用函数调 3 效用驱动的目标优化 度算法 利用上面给出的效用模型，用时间、预算和服 用效用函数作为QS属性描述函数，把对服 务可用性的联合效用函数来选择服务完成资源分 务质量的要求通过一个效用函数表示出来，并以 配.假设有n个任务，m个服务节点，对于任意 效用函数为目标函数进行调度优化，给系统更大 的灵活性为达到不同的要求进行资源分配.基于 任务t(1≤i≤n)在第j个服务节点S(1≤j≤ 资源分配的效用模型设计了多QoS属性联合效 m)的效用包含三方面属性：其时间效用表示该任 用函数调度算法joint utility function scheduling,. 务在S,上完成时间FT)的效用值，用u1(FT) JUS),算法的执行过程如下： 表示：预算效用表示S完成该任务所需的服务费 Step1输入任务QS需求参数，如时间限 用C的效用值，表示为u2(C:服务的可用性效 制(deadline)、预算限制(budget). 用函数表示S正常工作的效用，表示为 Step2查询注册的服务，获得服务静态信 u3Av),为任务G构建决策矩阵A= 息和可用服务列表brokerResourceList. (ak)m×d,其中m表示可提供服务的服务者数 Step3获得服务列表brokerResourceList中 量，d表示用户关心的QoS属性的维数，通过前 服务的动态信息，包括服务节点队列长度、服务速 面的论述可知d=3,a1=u1(FT),a2= 率、服务价格、服务可用性信息 u2(CHy93玩e(Academic Joumal Electronic Publishie4us从服务列表bmkereois中挑ki.net

的总效用表示为 ui = ∑ d i j =1 ωijuij ( Qij), 其中 ωij为 任务 ti 的不同 QoS 属性的权重. 2.2 QoS 生产模型 服务提供者根据计算能力 、用户对服务质量 的需求和偏好以及服务成本来组织和调度资源. 对某个任务的资源分配是服务提供者的生产要 素, 以一定的生产函数生产 QoS 产品, 服务的成 本决定于需要的资源、使用的时间 、服务等级.该 生产函数将资源分配和 QoS 联系在一起, 描述了 系统的性能模型.定义服务提供者为任务 ti 提供 第 k 个 QoS 级别的服务所需要的资源分配为 ri =( rik 1, …, rikm), 定义生产函数 hi∶ri ※Qi , 表示 给定资源组合, 可以提供什么级别的服务.又根 据 Qi 和效用的关系, 得到资源分配和效用的关 系, 表示为 hi ( ri) ={q ∈ Qi arg max ui( q)}, 资 源分配 、QoS 和效用三者的关系如图 1 所示 .从 图 1 中可以反映出, 给定一组资源, 生产者可以提 供一定级别的服务, 通过获得服务, 实际用户或应 用可以获得完成任务的效用. 图1 资源分配、QoS 和效用关系示意图 Fig.1 Relation among resource allocation, QoS and utility 3 效用驱动的目标优化 利用上面给出的效用模型, 用时间 、预算和服 务可用性的联合效用函数来选择服务完成资源分 配.假设有 n 个任务, m 个服务节点, 对于任意 任务 ti( 1 ≤i ≤n )在第 j 个服务节点S j( 1 ≤j ≤ m)的效用包含三方面属性 :其时间效用表示该任 务在 Sj 上完成时间 FT ij 的效用值, 用 u1 ( FT ij) 表示;预算效用表示 Sj 完成该任务所需的服务费 用Cij的效用值, 表示为 u 2( Cij) ;服务的可用性效 用函 数 表 示 Sj 正 常 工 作 的 效 用, 表 示 为 u3( Avij) , 为 任 务 ti 构 建 决 策 矩 阵 A = ( ajk ) m ×d , 其中 m 表示可提供服务的服务者数 量, d 表示用户关心的 QoS 属性的维数, 通过前 面的 论 述 可 知 d =3, aj1 = u1 ( FT ij ) , aj2 = u2( Cij) , aj 3 =u3(Av ij) . 在时间、花费和可用性三方面属性中, 时间和 花费为成本型属性, 即数值越低对用户越有利;而 可用性为效益型属性, 即数值越高对用户越有利, 故可对矩阵 A 进行如下规范化处理从而得到规 范化矩阵 R =( rik ) m ×3 . rjk = min j ( ajk ) ajk , j =1, …, m, k =1, 2 ; rjk = ajk max j ( ajk ) , j =1, …, m, k =3 假设属性权重向量为 ω=( ω1, ω2, ω3), 并满 足单位化约束条件 ∑ 3 k =1 ω2 k =1 , 则表示对服务提 供者选择方案的综合评价的效用函数可定义为: Uij ( ω) = ω1 u1( FTij ) +ω2 u2( Cij) +ω3 u 3(Av ij) . 本文运用离差最大化进行多属性决策和排 序, 即若所有的服务提供者在属性 uk 下的属性值 差异越小, 则说明该属性对方案的选择与排序所 起的作用越小;反之, 如果属性 uk 能使所有服务 提供者的属性值有较大的差异, 则说明其对排序 比较将起重要的作用 .因此, 从对各方案进行排 序的角度考虑, 属性值偏差越大的属性应该赋予 越大的权重.将属性权重求解后代入 Uij ( ω) = ∑ 3 k =1 rjkωk , 可求出相应的 Uij( ω) , 利用其对各 方案进行排序便可求出最适合的服务提供者, 从 而完成服务选择和资源分配. 4 基于多 QoS 属性联合效用函数调 度算法 用效用函数作为 QoS 属性描述函数, 把对服 务质量的要求通过一个效用函数表示出来, 并以 效用函数为目标函数进行调度优化, 给系统更大 的灵活性为达到不同的要求进行资源分配 .基于 资源分配的效用模型设计了多 QoS 属性联合效 用函数调度算法( joint utility function scheduling, JUFS) , 算法的执行过程如下 : Step 1 输入任务 QoS 需求参数, 如时间限 制( deadline) 、预算限制( budget) . Step 2 查询注册的服务, 获得服务静态信 息和可用服务列表 brokerResourceList . Step 3 获得服务列表 brokerResourceList 中 服务的动态信息, 包括服务节点队列长度、服务速 率、服务价格、服务可用性信息 . Step 4 从服务列表 brokerResourceList 中挑 · 1088 · 北 京 科 技 大 学 学 报 2006 年第 11 期

Vol.28 No.11 刘丽等：基于多服务质量属性联合效用函数的网格资源调度 。1089。 选满足预算限制的服务资源并把这些资源加入费 行性能分析，验证JUS算法在计算网格资源管 用预算列表brokerResourcesToCostUse. 理中的有效性.GridSim是网格应用、资源以及调 Step5从费用预算列表中挑选满足时间限 度算法的建模和模拟工具，它能够模拟异构和分 制的服务资源并把这些资源加入使用资源列表 布的网格资源，建立不同需求的应用模型，并能够 brokerResourcesToUse. 测试不同的调度算法性能，支持静态和动态调度 Step6按照多QoS属性联合效用值排序.为 模拟.为了说明JUFS算法，分别对Nimrod/G中 了求解联合效用函数最大化，构造决策矩阵，计算 的花费时间优先算法(deadline and budget con- 每个QS属性的权值：计算每个节点的联合效用 strain cost-time optimization,DBC-CT)以及非经 并排序：同时把最大联合效用值放到列表MaxU- 济的最早完成时间优先算法(early deadline first, tility中. EDF)进行模拟，对比分析三种算法的性能.DBC Step7执行任务调度，分配任务给具有最大 ℃T算法按任务执行费用排序，优先选择费用最 联合效用值的服务节点 小的服务节点完成任务，当存在两个以上具有相 重复以上过程直到所有任务都完成. 同费用的服务节点时，选择任务完成时间最短的 模拟实验结果 服务节点：EDF算法中任务被随机地分配到能在 5 最短时间内完成该任务的服务节点.实验结果如 用网格模拟器GridSim对JUFS调度算法进 图2(a)~(d所示. 3000+ 2.0 18 2500 1.6 1.4 2000 ·JUFS(时间限制-3000) 1.0 1500 DBC-CT(时间限制=3000) .8 ·UFS(时间限制3000) ◆EDF(时间限制=300O) 06 DBC-CT(时间限制=3000) ◆EDF(时间限制3000) 1000 04 02 5006 051.0152.0253.035 0.5 1.0152.02.53.03.5 预算限制/10 预算限制10 (a)任务执行时间随预算限制的变化情况 (b)任务花费随预算限制的变化情况 10000 5000 9000 4500 8000 4000 7000 3500 6000 3000 5000 2500 4000 ◆JUFS(预算限制=5000) 审20 3000 DBC-CT(预算限制=5000) EDF(预算限制=5000) 1500 ◆JUFS(预算限制=5000) 平DBC-CT(预算限制=5000) 2000 1000F ·EDF(预算限制=5000) 1000 500 0 0 0.5 1.0 1.5 0.5 1.0 15 时间限制10 时间限制/10 (©)任务执行时间随时间限制的变化情况 (任务花费随时间限制的变化情况 图2JUS算法与DBe-CT算法，EDF算法在不同情况下性能比较 Fig 2 Performance comparison of JUFS algorithm with DBC-CT and EDF algorithms 图2(a),(b)显示的是在时间限制为3000 受到时间限制的影响，采用DBC-CT算法与EDF 时，随着预算限制的增加执行时间和花费的变化 算法时，尽管预算限制不断增加，但任务花费很快 情况.实验结果显示，采用JUFS算法时执行时 就不再变化这说明在这两种算法中，在一定的时 间的增加速度得到了有效的控制，另一方面，由于 间限制内，增加预算限制对任务的执行情况没有 (C)1994-2020 China Academic Journal Electronic Publishing House.All rights reserved. http://www.cnki.ne

选满足预算限制的服务资源并把这些资源加入费 用预算列表 brokerResourcesToCostUse. Step 5 从费用预算列表中挑选满足时间限 制的服务资源并把这些资源加入使用资源列表 brokerResourcesToUse . Step 6 按照多 QoS 属性联合效用值排序.为 了求解联合效用函数最大化, 构造决策矩阵, 计算 每个 QoS 属性的权值;计算每个节点的联合效用 并排序 ;同时把最大联合效用值放到列表 MaxU￾tility 中 . Step 7 执行任务调度, 分配任务给具有最大 联合效用值的服务节点. 重复以上过程直到所有任务都完成 . 5 模拟实验结果 用网格模拟器 GridSim 对 JUFS 调度算法进 行性能分析, 验证 JUFS 算法在计算网格资源管 理中的有效性.GridSim 是网格应用 、资源以及调 度算法的建模和模拟工具, 它能够模拟异构和分 布的网格资源, 建立不同需求的应用模型, 并能够 测试不同的调度算法性能, 支持静态和动态调度 模拟.为了说明 JUFS 算法, 分别对 Nimrod/G 中 的花费时间优先算法( deadline and budget con￾strain cost-time optimization, DBC-CT) 以及非经 济的最早完成时间优先算法( early deadline first, EDF) 进行模拟, 对比分析三种算法的性能.DBC -C T 算法按任务执行费用排序, 优先选择费用最 小的服务节点完成任务, 当存在两个以上具有相 同费用的服务节点时, 选择任务完成时间最短的 服务节点 ;EDF 算法中任务被随机地分配到能在 最短时间内完成该任务的服务节点 .实验结果如 图 2( a) ～ ( d) 所示. 图 2 JUFS 算法与 DBC-CT算法、EDF 算法在不同情况下性能比较 Fig.2 Performance comparison of JUFS algorithm with DBC-CT and EDF algorithms 图 2( a) , ( b) 显示的是在时间限制为 3 000 时, 随着预算限制的增加执行时间和花费的变化 情况.实验结果显示, 采用 JUFS 算法时执行时 间的增加速度得到了有效的控制, 另一方面, 由于 受到时间限制的影响, 采用 DBC-CT 算法与 EDF 算法时, 尽管预算限制不断增加, 但任务花费很快 就不再变化, 这说明在这两种算法中, 在一定的时 间限制内, 增加预算限制对任务的执行情况没有 Vol.28 No.11 刘 丽等:基于多服务质量属性联合效用函数的网格资源调度 · 1089 ·

。1090。 北京科技大学学报 2006年第11期 影响，而JUFS算法由于任务执行时间明显优于 Computing Infrastructure.Morgan Kaufmann Pubishers. 前两种算法，所以可以在此时限内，通过增加预算 1999 【习张金水.数理经济学一理论与应用.北京：清华大学出版 限制而完成更多的任务.图2中(c,(d)显示了 社，1998 在预算限制为5000时，执行时间和花费随着时 【3习武康平.高级微观经济学.北京清华大学出版社，2001 间限制的增加发生变化的情况.从这两个图中可 [4 Foster I.Roy A.Sander V.A quality of service architecture 以看出，采用DBC-CT算法和EDF算法时执行 that combines resource reservation and application adaptation 时间与花费都达到了一个较高的值，当采用 /In 8th International Workshop on Quality of Service (I- WQos'00),2000 JUFS算法时只有花费上与前两种算法相近，而 [5 AFAli R.Amin K,Laszewski G.et al.An OGSA-based quah 执行时间得到较好的控制. ity of service framw ork /In Procedings of the Second Inter 6结论 national Workshop on Grid and Cooperative Computing (GCC2003),2003 提出了基于计算经济模型的网格QoS控制 [6 Keahey K,Motawi K.The Taming of the Grid:Virtual Ap 机制，给出了多Q$属性优化的资源分配效用模 plication Service.Argonne National Laboratory Technical Memorandum,Report Number(s)ANL/MCS-TM-262[R/ 型.以效用最大化为目标设计了多QS属性联合 0山.200305-26.http∥ats.merse.go/events/Wok- 效用函数调度算法(JUFS),JUS以任务完成时 shop2003 间、花费和服务可用性的联合效用函数最大化为 [7]Buyya R,Abramson D,Giddy J.Nim modG:an architecture 目标进行任务调度.用网格模拟工具模拟了算法 for a resource management and scheduling system in a global 的性能，并与其他经济的和非经的算法比较.实 computational grid The 4th International Conference on 验结果表明JUS可以权衡多QS属性，反映了 High Performance Computing in Asia-Pacific Region.IEEE Computer Socicty Press,2000 用户的最佳效用，使调度更具灵活性. [8 Buyya R.VenugopalS.The gridbus toolkit for service onient- ed grid and utility computing /An Overview and Status Re 参考文献 port Presented at the Ist IEEE Int.Scoul Workshop Grid E- [1]Foster I.Kesselman C.The Grid:Blueprint for a Future conomics and Business Models (GECON 2004),2004 Grid resource scheduling based on the multi-QoS attributes joint utility function LIU Li",YANG Yang,LIU Meijia2,TAO Lihong" 1)Information Engineering Schodl.University of Science and Technology Beijing,Beijing 100083.China 2)Beijing Materials Handling Research Institute.Beijng 100007.China ABSTRACT The economic model was applied to solve the QoS(quality of service)guarantees problem, and a utility model expressed in multi-QoS attributes was presented,which can be used to dy namically allo- cate resource in the Grid.A multi-QoS attributes-based joint utility function scheduling (JUFS)algorithm under the deadline and budget constrain was proposed.The performance of the algorithm was evaluated through a series of simulations.Comparisons with other economic and non-economic algo rithms show that the performance of the JUFS algorithm matches well with the service on demand in the Grid. KEY WORDS grid;quality of service;utility model;resource scheduling (C)1994-2020 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net

影响, 而 JUFS 算法由于任务执行时间明显优于 前两种算法, 所以可以在此时限内, 通过增加预算 限制而完成更多的任务.图 2 中( c), ( d)显示了 在预算限制为 5 000 时, 执行时间和花费随着时 间限制的增加发生变化的情况.从这两个图中可 以看出, 采用 DBC-CT 算法和 EDF 算法时执行 时间 与花费都达到了一 个较高的值, 当采用 JUFS 算法时只有花费上与前两种算法相近, 而 执行时间得到较好的控制 . 6 结论 提出了基于计算经济模型的网格 QoS 控制 机制, 给出了多 QoS 属性优化的资源分配效用模 型.以效用最大化为目标设计了多 QoS 属性联合 效用函数调度算法( JUFS) , JUFS 以任务完成时 间、花费和服务可用性的联合效用函数最大化为 目标进行任务调度.用网格模拟工具模拟了算法 的性能, 并与其他经济的和非经的算法比较 .实 验结果表明 JUFS 可以权衡多 QoS 属性, 反映了 用户的最佳效用, 使调度更具灵活性. 参 考 文 献 [ 1] Foster I, Kesselman C .The Grid:Blueprint f or a Futu re Computing Infrastructu re .Morgan Kaufmann Publishers, 1999 [ 2] 张金水.数理经济学———理论与应用.北京:清华大学出版 社, 1998 [ 3] 武康平.高级微观经济学.北京:清华大学出版社, 2001 [ 4] Foster I, Roy A, Sander V.A quality of service architectu re that combines resource reservation and application adaptation ∥ In 8th Int ernational Workshop on Quality of S ervice ( I￾WQoS ' 00) , 2000 [ 5] Al-Ali R, Amin K, Laszewski G, et al.An OGSA-based qual￾it y of service framw ork ∥In Proceedings of the Second Inter￾national Workshop on G rid and Cooperative Com puting ( GCC2003) , 2003 [ 6] Keahey K, Motaw i K.The Taming of the Grid:Virtual Ap￾plication Service, Argonne National Laboratory Technical Memorandum, Report Number( s) ANL/ MCS-TM-262 [ R/ OL] .2003-05-26.http:∥acts.nersc.gov/ events/ Work￾shop2003 [ 7] Buyya R, Abramson D, Giddy J.Nim rod-G :an architectu re f or a resource management and scheduling system in a global comput ational grid ∥ The 4th International Conf erence on High Performance Computing in Asia-Pacifi c Region.IEEE Computer Societ y Press, 2000 [ 8] Buyya R, Venugopal S.The gridbus t oolkit for service ori ent￾ed grid and utilit y computing ∥ An Overview and S tatus Re￾port Present ed at the 1st IEEE Int .Seoul:Workshop Grid E￾conomi cs and Business Models ( GECON 2004) , 2004 Grid resource scheduling based on the multi-QoS attributes joint utility function LIU Li 1) , Y ANG Yang 1) , LIU Meijia 2) , TAO Lihong 1) 1) Information Engineering School, University of S cience and Technology Beijing, Beijing 100083, China 2) Beijing Materials Handling Research Institut e, Beijing 100007, China ABSTRACT The economic model w as applied to solve the QoS ( quality of service) guarantees problem, and a utility model expressed in multi-QoS attributes w as presented, which can be used to dy namically allo￾cate resource in the Grid .A multi-QoS attributes-based joint utility function scheduling ( JUFS) algorithm under the deadline and budget constrain w as proposed .The performance of the algorithm was evaluated throug h a series of simulations.Comparisons with other economic and non-economic algo rithms show that the perfo rmance of the JUFS algorithm matches well with the service on demand in the Grid . KEY WORDS g rid ;quality of service;utility model ;resource scheduling · 1090 · 北 京 科 技 大 学 学 报 2006 年第 11 期