（计算机系统结构专业论文）基于可信度预测的自适应分布式计算系统研究.pdf

上海大学硕士学位论文 摘要 随着互联网络的迅速发展和普及，为了追求网络上空闲资源的有效利用， 一些著名的分布式计算项目陆续出现在了我们眼前。它们通常是把一个非常庞 大繁重的计算问题分解成许许多多小的、容易解决的问题，通过互联网上闲置 计算机自愿提供的计算来解决这些问题。这些分布式计算项目的发展告诉我们， 网络上闲置资源加在一起所提供的强大计算潜能完全有能力超过专用的高性能 计算机。 目前，在如高校、大公司等机房中，由于各种原因，任意时段总有一定数 量的计算机处于待机状态，本文旨在设计开发一种自适应分布式计算系统。在 该系统中，当出现空闲计算机时，部署于该节点上的客户端将通知管理服务器 把该节点纳入系统，从而系统得到扩充，如有计算作业，则向该节点派发。这 样，空闲的计算资源便可被高效地利用起来。 由于这些机房计算机的使用情况在时间上具有一定规律性，据此，本文提 出了自适应分布式系统资源可信度的概念，并使用一种基于资源节点的历史信 息推算未来资源节点可信度的模型，该预测模型依据时间序列分析法通过输入 资源的相关历史信息，来预测资源的可信度，为自适应分布式系统中计算资源 的调度提供依据，提高了计算服务的质量。在设计自适应分布式计算系统中， 本文把系统功能分为四个重点组成部分：计算资源监视器、计算资源池、自适 应管理器和作业管理器，然后利用j i n i 基础件来构建本系统，并把基于可信度 预测的模型应用在资源调度中。最后，我们将本系统成功部署在这些机房中， 实现了充分利用闲置资源来进行高性能计算的重要意义。 关键词：分布式计算，可信度，自适应，时间序列，j i n i v 上海大学硕士学位论文 a b s t r a c t w i t ht h er a p i d l yd e v e l o p m e n ta n dp o p u l a r i z a t i o n o fi n t e r n e t ，s o m ef a m o u s d i s t r i b u t e dc o m p u t i n gp r o je c t sa p p e a ro ni n t e m e t t h ed i s t r i b u t e dc o m p u t i n g p r o j e c t su s u a l l yd e c o m p o s et h el a r g eh e a v yc o m p u t i n gp r o b l e mi n t om a n ys m a l la n d e a s yo n e s ，a n dd i s p a t c ht h e mt o t h ei d l ec o m p u t e r so ni n t e m e tb yv o l u n t e e r c o m p u t i n gt os o l v et h ep r o b l e m t h ed e v e l o p m e n to fd i s t r i b u t e dc o m p u t i n gp r o j e c t s t e l l su st h a tt h ep o t e n t i a lc o m p u t i n gc a p a b i l i t yo fi d l er e s o u r c e so nn e t w o r kh a s c o m p l e t e l ye x c e e d e dt h a to fs p e c i a lh i g l lp e r f o r m a n c ec o m p u t e r s a tp r e s e n t ，t h ec o m p u t e rr o o m sa l w a y sh a v ea q u a n t i t yo fc o m p u t e r si ns t a n d b y s t a t ea te a c ht i m ef o rs o m ek i n d so fr e a s o n si ns u c hu n i v e r s i t i e sa n dc o m p a n i e s t h i s p a p e ri sa i mt od e s i g na na u t o - a d a p t i v ed i s t r i b u t e dc o m p u t i n gs y s t e m i nt h i ss y s t e m ， w h e ni d l ec o m p u t e ra p p e a r s ，t h ec l i e n td e p l o y e do ni tw i l l n o t i f yt h ec e n t r a l a d m i n i s t r a t o rs e r v e rt o b r i n gi t i n t o s y s t e m t h u s ，a u t o a d a p t i v ed i s t r i b u t e d c o m p u t i n gs y s t e mw i l lb ee n h a n c e d w h e nt h e r ec o m e sc o m p u t i n gt a s k ，s y s t e mw i l l s e n di tt ot h ei d l ec o m p u t e r i nt h i sw a y , w ec a nm a k ee f f e c t i v eu t i l i z a t i o no fi d l e c o m p u t i n gr e s o u r c e s i ns u c hc o m p u t e rr o o m s ，t h et i m eo fu s i n gc o m p u t e r sh a ss o m ec e r t a i nr u l e s s o ， t h i sp a p e rp r o p o s e sac o n c e p to fr e s o u r c er e l i a b i l i t yi na u t o a d a p t i v ed i s t r i b u t e d c o m p u t i n gs y s t e m w eu s e dap r e d i c t i o nm o d e l ，w h i c hi sb a s e do nh i s t o r i c a l i n f o r m a t i o n , t op r e d i c tr e l i a b i l i t yo fr e s o u r c e s t h i sp r e d i c t i o nm o d e lu t i l i z e st i m e s e r i e sa n a l y s i st op r e d i c tf u t u r er e l i a b i l i t yo fr e s o u r c e sb yr e l a t e dh i s t o r yi n f o r m a t i o n t h ep r e d i c t i v er e l i a b i l i t yi st h ee v i d e n c e o fr e s o u r c es c h e d u l es t r a t e g ya n di t i m p r o v e st h eq u a l i t yo fc o m p u t i n gs e r v i c e w h i l ed e s i g n i n gt h es y s t e m ，w ed i v i d e t h ef u n c t i o n si n t of o u rm a i np a r t s t h e ya r ec o m p u t i n gr e s o u r c em o n i t o r 、 c o m p u t i n gr e s o u r c ep o o l 、a u t oa d a p t i v em a n a g e r a n dj o bm a n a g e r t h e n ，w e c r e a t et h ea u t o a d a p t i v ed i s t r i b u t e dc o m p u t i n gs y s t e mb a s e do nr e l i a b i l i t yp r e d i c t i o n b yj i n it e c h n o l o g ya n ds u c c e e di nd e p l o y i n gi ti nc o m p u t e rr o o m sa n dr e a l i z et h e a i mo fm a k i n ge f f e c t i v eu t i l i z a t i o no fi d l er e s o u r c e s k e y w o r d s ：d i s t r i b u t e dc o m p u t i n g ，r e l i a b i l i t y , a u t o a d a p t i v e ，t i m es e r i e s ，j i n i v l 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 签名：蓥盘怎么。日期：罂壁! 主：；。 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，h p ： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：蓥丛导师签名：盘主! 至兰日期：丝堕：耋兰9签名：经丛导师签名：基玉兰聋坠日期：丝堕：耋兰9 h 上海大学硕士学位论文 1 1 课题背景 第一章绪论 随着计算机技术的广泛应用，计算已经成为科学研究和探索未知世界的一 种重要途径。所拥有计算能力的强弱已经成为了影响科研水平的一项重要因素。 购买c o n s t e l l a t i o n s 、m p p 、c l u s t e r 等各种类型的高性能计算机【i 】，是获得强大 计算能力的一种重要手段，然而，伴随着计算能力而来的还有前期购买和后期 维护所需的费用，即便是其中相对廉价的c l u s t e r ，其开支也是相当不菲的。 除了购买专用的计算机还有其他获得强大计算能力的方法吗? 美国加州大 学伯克利分校的s e t i h o m e 2 】项目就很好的回答了这一问题。s e t i ，h o m e 是 一项利用全球联网的计算机共同搜寻地外文明的科学实验计划。瞄准太空的射 电天文望远镜时刻捕捉着来自外太空的大量信息( 每天信息量约3 0 0 g b ) ，这些 信息被传回并保存，但是，其信息量之大，绝非若干台高性能计算机所能处理。 这些信息存在一些特点：各部分数据之间依赖性小( 即每一部分的计算都不需 要过多依赖其他部分的处理结果) ，如被分治处理，基本无需通信。基于这些特 性，伯克利分校启动了s e t i h o m e 项目，它试图使用全世界联网的各种计算 资源来一同处理这些被传回的数据，自1 9 9 9 年项目发起至今，已有约3 2 万台 联网电脑参与，为处理这些数据提供了强大的计算能力【3 】。 s e t i h o m e 项目启示我们，有效收集和使用联网的计算资源，可以为解决 数据依赖性低的问题提供强大的计算潜能。事实上，在生产和科研中，这类低 数据依赖性问题还是较为常见的，如：平面图像处理、模式识别、3 d 模型渲染 等。 当今，在企业办公、学校教学、家庭生活中，个人电脑的使用已经非常普 及。由于网络硬件环境的高度发展，这些计算机一般都已通过i n t r a n e t 和i n t e m e t 互联。很多调查研究表明，计算机至少有1 3 到2 3 的时间是空闲的，而随着硬 件处理能力的提高，空闲时间会不断增加，最近的统计资料表明，c p u 的平均 利用率仅有1 0 左右【4 1 。如果能将这些处于空闲状态的计算资源统一管理和利 用起来，将可以在不投入新开支的情况下获得强大的计算能力。 在任何一所大学里，其学生机房拥有数百台计算机是不足为奇的，任意时 段总有一定数量的计算机处于空闲状态，本课题所涉及的项目旨在设计开发一 个自适应分布式计算系统，当部署该系统的机房中出现空闲计算机时，部署于 该节点上的系统客户端将自动通知管理服务器把该节点纳入系统，从而系统得 上海大学硕士学位论文 到扩充，如有计算作业，则向该节点派发：如有人开始使用已纳入系统的节点， 则该客户端从计算系统中被删除，系统规模缩减。这样，间歇性出现的计算资 源便可被高效地利用起来。由于学校机房计算机的使用情况在时间上具有一定 的规律性，据此，项目中提出了资源可信度的概念，它用来描述计算资源服务 能力的可靠程度，并在系统资源调度中使用了一种基于历史信息预测未来计算 资源可信度的模型，该模型通过输入计算资源的相关历史信息，来预测下一时 段内的资源可信度，从而为自适应分布式计算系统中的资源调度提供较可靠的 依据，提高计算服务质量。 1 2 国内外研究现状 分布式计算是网络技术发展的新阶段，采用分布式技术可以将i n t e r a c t 或 者某个局域网中的闲置的计算机都收集起来形成一个潜在的资源池，产生了强 大的计算能力【5 】。当用户需要进行大规模计算时，只需要提交任务，也不必知 道使用了这个资源池里的哪些资源进行计算，以及具体资源所在的位置。这样 的话，不管是何时何地，闲置的计算机资源都能得到合理的应用，而且能够得 到一个理想的计算效果。 利用分布式计算来处理繁重的计算问题可以大大的提高效率，从而节约了 时间，减少了成本。因此，分布式计算目前的主要用途，就是用在一些需要强 大运算能力的实验上【6 】。 2 0 0 2 年1 0 月7 日，以破解加密技术而著称的d i s t r i b u t e d n e t t 刀宣布，在经 过全球3 3 1 万名电脑高手共同参与，苦心研究了4 年之后，破解了以研究加密 算法而著称的美国r s a 数据安全实验室开发的r c 5 6 4 密匙。业内人士认为， 这一成果将在计算机发展史上具有里程碑般的意义。 其实，国外利用“分布式计算 完成庞大计算工程的项目已经有好多了。 比如，为了根除炭疽的威胁，美英科学家和几家高技术公司向全世界的个人电 脑用户发出求助公告，希望利用他们个人电脑的闲置资源帮助寻找治疗炭疽的 有效方法【8 】。在这个计划中，个人电脑用户可以在英特尔公司的网址下载一个 程序。当他们的电脑开机而闲置的时候，这个程序会在后台自动运行，而在屏 幕上出现一个屏幕保护图案。该程序的功能是利用个人电脑闲置的计算能力， 分析分子结构。如果一批数据处理完毕，程序会把结果发回联合设备公司的数 据中心，然后要求下载新一套数据继续计算。参与炭疽研究的个人电脑将帮助 科学家分析、筛选总共3 5 亿个化合物分子，从中找出合适的药物来治疗炭疽。 这相当于无数个人电脑用户捐献出他们电脑中多余资源和零碎时间，建立一个 2 上海大学硕士学位论文 虚拟的超级计算机来执行运算。再比如，在英特尔与联合设备公司以前合作的 癌症研究项目中，世界上有1 3 0 多万台个人电脑参与，其计算能力为科学家提 供了一台模拟超级计算机，比目前世界上最强大的l o 台超级计算机加在一起还 要强 9 1 。参与炭疽研究项目的英国牛津大学项目科学主管格雷厄姆理查德说， 如果没有分布式计算技术的支持，科学家完全没有其他办法可以完成这么庞大 的工程。 因特网上分布式计算还应用在数学领域，“梅森素数大寻找”( g i m p s ) 1 0 】 这一项目的目的是寻找梅森素数( 即2 的素数次幂减1 ) 中的大素数，最近发现 的第3 7 个梅森素数是由美国加州大学1 9 岁学生罗兰克拉克森发现的 l o = 3 0 2 1 3 7 7 的梅森素数，这是一个共有9 0 9 5 2 6 位的数。 基于网络的分布式计算的实现及其应用也不仅仅局限在上述几方面，随着 信息社会的迅猛发展，越来越多的领域都涉及到处理海量的数据。更多的前沿 科学需要借助这样的平台来推动其研究的发展。这些需求不只是局限在科学计 算、国家高端科技上，在工业和商业领域也不断地体现其价值。例如：船舶设 计、汽车制造、证券指数计算、电力安全评估、建筑工程抗震性评估、电磁辐 射计算等。 然而，目前国内对于这类开放的分布式计算应用项目的研究还是不多，有 些也只是刚刚起步。在国际高科技竞争日益激烈的今天，分布式计算对促进科 技进步、推动经济发展的作用是有目共睹的。我们完全有必要对这类分布式计 算进行新的探索与研究，充分利用好网络上闲置的计算资源，把分布式计算真 正融入我们的生活中，将分布式计算应用开展的更加广泛，为我们解决更多的 实际问题。 1 3 本文主要内容和组织结构 目前，国外已经开展了较多的分布式计算项目，但国内对此方面的研究还 比较少。本文根据当前高校机房计算机的使用情况，设计了一种自适应分布式 计算系统，利用空闲计算资源来为用户提供计算服务。由于机房排课的原因， 通常会有无课程安排的空闲时间段，在这些时间段中，机房中少量的计算机会 有人使用，而绝大部分计算机则处于空闲状态。根据计算机的使用情况，有选 择性地将空闲的计算机纳入自适应分布式计算系统中。这样，闲置的计算资源 就可以通过该系统被收集起来，组成一个强大的计算资源池，利用这些闲置资 源为一类可划分为多个小粒度且数据无依赖性的问题提供高性能计算服务，从 而充分利用了这些闲置的计算资源。 3 上海大学硕士学位论文 在自适应分布式计算系统中，本文重点研究了自适应分布式计算系统中计 算资源提供服务的可靠性问题，提出了一种动态描述分布式系统资源可信度的 概念，并针对机房中计算机在使用时间上的特点，结合时间序列预测法，设计 了一种基于可信度预测的调度模型，该模型通过输入资源节点的相关历史信息， 来预测下一时段内计算资源的可信度，从而为自适应分布式系统中资源调度提 供了依据，以此来调度比较可靠的空闲资源给用户，同时保证了计算服务的质 量。 本文分为六章：在第一章绪论中介绍了本课题的研究背景以及目前分布式 计算的研究现状。 第二章详细介绍了分布式系统的概念，包括分布式系统定义、分布式计算、 分布式系统的调度结构、调度中的一般问题和自适应分布式系统。 第三章研究了自适应分布式计算系统中计算资源提供服务的可靠性问题， 提出了一种动态描述分布式系统资源可信度的概念，结合可信度的多方面性给 出了一种有效的综合计算资源可信度的方法，用资源可信度的大小来描述计算 资源服务能力的可靠程度。并根据自适应分布式系统中计算资源的特点，提出 了可信度预测的意义和必要性。 第四章详细描述了可信度预测的方法，把资源节点的负载预测作为可信度 预测的主要指标。分析了资源的负载指标、负载的获取方法及负载的特性，介 绍了4 种预测方法。然后，本文结合高校机房中计算机在使用时间上的规律性， 将时间序列分析法运用在负载预测中，并详述了如何利用时间序列a r m a 模型 对计算资源进行负载预测的过程，并通过与其他预测方法的误差比较，a r m a 模型获得了较好的预测效果。最后，我们设计了一种基于可信度预测的调度模 型，它包括了基本预测模型、可信度预测调整机制和资源调度算法，通过该模 型可以较有效地预测未来时段内的资源可信度，为自适应分布式系统中资源调 度提供了依据，同时提高了系统中空闲资源的服务质量。 第五章对自适应分布式计算系统进行了详细设计，包括系统的四个主要组 成部分：计算资源监视器、计算资源池、自适应管理器和作业管理器。描述了 自适应分布式计算系统的构建方法和系统的自适应性，并把基于可信度预测的 模型应用在资源调度中。然后，我们将该系统成功部署在机房中，并进行了分 布式作业提交实验，获得了较好的效果，证实了该系统的可用性，基于可信度 预测的调度模型也有效地为用户选择了较可靠的计算资源，缩短了作业运行总 时间，提高了作业执行的成功率，实现了充分利用闲置计算资源来进行高性能 计算的重要意义。 第六章总结了本文工作，提出了自适应分布式计算系统的改进与未来展望。 4 上海大学硕士学位论文 第二章分布式系统概述 2 1 分布式系统 随着计算机网络的发展，计算机系统也有了新的发展，具体表现为由单机 向并行多处理机，由集中式向分布式，由单一信息媒体向多媒体方向发展的趋 势【l l 】。 当今计算机技术的飞速发展，导致了硬件价格不断下跌，微型机、工作站 数量也开始增加，大量的微型机、工作站分布在各个地域中。由于传统的v o n n e u m a n n 体系结构日趋到达其处理能力的物理极限，计算机系统正朝向多机系 统和松耦合的分布式系统方向发展。人们希望在利用网络环境来充分利用这些 资源的同时，又能像以往单机用户那样简单方便地操作，而不需要知道网上用 户和当前网上资源等网络层次的实现细节【1 2 】。针对这一要求，以微型机、小型 机为主，通过局域网络互联的分布式计算机系统就应运而生了。 分布式计算机系统是计算机应用发展的必然趋势，微型机特别是高档的3 2 位微处理器为开发分布式计算机系统提供了物质基础，局域网技术为互连主机 提供了物理环境和做好了技术准备，使计算机系统由集中式走向分布式。： 从上面的叙述可以看到，分布式计算机系统( 或简称分布式系统) 就是由 多台计算机组成的系统，更确切地说，它是满足以下条件的多计算机系统【l3 】： 系统中的计算机之间可以通过通信来交换信息。因此，运行于系统中 的计算机上的程序之间可以使用系统提供的通信手段来交换数据。 系统中的各台计算机没有主次之分，既没有控制整个系统的主机，也 没有受控于它机的从机。因此，主从控制计算机系统或分机控制计算 机系统都不是分布式系统。 系统的资源为所有用户所共享。在某台计算机终端上的用户不仅可以 使用位于该机上的资源，还可以使用位于它机上的资源。而且分布式 系统提供的资源共享功能，可以使用户只需要考虑系统是否具有自己 所需要的资源，而无需考虑资源在哪里。 系统中的若干台计算机可以互相协作来完成一个共同的任务，或者说， 一个程序或任务可以分布于几台计算机上并行地运行。 人们研究分布式系统是为了开辟一条发展计算机的新途径，经过多年的研 究实践，分布式系统在办公自动化、自动控制、企业管理、计算机教学系统和 计算机辅助测试等方面已经有了越来越广泛和深入的应用，人们也已经看到， 上海大学硕士学位论文 由若干台计算机所组成的分布式系统在许多方面都比单计算机的集中式系统优 越，比如，运行坚定，维护方便，扩充容易，真正地并行工作，效率较高等等。 2 2 分布式计算 分布式计算( d i s t r i b u t e dc o m p u t i n g ) 是：指借助计算机网络将分布在不同地点 的计算实体组织在一起，进行信息处理的一种方式【l4 1 。分布式计算主要是将计 算工作分摊到多个计算机中，提高了执行的并行性，降低集中在单个计算机上 运算的负载及可能的危险【l 们。分布式计算在系统可靠性、可扩展性、可用性和 并行处理等方面具有明显的优势。 计算机网络技术的发展使相互独立的计算机集合成一个相互协调的有机整 体【1 7 】。基于网络的分布式计算有着巨大的计算潜力、良好的可扩展性和灵活的 体系结构，成为当今计算机技术发展的一个重要分支。 2 3 资源调度的必要性 在一个分布式系统环境中，大部分节点在大部分时间内都处于低利用率状 态。加州大学b e r k e l e y 研究小组的研究结果表明：即使在每天下午最繁忙的时 候，平均也有近6 0 的节点处于空闲可利用状态。分布式系统中这些空闲节点， 如果不加以合理的利用，其c p u 等计算资源就浪费了【1 8 】。而实际上在一个局域 网或高速网络内，在适当的调度机制的控制与管理下，可以充分利用这些闲置 节点来执行大规模并行计算。 在论及分布式系统调度的必要性时，r i c h a r de f r e u n d 等人列举过一个具有 多层并发度计算需求的计算实例【1 8 】。经计算分析表明，“该程序对于普通串行机 需要运行1 0 0 个时间单位，对于向量机需要5 0 个时间单位，而采用分布式系统， 计算过程仅需5 个时间单位。显然，后者所付出的代价是：必须进行适当的任 务分解、分配和调度。 分布式系统确实能够提供巨大的处理能力，但要实现和充分利用这一能力， 需要优良的资源分配方案，对系统进行进一步的优化。资源调度是分布式系统 的资源管理核心，它主要是合理地在各资源节点之间分配系统负载，以达到系 统的综合性能最优。 由此看来，资源调度对于提高分布式系统的计算性能是十分重要的。对于 分布式系统需要采取一定的调度策略，合理地分配任务，并调度任务到各个资 源节点上，保证总任务尽快完成。 6 上海大学硕士学位论文 2 4 自适应分布式系统 所谓系统的自适应性就是指系统能够改变自身的某种特性以适应系统中参 数变化的一种特征。任何一个实际系统都具有不同程度的不确定性，自适应系 统能够通过修正自己的特性以适应系统参数动态性的变化【l 引。 本文所设计的自适应分布式系统是通过在潜在的计算资源节点上部署，监 测这些资源节点的使用情况( 这里所说的情况可以通过具体环境的不同而有针 对性地定义，本系统中将情况分为在时间长度tr a n g e 内有无鼠标、键盘事 件两种) ，从而判定这些节点是否空闲( 本系统中，tr a n g e 内无鼠标键盘事 件被判定为空闲) ，如处于空闲状态，则与管理服务器通信，加入计算系统，计 算系统的规模扩充，全系统的计算能力得到增强。系统的规模可以随资源节点 的使用情况动态增大或减小，达到了充分利用机房中闲置计算资源的目的。 本系统的自适应性主要体现在计算资源可以在任意时刻加入或退出分布式 计算系统。由于计算资源有这些灵活性的特点，用传统的分布式系统资源调度 的方法来进行资源调度显然是不太合适的，因为系统无法及时获得计算资源的 动态信息，也较难判断资源节点的未来状态。 因此，为了保证自适应分布式计算系统为用户提供计算服务的质量，本文 结合了自适应分布式系统中计算资源动态性的特点，提出了一种资源可信度的 概念，用来描述自适应分布式系统中计算资源提供服务能力的可靠程度，以此 来作为系统中资源调度的依据，达到充分利用闲置资源的目的。 下一章我们将对资源可信度做详细介绍。 2 5 本章小结 本章重点描述了分布式系统的概述，包括分布式系统、分布式计算、分布 式系统资源调度的必要性和自适应分布式计算系统的基本特性。 7 上海大学硕士学位论文 第三章自适应分布式系统的资源可信度 3 1 资源可信度概念 3 1 1 资源可信度的提出 在自适应分布式系统中，资源节点可以动态地加入和退出系统，可能会导 致提供计算服务的不可靠性。因此，在自适应分布式系统中，对资源节点的动 态评价是十分重要的。为了更好地反映资源的动态性、可用性和可靠性，本文 提出了一种资源可信度的概念，它是用来动态描述资源节点提供服务的可靠程 度。 3 1 2 资源可信度定义 可信度【2 0 】是描述资源提供服务能力的一种可靠程度，它已经成为判定资源 节点是否可信的一个重要因素，较多地运用在网格计算和p 2 p 网络模型中，然 而至今可信度仍没有一个很明确的概念。1 9 7 3 年d e u t s c h 给出的定义为：_ 个 个体可以找到拥有其所需资源节点的信心【2 1 】；而2 0 0 0 年g r a n d i s o n 和s l o m a n 则把可信度定义为一个整体可以单独、安全、可靠的完成某个特定方面内容的 能力【捌。本文结合文献 2 3 】的定义以及自适应分布式系统中资源节点的特点提 出了一种资源可信度的定义。 资源可信度( r e s o u r c er e l i a b i l i t y ) 是指一个资源节点基于自身性能和提供 服务的可靠程度所被用户所信任使用的能力，用r 表示。 资源可信度可以描述资源节点的动态行为，以此作为资源选择的依据，使 比较稳定可靠的资源节点能有较大的作业执行机会，从而提高整个自适应分布 式系统的服务质量。 资源可信度的值表示用户信任使用计算资源的程度，也可以表示用户信任 计算资源能做好此次计算服务的概率，它可以是连续的，也可以是离散的。每 个计算资源都拥有一个资源可信度【2 4 】。 f a r a ga z z e d i n 提出了可信度的数值应该在完全不值得信任到完全值得信任 区间内，是一个离散的变量，并把可信度的层次分为5 层【2 5 1 。其解释如表3 1 所示。 上海大学硕士学位论文 表3 1 可信度层次解释 可信度层次等同的可信度数值 描述 a1 非常低的可信度 b 2较低的可信度 c3一般的可信度 d 4 较高的可信度 e5非常高的可信度 除了用离散的数值来表示可信度，还可以对可信度的取值是连续的数值， 通常用的比较多的取值区间为 o ，1 】。当资源可信度的取值区间为【0 ，1 时，值为 o 时表示不信任此资源节点，值为1 时则表示完全信任此资源节点，而在此区 间内的其他取值时表示此节点被信任的概率。 本文采用的资源可信度为一个连续的数值，它的取值区间为 o ，1 】，即：每 个资源的可信度是一个 0 ，1 】的正小数。 3 1 3 资源可信度特点 自适应分布式系统中的资源可信度有如下几个特点： 可信度是动态变化的，根据资源节点提供的服务质量而进行改变。在 自适应分布式系统中，资源是可以自由加进和退出的。因此，当资源 节点提供的服务质量好，可信度就增加；当资源节点提供的服务质量 不可靠，可信度就减小。 资源节点可信度多方面性。对一个资源节点的可信度描述是多方面的， 这与用户作业的资源需求有关。 可信度的评价是主观的。对一个资源节点的可信度评价是用户根据作 业需求对资源节点所提供服务的评价值。每个作业都有自己的一个服 务满意标准，作业种类不同，标准就不同，故在对资源节点可信度评 价时，也要考虑到全方面性。 3 2 可信度计算 根据资源可信度具有上述3 方面的特点，它的计算方法也必须考虑到多方 面性。首先，资源可信度与资源节点的负载情况有关，资源节点的负载越高其 可用性就越差，提供服务的质量也降低，资源可信度的值就越低：其次，资源 可信度与资源节点所拥有的硬件性能有关，硬件性能越强越可以提高用户作业 的执行效率，其可信度的值越高；再次，资源可信度与资源节点执行作业的历 9 上海大学硕士学位论文 史情况有关，那些历史作业完成率高的资源节点，能保证作业的稳定完成，其 资源可信度也就越高；最后，资源可信度还与资源节点的在线时间有关，那些 经常在线的资源节点具有较高的可信度，可以完成一些艰巨的任务。 设资源硬件性能为p ，资源负载为l ，资源负载空闲度为i ( 即：资源满负 载减去资源负载l ) ，资源历史作业完成率为d ，资源在线时间为t 。 资源可信度r 就可以表示成p 、i 、d 和t 的函数，用公式可以表示为： r = f ( i ，p ，d ，t ) = 入i * i + 入p * p + 入d * d + 入t * t( 3 1 ) 其中，入i 、入p 、入h 、入t 分别为资源负载空闲度i 的可信度权值、资源硬 件性能p 的可信度权值、资源历史作业完成率d 的可信度权值、资源在线时间 t 的可信度权值。这些可信度权值都是可以动态调整的，且满足：入i + 入p + 入d + 入t = 1o 在计算可信度过程中，硬件性能p ，资源负载空闲度i ，资源历史作业完成 率d ，资源在线时间t 在计算中都必须做归一化处理。 归一化处理公式：z i = ( 3 2 ) 式3 2 中，x i 是资源节点i 的参数值，z i 是该资源节点参数进行综合归一化 后的值。归一化的目的就是去掉不同参数中不同单位所带来的计算影响，对于 综合评价可信度是十分有效的。 从式3 1 中可以看出不同的可信度参数分别对应了不同的可信度权值，由 于权值不同，导致了可信度参数对资源可信度的影响程度不同。这些可信度权 值可以根据用户提交作业的需求情况进行调整。比如：用户提交的作业对资源 的计算效率要求比较高，就可以把h 和砩设定了高些，其他两个权值设定了低 些；用户希望提交的作业能够稳定完成，则可以把九d 和h 设定了高些，其他 的权值设定了低些。这些权值的设定都在用户提交作业的时候预先根据自己的 需求而设定的，这样就满足了不同需求的作业可以找到自己满意的资源节点。 下面，我们将根据系统中闲置资源节点的当前参数对可信度进行计算。 表3 2 列出了自适应分布式计算系统中当前可用资源节点的可信度参数信 息。其中，当前负载大小为资源的当前系统利用率；负载空闲大小为( 1 0 0 一 当前负载) ；资源性能大小用c p u 的主频大小( 单位：m h z ) 来表示；历史作 1 0 上海大学硕士学位论文 业完成率大小为( 完成作业数接收作业总数) ；在线时间的大小为资源加入系 统的总时间( 单位：r a i n ) 。 表3 2 资源节点的可信度参数信息 ，翻鼻品，警g _ 眦；旦勇而r 胂- 一崔硎弹旦! 凹川_ _ _ ，疗；谚置 墨；口= 簧e a 翻呵璺7 碚口r 坍- 节点10 8 6 ；0 1 43 o0 41 2 0 i n - j ，_ 节点2 ；0 6 70 3 33 2o 5 2 0 0 一一， 节点3 0 7 2o 2 82 80 31 3 0 节点4 0 5 3 o 4 73 2o 6 1 4 0 i 节点5 0 2 1 0 7 93 20 83 4 0 ，。 。， 节点6 0 4 5 0 5 53 00 52 1 0 v 一” ”一 节点7 ：0 1 7 o 8 33 oo 83 4 0 节点8 ；0 5 8 o 4 23 2o 61 0 0 节点9 ；0 3 4 o 6 63 oo 52 1 0 ：“一“ 节点1 0 0 2 8o 7 23 0o 73 2 0 经过式3 2 的归一化处理后，可以得出资源可信度的具体参数，见表3 3 。 根据作业需求，预先在系统中设定好各可信度参数的权值大小，一般用户 所需要的是计算服务，可以设入i = 0 7 5 ，入p = 0 1 ，入d = 0 1 ，入t = 0 0 5 。 经过计算后，各资源节点的可信度计算结果可见表3 4 。 上海大学硕士学位论文 表3 4 资源节点的可信度计算结果 节0 0 6 o 0 30 0 2o o l o 1 2 ， “ “h ，一 节0 1 4 0 0 3 o 0 3o 0 l0 2 2 0 1 20 0 30 0 20 0 lo 1 7 节点3 o 2 0o 0 30 0 30 0 l0 2 7 节点4 0 3 30 0 3o 0 4 o 0 20 4 3 节点5 0 2 30 0 30 0 3o 0 10 3 1 节点6 0 3 50 0 30 0 4o 0 20 4 5 节点7 0 0 30 0 30 0 l0 2 5o 1 8 o 2 80 0 3 1 0 0 3o o lo 3 5 节点9 0 3 00 0 3o 0 4 0 0 2o 3 9 节点1 0 3 3 可信度预测的意义 要准确描述一个资源节点的可信度就必须把资源节点的历史情况和将来可 能出现的情况综合在一起考虑，综合评价出资源节点对于未来时段中提供服务 的可信度。在自适应分布式系统中，资源节点的不确定性决定了它未来时段中 提供服务的可靠程度是不同的。例如：机房中某一时刻有闲置资源节点，自动 加入了分布式计算系统后，注册成为了服务资源，可供用户计算使用。尽管该 资源节点的当前负载不是很高，但是根据历史使用情况，该机房的资源节点会 在下一时段被别人使用，很有可能在短时期内退出分布式计算系统。这样的资 源是不可靠的，如果把用户提交的作业分配给该类资源节点进行计算，就不能 保证提交的作业可靠完成。此时，就可以把那些根据历史使用情况推测出在下 一时段中空闲机房的资源节点作为资源服务节点分配给用户使用，增加了作业 完成的可靠性，同时也缩短了作业执行时间，真正地提高了系统的服务质量。 所以，在自适应分布式计算系统中，资源可信度的有效预测对于提高计算 1 2 上海大学硕士学位论文 服务质量和闲置资源合理调度都是十分有意义的。 3 4 本章小结 本章重点讨论与分析了自适应分布式系统中的资源可信度概念与特点，综 合它的多方面性给出了一种综合计算资源可信度的方法，并将它作为系统中资 源调度的依据。然后，根据系统中资源节点在使用时间上的特点，提出了资源 可信度预测的意义，利用资源可信度的预测值来进行资源调度可以有效地提高 计算服务的质量。 上海大学硕士学位论文 第四章可信度预测方法 4 i 可信度预测的主要指标 在自适应分布式计算系统中，结合资源节点在使用时间上的规律性，资源 可信度的预测可以较好地反映资源节点在未来时段中提供服务的可靠程度，并 用它来作为分布式系统中资源调度的依据也能够有效提高未来时段中计算服务 的质量。 在可信度计算公式3 1 中，硬件性能p ，历史作业完成率d ，资源在线时间 t 都可以通过资源节点自身的记录信息来获得到，而资源空闲度i 并不是这样， 它是一个实时变化的参数。通常情况下，我们都是用( 资源满负载一资源当前 负载l ) 来得出当前资源空闲度i 的大小。但是，系统中资源节点的当前负载l 只能表示当前时刻的系统负载，并不能推测下出资源节点在接受用户提交作业 后一段时间内的资源负载也是如此。显然，用资源负载的当前值来计算资源可 信度不能准确地描述资源节点的可信度。 因此，要获得一个比较准确的资源可信度预测，最重要的是对资源节点的 未来负载进行预测，它是可信度预测的主要指标，能否有效地预测资源节点在 未来时段中的负载情况对于可信度预测的准确性是非常重要的。 这样，可信度预测的计算公式可以进一步写成： r ( p r 。d i 。l o n ) = f ( i ( p ，e d i 。t i 。) ，p ，d ，t ) = 入i * i ( p ，e d i 。“。) + 入p * p + 入d * d + 入t * t( 4 1 ) 式中，r ( p r 川州是可信度预测值，i ( p r 础川是资源节点空闲度的预测值， l 。m 。是资源节点的负载预测值，其他参数不变。且i 。m 妣。渤，= ( 资源满负载 - - l ( p r 。d i c t io t i ) ) 。 由上可以看出，为了提高自适应分布式计算系统的服务质量，需要对资源 可信度进行有效预测，而对资源可信度的有效预测中，对资源负载l 的预测是 最主要的，它能较好地描述资源节点的未来动态变化，对用户提交作业的成功 完成有很大影响。若对资源节点未来负载情况把握的不好，就会使得用户提交 的作业不能可靠完成，浪费了计算时间。 只要利用有效的预测方法，并结合机房中计算机在使用时间上的特性，对 资源节点进行负载预测完全是可行的。在下文中，我们将重点讨论资源节点负 载预测的方法。 1 4 上海大学硕士学位论文 4 1 1 负载的定义 计算机的负载取决于负载指标。负载指标是衡量资源节点负载情况的特征 值，用于描述计算资源的空闲程度和提供服务的能力。负载指标主要有c p u 利 用率、内存利用率、磁盘利用率、网络延时等。在资源节点负载受多个负载指 标影响时，每个负载指标值的变化对负载所产生的影响也是不一样的。不同的 负载指标有不同的负载权重，权重越大表示这个负载指标的变化对资源负载产 生的影响越大；权重越小表示这个负载指标的变化对资源负载所产生的影响越 小。 资源负载的定义公式如下： n l = 厶木w ( 4 2 ) i = l 式中，w l + w 2 + + w n - 1 ，l 是资源节点负载，l i 是资源节点的负载指标， w i 是相应负载指标的权重。由于资源负载l 取决于负载指标和相应的权重，如 何选取负载指标以及如何确定负载指标的权重就成为计算资源节点负载的关键 问题。 负载指标的选择主要是根据资源节点所提供的服务类型来确定的。在白适 应分布式计算系统中，计算资源的主要功能是为用户提供计算服务，我们可以 把资源节点的c p u 利用率、内存利用率和磁盘利用率作为负载指标。 设c p u 利用率为c p u 、内存利用率为m e m o r y 和磁盘利用率为d i s k ，它们 的权重分别为w c p u 、w 删、w d i s k ，那么资源节点的负载l 就可以表示为下式： l _ c p u 毒w c p t i + m e m o r y * w 蛳f y + d i s 妒w 缸k ( 4 3 ) 其中，w c p u + w m 锄呵+ w d i s k = 1 o 在负载指标选定后，就要为每个指标确定权重。一般计算类服务对c p u 有 较高要求，我们把c p u 利用率的权重设了高些，内存利用率和磁盘利用率两个 指标的权重可以设了相对低些。 然后，我们分别对c p u 利用率、内存利用率和磁盘利用率进行定义，为后 面获取这些负载信息提供方便。资源节点的负载定义用如下代码片段表示： 上海大学硕士学位论文 4 1 2 负载的获取 以下代码片断表示的是读取资源节点的负载信息。 1 6 上海