略论一种基于负载均衡异构分布式系统的改进容错调度算法

1、略论一种基于负载平衡异构分布式系统的改进容错调度算法摘要:基于基/副版本技术提出了一种具有容错功能的静态进程调度算法。给出了一个新的设计模型,并在该模型上提出hdal算法。此前类似负载平衡容错调度算法都是通过排序来解决故障发生前后的负载平衡调度问题。该算法与以往算法不同之处就是在不依赖排序情况下,通过引进控制进程来解决负载平衡调度问题,并且该算法的负载平衡性在一定程度上具有了可控性。最后通过模拟实验得到以下有意义的结论:在业务繁忙的异构系统中,hdal算法比以往算法资源利用率高,负载平衡性更好,并且在调度速度上优势明显。关键词:异构分布式系统;hdal算法;负载平衡;容错;时间复杂度dengj

2、ian-b,zhangli-hen,fuli-hua(faultyfputer,guangdnguniversityftehnlgy,guangzhu510006,hina)abstrat:basednthebase/deputyversinfthetehnlgy,thispaperprpsedafault-tlerantshedulingalgrithfrastatipress.itputfrardanedesigndel,prpsedandanalyzedthehdal(hetergeneusdistributed-systeatuallad)algrith.earlierasiilarf

3、ault-tlerantshedulingalgrithfrlad-balaningtaddressthefailuretsrtthrughaftertheurreneflad-balaningshedulingprble.thealgrithdifferedfrthepreviusalgrithasntdependentsrtingasesthrughtheintrdutinfntrlfthepresstslvetheladbalaningshedulingprble,andthealgrithasladbalanedtaertainextent,ithantrllable.finallyt

4、hrughsiulatinexperients,thefllingsignifiantnlusins:busyinthebusinessfhetergeneussysteshdalalgrithresure-effiientthaninthepasthasbetterladbalaning,andshedulingspeedadvantagesarebvius.keyrds:hetergeneusdistributedsystes;hdalalgrith;ladbalaning;faulttlerane;tieplexity对系统软件容错研究中的备份技术2是一种常见的容错模型,许多文献中讨论过

5、容错模型技术3。对分布式系统中具有基/副版本的进程调度问题作了大量研究46。文献4提出了基于基/副版本技术和edf容错调度算法;文献5提出了在分布式实时系统中同时调度具有容错需求与无容错需求进程的混合调度算法;文献6讨论了异构分布式系统中基于负载平衡的容错调度算法,并给出hdalf和hdldf两种不同容错调度算法;文献7提出一种在同构环境中的两阶段算法,但上述算法在容错调度时都选择对待调度进程排序方法来解决调度负载平衡问题。本文主要是对异构分布式系统基于负载平衡的一种改进算法的讨论。建立了一种新的容错调度模型,在该模型根底上提出hdal算法,并与文献6中提出的hdldf算法作比较,结果说明该算

6、法在时间复杂度上优于hdldf算法。最后通过模拟实验证明hdal算法的负载平衡性占优,同时当进程到达一定数量时最少处理机需求略少于hdldf算法,这说明hdal算法资源利用率更高。最后还通过在不同异构环境下测试得出hdal算法适应不同的异构环境,而hdldf算法在节点性能差异较少的异构系统中,算法资源利用率明显不如hdal算法。但是本文所研究,还是在异构分布式系统中被动进程复制模型的静态容错调度算法,即进程分配的开始阶段一次性将所有进程全部分配完毕。1容错调度模型在异构分布式系统中假设有+n个进程运行在含有n个节点机的分布式系统中,且系统中的任何一个节点机失效可以被立即检测出。其中有个事务进程

7、、n个控制进程。由于笔者考虑的是静态调度算法,即所有进程的pu负载预先进程集合定义如下:由上面的定义可以看出,模型中引入了负载使用率和使用上限控制常量,同时还引入了控制进程来控制当前节点机,这种模型可以应用到更为广泛的动态容错调度算法中。为了使问题简化而不失一般性,设所有事务进程都具有互相独立性,且都只有一个副进程。算法有如下性质:性质1集合t中的进程在一个处理机失效时仍然可以继续运行,当且仅当该进程的基/副版本被调度到不同的处理机上6。该充要条件可以形式化描绘为性质2用户在使用分布式系统时设置了一个负载使用率上限值,即系统任何一次算法调度任何节点负载使用率不能大于,所以在调度前后,算法执行成

8、功的充分必要条件形式化描绘为性质3当一个节点机发生故障后,该节点上的基版本进程相应的副版本进程被激活,也就是说,在调度后其他节点上的负载都会产生一个增值,因此计算当前每个节点负载使用率时应把这个增值考虑进来(引用文献6的一些思想)。从式(5)可以看出满足式(5)就满足式(2)。因此性质2可以描绘成任何节点失效后一次进程调度成功的充要条件是:任意节点在调度后的负载使用率始终不大于。下面将提出一种基于上面模型的调度算法,并在判断一次进程调度是否成功时用到了该性质并与文献6的hdldf算法作比较。2启发式调度算法2.1hdldf算法6hdldf算法称为负载增值优先考虑算法。分配副版本进程时优先考虑的

9、是副版本进程的负载增值,而不是根据其实际负载值分配。这样保证了在发生故障后在异构系统中有较好的负载平衡性。为了描绘hdldf算法,先引入两个定义:a)处理机性能参数。详细算法过程请参考文献6,限于篇幅,本文不再给出。2.2hdal算法选择任务调度处理、满足上述条件时应尽量选择负载小的处理进展调度。假设不满足就分配pi+1,即选择负载次优的处理机直到k=n。当k=n时说明待分配进程没有适宜的处理机进程分配,那么算法1hdal算法输入:进程集合,处理机个数n及的值输出:result,节点机集合ta)初始化并更新控制进程计算节点上的基版本进程的ai,即式(3)及更新控制进程argai;if(i=n)

10、and(进程没有被调度成功)returnfailed;elsej+;/*下一个基版本进程*/if(i=n)and(进程没有被调度成功)returnfailed;elsej+;/*下一个副版本进程*/更新n个节点机的控制进程参数所需时间为nlg。调度进程计算进程负载变化所需时间及分配基版本进程所需时间是2(n-1)lg。整个hdal算法时间复杂度为(nlg)。从时间复杂度来看,hdal优于hdldf算法。3性能分析(7)根据上面计算方法知,的值越大说明负载平衡性越差,反之亦然。3.1节点间负载平衡性分析3.2算法最小节点需求分析算法2fnp算法输出:k,节点机集合a)ler=1;hight=+n

11、;/*hdldf算法中n=0*/b)k=(ler+hight)/2;if(k=ler)thenk=k+1;exit;图2说明进程个数增加所需最小节点机个数增加。因为调度的进程数越多,就需要更多节点机,以保证每一节点的负载不超过其所能承受的负载上限。同时还可以看出两种算法在进程数到达一定数量时,hdal算法所需最小节点机个数略小于hdldf算法。这是因为当进程数增加时hdal算法的控制进程所占的负载比重变小,而hdal算法平衡性优于hdldf算法,并且进程数越大这种优势越明显。但是进程数量较少时hdldf算法所需最小节点占优,因为一样的业务量情况下,hdal算法需要额外的控制进程即需要额外负载。

12、这就说明在任务繁忙的系统中应该选择hdal算法,而在业务相对轻松的系统中选择hdldf算法。模拟实验3是为了说明不同范围处理机承受的最大负载与最小处理机需求个数的关系,处理机最大承受负载是反映异构分布式系统中处理机性能差异的标准参数。的值变化区间越大,说明系统中处理机之间性能的差异越大。本文分别取在(30,150)(50,120)(90,90)三个区间上的变化,调用hdal算法及在(90,90)调用hdal算法得到图3。从图3可以看出,在取不同区域调用hdal算法最小处理机需求根本没有变化,这说明该算法负载平衡性对异构系统性能差异依赖少。主要是因为hdal算法调度进程通过控制进程来选择调度处理

13、机,而文献6的hdldf算法在同构环境中退化为二阶段算法6,这也就说明hdldf算法只适宜于性能差异较大的系统,所以在业务繁忙的系统应选择hdal算法。4完毕语本文首先提出一种新的基于基/副版本进程的模型。在模型中引进了控制进程,并可以控制异构分布式容错系统中节点性能最大使用率。并提出了hdal算法,计算出算法时间复杂度,通过模拟实验对算法的负载平衡稳定作了分析,结果显示故障发生前后算法的负载平衡性稳定。其次,通过利用(fnp)算法计算出hdal算法在不同的异构环境所需最小节点机个数,结果说明算法的最小节点机需求与异构系统性能差异无关,说明在越庞大、任务繁忙的异构分布式容错系统中采用hdal算

14、法更为合理,反之亦然。在本文中待研究的问题:a)该容错任务调度算法的前提假设还是在异构分布式系统中被动进程复制模型的静态容错调度算法,即进程分配的开始阶段一次性将所有进程全部分配完毕;b)进程粒度与异构分布系统性能及整个系统进程数量互相关系还有待进一步分析,因此本文给出的结果只是当前模拟实验环境下得出的。参考文献:2sieirekdp,sartzrs.reliablesystedesign:thetheryandpratie.neyrk:digitalpress,1992.3linteinh,shinkg.daageassessentfrptialrllbakreveryj.ieeetransnputers,1998,47(57):603-613.4liuhuai,feishu-in.afault-tlerantshedulingalgrithbasednedffrdistributedntrlsystesj.jurnalfsftare,2022,14(8):1371-1378.6guhui,angzhi-guang,zhujing-li.ladbalaningbasedpres