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

略论一种基于负载平衡异构分布式系统的改良容错调度算法
　　摘要:基于基/副版本技术提出了一种具有容错功能的静态进程调度算法。给出了一个新的设计模型,并在该模型上提出hdal算法。此前类似负载平衡容错调度算法都是通过排序来解决故障发生前后的性,设所有事务进程都具有互相独立性,且都只有一个副进程。算法有如下性质:
　　性质1集合t中的进程在一个处理机失效时仍然可以继续运行,当且仅当该进程的基/副版本被调度到不同的处理机上[6]。该充要条件可以形式化描绘为
　　性质2用户在使用分布式系统时设置了一个负载使用率上限值ρ,即系统任何一次算法调度任何节点负载使用率不能大于ρ,所以在调度前后,算法执行成功的充分必要条件形式化描绘为
　　性质3当一个节点机发生故障后,该节点上的基版本进程相应的副版本进程被激活,也就是说,在调度后其他节点上的负载都会产生一个增值,因此计算当前每个节点负载使用率时应把这个增值考虑进来(引用文献[6]的一些思想)。
　　从式(5)可以看出满足式(5)就满足式(2)。因此性质2可以描绘成任何节点失效后一次进程调度成功的充要条件是:任意节点在调度后的负载使用率始终不大于ρ。下面将提出一种基于上面模型的调度算法,并在判断一次进程调度是否成功时用到了该性质并与文献[6]的hdldf算法作比拟。
　　2启发式调度算法
　　[6]
　　hdldf算法称为负载增值优先考虑算法。分配副版本进程时优先考虑的是副版本进程的负载增值,而不是根据其实际负载值分配。这样保证了在发生故障后在异构系统中有较好的负载平衡性。为了描绘hdldf算法,先引入两个定义:
　　a)处理机性能参数λ。
　　详细算法过程请参考文献[6],限于篇幅,本文不再给出。
　　
　　选择任务调度处理、满足上述条件时应尽量选择负载小的处理进展调度。
　　假如不满足就分配pi+1,即选择负载次优的处理机直到k=n。当k=n时说明待分配进程没有适宜的处理机进程分配,那么
　　算法1hdal算法
　　输入:进程集合φ,处理机个数n及ρ的值
　　输出:result,节点机集合t
　　a)初始化并更新控制进程
　　计算节点上的基版本进程的ρai,即式(3)及更新控制进程ρargai;
　　if(i=n)and(进程没有被调度成功)returnfailed;elsej++;/*下一个基版本进程*/
　　if(i=n)and(进程没有被调度成功)returnfailed;elsej++;/*下一个副版本进程*/
　　更新n个节点机的控制进程参数所需时间为nlg。
　　调度进程计算进程负载变化所需时间及分配基版本进程所需时间是2(n-1)lg。整个hdal算法时间复杂度为(nlg)。从时间复杂度来看,hdal优于hdldf算法。
　　3性能分析
　　(7)
　　根据上面计算方法知,δρ的值越大说明负载平衡性越差,反之亦然。
　　
　　
　　算法2fnp算法
　　输出:k,节点机集合ф
　　a)ler=1;hight=+n;/*hdldf