论文研究-一种基于负载均衡异构分布式系统的改进容错调度算法.pdf

所需积分/C币:6 2019-07-22 19:09:00 664KB .PDF
收藏 收藏
举报

基于基/副版本技术提出了一种具有容错功能的静态进程调度算法。给出了一个新的设计模型,并在该模型上提出HDAL算法。此前类似负载均衡容错调度算法都是通过排序来解决故障发生前后的负载均衡调度问题。该算法与以往算法不同之处就是在不依赖排序情况下,通过引进控制进程来解决负载均衡调度问题,并且该算法的负载均衡性在一定程度上具有了可控性。最后通过模拟实验得到以下有意义的结论:在业务繁忙的异构系统中,HDAL算法比以往算法资源利用率高,负载均衡性更好,并且在调度速度上优势明显。
第7期 邓建波,等:一种基于负载均衙异构分布式系统的改进容错调度算法 2481 具体算法过程请参考文献[6],限于篇幅,本文不再给出 3性能分析 2.2HDAL算法 DAL与 HDLDE算法不同的是,HDAL算法首先在新的 本章对HDAL算法通过模拟实验进行负载均衡性分析,同 设计模型下无须对基/副版本进程进行排序。首先该算法在故时还应用文献5]中计算最小节点需求算法( find minimal 障发生后会通过控制进程计算出故障发生后异构分布系统基/ number of processors,FMN)计算出HDAL算法与 HDLDF算法 副版本进程负载平均使用率,并更新所有节点的控制进程参最小节点需求并进行比较得出相关结论。使用1.6GHz 数。某节点失效对于整个系统而言实际负载总量并没有变化,Core2 Duo Cpu,内存2GB的PC机进行模拟实验,程序语言 因为失效节点的进程按一定的规则分型到其他节点上,但是系使用Jaa,编译工具使用 Eclipse3.5。本文应用平均方差来衡 统能承受的最大负载总量变小。其次分配基/副版本进程时可量异构分布式系统中的负载均衡性。形式化描述为 以随机取出待调度的基/劑版本进程,只要满足性质1、2和3, △p(N:)=(N,H-2(N,1)/n)/∑(N.p)/nn (6) 即当某一进程P分配到节点机N,进程P的基/副版本进程 不能同时在N上,且如果是P(基版本进程i)分配到节点N 由于在昇构系统屮节点机的性能不同,本文引入一个节点 上,那么节点N上的基版本进程负载使用率不大于平均负载在系统中的权值。其中E,表示节点N在整个异构系统所占 使用率值,形式化描述为pn≤p;如果是Pa(副版本进程)的重要程度。为了使问题简单前不失一般性,本文把£表示 即满足p≤pm,且为了减少系统总的负载,在选择任务调度当前节点机承载的最大负载与整个异构系统中载的最大 处理、满足上述条件时应尽量选择负载小的处理进行调度。如负载的比值,即=MM,j∈[1,n],那么可知 果不满足就分配P1,即选择负载次优的处理机直到k=几。()=1且0<<1。由上面表达式可知一次模拟实验中负 当k=n时说明待分配进程没有合适的处理机进程分配,那么载均衡性为 返回调度失败。如果分配完所有进稈则请度成功。因为故障 △p=Σ(△p(N1)×5;) 发生时重新更新μ-与ps的值,能很好地控制负载均衙 问题。 依据上面计算方法知,△p的值越大表明负载均衡性越差, 算法1HDAL算法 反之亦然 输入:进稈集合Φ,处理机个数n及p的值 3.1节点间负载均衡性分析 输出: result,节点机集合 仿真模拟实验1:令基版本进程的负载等概率分布在1 a)初始化并更新制进程 9;副版本的进程负载以等概率分布在其基版本负载的5% h)for(i=ltom)and(P;∈PA)and(没有调度)do/*调度基版本 进程* 10%;处理机最大能承受负载μ在30-150变化,即性能最高 计算节点上的基版本进程的pA,因式(3)及更新控制进程 p aryan; 的节点机是性能最差节点机处理能力的5倍。在实验中先随 6r=1bn{选择节点N,且满足(N=T,N,pn≤N,pm)机生成基/版本过程集合和节点机集合,并为每个节点注上 NpA+N,pB≤∩PP、f=minP.PAf,Vj∈[1,n]:i(满足)控制进程,其负载大小设为5。然后调用HDAI.与HDDF算 PPAN=j,=NA+PA|NpA=NPA+( Pi Pai Ig/法输出节点机集合①,并通过式(7)训算△p值,重复100次, N,p);clse选择次优节点机}; 并求Δρ平均值,得到图1。图1是在保证算法都能正确调度 if(i=n)and(进程没有被调度成功) return failed; else i++;/ 个基版本进程* 完所有进程情况下得到的故障发生前后负载均衡图。图中显 c)for(j=1tom)and(P;∈Pg)and(没有调度)/*调度副版本进 示在节点为25个、p值为1,进程数在100~600时,故障发生 程*/ 前与发生后负载均衡的调度情况。从图1可以看出,故障发生 计算节点N上某版本进程与其对应的副版本进程负载变化,即式前后HDAL算法的负载均衡性基本没有变化,而 HDLDE算法 (4)更新控制进程pnsi; 在故障发生后节点的负载均衡性冇所下降,虽然随着进程数量 fori1tn|选择节点N日满足(NT(N,p≤N,pm)∩的增加负载均衡性有所上升,但是HDAL算法负载均衡性优于 (N·PA+N,PB≤p)CP,PB,f=minP,PB,f4,Vj∈1,n IIDLDE。这说明∫IDAL算法在故障发生前后负载均衡性稳 满足)N·pB=p+(P.PA--P.Py,fa)/N,p;NOB N: WB+ PBII else i++|: I 定,主要原因是无论故障发生前后HDAL算法都通过更新控制 if(i=n)and(进程没有被调度成功) return failed; else j++;/*下 进程来控制各节点负载使用率。 副版本进程 0.25 HDAL算法枚障前 02 HDLDF算法改障前 d) if(N ≠∪N,A≠) then result= false,exit;else 0.15 -HD)L算法故障后 HDLDE算法故障后 break 0 HDAL算法首先分配基版本进程,从待调度基版本进程中 0.05 取一个进程分配到节点机N上,同时保证节点N的负载低于 100200300400500600 平均负载且进程调度到该处理机上负载相对较小,如果满足条 调度进程数 件则更新N节点相关信息。调度副版本进程时同理。时间复 图1HDAL与 HDLDE算法负载均衡图 杂度分析如下 3.2算法最小节点需求分析 更新n个节点机的控制进程参数所需时间为 n log m。调 HDAL和 HDLDE算法都是启发式的异构分布式模型下基 度进程计算进程负载变化所需时间及分配基版本进程所需时于负载均衡的容错调度算法。两种算法都是输入带有某/副版 问是2(n-1)mlgm。幣个IDAL算法时间复杂度为O(mm本的进程集合Φ;和处理机个数n,因此在系统发生故障前后 legm)。从时间复杂度来看,HDAL优于 HDLDF算法 负载均衡的重要性相同的情况下,可以通过对最小节点需求比 2482 计算机应用研究 第27卷 较来对算法作出选择。本文参考了文献[5]提出的求解最小 HDAL算法Ac(30.150 口HDAL算法μ∈(50,120) 处理机个数的(FMNP)算法,通过模拟实验比较得出两种算法 HDAL算法∈(90,90) HDDF算法=(990 利用率。FMNP算法描述如下 10 算法2FMNP算法 输入:进程集合{p,ψ,t及p=1/* HDLDF算法只使用 100200300400500600 调度进程数 图3不同A值的HDAL算法最小处理机数 输出:k,节点机集合Φ a) Lower=1: Hight=m+n;/* HDLDF算法中n=0* 4结束语 b,k=( Lower+ Hight )/2 if(k= Lower)then k=k+l: exit 本文首先提出一种新的基于基/副版本进程的模型。在模 c)if(type=HDAL) then hdal(up,ψ:,△a,p,k; resuli,Φ) 型中引进了控制进程,并可以控制异构分布式容错系统中节点 模拟实验2与1类似,先随机产生进程集合{Φ,Φn},调性能最大使用率。并提出了HDAL算法,计算出算法时间复杂 用FMNP算法,输出算法所需最小处理机个数k。重复实验50度,通过模拟实验对算法的负载均衡稳定作了分析,结果显示 次,求得k的平均值,得到图2 故障发生前后算法的负载均衡性稳定。其次,通过利用(FM Hilde算法 NP)算法计算出HDAL算法在不同的异构环境所需最小节点 新20 HDAL算法 机个数,结果表明算法的最小节点机需求与异构系统性能差异 无关,说明在越庞大、任务繁忙的异构分布式容错系统中采用 82 HDAL算法更为合理,反之亦然。 100200300400500600 在本文中待研究的问题:a)该谷错任务调度算法的前提 调度进程数 假设还是在异构分布式系统中被动进程复制模型的静态容错 图2HDAL与 HDLDF算法最小处理机个数 调度算法,即进程分配的开始阶段一次性将所有进程全部分配 图2说明进程个数增加所需最小节点机个数增加。因为完毕:出)进程粒度与异构分布系统性能及整个系统进程数量 调度的进程数越多,就需要更多节点机,以保证每一节点的负 相互关系还有待进一步分析,因此本文给出的结果只是当前模 载不超过其所能承受的负载上限。同时还可以看出两和算法拟实验环境下得出的。 在进程数达到一定数量时,IDAL算法所需最小节点机个数略 小于ⅢDLD算法。这是因为当进程数增加时IDAL算法的参考文献: [1 KOPETZ H, GRUNSTEIDL G TTP: a protocol for fault-tolerant real 控制进程所占的负载比重变小,而HDAI算法均衡性优于 time systems[ J]. IEEE Computer, 1994, 27(1): 14 HDLDE算法,并且进程数越大这种优势越明显。但是进程数[21 SIEWIOREK D P, SWARTZ R S. Reliable system design: the theory 量较少时 HDLDF算法所需最小节点占优,因为相同的业务量 and practice[ M]. New York: Digital Press, 1992 情况下,HDAL算法需要额外的控制进程即需要额外负载。这[31 LINTEIN H, SHIn K G, Damage assessment for optimal rollback re 就说明在任务繁忙的系统中应该选择HDAL算法,而在业务相 every[J. IEEE Trans on Computers, 1998, 47(57): 603-613 对轻松的系统屮选择 HDLDF算法 [4 LIU Huai, FEI Shu-min. A fault-tolerant scheduling algorithm based EDF for distributed cunLrul syslems[ J. Journal of Software 模拟实验3是为了说明不同范围处理机承受的最大负载 2003,14(8):1371-1378. 与最小处理机需求个数的关系,处理机最大承受负载μ是反[5] QIN Xiao, PANG Li-ping, HAN Zong-fen. Algorithms of fault- tolerant 映异构分布式系统巾处理机性能差异的标准参数。μ的值变 scheduling in distributed real-time sy stems[J] Journal of Compu 化区间越大,说明系统中处理机之间性能的差异越大。本文分 ters,2000,23(107):1056-1063 [6 GUO Hui, WANG Zhi-guang, ZHOU Jing-li. Load balancing hased 别取μ在(30,150)(50,120)(90,90)三个区间上的变化,调 process scheduling with fault-tolerant in heterogeneous distributed sys 用HDAL算法及μ在(90,90)调用HDAL算法得到图3。从图 tem[J. Chinese Journal of Computers, 2005, 28(11): 180 3可以看出,在μ取不同区域调用HDAL算法最小处理机需求 816 基本没有变化,这说明该算法负载均衡性对异构系统性能差异7KIMJ,LEEH,LEES. Process allocation lur lvad distribulion iu lall 依赖少。主要是因为HDAL算法调度进程通过控制进程来选 tolerant multi-computers[ C]//Proc of the 25 th International Symposi 择调度处理机,而文献6]的 HDLDE算法在同构环境中退化 um on Fault-Tolerant Computing. 1995: 124-129 为二阶段算法,这也就说明 HDLDE算法只适合于性能差8] BERTOSSIA A, MANCINI L V. ROSSINI F. Fault-tolerant rate-mc notonic first-fit in hard re al-time scheduling sy stems J. IEEE Trans 较大的系统,所以在业务繁忙的系统应选择HDML算法 on Para Newland Distributed Systems, 1999, 10(9): 934-94.5 (上接第2478页) Knowledge Discovery and Data Mining. Washington DC: [sn] [8 KURAMOCHI M, KARYPIS G. Frequent subgraph discovery[C// 2003:24-27 Proc of International Conference on Data Mining. San Jose: [s.n. [11 HAN Jia-wei, PEI Jian, YANG Xi-feng From sequential pattern mining 2001:313-320 tured pattern mining: a pattern-growth approach[J] Journal of [9] YAN Xi-feng, HAN Jia-wei gSpan: graph-based substructure pattern Computer Science and Technology 2004, 19(3): 257-279 mining[ C]//Proc of the 2nd International Conference on Data Min-[ 12] LI Yu-hua, LIN Quan, ZHONG Gang et al. A directed labeled graph ing Maebashi: s.n. 1, 2002: 721-724 frequent pattern mining algorithm based on minimum code C//proc 10J YAN Xi-feng, HAN Jia-wei Close graph: mining closed frequent graph of the 3rd International Conference on Multimedia and Ubiquitous E patterns[ C//Proc of ACM SIGKDD of International Conference on gineering Qingdao: [s.n. 1, 2009:353-359

...展开详情
试读 4P 论文研究-一种基于负载均衡异构分布式系统的改进容错调度算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    img

    关注 私信 TA的资源

    上传资源赚积分,得勋章
    最新推荐
    论文研究-一种基于负载均衡异构分布式系统的改进容错调度算法.pdf 6积分/C币 立即下载
    1/4
    论文研究-一种基于负载均衡异构分布式系统的改进容错调度算法.pdf第1页
    论文研究-一种基于负载均衡异构分布式系统的改进容错调度算法.pdf第2页

    试读已结束,剩余2页未读...

    6积分/C币 立即下载 >