摘 要:基于基/副版本技术提出了一种具有容错功能的静态进程调度算法。给出了一个新的设计模型,并在该模型上提出hdal算法。此前类似负载均衡容错调度算法都是通过排序来解决故障发生前后的负载均衡调度问题。该算法与以往算法不同之处就是在不依赖排序情况下,通过引进控制进程来解决负载均衡调度问题,并且该算法的负载均衡性在一定程度上具有了可控性。最后通过模拟实验得到以下有意义的结论:在业务繁忙的异构系统中,hdal算法比以往算法资源利用率高,负载均衡性更好,并且在调度速度上优势明显。
关键词:异构分布式系统;hdal算法;负载均衡;容错;时间复杂度
lad balaning based press sheduling ith fault-tlerant iprved algrith in hetergeneus distributed systes
deng jian-b,zhang li-hen,fu li-hua
(faulty f puter, guangdng university f tehnlgy, guangzhu 510006, hina)
abstrat:based n the base/deputy versin f the tehnlgy,this paper prpsed a fault-tlerant sheduling algrith fr a stati press.it put frarda ne design del, prpsed and analyzed the hdal (hetergeneus distributed-syste atual lad) algrith.earlier a siilar fault-tlerant sheduling algrith fr lad-balaning t address the failure t srt thrugh after the urrene f lad-balaning sheduling prble.the algrith differed fr the previus algrith as nt dependent srting ases thrugh the intrdutin f ntrl f the press t slve the lad balaning sheduling prble, and the algrith as lad balaned t a ertain extent, ith a ntrllable. finally thrugh siulatin experients,the flling signifiant nlusins: busy in the business f hetergeneus systes hdal algrith resure-effiient than in the past has better lad balaning, and sheduling speed advantages are bvius.
key rds:hetergeneus distributed systes; hdal algrith; lad balaning; fault tlerane; tie plexity
随着各种控制系统复杂性的提高,分布式控制系统已越来越多地应用于各种控制领域,系统控制器出现故障的可能性也相应增加。为了避免这种故障的发生具有容错能力变得尤为重要。在分布式容错系统中硬件冗余是一种解决问题的常见方法[1],然而硬件冗余方法需要更高的代价,但某些领域如航天对系统本身的质量有严格限制,因此软件容错技术得到发展。
对系统软件容错研究中的备份技术[2]是一种常见的容错模型,许多文献中讨论过容错模型技术[3]。对分布式系统中具有基/副版本的进程调度问题作了大量研究[4~6]。文献[4]提出了基于基/副版本技术和edf容错调度算法;文献[5]提出了在分布式实时系统中同时调度具有容错需求与无容错需求进程的混合调度算法;文献[6]讨论了异构分布式系统中基于负载均衡的容错调度算法,并给出hdalf和 hdldf两种不同容错调度算法;文献[7]提出一种在同构环境中的两阶段算法,但上述算法在容错调度时都选择对待调度进程排序方法来解决调度负载均衡问题。
本文主要是对异构分布式系统基于负载均衡的一种改进算法的讨论。建立了一种新的容错调度模型,在该模型基础上提出hdal算法,并与文献[6]中提出的hdldf算法作比较,结果表明该算法在时间复杂度上优于hdldf算法。最后通过模拟实验证明hdal算法的负载均衡性占优,同时当进程达到一定数量时最少处理机需求略少于hdldf算法,这说明hdal算法资源利用率更高。最后还通过在不同异构环境下测试得出hdal算法适应不同的异构环境,而hdldf算法在节点性能差异较少的异构系统中,算法资源利用率明显不如hdal算法。但是本文所研究,还是在异构分布式系统中被动进程复制模型的静态容错调度算法,即进程分配的开始阶段一次性将所有进程全部分配完毕。
未完...点击下方链接下载完整文档