_n为：             (4)     由此得到集群系统的可用度为               (5)     对式(5),随着节点数的增加，系统的可用度迅速增加。假定平均修复时间为0.5小时。计算可得，在有4个结点的集群系统中，即使每个结点的故障率高达0.1次/小时，集群系统的可用度已经达到99.9%。那么已知系统所需的可用度为A_n，很容易得到所需服务器台数为：   n=         (6)

3 基于概率的实时容错调度

3.1 实时容错调度算法的基本思想

    随着电子商务等关键业务的发展，要求任务的执行可用度很高，而且往往都有严格的时间约束,若由于处理机的故障导致某些任务不能完成，或不能在其限定的时间之前完成，就可能造成重大损失^[1,6]。因此需要在Web集群系统中提供一定的实时容错调度能力以提高整个系统的可用性。 文献[7]、[8]提出在不同处理机上调度任务的多个版本来运行，以此达到容错的目的。 但是，同样任务的多个版本，运行时具有同样的请求，系统利用率只有1/n。文献[9]提出了一种回收的方法，提高了系统效率。     系统的请求集可定义为Γ={T_i|i=1,2,…}。T_i可以用一个四元组(G_i，S_i，D_i，P_i)来表示。其中，G_i表示请求到达系统的时间；S_i表示请求被调度开始执行的时间；D_i表示请求必须执行完成的时间，即deadline；P_i表示请求的执行时间；采用的故障模型同第2节^[5]，另外，在对请求进行容错调度的同时，系统要能及时通过“心跳”诊断并报告处理机故障^[10]。由于处理机之间通信所需时间与请求的执行时间相比非常短，因此可忽略处理机之间消息的传递时间^[7,8]。     基于概率的实时容错调度算法基本思想如下：对任一动态到达系统的非周期性任务T_i，我们将首先置入主请求队列Q_p，同时将此请求复制一份到从请求队列Q_b，主请求记为P_ti,，从请求(或称为后备请求)记为B_ti，确定它的区分服务等级k，以区分服务的等级确定从备份请求的延迟时间和重发的概率，以这二个参数标记从备份请求队列B_ti，如果在T_ri重发时间前收到P_ti成功执行的报告，则取消B_ti，否则按标记重发T_ri，这就是无错时停止重发以提高系统的性能。 假设P_ti与B_ti被调度的时间段分别记为Slot(P_ti)与Slot(B_ti)，那么实时容错调度算法如图2所示。

3.2  实时容错调度算法

算法：实时容错调度算法 1、   当一个新请求T_i到达系统后，先将P_ti置入主请求调度队列，通过复制获得从备份请求B_ti，置入从请求队列。确定四元组中的三个元素{ G_i，D_i，P_i }和区分服务等级K_i。 2、   在前端分发器中调度P_ti。 ① 主请求队列中的P_ti根据负载均衡原则调度到调度表中允许的可用服务器，调度开始执行时间为S_i。 ② 依据区分服务等级确定延迟时间区间范围：Delay_ti=[S_i,D_i-P_i]； ③ 依据区分服务等级确定重发的时间SB_ti和概率PB_ti，SB_ti=（1-ξ）* Delay

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说计算机Web集群中基于实时概率的容错调度算法研究(2)在线全文阅读。