资源描述:
《略论一种基于负载均衡异构分布式系统的改进容错调度算法的论文》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、略论一种基于负载均衡异构分布式系统的改进容错调度算法的论文 摘要:基于基/副版本技术提出了一种具有容错功能的静态进程调度算法。给出了一个新的设计模型,并在该模型上提出hdal算法。此前类似负载均衡容错调度算法都是通过排序来解决故障发生前后的负载均衡调度问题。该算法与以往算法不同之处就是在不依赖排序情况下,通过引进控制进程来解决负载均衡调度问题,并且该算法的负载均衡性在一定程度上具有了可控性。最后通过模拟实验得到以下有意义的结论:在业务繁忙的异构系统中,hdal算法比以往算法资源利用率高,负载均衡性更好,并且在调度速度上优势明显。 关键词:异构分布式系统;
2、hdal算法;负载均衡;容错;时间复杂度 loadbalancingbasedprocessschedulingprovedalgorithminheterogeneousdistributedsystems dengjian-bo,zhangli-chen,fuli-hua (facultyofputer,guangdonguniversityoftechnology,guangzhou510006,china) abstract:basedonthebase/deputyversionofthetechnology,thispaperp
3、roposedafault-tolerantschedulingalgorithmforastaticprocess.itputforodel,proposedandanalyzedthehdal(heterogeneousdistributed-systemactualload)algorithm.earlierasimilarfault-tolerantschedulingalgorithmforload-balancingtoaddressthefailuretosortthroughaftertheoccurrenceofload-balancin
4、gschedulingproblem.thealgorithmdifferedfromthepreviousalgorithm,andthealgorithmulationexperiments,thefolloshdalalgorithmresource-efficientthaninthepasthasbetterloadbalancing,andschedulingspeedadvantagesareobvious. keys;hdalalgorithm;loadbalancing;faulttolerance;timeplexity 随着各种控
5、制系统复杂性的提高,分布式控制系统已越来越多地应用于各种控制领域,系统控制器出现故障的可能性也相应增加。.为了避免这种故障的发生具有容错能力变得尤为重要。在分布式容错系统中硬件冗余是一种解决问题的常见方法[1],然而硬件冗余方法需要更高的代价,但某些领域如航天对系统本身的质量有严格限制,因此软件容错技术得到发展。 对系统软件容错研究中的备份技术[2]是一种常见的容错模型,许多文献中讨论过容错模型技术[3]。对分布式系统中具有基/副版本的进程调度问题作了大量研究[4~6]。文献[4]提出了基于基/副版本技术和edf容错调度算法;文献[5]提出了在分布式实
6、时系统中同时调度具有容错需求与无容错需求进程的混合调度算法;文献[6]讨论了异构分布式系统中基于负载均衡的容错调度算法,并给出hdalf和hdldf两种不同容错调度算法;文献[7]提出一种在同构环境中的两阶段算法,但上述算法在容错调度时都选择对待调度进程排序方法来解决调度负载均衡问题。 本文主要是对异构分布式系统基于负载均衡的一种改进算法的讨论。建立了一种新的容错调度模型,在该模型基础上提出hdal算法,并与文献[6]中提出的hdldf算法作比较,结果表明该算法在时间复杂度上优于hdldf算法。最后通过模拟实验证明hdal算法的负载均衡性占优,同时当进程
7、达到一定数量时最少处理机需求略少于hdldf算法,这说明hdal算法资源利用率更高。最后还通过在不同异构环境下测试得出hdal算法适应不同的异构环境,而hdldf算法在节点性能差异较少的异构系统中,算法资源利用率明显不如hdal算法。但是本文所研究,还是在异构分布式系统中被动进程复制模型的静态容错调度算法,即进程分配的开始阶段一次性将所有进程全部分配完毕。 1容错调度模型 定义1设分布式系统中处理机节点个数为n,该系统中处理机的集合定义为t={n1,n2,…,nn}。其中ni表示第i个处理机节点。每个处理机节点可以由一个四元组(μ,ωa,
8、ωb,β)组成。其中:μ为该处理机能承受的最大负载;ωa表示调