（计算机软件与理论专业论文）面向用户体验的多qos约束多流程调度方法研究.pdf

曾 i 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究作出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名：盔丝e t 期：2 z ! ：垒 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：缘礁导 臌名一：一 山东大学硕十学位论文 目录 摘要i a b s t r a c t i 第一章绪论1 1 1 课题研究背景1 1 2 本文的主要工作与意义2 1 3 本文的组织结构3 1 4 本章小结4 第二章相关研究5 2 1 流程调度算法的研究5 2 1 1 流程调度概述5 2 1 2 针对q o s 目标的流程调度6 2 1 3 多流程调度7 2 2 用户体验及其度量8 2 3 本章小结1 0 第三章面向用户体验的多q o s 约束多流程调度系统整体框架1 l 3 1 概述l l 3 2 面向用户体验的多q o s 约束多流程调度系统框架1 3 3 3 面向用户体验的多q o s 约束多流程调度策略的工作流程1 5 3 4 本章小结1 7 第四章面向用户体验的多q o s 约束多流程调度1 8 4 1 多q o s 约束多流程调度算法18 4 1 1 算法思想1 8 4 1 2 相关定义1 9 4 1 3q o s 的计算方法2 0 4 1 4 各任务属性的计算方法2 1 4 1 5 调度算法2 2 4 2 用户体验的度量方法2 4 4 2 1 用户体验度( u e d ) 权重2 4 i i i 东大学硕七学位论文 4 2 2 用户体验度( u e d ) 权重的计算方法2 5 4 2 3 用户体验度( u e d ) 的计算j 2 6 4 3 面向用户体验的多q o s 约束多流程调度算法2 7 4 4 本章小结2 8 第五章仿真实验及结果分析3 0 5 1 实验环境介绍3 0 5 2 实验结果与比较3 0 5 2 1 多q o s 约束多流程调度算法实验结果分析3 0 5 2 2 面向用户体验的多q o s 约束多流程调度算法实验结果分析3 4 5 3 本章小结3 6 第六章结束语3 7 6 1 总结3 7 6 2 展望3 7 参考文献3 8 致谢4 2 攻读学位期间发表的学术论文目录4 3 鼻 山东大学硕士学位论文 t a b l eo fc o n te n t s a b s t r a c ti nc h i n e s e i 想 a b s t r a c ti ne n g l i s h i i i 一 一 c h a p t e r1i n t r o d u c t i o n 1 1 1r e s e a r c hb a c k g r o u n d 1 1 2t h em a i nc o n t e n ta n ds i g n i f i c a n c eo f t h et h e s i s ：2 1 3t h es t r u c t r u eo f t h et h e s i s 3 1 4c h a p t e rc o n c l u s i o n 4 c h a p t e r2r e s e a r c ha c t u a l i t y 5 2 1 s t u d yo f s c h e d u l i n ga l g o r i t h m 5 2 1 1i n t r o d u c t i o no f s c h e d u l i n ga l g o r i t h m 5 2 1 2q o sc o n s t r a i n e ds c h e d u l i n ga l g o r i t h m 6 2 1 3m u l t i p l ew o r k f l o ws c h e d u l i n ga l g o r i t h m 7 2 2u s e re x p e r i e n c ea n dm e a s u r em e t h o d 8 2 3c h a p t e rc o n c l u s i o n 1 0 c h a p t e r3u s e re x p e r i e n c eb a s e dm u l t i q o sc o n s t r a i n e dm u l t i - p r o c e s s e ss c h e d u l i n g s t r a t e g yo v e r v i e w 1 1 3 1o v e r v i e w l1 3 2s c h e d u l i n gs t r a t e g yf r a m e w o r k 1 3 3 3p r o c e d u r eo f s c h e d u l i n gs t r a t e g y 1 5 3 4 c h a p t e rc o n c l u s i o n 1 7 c h a p t e r4u s e re x p e r i e n c eb a s e dm u l t i q o sc o n s t r a i n e dm u l t i - p r o c e s s e ss c h e d u l i n g a l g o r i t h m 1 8 4 1m u l t i q o sc o n s t r a i n e dm u l t i p l ew o r k f l o w ss c h e d u l i n g 18 4 1 1o v e r v i e w o f m q m w 1 8 4 1 2d e f i n i t i o n ：1 9 4 1 3c o m p u t i n gm e t h o do f q o s 2 0 4 1 4c o m p u t i n gm e t h o do f t a s ka t t r i b u t e s 2 1 【l i 东大学硕士学位论文 4 1 5s c h e d u l i n ga l g o r i t h m 2 2 4 2 m e a s r u em e t h o do f u s e re x p e r i e n c e 2 4 4 2 1w e i g h to f u s e re x p e r i e n c ed e g r e e ( u e d ) 2 4 4 2 2c o m p u t i n gm e t h o do f w e i g h to f u e d 2 5 4 2 3c o m p u t i n gm e t h o do f u e d 2 6 4 3u s e re x p e r i e n c eb a s e dm u l t i q o sc o n s t r a i n e dm u l t i - p r o c e s s e ss c h e d u l i n g a l g o r i t h m 2 7 4 4c h a p t e rc o n c l u s i o n 2 8 c h a p t e r5e x p e r i m e n t sa n da n a l y s i s 3 0 5 1i n t r o d u c t i o no f e x p e r i m e n t s 3 0 5 2r e s u l ta n d a n a l y s i s - 3 0 5 2 1r e s u l to f m q m w a l g o r i t h m 3 0 5 2 2r e s u l to f u e b p d a l g o r i t h m 3 4 5 3c h a p t e rc o n c l u s i o n 3 6 c h a p t e r6c o n c l u s i o na n do u t l o o k ：3 7 6 1c o n c l u s i o n 3 7 6 2e x p e c t a t i o n 3 7 r e f e f e n c e s 3 8 a c k n o w l e d g m e n t 4 2 t h et h e s i sp u b l i s h e df o r t h em a s t e r d e g r e e 4 3 山东大学硕士学位论文 摘要 随着信息技术的发展和普及，互联网逐渐成为一种计算平台。基于互联网 平台的应用普遍是一种分布协同的过程。流程在这一协同过程中起着重要作用。 目前互联网应用所面临的客户端层次比以前更加广泛，因此需求也呈现出多元 化的特点。需求的多元化不仅仅体现在业务需求上，同时还体现在q o s 需求之 上。与此同时互联网应用的用户规模呈爆炸性增长，由此引发的请求高并发性 使得规模化的流程被触发。由此可见，基于互联网的大规模流程应用普遍呈现 出q o s 需求多元化及流程数量急剧增加的特点。 本文针对基于互联网的大规模流程应用所面临的用户o o s 需求多样化、流 程数量巨大两大核心问题，以尽可能多地满足大规模用户个性化q o s 需求为目 标，从用户体验角度出发，提出了面向用户体验的多q o s 约束多流程的调度策 略及相关算法，实现了大规模流程应用的平衡调度，增强了用户的体验。该调 度策略由多q o s 约束多流程调度算法及面向用户体验的度量算法两部分组成。 多o o s 多流程调度算法用于解决多o o s 约束的多流程调度问题，目标是满足尽 可能多的用户的q o s 需求，而并非提高某一用户的执行效率，从而提高整体用 户的满意度。算法通过将流程的整体q o s 需求分解到各个任务上，成为任务的 q o s 约束，然后将所有流程的就绪任务根据其q o s 约束进行调度。面向用户体 验的度量算法加入了用户体验的描述及度量方法，并把用户的反馈经过处理以 后纳入到调度策略中，以提高用户的体验。通过把用户的反馈信息加入到调度 过程中，并且在选择资源时，根据定义的用户体验度指标进行选择，能够在调 度过程中更好的反应用户的需求，增强用户体验。 实验表明，多q o s 约束多流程调度算法能够满足更多用户的不同o o s 需求， 有效的提高调度的成功率。多o o s 约束多流程调度算法与面向用户体验的度量 算法的结合使用，能够使用户的反馈有效的参与到调度过程中，从而提高用户 体验。 本文的研究成果是大规模网络协同应用的核心技术，对提高网络应用中的 流程执行效率，提高吞吐量，增强用户的应用体验都具有重要意义。同时，论 山东大学硕士学位论文 文成果也是云计算以服务及其流程为核心计算架构的关键技术之一，具有广阔 的应用前景。 关键词：流程调度；o o s ；用户体验 t w of e a t u r e s ：t h ed i v e r s i t yo f q o sr e q u i r e m e n t sa n dt h el a r g en u m b e ro f p r o c e s s e s t h i sp a p e ri sf o c u so nt h ed i v e r s i t yo fq o sr e q u i r e m e n t sa n dt h el a r g en u m b e r o fp r o c e s s e sp r o b l e m sw h i c ht h el a r g es c a l ep r o c e s s e sa r ef a c e d t h em a i no b j e c t i v e i st os a t i s f ym o r eu s e r s q o sr e q u i r e m e n t sa n de n h a n c et h eu s e re x p e r i e n c e b a s e d o nt h i so b je c t i v e ，t h eu s e re x p e r i e n c eo r i e n t e dm u l t i q osc o n s t r a i n e dm u l t i p r o c e s s s c h e d u l i n gs t r m e g yi sp r o p o s e d t h es c h e d u l i n gs t r a t e g yc a ns c h e d u l e al a r g e n u m b e ro fp r o c e s s e sa n de n h a n c et h eu s e re x p e r i e n c e t h i ss c h e d u l i n gs t r a t e g y i n c l u d e sam u l t i q o sc o n s t r a i n e dm u l t i - - p r o c e s ss c h e d u l i n ga l g o r i t h ma n dau s e r e x p e r i e n c e m e a s u r e a l g o r i t h mt h ef i r s ta l g o r i t h m a d d r e s s e st h em u l t i - q o s c o n s t r a i n e dm u l t i - p r o c e s ss c h e d u l i n gp r o b l e mt h i sm e t h o di sm a i n l yt om e e ta s m a n yu s e r s o o sr e q u i r e m e n t s ，r a t h e rt h a nt oi m p r o v et h ee x e c u t i n ge f f i c i e n c yo f o n eu s e r t h ea l g o r i t h md e c o m p o s e st h eq o sr e q u i r e m e n t so ft h ep r o c e s st ot h et a s k o ft h ep r o c e s s a n dt h e ns c h e d u l i n gt h et a s k sa c c o r dt ot h eq o sc o n s t r a i n e d t h e s e c o n da l g o r i t h mi n t r o d u c e st h ed e s c r i p t i o na n dm e a s u r em e t h o do ft h eu s e r e x p e r i e n c e t h eu s e r s f e e d b a c ki st a k e ni n t oa c c o u n ti nt h es c h e d u l i n gp r o c e s s o f t h i sm e t h o dt oi m p r o v et h eu s e re x p e r i e n c e b yt h i sw a y ，t h er e s o u r c e sc a nb e s e l e c t e da c c o r d i n gt ot h eu s e re x p e r i e n c ed e g r e e ( u e d ) s ot h eu s e r s r e q u i r e m e n t s c a nb em e tb e t t e ra n dt h eu s e re x p e r i e n c ec a nb ei m p r o v e d i 【ii 东大学硕士学位论文 e x p e r i m e n t ss h o wt h a tt h em u l t i - q o sc o n s t r a i n e dm u l t i - p r o c e s ss c h e d u l i n g a l g o r i t h mc a l ls a t i s f ym o r eu s e r s q o sr e q u i r e m e n t sa n de f f e c t i v e l yi m p r o v et h e s u c c e s sr a t eo fs c h e d u l i n g f u r t h e r m o r e ，b yu s i n gt w oa l g o r i t h m si n t r o d u c ei nt h i s p a p e r ，t h eu s e r s f e e d b a c kc a l lb et a k e ni n t ot h es c h e d u l i n gp r o c e s sa n dt h eu s e r e x p e r i e n c ec a nb ei m p r o v e d t h ea l g o r i t h m sp r o p o s e di nt h i sp a p e ra r et h ec o r et e c h n o l o g yo fl a r g es c a l e c o o p e r a t i o na p p l i c a t i o n s t h e yc a ni m p r o v et h ee x e c u t i o ne f f e n c i e n c ya n dt h e t h r o u g h p u t m o r e o v e r , t h eu s g te x p e r i e n c e c a nb ee n h a n c e do b v i o u s l y o nt h eo t h e r h a n d ，t h es c h e d u l i n gs t r a t e g yi nt h i sp a p e ri so n eo ft h ek e yt e c h n o l o g i e si nt h ec l o u d c o m p u t i n gp l a t f o r m s oi th a saw i d ep r o s p e c to fa p p l i c a t i o n k e y w o r d ：p r o c e s ss c h e d u l i n g ；q o s ；u s e re x p r i e n c e i v 1 1 课题研究背景 随着信息技术的发展和普及，信息能够在互联网上共享，互联网逐渐成为 一种计算平台。这一平台之上的各种应用越来越丰富，尤其是基于互联网平台 的大型应用占据着越来越重要的地位。而这类应用普遍是一种分布协同的过程， 流程在这一过程中起着重要作用。在全球化的大背景下，流程中的任务可能分 配到任何地方，因此，i n t e r n e t 便成为了不可或缺的工具。目前的互联网应用 的普及程度相比十几年前有了大幅提高，各种信息技术也得到了长足发展，导 致当前互联网应用所面临的客户端层次更加广泛，因此需求也呈现出多元化的 特点。需求的多元化不仅仅体现在业务需求上，同时还体现在q o s 需求之上。 与此同时，用户规模的爆炸性增长带来了用户请求的高并发性。在流程应用中， 用户请求的高并发性引起规模化流程被触发，使得有大量流程实例同时执行。 由此可见，基于互联网的大型流程应用逐渐呈现出如下特点： ( 1 ) 流程数量规模巨大。由于基于互联网的大型流程应用需要面向互联网上 的大量用户，而每个用户又可能同时执行多个流程，因此，需要同时执行的流 程数量可能很大。 ( 2 ) q o s 需求多样化。各流程对q o s 的需求可能有所差别，甚至差别巨大。 另外，又可能是由不同用户请求的流程执行，每个用户对于q o s 的需求也可能 差别很大。因此，执行中的流程对q o s 的需求呈现出多样化的特点。 在流程执行过程中，核心问题就是流程的调度。上述两个特点对当前流程 调度的研究工作带来了前所未有的挑战： ( 1 ) 多流程的调度。一般来说，分布式系统中的调度问题是n p 难解的。由 于分布式系统中的资源很多，并且流程各个任务之间存在一定的时序关系，在 调度一个流程的问题上已经非常困难。当系统中的流程增多，无疑更加加大了 调度的难度。在调度过程中不但需要考虑流程中任务之间的相互关系，同时还 要考虑到流程之间的相互影响。另外，此处的多流程不仅仅指同一流程的多个 实例，还指结构完全不同的多个流程，即调度算法应当不但能够调度相同流程 山东大学硕士学位论文 im l 的多个实例，还应当能够调度结构完全不同的多个流程。 ( 2 ) 多o o s 约束下的流程调度。在流程的调度过程中，仅仅考虑一个o o s 指 标与同时考虑多个q o s 指标有着根本的区别。因为在o o s 指标中，有些指标之 间具有相互矛盾的特点，比如，执行时间与执行成本。一般情况下，执行时间 短的资源所需成本要更高。因此，多q o s 约束下的流程调度需要综合考虑用户 各方面的q o s 需求，选择最合理而不是某一q o s 指标最优的资源。 ( 3 ) 上述两点的结合，更加加大了调度的难度。同时调度多个流程，每一流 程又有不同的多个q o s 需求。如何能够满足更多流程的q o s 需求，使更多的用 户对执行结果满意，成为最大的挑战。 1 2 本文的主要工作与意义 本文主要针对基于互联网的大型流程应用的q o s 需求多元化及流程数量规 模巨大两大特点，重点研究多q o s 需求的多流程调度，及如何以用户体验为衡 量调度好坏的标准，并通过此标准提高用户体验。主要包括以下几点： ( 1 ) 多流程的处理。 流程的调度应当能够同时处理不同用户的多个流程。虽然针对单流程调度 算法，通过一定的处理也能够进行多流程的调度，然而，由于算法本身不是专 门针对多流程进行设计，因此，在应用上会有诸多限制，并且调度的结果也不 理想。本文介绍的算法能够同时调度大量流程，而不仅是单一流程或者一个流 程的多个实例。 ( 2 ) 多o o s 需求的处理。 由于调度本身是面向多用户的，而每个用户的q o s 需求必然不会相同，因 此，调度算法必须能够根据不同用户的不同o o s 需求进行处理。q o s 属性的多 样化，造成了其处理方法的不同，这也为调度算法增加了难度。此外，还应当 能够处理不同类型的q o s 需求。本文介绍的方法针对不同流程、不同用户的o o s 需求进行调度，并且能够满足多q o s 目标，而不是仅仅针对某一q o s 目标进行 调度。同时，在调度时考虑了用户之间的相互影响，尽最大可能满足更多用户 的o o s 需求。 ( 3 ) 以用户体验为衡量标准。 2 山东大学硕士学位论文 以前的调度算法大都以计算出的结果为调度好坏的衡量标准。然而，实际 应用中由于系统的状态、用户的主观体验等未知因素的影响，调度结果可能并 非象理想状况下那样。另外，调度的根本目的还是为了为用户提供更好的服务， 提高用户的体验，增加用户满意度。因此，有必要设计一种以用户的体验为衡 量标准，目的是提高用户体验的调度算法。本文对于调度结果的衡量，并不简 单的以流程执行效率或者某些q o s 的参数为标准。因为对于不同的用户对于流 程执行的要求不同，体验也就不同。而是建立了一个以用户体验为主的衡量标 准，所有的调度围绕提高用户体验这一总体目标进行。 随着w e bs e r v i c e 、w e b 2 0 及s o a 技术的不断发展和应用，未来的计算平 台呈现出以i n t e r n e t 为主，大型应用流程化的趋势。而流程执行过程中最核心 的问题就是调度。由于i n t e r n e t 的开放性，其必然要为全球用户提供服务，流 程的多样性、大量化，用户需求的个性化、多样性也必然出现。因此，研究如 何以用户体验为衡量标准的多q o s 约束下的多流程调度是很有意义，也很有必 要的。此外，云计算等新的计算模式最近得到了不断发展，本文的成果也是云 计算中以流程为核心架构的关键技术之一，具有非常广阔的应用前景。 1 3 本文的组织结构 本文是按照下面的结构组织的： 第一章引言部分介绍了本文研究的背景，并介绍了本文所做的工作及主要 意义，最后介绍了本文的组织结构。 第二章分析了本文研究涉及的相关领域的研究现状和不足，并对现在的方 法进行了分析比较。 第三章介绍了整个调度策略的框架，使读者对本文提出的调度策略有一个 整体的了解。 第四章介绍了面向用户体验的多q o s 多流程调度策略，主要介绍了如何实 现同时调度多流程，及如何处理多q o s 需求的调度。并引入了用户体验的标准 衡量，并将用户的反馈引入到调度中来增强用户体验 第五章主要介绍了本文提出的调度策略的模拟实验结果，通过实验对比， 可以看出，本文所提出的方法在调度多流程的同时，能够很好的满足用户的q o s 3 l 【j 东大学硕士学位论文 需求，并增强用户体验。 第六章对全文进行了总结，分析了本文研究成果的理论意义和应用前景， 并指出了今后需要进一步研究的工作。 1 4 本章小结 本章作为本文的绪论，首先介绍了论文研究的背景：然后对本文的主要工 作及意义进行了阐述；最后给出了本论文的结构框架，使得读者对全文的主要 内容有个一个全局、总体的了解。 l i f 东大学硕士学位论文 第二章相关研究 2 1 流程调度算法的研究 2 1 1 流程调度概述 在流程执行过程中，任务调度是其核心问题，它要根据用户提交的任务信 息采用适当的策略把不同的任务分配到相应的资源节点上去运行。由于系统的 异构性和动态性，以及运行于系统之中任务对于资源的不同需求，使得任务调 度变得极其复杂，不好的任务分配策略，将会增加任务的执行时间、成本，降 低整个系统的吞吐量。同时，系统中任务和资源的数目都比较大，任务和资源 之间的匹配关系也比较复杂。任务与任务、任务与资源、资源与资源之间的相 互关系最终都会影响任务的调度顺序和任务与资源之间的匹配。基于以上原因， 任务调度问题具有以下几个特点 1 ： ( 1 ) 任务调度是面向异构平台的。由于系统是由分布在各地的各种资源组成 的，包括各类主机、工作站、甚至p c ，并且运行的操作系统也可能完全不同， 因此，系统中的任务调度必须面向异构平台，能够在这些平台上实现任务的调 度。 ( 2 ) 任务调度是大规模的、非集中式的。由于系统需要同时处理大量流程， 并且要在分布在不同位置的资源上进行任务调度，因此任务必须以分布、并行 方式进行任务的管理与调度。 ( 3 ) 任务调度不干涉节点内部的调度策略。在系统中，各节点的内部调度策 略是自治的，任务调度系统无法也不应该干预其内部的调度策略。 ( 4 ) 任务调度必须具有可伸缩性。节点加入与退出系统是自由的，因此系统 规模也在不断变化之中。任务调度应当能够适应不同的系统规模，在资源规模 不断扩大、应用不断增加的情况下，系统的任务调度必须具有可伸缩性，不致 降低系统的性能。 工作流的调度策略可以分为静态调度和动态调度两种。静态调度是指在调 度发生时，为工作流的所有任务一一指定好资源，文献 2 - 5 ，3 8 4 0 都是基于该 5 l l f 东大学硕七学何论文 调度策略进行工作流的调度：而实时动态调度，则是调度发生时，仅为当前的任 务选择一个最佳的资源，直至工作流应用的完成。显然，实时的动态调度更加适 应网格环境中资源的动态性，但是需要实时地获取资源的信息，为资源的选择提 供依据，文献 6 提出了一种实时的调度算法m y o p i c ，但只能调度简单的工作流。 t r i a n a 7 系统也提供了简单工作流的实时动态调度策略。 2 1 2 针对o o s 目标的流程调度 基本调度算法只能解决单一的调度目标。然而用户的需求往往不是单一目 标，因此，j i ay u 等 8 利用对工作流进行分区的方法，生成满足用户提出的 时间限制且工作流的花费尽量小的调度。但是该方法仅仅在满足用户的时间限 制的情况下，对流程的花费进行优化调度，并不是真正的针对多个o o s 属性对 流程调度进行优化。 - k h a l e dt a l u k d e r 等【9 】提出了m u l t i o b j e c t i v ed i f f e r e n t i a le v o l u t i o n ( m o d e ) 的 方法对执行时间和花费两个q o s 属性进行优化调度。该方法可以对两个q o s 属性进行优化，但对于更多的q o s 属性无能为力。 胡春华等人在重定义粒子群算法的位置、速度、加减法和乘法的基础上， 结合遗传算法中的交叉、变异操作，设计了基于混合粒子群的o o s ( q u a l i t yo f s e r v i c e ) 调度方法，保证在可选服务不断增长时能够满足用户的个性化需求 1 0 。 胡志刚与胡周君在考虑用户多个q o s 要求及工作流任务间通信时间的基础 上，提出基于信任与花费的综合效益函数，给出信任与花费权值的确定方法以 及一个以综合效益最优为目标的调度算法- - t c d ，算法通过追求局部最优达到全 局多目标优化调度 1 1 。 刘书雷等人 1 2 提出了一种服务聚合中q o s 全局最优服务动态选择算法。 算法的主要思想是把服务动态选择全局最优化问题转化为一个带q o s 约束的多 目标服务组合优化问题，利用多目标遗传算法的智能优化原理，通过同时优化多 个目标函数，最终产生一组满足约束条件的p a r e t o 优化服务聚合流程集。 文献 3 0 在大规模的多管理域网络系统中引入了q o s 驱动的资源管理策略， 利用效益函数量化服务质量等级，提出作业级动态调度算法来优化o o s 中的执 6 l i f 东大学硕十学位论文 行时间和优先级。d i n g 等 3 1 提出了映射一组相互独立作业的策略，通过采用重 复映射来更好地适应互联网服务环境下的动态性和自治性，并使用定义的效益 函数，来追求执行时间等o o s 需求的优化。h e 等 3 2 通过改进m i n - m i n 调度算 法，提出了一个自适应的q o s 驱动的m i n - m i n 启发式算法。同样，w e n g 等 3 3 以 执行时间和平均响应时间作为q o s 需求，提出以s u f f e r a g e 为基础的q s u f f e r a g e 算法，该算法在执行时间和平均响应时问方面显著优于x s u f f e r a g e 及m a x - m i n 算法。文献 3 4 针对服务互联网中的工作流应用，深入研究了基于o o s 的服务管 理与调度算法。张伟哲等 3 5 提出了一种解决多o o s 约束网格作业调度问题的 多目标演化算法，仿真结果表明，在时间维度、可靠性维度、安全性维度q o s 效 用值等用户级o o s 指标，以及丢弃作业数等系统级指标方面该算法与 o o s - m i n - m i n 和q o s - s u f f e r a g e 等同类算法相比具有较好的综合性能。陈晶等 3 6 在执行时间和网络带宽的双重属性约束下结合预测机制，提出了网格资源 调度算法s e n i o r 。 2 1 3 多流程调度 在流程的调度过程中，流程越多，调度问题的复杂性越高。因此，简单的 流程调度方法都是针对单流程的。虽然经过一定的处理 2 2 ，多个流程可以合 并为一个流程，然后使用单流程的调度方法进行调度。但是该方法仅能处理同 时开始的多个流程，并且由于本质上使用的是单流程的调度方法，因此，结果 并不理想。 k el i u 等提出了一种在p 2 p 网格环境下调度事务密集型工作流的策略 1 3 。 事务密集型工作流指的是同一时刻有同一流程的大量的流程实例同时运行。这 与多流程即有相同之处，也有不同之处。相同之处是系统中都同时运行这大量 的流程实例，不同之处是多流程的流程实例即可能是相同流程的实例，也可能 是不同流程的实例，而事务密集型工作流的流程实例都是同一流程的。其核心 思想是将整个系统分为2 层，上层由超级节点组成，下层由超级节点及其控制 的普通节点所构成的组组成。超级节点负责管理和任务调度，普通节点负责任 务的具体执行。在上层使用o a l 算法，主要目的是使各组间负载均衡。算法的 核心思想是使用o a l 值计算分配到个组的工作流实例的数量。对节点a ，其邻 7 山东大学硕士学位论文 居b 的o a l 值为b 及其除a 之外的邻居的负载平均值。在下层使用e m m 算法， 主要目的是增加系统的吞吐量。算法的核心思想是首先调度具有最早开始时间 的可调度任务到最优资源。该方法是专为事务密集型工作流设计的，并不适用 于普通的多流程调度。 文献 2 4 提出了一种针对实例密集型工作流的预演算调度算法p c s a ，该算 法对工作流应用进行初始化计算，按照各实例在不考虑竞争的情况下优先选择 的顺序使得每个任务获得一个可执行节点的优先级序列，实例按照优先级最高 原则选择空闲计算资源执行，从而保证不同运行环境下每个流程实例的运行结 果接近最优，即执行代价与传输代价总和最小。 z h i f e n gy u 和w e i s o n gs h i 1 4 提出了一种基于计划的多工作流调度策略， 其核心思想是赋予工作流中的每一任务一个权值，权值是在单个工作流中根据 任务的执行开销计算得到，每一工作流实例对应一个计划器，计划器将工作流 实例中的可调度任务加入到任务池中，由执行器根据任务的权值进行调度。当 任务池中的任务属于单个工作流实例时，首先调度权值高的任务，属于多个工 作流实例时，首先调度权值低的任务。此方法的目的在于维持资源利用率和吞 吐量基本不变的前提下，缩短单个工作流实例的执行时间。但是该方法可能出 现饿死情况，即某些任务可能无法得到调度。另外，该方法也是仅仅考虑了流 程的执行时间，并没有将其他q o s 属性考虑在内。 孙瑞志等 3 7 针对过程中活动间不同活动语义的上下文，对活动多实例的 活动属性进行了统一的形式描述，提出了活动多实例控制体s h e l l ，用于控制活 动多实例的分配和提交并根据不同的活动语义，处理多实例的同步并控制整个 过程的运行。 2 2 用户体验及其度量 用户体验( u s e re x p e r i e n c e ，简称u ) ( 或u e ) 是一种纯主观的在用户使 用一个产品( 服务) 的过程中建立起来的心理感受。由于用户体验是一种纯主 观的心理感受，就必然带有一定的不确定性因素。个体的差异也决定了每个用 。 户的真实体验是无法通过其他途径来完全模拟或再现的。但是对于个界定明 确的用户群体来讲，其用户体验的共性是可以经由良好设计的实验来认识到的。 8 山东大学硕士学位论文 随着计算机技术和互联网的发展，技术创新形态正在发生转变，以用户为中心、 以人为本越来越得到重视。 “用户体验”这个术语很复杂。狭义的说，它是指以电子为媒介的消费者 关系以及它的支持机制，包括看得见得用户界面、参与和交互处理程序以及反 馈系统。广义的说“用户体验”这个术语包含了终端用户的行为和态度以及他 们实际使用系统的动机。满足终端用户的需求以便他们改变行为并愿意分享体 验是成功的重要条件。如果这些基本条件得不到满足，主要的用户体验就无望 得到广泛采用。为了成功，用户体验必须实现企业和用户之间的价值平衡，在 追逐盈利能力的同时，致力于建立信任，满足客户需求，促使任务的顺利完成。 用户体验贯穿在一切设计、创新过程，如用户参与建筑设计和工作环境、 生活环境的设计和改善，用户参与i t 产品设计和改善等。i t 应用设计方面的 用户体验主要是来自用户和人机界面的交互过程。在早期的软件设计过程中， 人机界面被看做仅仅是一层包裹于功能核心之外的“包装”而没有得到足够的 重视。其结果就是对人机界面的开发是独立于功能核心的开发，而且往往是在 整个开发过程的尾声部分才开始的。这种方式极大地限制了对人机交互的设计， 其结果带有很大的风险性。因为在最后阶段再修改功能核心的设计代价巨大， 牺牲人机交互界面便是唯一的出路。这种带有猜测性和赌博性的开发几乎是难 以获得令人满意的用户体