《基于异构分布式系统的实时容错调度算法》由会员分享，可在线阅读，更多相关《基于异构分布式系统的实时容错调度算法（8页珍藏版）》请在金锄头文库上搜索。
1、第 25卷 第 1期 2002年 1月计 算 机 学 报 CHINESE J. COM PUTERSVol. 25 No. 1 Jan. 2002基于异构分布式系统的实时容错调度算法秦 啸 韩宗芬 庞丽萍(华中科技大学计算机科学与技术学院 武汉 430074)收稿日期: 2000-08-03;修改稿收到日期: 2001-09-12.秦 啸 ,男 , 1974年生,硕士,主要研究领域为实时系统、实时容错技术、调度理论、网络通信和数据库管理系统 .E-mail:xqincse.unl.edu.韩宗芬 ,女 , 1950年生 ,副教授,主要研究领域为分布式实时系统、操作系统、软件工程.庞丽萍 ,女,
2、 1944年生 ,教授 ,主要研究领域为并行分布式程序设计、分布实时系统 .摘 要 目前文献中研究的实时容错调度算法都是基于同构分布式系统 ,系统中的所有处理机完全相同 .该文首先建立了一个基于异构分布式系统实时容错调度模型 ,异构分布式系统中的各个处理机均不相同 .基于该异构分布式系统模型 ,该文引入了可靠性代价 (reliability cost)概念 ,并提出两种静态实时容错调度算法 ( RTFTNO和RTFTRC)用于调度周期性实时容错任务.算法 RT FT RC在调度任务时 ,尽量使系统的可靠性代价最小; 而算法RTFTNO在调度实时任务时 ,没有考虑系统的可靠性代价 .该文详细讨论
3、了两种调度算法的性能 .性能模拟实验分别比较了两个算法的可靠性代价 ,超时比率和可调度性;并研究了任务的计算时间与可靠性代价的关系以及调度长度阈值与最小处理机个数的关系 .实验结果表明 ,算法 RTFTRC的性能优于算法 RT FTNO.关键词 容错 ,实时调度 ,异构分布式系统 ,模拟实验 ,性能分析中图法分类号:TP302Real-Time Scheduling with Fault-Tolerance in Heterogeneous Distributed SystemsQIN Xiao HAN Zong-Fen PANG Li-Ping( School of Computer Sci
4、ence and Technology , Huazhong University of Science 该性质可形式化描述为 , (One processor failure is tolerated)i 1,n , (dpidbi) (spi+ c(i,dpi)sbi) .性质 3. 对于异构分布式系统中的每一个处理机 Pj, 满足 j 1,m ,tpi jc(i, j )+tbi jc(i , j )DL.3 实时容错调度算法与实时调度算法一样 ,实时容错调度算法也是一个 NP难度问题 ,本节提出两个启发式算法.算法RTFTNO是一个经典的实时容错调度算法 ,该算法在调度任务时 ,仅仅考
5、虑如何使所有处理机的调度长度尽量小 ,由于该算法没有考虑到异构分布式系统的特点 ,它只适用于同构分布式系统 ,而在异构分布式系统中的性能比较差.第 4节将详细研究该算法的性能.算法 RTFTNO的描述如下 .算法 1. RTFTNO输入:T,K,DL输出: sch_success,K, RC0(K0)1. 初始化处理机集合 K 、任务集合 T 和系统的可靠性代价 RC0(K);2. 对于每一个实时任务基版本tpi/ * 首先调度实时任务的基版本*/3. 选择j, 满足 k 1,m,ajak;/*tpi被调度到处理机Pj*/4. j= tpi+ j; dpi= j; spi= aj; aj= a
6、j+ c (i, j);RC0(K)= RC0(K)+ j c(i, j);5.对于每一个实时任务副版本 tbi/ * 调度实时任务副版本*/6. 选择 jdpi,满足 k 1,m , kdpi ajak;/* tbi被调度到处理机 Pj*/7. j= tpi+ j; dp i= j; sp i= aj; aj= aj+ c (i, j);RC0(K)=RC0(K)+jc(i,j);8. if (aj DL ) return( FAIL);9. return( SU CCESS);与算法 RTFTNO相比 ,算法 RT FT RC在不增加系统硬件代价的情况下 ,提高了系统的可靠性.算法 RTF
7、T RC的调度目标有两个 ,减少处理机的调度长度和减少系统的可靠性代价.对于每一个基版本 tpi,当其调度到处理机 Pj上时 ,使系统中的可靠性代价增加尽量地少 .然而 ,当一个处理机的调度长度 Lp过大后 ,可能会造成一些任务的副版本无法在规定的截止期限内完成.对每一个处理机的调度长度 进行 限 制将 有 利于 解决 这 个问 题. 算 法RT FTRC在调度任务的副版本时 ,要求满足三个情况: ( 1) 副版本所在的处理机与其基版本所在的处理机是不同的; ( 2) 副版本被调度到处理机 Pj上时 ,使系统中的可靠性代价增加尽量地少; ( 3) 副版本可以在截止期限内完成 .在给出算法 RT
8、FTRC之前 ,为每一个任务 ti定义一个可靠性代价向量 ,RCVi= rcvi1, ,rcvim,其中 rcvij= (rcij, dij). rcvi j可以通过向量 Ci和处理机集合 K推导出 , rcij=c(i ,dij)d i j. RCVi中的元素按其可靠性代价非减的顺序进行排序 ,形式化描述排序结果为 i 1,n ,j ,k 1,m ( j 70时 , PMD将恒定为 100 % .与算法 RT FTNO相比 ,算法 RT FT RC的 PMD仅仅在区域 97, 103发生变化; PMD为零 ,当 n 103, PMD等于 100 % .表 1的数据同时显示出两种算法的 PMD
9、值在变化区域增加很快.该结果说明在相同的实验前提下 ,实时任务越 多 ,算法的可调度性越小. 4. 4节实验将进一步讨论可调度性问题. 本实验数据证明 ,对于性能指标531期秦 啸等: 基于异构分布式系统的实时容错调度算法PMD 而 言 , 算 法RT FT RC 的 性 能 优 于 算 法 RTFTNO.因为如果两个算法具有相同的 PMD值 ,则算法 RTFTRC可以调度的任 务个数比算法RTFTNO的任务个数要多.例如在 PMD值为 1 %的情况下 ,算法 RTFTRC可以调度的任务个数是97,然而算法 RTFTNO的任务个数只有 56.从超时比率这项性能指标而言 ,算法 RT FT RC
10、的性能优 于算法 RTFTNO.表 1 算法RTFTNO和算法RTFTRC的PMD值比较(DL= 1400, Lp= 700, m= 5)nRTFTNO(% )nRTFT RC(% )561971 588982 6024993 62501005 647410135 668910297 689710399 70994. 4 可调度性的比较实时容错调度算法的可调度性通过最小处理机个数表现 ,即给出一组任务集合 ,算法所需的处理机个数 k越小 ,则说明该算法的可调度性越好 .求解最小 处 理 机 个 数 算 法 ( Find Minimal Number ofProcessors, FMNP)的设计
11、请参见文献 18,当给出任 务 集 合 , 该 算 法 可 以 为 算 法RT FTNO 及RTFTRC分别计算出满足实时容错调度需求的最小处理机个数 .为方便算法 FMNP求解最小处理机个数 ,不妨在本模拟实验中设所有处理机的失效率均为 10- 6次 /小时.本模拟实验的基本参数与 4. 2节实验的相同 ,实验结果如图 3所示.该实验结果首先表明 ,对于两种算法而言 ,随着任务个数的增加 ,最小处理机个数随之增加 .因为系统中的实时任务个数越多 ,就需要更多的处理机来保证在截止时限之前完成所有的任务.其次 ,实验证明算法 RT FT RC的可调度性比算法 RTFTNO的要好 ,而且任务的计算
12、时间越长 , RT FTRC的性能比 RT FTNO的可调度性越高.因为在相同的实验参数条件下 ,算法RTFTRC所需的最小处理机个数比算法 RTFTNO的要小.例如 ,当有 100个任务时 ,如果计算时间满足 5, 100的均匀分布 , RTFTNO的最小处理机个数为 8. 65,而 RTFTRC的仅为 5. 36;如果计算时间满足 5, 200的均匀分布 , RTFTNO和 RT FT RC的最小处理机个数分别为 16. 64和 7. 09.本实验的第三个结论是 ,在任务个数固定的前提下 ,两个调度算法的最小处理机个数随着任务计算时间增加而增加.因为系统中的任务个数固定时 ,任务的计算时间
13、越长 ,系统需完成的工作量越大 ,也就需要更多的处理机来保证在截止时限之前完成所有的大工作量 .4. 5 调度长度阈值与最小处理机个数的关系调度长度阈值不影响算法 RTFTNO的性能 ,但该值决定了调度算法 RT FTRC的性能好坏 .本实验的目的是研究算法 RT FTRC中 ,调度长度阈值与最小处理机个数的关系.实验参数与 4. 1节基本相同 ,计算时间满足 5, 200上的均匀分布.分别设任务个数为 40, 60和 100,进行三组实验.从图 4的实验结果中可看出 ,随着 Lp值的增加 ,最小处理机个数的值随之减小.当调度长度阈值的值大于700后 ,最小处理机个数进入相对平稳阶段 .例如:
14、当 Lp值大于 700后 ,如果任务个数为 40,则最小处理机个数在 4. 48到 4. 50之间; 如果任务个数为100,则最小处理机个数在 7. 07到 7. 08之间.这说明在调度算法 RTFTRC中 ,将参数 Lp值设为大于DL /2后 ,调度长度阈值 Lp对算法 RTFT RC的影响不大.所以 ,作为传统分布式系统调度算法负载平 衡参数的调度长度阈值 ,在算法 RTFTRC中的意54计 算 机 学 报 2002年义并不是很大 .5 结束语已有一些论文研究了实时容错调度算法 ,然而这些算法都是基于同构分布式系统的.同构分布式系统中的处理机完全相同 ,而在异构分布式系统中 ,各个处理机有
15、不同的失效率 ,每个任务在不同的处理机上有不同的计算时间 .本文的创新是提出了基于异构分布式系统的实时容错调度算法 ,并对调度算法的性能进行了模拟与评价.实验结果表明 ,算法RTFTRC的性能比算法 RTFTNO的要好 ,算法RTFTRC更适合异构分布式系统.本文中研究的算法 RTFTNO与 RTFTRC是两个静态调度算法 ,这是我们基于异构分布式系统实时容错调度研究的第一步工作.正在进行的研究工作是 ,在此工作的基础上 ,结合文献 18提出的混合调度技术 ,研究基于异构分布式系统的混合型实时容错调度算法.下一步的工作还包括 ,提出基于异构分布式系统的高效率实时容错调度算法 ,该算法的处理机利
16、用率和算法的可调度性都将比本文提出的算法 RTFT RC的要高.致 谢 Hong Jiang教授 , Steven Goddard博士和Olaf Barheine与我们深入讨论了实时容错调度的问题 ,刘键教授和尹浩同学对本文第一版本提出大量有价值的建议.在此对他们给予的学术上的指导和帮助表示衷心地感谢 .参考文献1Kieckhafer R M , Walter C J, Finn A M, Thambidurai P M.The M AFT architecture fo r distributed fault tolerance.IEEET rans Computers, 1988, 37( 4): 398- 4052Factor M.Real-time data fusion in the intensive care unit.IEEE Computer, 1991, 24( 11): 45- 54
