资源描述：
《web集群中基于实时概率的容错调度算法研究 》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、Web集群中基于实时概率的容错调度算法研究摘要论文中首先对arkov模型描述了其可用性，从理论上建立了集群高可用模型。然后，着重针对arkov模型描述了其可用性，从理论上建立了集群高可用模型。然后，着重针对Dt；④同时出现两个或更多个节点故障或修理的概率是零；⑤每个节点的故障或修理的事件与所有其它事件无关。这样就可以建立集群系统的可用度模型。集群系统由n个节点组成，其状态n的稳态概率pn就是集群高可用系统中所有节点都出现故障，即整个系统不可用的概率，而A=(1-pn)即为集群系统的可用度。(3)求解(2)、(3)式得：这样，集群系统处于状态n的稳态概率p
2、n为：(4)由此得到集群系统的可用度为(5)对式(5),随着节点数的增加，系统的可用度迅速增加。假定平均修复时间为0.5小时。计算可得，在有4个结点的集群系统中，即使每个结点的故障率高达0.1次/小时，集群系统的可用度已经达到99.9%。那么已知系统所需的可用度为An，很容易得到所需服务器台数为：n=(6)3基于概率的实时容错调度3.1实时容错调度算法的基本思想随着电子商务等关键业务的发展，要求任务的执行可用度很高，而且往往都有严格的时间约束,若由于处理机的故障导致某些任务不能完成，或不能在其限定的时间之前完成，就可能造成重大损失[1,6]。因此需要在W
3、eb集群系统中提供一定的实时容错调度能力以提高整个系统的可用性。文献[7]、[8]提出在不同处理机上调度任务的多个版本来运行，以此达到容错的目的。但是，同样任务的多个版本，运行时具有同样的请求，系统利用率只有1/n。文献[9]提出了一种回收的方法，提高了系统效率。系统的请求集可定义为Γ={Ti
4、i=1,2,…}。Ti可以用一个四元组(Gi，Si，Di，Pi)来表示。其中，Gi表示请求到达系统的时间；Si表示请求被调度开始执行的时间；Di表示请求必须执行完成的时间，即deadline；Pi表示请求的执行时间；采用的故障模型同第2节[5]，另外，在对请求进行
5、容错调度的同时，系统要能及时通过“心跳”诊断并报告处理机故障[10]。由于处理机之间通信所需时间与请求的执行时间相比非常短，因此可忽略处理机之间消息的传递时间[7,8]。基于概率的实时容错调度算法基本思想如下：对任一动态到达系统的非周期性任务Ti，我们将首先置入主请求队列Qp，同时将此请求复制一份到从请求队列Qb，主请求记为Pti,，从请求(或称为后备请求)记为Bti，确定它的区分服务等级k，以区分服务的等级确定从备份请求的延迟时间和重发的概率，以这二个参数标记从备份请求队列Bti，如果在Tri重发时间前收到Pti成功执行的报告，则取消Bti，否则按标记
6、重发Tri，这就是无错时停止重发以提高系统的性能。假设Pti与Bti被调度的时间段分别记为Slot(Pti)与Slot(Bti)，那么实时容错调度算法如图2所示。3.2实时容错调度算法算法：实时容错调度算法1、当一个新请求Ti到达系统后，先将Pti置入主请求调度队列，通过复制获得从备份请求Bti，置入从请求队列。确定四元组中的三个元素{Gi，Di，Pi}和区分服务等级Ki。2、在前端分发器中调度Pti。①主请求队列中的Pti根据负载均衡原则调度到调度表中允许的可用服务器，调度开始执行时间为Si。②依据区分服务等级确定延迟时间区间范围：Delayti=[S
7、i,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
8、的服务器；4、对从请求任务在调度前收到Pti正常执行结束的消息,则取消从备份队列中的Bti请求。图2实时容错调度算法4分析与仿真实验结果通过对第2节的分析，我们很容易得到在不同系统参数下，.Colajanni,P.S.Yu.ThestateoftheartinlocallydistributedputingSurveys,2002,34(2):1-49.2钱方，贾焰等.提高冗余服务性能的动态容错算法.软件学报，2001，12(6):928-935.3周幼英，李福超等.关于调度算法与icroprocessingandMcroprogramming,1994
9、,40:193～206.8PiestmanAL.Afault-tolerants
