分布式实时系统中动态负载共享算法的研究

分布式实时系统中动态负载共享算法的研究

刘军万[1]2002年在《分布式实时系统中动态负载共享算法的研究》文中研究表明在分布式实时系统中,如果任务到来不均衡地分布到结点上,那么有些结点可能过载,而另外一些结点处于空载或轻载状态,这时,即使整个系统完全有能力完成所有任务,也有些任务不能在截止时间以前完成,减少这个问题的一种方法是LS(负载共享)。 本文提出了一个在实时分布式系统有失败结点情况下容错的、动态的带区域状态变化信息广播的负载共享算法。无论何时当一个结点的状态从轻载状态到重载状态或相反,它都会向被称为伙伴集的一个结点集合中的其他结点广播这种变化,同样,一个超载的结点不通过探查其他结点的状态也能从它的优先列表中选择第一个可用的结点。本文主要讨论两个问题:确定最佳的超时值T_(out)~((i)),以便一个结点的失败能被其他的结点检测出来,即如果结点n自从最后一次收到结点i的广播信息以后还T_(out)~((i))没有收到结点i的广播信息,就认为结点i失败,并且在再次收到广播消息以前不考虑把任务交给结点i;提出了调整结点的优先列表的算法,以保证每个结点被一个也只能是一个结点选择做自己的第七个优先结点,并相应地提出了一个处理结点失败的算法。 用于诊断一个结点是否失败的超时值T_(out)~((i))的确定取决于以下叁个因素:系统负载的动态变化;此结点上的负载分配;结点的初始状态。用于计算T_(out)~((i))所需的参数可以通过贝叶斯估技术在结点i上在线估计得到,然后应用状态信息计算T_(out)~((i))。 本文的实验结果显示,带有在线估计参数、超时机制和额外的及时广播信息的动态LS算法相比其他没有任何超时机制或带有固定超时值的算法,能有效地减少任务的失败率;同时实验结果还显示,无论系统中失败结点数有多少,应用相应算法调整之后的优先列表都能保持原来的特性,而且简单的容错的备份队列方法能减少任务丢失数。

刘军万, 谭骏珊, 吴敏, 曾广平[2]2003年在《分布式实时系统中动态负载共享新策略》文中指出提出了一个在实时分布式系统中有失败结点情况下容错的、动态的、带区域状态变化信息广播的负载共享算法。如果结点 n自从最后一次收到结点i的广播信息以后T(i)out还没有收到结点i的广播信息,就认为结点i 失败,然后调整各正常的结点的优先列表,以保证每个结点被一个也只能是一个结点选作自己的第k个优先结点,以减少任务的失败率。该文主要确定最佳的超时值及时检测一个结点的失败;调整结点的优先列表以处理结点的失败。

张先哲[3]2009年在《分布式系统中的负载平衡检测与优化策略研究》文中指出分布式系统因其并行性可以降低处理的瓶颈,提供更好的性能价格比,并且具有在系统出现故障的情况下继续运行的潜力,因而得到了越来越广泛的研究和应用。然而由于分布式系统中结点的自治性,常会出现系统运行一段时间后一些结点的任务仍然很多,称之为超载,而部分结点却处于空闲状态,称之为轻载,这种空闲与忙等待并存的情况严重影响了系统的整体性能。负载平衡的目的就是尽量平衡系统各结点的负载以提高系统整体性能。前人在此方面也做了很多工作,提出了多种负载平衡策略及算法,但仍然存在一些问题。本文针对负载平衡过程中出现的负载评价和抖动问题,提出了一种新的分布式系统负载平衡策略,重点在负载平衡检测和优化方面。本文首先分析介绍了分布式系统的发展史以及其软件硬件支持,详细给出了分布式系统的结构。其次,介绍了负载平衡的相关知识,其中重点介绍了动态负载平衡。最后,提出了一种新的分布式系统负载平衡策略,并给出了其算法基本流程。本文的主要贡献首先在于在负载平衡检测方面,引入了多项重要负载指标,综合评价结点负载状况,定义了结点动态负载值。鉴于目前算法大多只把CPU队列作为负载指标,本文根据任务的不同类型给各个负载指标设置不同系数以区别各个负载指标的重要性,并将结点的动态负载值作为判断结点轻载重载的依据。这样可以较准确有效的获取结点负载状况,使超载结点迅速转移超载部分任务而不再继续接收新任务。其次,在负载平衡优化方面,引入系统管理站和实时负载值。由管理站负责周期收集并计算记录结点负载,避免了忙结点向系统广播超载信息,一定程度上减轻了忙结点的负担。同时管理站根据结点动态负载值和初始负载值计算结点的实时负载值,并生成接收结点负载线性表,以供超载结点查找最优空闲结点,从而减少任务的响应时间,同时避免因任务多次迁移得不到执行而引起的抖动现象。最后,设计负载平衡系统模型,并利用OPNET对负载平衡系统进行仿宾建模,以求素数为例对各结点CPU利用率进行比较分析,以验证平衡策略的有效性。

符利华[4]2011年在《基于CPS的实时系统的面向方面的容错调度模型》文中研究说明随着计算技术、网络技术和控制技术的深入发展,一种最新的复杂系统Cyber-physical Systems应运而生。Cyber-physical Systems是运用3C技术和3i技术手段集计算、通信与控制于一体的下一代智能系统。Cyber-physical Systems高可靠性要求已成为影响其安全、可控的关键因素,提高Cyber-physical Systems实时系统的可靠性具有重要意义。实时任务的容错调度作为保障实时系统可靠性的重要技术,已经成为实时系统研究的热点。因此,研究和设计出高效、简单、适应于Cyber-physical Systems实时系统的容错调度模型和算法是Cyber-physical Systems需要解决的首要问题。本文也是在此背景下研究Cyber-physical Systems实时系统的容错调度模型和算法。本文首先介绍了Cyber-physical Systems的体系结构、与物联网的关系、新特点以及Cyber-physical Systems的应用前景。然后引入面向方面编程技术和UML扩展机制,利用UML扩展框架,实现UML在面向方面的建模技术和横切点分离技术的扩展,为Cyber-physical Systems实时系统的容错分析提供可视化的图形模型。在此基础上,本文对Cyber-physical Systems实时系统的容错模型做了深入研究,主要工作如下:1.介绍了UML在面向方面的扩展机制,实现了面向方面的可视化建模。运用UML的扩展框架UMLTM对实时系统的容错方面和时间方面建立可视化的视图,并结合Cyber Physical网络环境下的实时系统,通过UMLTM框架,将面向方面的思想运用到分析Cyber Physical网络环境下的分布式实时系统容错性和调度算法模型。2.提出了Cyber-physical Systems网络环境下的分布式实时系统的概念,并进一步给出了CPS异构分布式实时系统的概念。然后分析了CPS异构分布式实时系统的基本特征,给出了CPS异构分布式实时系统的基本任务模型,证明了其任务的可调度性,并给出了分析CPS异构分布式实时系统任务调度算法性能的评价体系。3.文中提出了两种适用于Cyber-physical Systems实时系统的容错调度算法:CPS实时任务动态负载均衡算法(CPS_DLBA)和面向方面的CPS实时容错算法(AO_CPS_RTFT)。结合仿真实验对两种算法进行了对比,根据实验图,得出了在算法均衡性和任务负载率两方面AO_CPS_RTFT均优于CPS DLBFT的结论。4.用城市地铁系统这个实例来阐述Cyber-physical Systems的基本概念以及Cyber-physical Systems异构分布式实时系统的面向方面的容错调度模型的运用,实例充分体现了面向方面技术的优点,UML扩展机制可视化建模在分析Cyber-physical Systems的优势。

王少峰, 周忠, 吴威[5]2008年在《一种面向分布式虚拟环境的分层迭代负载平衡算法》文中研究指明为了支持大规模用户共享虚拟环境,多服务器结构被应用到分布式虚拟环境系统中,每个服务器负责虚拟环境的一个区域划分.由于用户不可预知的移动和交互,可能会导致某些服务器负载过重.现有的负载平衡算法注重于将负载在服务器间重分配,但引入开销过大,影响系统交互性能.提出一种分层迭代的动态负载平衡算法,以过载区域为中心,分层地选择周围有限数量的区域作为调整目标,将过载部分由内向外迭代地扩散到各层,多次迭代达到负载平衡状态.针对倾斜和聚簇两种典型用户分布的虚拟环境,对算法进行验证并与现有的3种负载平衡算法进行比较.结果表明,该算法可以快速、有效地调整负载并引入较少的开销.

韩凤霞[6]2012年在《基于动态自适应策略的多核调度算法研究》文中研究表明多核处理器作为处理器发展的主流,依靠高效率、低成本的特点深受人们的喜爱,多核技术使微处理器的性能得到极大的提高。在对多核处理器系统研究的过程中,系统任务调度问题显得尤为重要,对调度算法提出了更高的要求。多核系统的飞速发展使多核系统中的任务调度问题成为一个新的研究课题,在任务并行运行的同时,如何提高系统的运行效率、保持系统的负载均衡是新时代的研究焦点。本文首先分析了课题研究的背景和意义,阐明了多核任务调度的基本理论知识并简要介绍了基于排队论的建模思想。针对依据单一性能指标很难对调度算法做出综合评价,本文考虑了平均周转时间、平均响应时间和CPU利用率等多个性能指标,在对多目标决策机制深入研究的基础上,给出“隶属度线性加权平均值”这一综合指标的表达式,为最优策略选择模块的设计提供了理论依据。其次,本文研究了典型调度算法,在此基础上提出了动态自适应调度算法。通过引入“隶属度线性加权平均值”这一综合指标来衡量资源对任务需求的满足程度,基于“隶属度线性加权平均值”的计算方法,并综合已有研究中所提出的各类调度算法,论文设计实现了一个具有可扩展能力的动态自适应调度模型。在任务调度时,系统通过选择“隶属度线性加权平均值”最优的调度算法为用户任务提供服务。实验结果显示,动态自适应调度算法能充分利用各类已有调度算法的特长,为不同类型的任务提供更优的服务。最后,结合负载均衡理论,递进地提出了基于负载均衡的动态自适应调度算法。所提出的基于负载均衡的动态自适应调度算法可缩短任务的平均响应时间,并均衡地提高处理器利用率。为了验证算法的性能,本文用C++语言在集成开发环境Microsoft Visual C++6.0中实现了上述算法,验证了算法的可行性和优越性。最终证实,本文提出的算法能够有效解决多核系统中的任务调度问题。

朱辉[7]2007年在《网络游戏引擎中负载均衡问题的研究》文中研究说明本文在两个863计划项目“网络游戏公共技术平台关键技术研究”以及“数字媒体公共技术平台研发”的支撑下完成,主要研究大型多人网络游戏引擎中的负载均衡问题。MMOG(Massively Multiplayer Online Games)是具有很大发展前景的大型网络游戏。这类游戏经常是成千上万个玩家同时处于一个虚拟世界,为了能够对玩家的信息进行实时响应,MMOG中通常需要多台服务器来处理来自各个玩家的信息。因此,怎样有效的分配玩家或者说如何找到一种高效的负载均衡算法成为MMOG中所面临的非常重要的一个问题。目前,网络游戏引擎中负载均衡技术的研究还不是很多,因此本文的研究具有比较重要的理论和现实意义。本文主要完成以下几项工作:1.详细分析了在网络引擎设计中要考虑的因素。包括采用分布式的体系结构,网络协议的选择,消息的等级划分和发送策略,以及采用集群化的游戏服务器。这些因素对整个系统的性能产生重要的影响。还介绍了网络游戏中比较常用的RakNet网络引擎。在后面设计的网络引擎系统架构中将使用RakNet作为系统底层通信模块。2.对目前网络游戏中的负载均衡技术做了较深入的研究。首先介绍了一般的负载均衡算法的分类以及实现技术,然后对应用于MMOG中的负载均衡技术的特点及常用的算法做了详细阐述。3.提出一种基于游戏空间划分的动态负载均衡算法,该算法将整个游戏虚拟世界进行分割,由多个游戏服务器来管理,在基于预订区域概念的基础上,通过向邻居服务器发送分配负载请求,使得一个超载的服务器能够方便地将它的一部分负载迁移到没有超载的服务器上,同时提出一种客户端迁移方案来减少该算法的开销,从而提高系统的响应速度和性能。4.在基于RakNet网络引擎的基础上设计一个网络游戏引擎系统,服务器端包括登录服务器、负载均衡服务器和多个游戏服务器。并通过该系统来验证玩家的登录退出、和游戏服务器的交互,以及用负载均衡服务器来实现一些静态的负载均衡算法。

顾伟[8]2012年在《分布式流数据实时计算框架的研究和开发》文中研究指明随着大数据量计算技术的发展,基于数据处理的应用受到广泛关注,而数据源的结构也显示出多样化的趋势,这些数据中不仅有传统的非实时的、静态结构化数据,还有很多实时的、动态产生的非结构化数据流。这类连续到达的非结构化数据序列,它们的输入率、输入量和来源都在不断变化,很难准确预测。面对庞大变化的海量数据流,要获取流数据中携带的重要信息,实时地进行复杂计算,依靠传统的分布式计算模式很难实现。这就促使本文对分布式流数据实时计算这一新的计算模式展开深入研究。目前,国内外针对分布式流数据实时计算框架的研究仍在起步阶段,尚没有一个成熟的产品。因此,作者在深入分析流数据处理应用需求的情况下,设计并实现了完整的分布式流数据实时计算框架iStream,对框架性能的关键性因素一负载均衡做了深入的研究和优化。经过实验和性能测试,证明该框架可以根据实际应用场景进行灵活的定制,并具有良好的实时性和可扩展性。本文的主要研究内容和成果如下:(1)对分布式计算框架中几个关键技术进行了研究,结合数据流形式的多样化和数据流应用场景的多样化的特点,本文实现和设计了一个不针对任何特定场景,可以解决多种复杂计算的分布式流数据实时计算平台iStream,它具有很强通用性和可扩展性,显着提高了第叁方开发人员的开发效率。(2)为了增加吞吐量、加强数据处理能力、提高计算节点集群的灵活性和可用性,研究了动态调度技术以及负载均衡算法,提出了使用时间序列预测算法解决并行计算中的任务调度这—NP-完全问题,并通过改进模型化AR模型评估算法来处理非平稳数据序列,使得程序更有效率,预测更精准,并可适用于流数据这类不能用简单的分段模型表示的数据源,同时保证了动态负载均衡算法的性能。(3)系统框架的设计与实现。在研究了并行计算中主流编程模型,诸如MapReduce等模型的基础上,将改进的发布—订阅者模型用到iStream框架中,并分析比较了多种主流的分布式进程通信方式,解决了高并发实时处理,分布式系统数据通信安全和自适应调整等分布式系统中的关键问题。并结合流计算的特点,在框架各模块的设计与实现中,对传统分布式计算策略进行了改进,提高了框架的安全性,显着降低了延迟率。(4)深入分析了分布式实时计算框架的适用场景,并通过基于CTR效果广告系统和在线参数优化系统作为案例研究了iStream在商业应用中的效果。最后对本课题进行了总结和下一步研究的展望。

雷州[9]1999年在《机群作业管理系统研究》文中认为计算机在50多年的发展中经历了五次重大的变革,大规模并行处理成为第五代计算机的最重要特征。机群系统以其卓越的性能价格比和良好的可扩展性等因素成为当今计算机体系结构与并行处理的发展方向,能够充分满足我们对计算机处理能力不断增长的需求,是当前的研究热点。 机群作业管理系统直接关系到机群性能的发挥和使用率的提高,是机群的一个重要组成部分。它能够充分利用机群的硬件软件资源及宝贵的CPU时间,有效地管理机群,合理调度作业,因此对机群作业管理系统的研究具有举足轻重的意义。 鉴于作业管理在机群系统中的重要地位,我们展开了对机群作业管理系统的研究。本文在总结前人工作的基础上,系统地研究了机群作业管理的关键问题,提出了机群作业调度的一种新的解决方案,最后就我们开发的基于曙光2000的作业管理系统进行了总结。主要工作包括: 1) 针对对机群作业管理系统的基本概念、组成、功能、特征等方面作了系统的概括。 2) 研究了几种MPP和机群系统上的作业管理系统,分析了它们的背景、基本结构、工作方式和功能特点,最后确立了作业管理系统的评判标准。 3) 从重要性的角度,设计与实现机群作业管理系统的关键问题可分为六个方面:可扩展性、负载平衡、检查点切取、进程迁移、作业调度及其它(资源管理、容错性、多用户特性等)。这几个方面既包括机群作业管理系统的重点,也包括难点。本文就当前它们的研究现状和解决方法进行了论述。

高岩[10]2005年在《银行数据交换平台中信息集成问题的研究与实现》文中研究指明本论文以银行业数据处理大集中的形式为背景,结合其对信息集成的要求,提出了在统一的基础业务平台之上进行银行应用信息集成的解决方案。即:通过在总行一级搭建数据交换软件平台,连接银行不同的业务系统,按照特定的业务逻辑完成交易转接功能。交换平台作为数据交换核心,将分布式的银行各种业务系统有机地连接成一个整体,实现丰富灵活的业务集成和信息集成。文章针对集成过程中最突出的叁个方面进行研究。为了支持相邻业务活动的应用系统间的互操作,实现业务功能的集成,分析了异构应用系统交互的两种模式。从交易的完整性、系统运行的稳定性、交互数据的一致性、中心控制带来的单点风险等角度比较了两种交互方式的响应能力和系统资源的锁定/释放速度,并从中甄选出了较好的交互方案。针对各业务的特点设计并实现了与之适应的逻辑单元分布方案,保障了功能集成后各自调用模式的一致性。对金融系统集成的设计开发有一定的借鉴意义。基于异构分布式系统的数据差异提供了一种分析转换的方法,该方法在元数据建模、数据映射等理论基础上,结合银行数据语法、语义的特性,对异构系统交互时产生的数据结构冲突和语义冲突进行识别,通过建立元数据转换知识库翻译交互的信息。同时对各异构系统的信息识别能力进行分析,制定了以VSAM文本文件存储和传输数据的方案。为了规避单点风险,保障互联体系的稳定运行,必须对体系的运行性能进行动态调控。在本文中基于结点处理能力、任务属性等因素,以负载均衡理论为基础,改良了一种进程调度算法。有效地均衡了各结点负载,提高了交易响应能力,降低了银行的运营风险。本文结合分布式交互、元数据建模、负载均衡等理论背景,对异构系统信息集成中功能集成、数据集成、负载均衡等重点问题提出了行之有效的分析解决方法。随着金融行业的业务集中、数据集中步伐的加快,本文所论述的方法对其系统集成、体系建设有一定的指导意义。同时,随着先进的集中化体系模型的演进,本文所做的分析研究为其大规模的应用进行了一项有意义的探索。

参考文献:

[1]. 分布式实时系统中动态负载共享算法的研究[D]. 刘军万. 中南大学. 2002

[2]. 分布式实时系统中动态负载共享新策略[J]. 刘军万, 谭骏珊, 吴敏, 曾广平. 计算机工程. 2003

[3]. 分布式系统中的负载平衡检测与优化策略研究[D]. 张先哲. 河南大学. 2009

[4]. 基于CPS的实时系统的面向方面的容错调度模型[D]. 符利华. 广东工业大学. 2011

[5]. 一种面向分布式虚拟环境的分层迭代负载平衡算法[J]. 王少峰, 周忠, 吴威. 软件学报. 2008

[6]. 基于动态自适应策略的多核调度算法研究[D]. 韩凤霞. 东北大学. 2012

[7]. 网络游戏引擎中负载均衡问题的研究[D]. 朱辉. 电子科技大学. 2007

[8]. 分布式流数据实时计算框架的研究和开发[D]. 顾伟. 浙江理工大学. 2012

[9]. 机群作业管理系统研究[D]. 雷州. 中国科学院研究生院(计算技术研究所). 1999

[10]. 银行数据交换平台中信息集成问题的研究与实现[D]. 高岩. 清华大学. 2005

标签:;  ;  ;  ;  ;  ;  ;  ;  ;  ;  ;  

分布式实时系统中动态负载共享算法的研究
下载Doc文档

猜你喜欢