分布式系统中负载平衡算法分析.doc
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《分布式系统中负载平衡算法分析.doc》由会员分享,可在线阅读,更多相关《分布式系统中负载平衡算法分析.doc(6页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、分布式系统中负载平衡算法分析摘要:该文简单描述了负载平衡算法提出的原因,负载平衡算法的分类以及动态平衡算法的需求。详细分析了动态负载平衡中的接受者驱动、发送者驱动和双向驱动算法以及双向驱动算法的改进算法,并对各算法的优缺点进行了分析。关键词:分布式系统 动态负载平衡1引言分布式系统是由多台分散的计算机连接而成的系统,其中各个资源单元(物理的或逻辑的)既互相协同又高度自治,能在全系统范围内实现资源管理,动态地进行任务分配或功能分配,并能并行地运行分布式程序。分布式系统具有良好的可用性、 可扩展性、 可靠性和健壮性,并为用户提供透明方便的用户界面.因此,近年来随着一些高速网络的兴起,分布式计算机系
2、统日益得以广泛的应用并受到人们的重视.经过研究发现,影响处理系统性能的因素包括处理机间的通信开销和分配的负载平衡等,但减少处理机的通信开销和均衡负载是相互冲突的两个因素,它们左右着任务分配策略。如负载均衡可以提高整个系统的吞吐量,因为它试图将模块尽可能均等地分配给处理机,但减少处理机的通信开销又迫使分配策略不得不尽可能地把较多的模块分配给尽可能少的处理机。由于一些并行任务之间的互相依赖关系和通讯量的大小很难在编译时就进行确定,所以人们更多地倾向于动态负载平衡的研究。随着研究的深入进行,人们注意到在一个由网络所连接起来的多个计算机系统环境中,在某一时刻,一些计算机系统的负载很重而另外一些计算机系
3、统的负载却很轻,影响了整个系统资源的利用率.由此,我们应该采用有效的负载平衡策略,即在减少处理机通信开销的基础上,提出行之有效的算法,提高整个系统资源的利用率.1。1 减少处理机通信开销系统管理站设计一个信息区,各模块每通信一次,节点累加器自动累加一次,最终将通信的模块信息和累加的次数一起存储到系统管理站的信息区.待系统下次运行时,系统管理站会根据信息区中以前模块信息通信的高低次数排序,按信息区的记录情况将通信频繁的模块安排到同一个节点,从而减少处理机的通信开销。1。2 负载平衡算法1。2.1概述负载平衡也称负载共享,是指对系统中的负载情况进行动态调整,以尽量消除或减少系统中各站点负载不均匀的
4、现象.因此,如何准确地评估各节点的工作负载能力并且分配新的请求任务到每个节点,成为分布式系统取得负载平衡的关键.1.2.2 负载平衡算法的需求(1)最小化客户请求的派发时间,使客户请求能够迅速地被派发给相应的服务副本,而不会因为低效的副本选择导致延迟。(2)最小化客户请求响应时间和最大化系统的吞吐量,使系统能够获得最高的性能和最大的资源利用率,最小化资源的空闲时间。(3)客户请求的响应时间具有可预期性.(4)保证副本间负载分配的平衡,从而降低发生过载的可能性,确保服务的可用性和系统的可靠性,同时能够在一定程度上抵御负载峰值的冲击。(5)具有好的可扩展性,不依赖于某种特定的资源或结构,也不对系统
5、中结点或副本的数目做出任何假设。(6)最小化系统的通信开销.1。2。3 负载平衡算法的分类负载平衡算法可分为动态算法和自适应算法两大类。动态算法是根据系统状态对可以接受任务的站点进行分析,可以将任务迁移到空闲站点,甚至可以将正在执行的任务迁移到其他空闲站点,但要注意的是,信息的收集、分析及作出决定要造成额外开销,不可小视。自适应算法是通过动态改变参数甚至策略来调整自身的行为,以适应正在改变的系统状态。如,某种负载平衡算法在A情况下的性能优于其他算法,而另一种算法在B情况下更优,自适应算法能够根据系统状态的变化选择合适的算法。在无法通过任务迁移提高系统性能的情况下,自适应算法是很好的选择。对按一
6、次局部负载平衡调度的启动者来说,又可分为接收者主动和发送者主动两种。其中,在发送者主动算法中,当一个站点超载时,它就尝试将任务发送给一个轻载站点,整个算法的思想是负载较重的节点试图甩掉超额的工作。接收者主动算法与发送者主动算法相反,当一个站点的任务队列长度小于阀值时,它就尝试从重载站点接收一个任务。综合以上算法,本文针对考虑节点工作负载能力、请求负载差异的和配置相对简单的因素,在减少处理机的通信开销基础上提出了双向主动均衡算法。2. 动态负载平衡算法2。1发送者主动算法发送者主动算法的思想是:当进程被创建时,它就运行在创建它的节点上,除非该节点过载了。过载节点的度量可能涉及太多的进程、过大的工
7、作集或者其他度量.如果过载了,该节点任意选择另一个节点并询问它的负载情况(使用同样的度量)。如果被探查的节点负载低于某些阀值,就将新的进程发送到该节点上。如果不是,则选择另一个机器探查.该策略需要交换处理器的负载信息,一个节点有多种方法 向邻接节点通知它的负载情况,如定期询问、每当任务数发生变化、接收到执行任务请求、响应请求或者当任务数超过一定阈值时.启动时,所有节点开始执行任务。在一段时间以后,节点开始检查自身是否是重载节点,如果是,它就试图在相关域中均匀的分布任务。具体来说,设该重载节点的负载为lp,相关域中有K个节点,其负载分别为l1,l2,lk,则平均负载Lavg为: Lavg=(1/
8、(K+1)(lp+l1+l2+lk)为达到任务的均匀分布,应求得重载节点传递给每个相关域中节点的负载量,因此引入权值hk以避免任务被迁移到负载更重的重载节点。如果Lavglk,则hk=Lavg-lk,否则hk=0。因此mk为:mk=(lpLavg)hk/(h1+h2+hk) 然后该节点就可以按照向各个相关节点发送任务。下图为发送者主动算法流程.图21 发送者主动算法(OL为任务队列长度,OLi为站点i的任务队列长度,T为阀值) 2。2接收者主动算法接收者主动算法与发送者主动算法相反,把所有节点按照阀值M划分为轻载节点和重载节点,所有当前负载tM的节点称为重载节点,tM的节点称为轻载节点。当一个
9、站点的任务队列长度小于阀值时,它就尝试从重载站点接收一个任务。在这个算法中,只要有一个进程结束,系统就检查是否有足够的工作可做。如果不是,它随机选择某台机器并要求它工作。如果该台机器没有可提供的工作,会接着询问第二台,然后第三台机器。如果在N次探查后,还没有找到工作,该节点暂时停止询问,去做任何已经安排的工作,而在下一个进程结束之后机器会再次进行询问。如果没有可做的工作,机器就开始空闲。在经过固定的时间间隔之后,它又开始探查。启动时,所有节点开始执行任务。在一段时间以后,节点开始检查自身是否是重轻载节点,如果是,它就试图在相关域中找到重载节点,并请求该节点上的任务。具体来说,设该轻载节点的负载
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 分布式 系统 负载 平衡 算法 分析
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内