摘 要:基于基/副版本技术提出了一种具有容错功能的静态进程调度算法。给出了一个新的设计模型,并在该模型上提出hdal算法。此前类似负载均衡容错调度算法都是通过排序来解决故障发生前后的负载均衡调度问题。该算法与以往算法不同之处就是在不依赖排序情况下,通过引进控制进程来解决负载均衡调度问题,并且该算法的负载均衡性在一定程度上具有了可控性。最后通过模拟实验得到以下有意义的结论:在业务繁忙的异构系统中,hdal算法比以往算法资源利用率高,负载均衡性更好,并且在调度速度上优势明显。
关键词:异构分布式系统;hdal算法;负载均衡;容错;时间复杂度
load balancing based process scheduling with fault-tolerant improved algorithm in heterogeneous distributed systems
deng jian-bo,zhang li-chen,fu li-hua
(faculty of computer, guangdong university of technology, guangzhou 510006, china)
abstract:based on the base/deputy version of the technology,this paper proposed a fault-tolerant scheduling algorithm for a static process.it put forwarda new design model, proposed and analyzed the hdal (heterogeneous distributed-system actual load) algorithm.earlier a similar fault-tolerant scheduling algorithm for load-balancing to address the failure to sort through after the occurrence of load-balancing scheduling problem.the algorithm differed from the previous algorithm was not dependent sorting cases through the introduction of control of the process to solve the load balancing scheduling problem, and the algorithm was load balanced to a certain extent, with a controllable. finally through simulation experiments,the following significant conclusions: busy in the business of heterogeneous systems hdal algorithm resource-efficient than in the past has better load balancing, and scheduling speed advantages are obvious.
key words:heterogeneous distributed systems; hdal algorithm; load balancing; fault tolerance; time complexity
随着各种控制系统复杂性的提高,分布式控制系统已越来越多地应用于各种控制领域,系统控制器出现故障的可能性也相应增加。wWw.133229.cOM为了避免这种故障的发生具有容错能力变得尤为重要。在分布式容错系统中硬件冗余是一种解决问题的常见方法[1],然而硬件冗余方法需要更高的代价,但某些领域如航天对系统本身的质量有严格限制,因此软件容错技术得到发展。
对系统软件容错研究中的备份技术[2]是一种常见的容错模型,许多文献中讨论过容错模型技术[3]。对分布式系统中具有基/副版本的进程调度问题作了大量研究[4~6]。文献[4]提出了基于基/副版本技术和edf容错调度算法;文献[5]提出了在分布式实时系统中同时调度具有容错需求与无容错需求进程的混合调度算法;文献[6]讨论了异构分布式系统中基于负载均衡的容错调度算法,并给出hdalf和 hdldf两种不同容错调度算法;文献[7]提出一种在同构环境中的两阶段算法,但上述算法在容错调度时都选择对待调度进程排序方法来解决调度负载均衡问题。
本文主要是对异构分布式系统基于负载均衡的一种改进算法的讨论。建立了一种新的容错调度模型,在该模型基础上提出hdal算法,并与文献[6]中提出的hdldf算法作比较,结果表明该算法在时间复杂度上优于hdldf算法。最后通过模拟实验证明hdal算法的负载均衡性占优,同时当进程达到一定数量时最少处理机需求略少于hdldf算法,这说明hdal算法资源利用率更高。最后还通过在不同异构环境下测试得出hdal算法适应不同的异构环境,而hdldf算法在节点性能差异较少的异构系统中,算法资源利用率明显不如hdal算法。但是本文所研究,还是在异构分布式系统中被动进程复制模型的静态容错调度算法,即进程分配的开始阶段一次性将所有进程全部分配完毕。
1 容错调度模型
定义1 设分布式系统中处理机节点个数为n,该系统中处理机的集合定义为t={n1,n2,…,nn}。其中ni表示第i个处理机节点。每个处理机节点可以由一个四元组(μ,ωa,ωb,β)组成。其中:μ为该处理机能承受的最大负载;ωa表示调度到该处理机上的基版本进程集合,即ωa={p1•pa1, p2•pa2 ,…,pm•pam,};ωb表示调度到该处理机上的副版本进程集合,即ωb={p1•pb1, p2•pb2,…, pm•pbm,};β为一组节点标号的集合{β 1,β2,…,βi},βi∈β表示含有分配该处理机上的副版本进程,其对应的基版本进程被调度在节点nβ上。
在异构分布式系统中假设有m+n个进程运行在含有n个节点机的分布式系统中,且系统中的任何一个节点机失效可以被立即检测出。其中有m个事务进程、n个控制进程。由于笔者考虑的是静态调度算法,即所有进程的cpu负载预先已知进程集合定义如下:
定义2 异构且具有容错功能的一组进程集合定义为φ={φp,φh}。其中φp表示事务进程集合,φh表示控制进程集合。φp={p1,p2,…,pi,…,pm},其中p是由一个二元组{pa ,pb}构成,即pi={pai,pbi},p∈φp。pa表示基版本进程集合,pb表示副版本进程集合,pa和pb也是由二元组{ntk,fd}来描述。ntk表示该版本的进程调度到的节点机,fd表示该版本的进程负载。φh表示控制进程集合,φh={phi}。其中i∈(1,n),phi∈φh可以描述为一个五元组phi={ρargai,ρargbi,ρai,ρbi,ρ}。其中:ρargai表示整个分布式系统所有基版本进程负载在当前整个系统负载中的平均使用率;ρargbi表示整个分布式系统所有副版本进程负载在当前整个系统负载中的平均使用率;ρargai与ρargbi是一种理想绝对均衡值;ρai表示当前节点基版本进程负载占用率;ρbi表示当前节点副版本进程负载使用率;ρ表示设定负载使用率的上限值且ρ∈(0,1)。
由上面的定义可以看出,模型中引入了负载使用率和使用上限控制常量,同时还引入了控制进程来控制当前节点机,这种模型可以应用到更为广泛的动态容错调度算法中。为了使问题简化而不失一般性,设所有事务进程都具有相互独立性,且都只有一个副进程。算法有如下性质:
性质1 集合t中的进程在一个处理机失效时仍然可以继续运行,当且仅当该进程的基/副版本被调度到不同的处理机上[6]。该充要条件可以形式化描述为
{pi∈φp,i∈(1,m)→pi•pa•ntk≠pi•pb•ntk}(1)
性质2 用户在使用分布式系统时设置了一个负载使用率上限值ρ,即系统任何一次算法调度任何节点负载使用率不能大于ρ,所以在调度前后,算法执行成功的充分必要条件形式化描述为
{ni∈t,i∈(1,n)→ρai+ρbi≤ρ}(2)
性质3 当一个节点机发生故障后,该节点上的基版本进程相应的副版本进程被激活,也就是说,在调度后其他节点上的负载都会产生一个增值,因此计算当前每个节点负载使用率时应把这个增值考虑进来(引用文献[6]的一些思想)。
基版本进程分配到节点机ni上且副版本进程被分配到nj上的进程集合定义为φpij={p∈φp|p•pa•ntk=j∩i≠j}(i,j∈[1,n]),则当节点ni失效时nj节点上的负载增值为p∈φpij(p•pa•fd-p•pb•fd),
节点nj负载使用率ρaj=(p∈φpij(p•pa•fd)+μ×ρaj)/μ,ρbj=(μ×ρbj-
p∈φpij(p•pa•fd))/μ。若考虑ni∈ф失效时,此时节点nj上的负载变化最大值为max{p∈φpij(p•pa•fd-p•pb•fd)},那么此时节点基/副版本进程实际负载使用率形式化描述为
ρai=(max[p∈φpij(p•pa•fd)]+μ×ρai)/μ(3)
ρbi=(μ×ρbi-max[p∈φpij
(p•pb•fd)])/μ(4)
由此得出任意节点失效都能够保证系统正常运行充要条件可形式描述为nj∈t,nj正常运行充要条件是
{max[p∈φpij(p•pa•fd-p•pb•fd)]+nj•μ×(ρaj+ρbj)}/nj•μ≤ρ(5)
从式(5)可以看出满足式(5)就满足式(2)。因此性质2可以描述成任何节点失效后一次进程调度成功的充要条件是:任意节点在调度后的负载使用率始终不大于ρ。下面将提出一种基于上面模型的调度算法,并在判断一次进程调度是否成功时用到了该性质并与文献[6]的hdldf算法作比较。
2 启发式调度算法
2.1 hdldf算法[6]
hdldf算法称为负载增值优先考虑算法。分配副版本进程时优先考虑的是副版本进程的负载增值,而不是根据其实际负载值分配。这样保证了在发生故障后在异构系统中有较好的负载均衡性。为了描述hdldf算法,先引入两个定义:
a)处理机性能参数λ。
b)调度到节点机上进程实际负载总和η,即hdldf算法模型下面的节点机形式化描述为一个五元组(λ,η,ωa,ωb,β)。
该算法描述如下:首先将集合ψp中的进程按其基版本负载非增排序,然后采用启发式贪婪算法对这些进程的基版本进行调度。根据分配在每一节点上的基版本进程,将该节点上的基版本进程对应的副版本进程分配成(n-1) 组,且这(n-1)组副版本进程在该节点失效时有近似相等的负载增值。n个节点总共有n×(n-1)组备份进程。同样依据贪婪算法,根据每组进程的实际负载增值进行调度,将实际负载值较大组分配到负载相对较小的处理机上。由于没有按照副版本进程的实际负载分配到各节点,在故障发生前节点的负载均衡性不如按照副版本进程的实际负载分配的算法,然而在故障发生后,这种优先考虑了副版本进程实际负载增值的分配方案,确保在发生单点故障时节点有最优的负载均衡性。下面给出备份进程组的定义。
定义3 设分布式系统中节点个数为n,则(n-1) 组副版本进程定义为集合δ={g1,g2,…,gn-1}。δ中的元素g∈δ表示为一个二元组,即g=(ξ,ε)。其中:ξ为调度到该组的副版本进程的负载增值总和,ε为该组中副版本进程的集合。定义为ε={p1•pb,p2•pb,…,pj•pb ,}在调度副版本进程组时同样依据贪婪算法,将总计为n×(n-1)组副版本进程根据其实际负载值依次将负载最大的备份进程组分配到负载最小的节点机上,同时应满足以下两个条件:
a)基版本进程分配在某一节点上,其副版本进程组不能又调度到该节点上,即p∈ψp,满足:p•pa•ntk≠p•pb•ntk。
b)同一节点上不能有两个来自相同节点的副版本进程组,即(pi•pb∈gm•ε)∩(pj•pb∈gm•ε)∩(pi•pa•ntk=pj•pa•ntk)∩(gm≠gn)→(pi•p a•ntk≠pj•pb•ntk)∩(pi•pb•ntk≠pj•pa•ntk)。
具体算法过程请参考文献[6],限于篇幅,本文不再给出。
2.2 hdal算法
hdal与hdldf算法不同的是,hdal算法首先在新的设计模型下无须对基/副版本进程进行排序。首先该算法在故障发生后会通过控制进程计算出故障发生后异构分布系统基/副版本进程负载平均使用率,并更新所有节点的控制进程参数。某节点失效对于整个系统而言实际负载总量并没有变化,因为失效节点的进程按一定的规则分配到其他节点上,但是系统能承受的最大负载总量变小。其次分配基/副版本进程时可以随机取出待调度的基/副版本进程,只要满足性质1、2和3,即当某一进程pi分配到节点机nk,进程pi的基/副版本进程不能同时在nk上,且如果是pai(基版本进程i)分配到节点nk上,那么节点nk上的基版本进程负载使用率不大于平均负载使用率值,形式化描述为ρai≤ρargai;如果是pbi(副版本进程) 即满足ρbi≤ρargbi,且为了减少系统总的负载,在
选择任务调度处理、满足上述条件时应尽量选择负载小的处理进行调度。
如果不满足就分配pi+1,即选择负载次优的处理机直到k=n。当k=n时说明待分配进程没有合适的处理机进程分配,那么
返回调度失败。如果分配完所有进程则调度成功。因为故障发生时重新更新ρargai与ρargbi的值,能很好地控制负载均衡问题。
算法1 hdal算法
输入:进程集合φ,处理机个数n及ρ的值
输出:result,节点机集合t
a)初始化并更新控制进程
b)for(j=1 to m)and (pi∈pa)and(没有调度)do/*调度基版本进程*/
计算节点上的基版本进程的ρai,即式(3)及更新控制进程ρargai;
for i=1 to n{选择节点nj且满足(nj∈t, nj•ρai≤nj•ρargai)∩nj.ρai+ nj.ρbi≤ρ∩pi.pa.fd=min{pj.pa.fd,j∈[1,n]} ; if(满足){pi.pai.ntk=j,nj.ωa= nj.ωa+{pai} nj.ρai= nj.ρai+(pi.pai.fd /nj.μ) }; else{选择次优节点机};}
if(i=n)and(进程没有被调度成功)return failed;else j++;/*下一个基版本进程*/
c)for(j=1 to m) and(pi∈pb)and (没有调度) /*调度副版本进程*/
计算节点 nj上基版本进程与其对应的副版本进程负载变化,即式(4)更新控制进程ρargbi;
for i=1 to n {选择节点nj且满足(nj∈t (nj•ρbj ≤nj•ρargbj) ∩(nj•ρaj+ nj•ρbj≤ρ)∩ pi•pb•fd=min{pj•pb•fd,j∈[1,n]};
if(满足){nj•ρbj=ρbj+(p•paj.fd-p•pbj•fd)/nj•μ;nj.ωb=nj.ωb+{pbj}}; else{i++};}
if(i=n)and(进程没有被调度成功) return failed;else j++;/*下一个副版本进程*/
d)if(ni•ωb≠ ∪ni.ωa≠) then result = false,exit;else break;
hdal算法首先分配基版本进程,从待调度基版本进程中取一个进程分配到节点机nj上,同时保证节点nj的负载低于平均负载且进程调度到该处理机上负载相对较小,如果满足条件则更新nj节点相关信息。调度副版本进程时同理。时间复杂度分析如下:
更新n个节点机的控制进程参数所需时间为n log m。
调度进程计算进程负载变化所需时间及分配基版本进程所需时间是2(n-1) m log m。整个hdal算法时间复杂度为o(nm log m)。从时间复杂度来看,hdal优于hdldf算法。
3 性能分析
本章对hdal算法通过模拟实验进行负载均衡性分析,同时还应用文献[5]中计算最小节点需求算法(find minimal number of processors,fmnp)计算出hdal算法与hdldf算法最小节点需求并进行比较得出相关结论。使用1.6 ghz coretm2 duo cpu,内存2 gb的pc机进行模拟实验,程序语言使用java,编译工具使用eclipse 3.5。本文应用平均方差来衡量异构分布式系统中的负载均衡性。形式化描述为
δρ(ni)=︱(ni•μ-nj=1(nj•μ)/n)/nj=1(nj•μ)/n︱(6)
由于在异构系统中节点机的性能不同,本文引入一个节点在系统中的权值ξ。其中ξi表示节点ni在整个异构系统所占的重要程度。为了使问题简单而不失一般性,本文把ξi表示为当前节点机承载的最大负载与整个异构系统中承载的最大负载的比值,即ξi=ni•μ/nj=1nj•μ,{i, j∈[1,n]},那么可知ni=1(ξi)=1且0<ξi<1。由上面表达式可知一次模拟实验中负载均衡性为
δρ=ni=1(δρ(ni)×ξi)
(7)
依据上面计算方法知,δρ的值越大表明负载均衡性越差,反之亦然。
3.1 节点间负载均衡性分析
仿真模拟实验1:令基版本进程的负载等概率分布在1～9;副版本的进程负载以等概率分布在其基版本负载的5%～10%;处理机最大能承受负载μ在30～150变化,即性能最高的节点机是性能最差节点机处理能力的5倍。在实验中先随机生成基/副版本进程集合和节点机集合,并为每个节点注上控制进程,其负载大小设为5。然后调用hdal与hdldf算法输出节点机集合ф,并通过式(7)计算δρ值,重复100次,并求δρ平均值,得到图1。图1是在保证算法都能正确调度完所有进程情况下得到的故障发生前后负载均衡图。图中显示在节点为25个、ρ值为1,进程数在100～600时,故障发生前与发生后负载均衡的调度情况。从图1可以看出,故障发生前后hdal算法的负载均衡性基本没有变化,而hdldf算法在故障发生后节点的负载均衡性有所下降,虽然随着进程数量的增加负载均衡性有所上升,但是hdal算法负载均衡性优于hdldf。这说明了hdal算法在故障发生前后负载均衡性稳定,主要原因是无论故障发生前后hdal算法都通过更新控制进程来控制各节点负载使用率。
3.2 算法最小节点需求分析
hdal和 hdldf算法都是启发式的异构分布式模型下基于负载均衡的容错调度算法。两种算法都是输入带有基/副版本的进程集合φp和处理机个数n,因此在系统发生故障前后负载均衡的重要性相同的情况下,可以通过对最小节点需求比较来对算法作出选择。本文参考了文献[5]提出的求解最小处理机个数的(fmnp)算法,通过模拟实验比较得出两种算法利用率。fmnp算法描述如下:
算法2 fmnp算法
输入:进程集合{ψp,ψh},type及ρ=1 /*hdldf算法只使用{ψp}*/
输出:k,节点机集合ф
a)lower=1;hight=m+n;/*hdldf算法中n=0*/
b)k=(lower+hight)/2;
if(k=lower)then k=k+1;exit;
c)if(type=hdal) then hdal(ψp,ψh,δa,ρ,k;result,ф);
模拟实验2与1类似,先随机产生进程集合{φp ,φh},调用fmnp算法,输出算法所需最小处理机个数k。重复实验50次,求得k的平均值,得到图2。
图2说明进程个数增加所需最小节点机个数增加。因为调度的进程数越多,就需要更多节点机,以保证每一节点的负载不超过其所能承受的负载上限。同时还可以看出两种算法在进程数达到一定数量时,hdal算法所需最小节点机个数略小于hdldf算法。这是因为当进程数增加时hdal算法的控制进程所占的负载比重变小,而hdal算法均衡性优于hdldf算法,并且进程数越大这种优势越明显。但是进程数量较少时hdldf算法所需最小节点占优,因为相同的业务量情况下,hdal算法需要额外的控制进程即需要额外负载。这就说明在任务繁忙的系统中应该选择hdal算法,而在业务相对轻松的系统中选择hdldf算法。
模拟实验3是为了说明不同范围处理机承受的最大负载μ与最小处理机需求个数的关系,处理机最大承受负载μ是反映异构分布式系统中处理机性能差异的标准参数。μ的值变化区间越大,说明系统中处理机之间性能的差异越大。本文分别取μ在 (30,150)(50,120)(90,90) 三个区间上的变化,调用hdal算法
及μ在(90,90)调用hdal算法得到图3。从图3可以看出,
在μ取不同区域调用hdal算法最小处理机需求基本没有变化,这说明该算法负载均衡性对异构系统性能差异依赖少。主要是因为hdal算法调度进程通过控制进程来选择调度处理机,而文献[6]的 hdldf算法在同构环境中退化为二阶段算法[6],这也就说明hdldf算法只适合于性能差异较大的系统,所以在业务繁忙的系统应选择hdal算法。
4 结束语
本文首先提出一种新的基于基/副版本进程的模型。在模型中引进了控制进程,并可以控制异构分布式容错系统中节点性能最大使用率。并提出了hdal算法,计算出算法时间复杂度,通过模拟实验对算法的负载均衡稳定作了分析,结果显示故障发生前后算法的负载均衡性稳定。其次,通过利用(fmnp)算法计算出hdal算法在不同的异构环境所需最小节点机个数,结果表明算法的最小节点机需求与异构系统性能差异无关,说明在越庞大、任务繁忙的异构分布式容错系统中采用hdal算法更为合理,反之亦然。
在本文中待研究的问题:a)该容错任务调度算法的前提假设还是在异构分布式系统中被动进程复制模型的静态容错调度算法,即进程分配的开始阶段一次性将所有进程全部分配完毕;b)进程粒度与异构分布系统性能及整个系统进程数量相互关系还有待进一步分析,因此本文给出的结果只是当前模拟实验环境下得出的。
参考文献:
[1]kopetz h,grnsteidl g.ttp:a protocol for fault-tolerant real-time systems[j].ieee computer,1994,27(1):14 -23.
[2]siewiorek d p,swartz r s.reliable system design:the theory and practice[m].new york:digital press,1992.
[3]lintein h,shin k g.damage assessment for optimal rollback recovery[j].ieee trans on computers,1998,47(57):603-613.
[4]liu huai,fei shu-min.a fault-tolerant scheduling algorithm based on edf for distributed control systems[j].journal ofsoftware,2003,14(8):1371-1378.
[5]qin xiao,pang li-ping,han zong-fen.algorithms of fault- tolerant scheduling in distributed real-time systems[j].journal of compu-ters,2000,23(107):1056-1063.
[6]guo hui,wang zhi-guang,zhou jing-li.load balancing based process scheduling with fault-tolerant in heterogeneous distributed system[j].chinese journal of computers,2005,28(11):1807-1816.
[7]kim j,lee h,lee s.process allocation for load distribution in fault-tolerant multi-computers[c]//proc of the 25th international symposium on fault-tolerant computing.1995:124-129.
[8]bertossi a a,mancini l v,rossini f.fault-tolerant rate-mo-notonic first-fit in hard real-time scheduling systems[j].ieee trans on para newland distributed systems,1999,10(9):934-945.
