假设Pti与Bti被调度的时间段分别记为Slot(Pti)与Slot(Bti)，那么实时容错调度算法如图2所示。
3.2 实时容错调度算法
|
算法：实时容错调度算法
1、 当一个新请求Ti到达系统后，先将Pti置入主请求调度队列，通过复制获得从备份请求Bti，置入从请求队列。确定四元组中的三个元素{ Gi，Di，Pi }和区分服务等级Ki。
2、 在前端分发器中调度Pti。
① 主请求队列中的Pti根据负载均衡原则调度到调度表中允许的可用服务器，调度开始执行时间为Si。
② 依据区分服务等级确定延迟时间区间范围：Delayti=[Si,Di-Pi]；
③ 依据区分服务等级确定重发的时间SBti和概率PBti，SBti=（1-ξ）* Delayti, PBti=K*ξ；
//ξ为区分服务所对应的级别，在(0～1)之间，K为常数；
④ 以(PBti，SBti ，Di，Pi)标记从备份请求Bti；
3、 以Bti的调度参数调度Bti执行，调度满足如下原则：Server(Pti)!= Server(Btj),如果Server(Pti)= Server(Ptj)且Server(Bti) = Server(Btj)，那么Slot(Bti)∩Slot(Btj)=Φ,其中,i≠j；
// Server(Ptj)表示处理请求Ptj的服务器；
4、对从请求任务在调度前收到Pti正常执行结束的消息,则取消从备份队列中的Bti请求。 |
图2 实时容错调度算法
4 分析与仿真实验结果
通过对第2节的分析，我们很容易得到在不同系统参数下，Web集群系统服务器台数与可用度的关系，如图3所示。
图3 不同参数下，系统可用度与服务器台数的关系
对于容错调度算法，Spare processor方法[9]是采用一个或多个处理机作为备份，若系统出现故障时，则把故障机上的任务全部转移到备份处理机上运行，采用重新执行的方式来恢复。而若在系统没出现故障时,备份处理机一直处于空闲状态。
实时容错调度算法中主要考虑系统可用度的提高与系统接纳率，我们考虑在第2节故障模型下，采用容错调度算法后，可用度与系统利用率的关系如图4所示，可用度越高，系统利用率则越低。
图4 可用度与系统利用率关系图 图5表示与其它算法[9]在不同负载率情况下拒绝率的对比，从而说明本研究中所提出的实时容错调度算法能提高系统的接收率。
图5 不同负载下系统拒绝率对比图
5 结论
服务器冗余是提高系统可用度的基础，但同时降低了系统性能。论文主要从集群系统可用度的数学建模和容错调度二个方面分析了提高可用度的措施，实验结果表明算法很好地支持了系统的可用性，对于集群与分布式系统的高可用性分析与容错调度有较好的指导作用。
参考文献
1 V. Cardellini, E. Casalicchio, M. Colajanni, P.S. Yu. The state of the art in locally distributed Web-server systems. ACM Computing Surveys, 2002, 34(2): 1-49.
2 钱方，贾焰等. 提高冗余服务性能的动态容错算法. 软件学报，2001，12(6): 928-935.
3 周幼英，李福超等.关于调度算法与Web集群性能的分析. 计算机研究与发展，2003,40(3): 483-492.
4 P.R. Parthasarathy ,R.B. Lenin On the exact transient solution of finite birth and death processes with specific quadratic rates. Math. Scientist, 1997, 22: 92-105.
5 高文，祝明发. 基于生灭过程的机群系统高可用性分析与设计. 微电子学与计算机，2001，18(4): 47-49.
6 郑在宾，金海等. 有TCP连接容错功能的网络负载平衡调度系统. 华中科技大学学报，2003,31(2): 17-19.
7 Ying feng,Son Sang H. Scheduling hard real-time tasks with tolerance of multiple processor failures. Microprocessing and Mcroprogramming, 1994,40: 193～206.
8 Piestman A L. A fault-tolerant scheduling problem. IEEE Trans on Software Engineering, 1988, (12): 1089-1095.
9 Sylvain Lauzac, Rami Melhem. Adding fault-tolerance to P-Fair real-time scheduling. In: Workshop on Embedded Fault-Tolerant Systems 1998，34-37.
10 曾碧卿，陈志刚. 服务器集群系统研究. 计算机应用研究，2004，21(3)：186-187，196
基于GF(2n)椭圆曲线点积改进算法的PKI数据传输模型研究
基于Struts和EJB的Web Service框架研究