一种基于可靠性驱动的云资源容错调度方法

摘要

一种基于可靠性驱动的云资源容错调度方法，包括以下步骤：1）初始化；2）计算DAG中的每个任务i的bl(i)和初始化tl(i)＝0；3）将开始任务插入α中；4）开始调度，按如下步骤进行操作，直至所有的任务都调度完成，具体包含如下步骤：4.1）调度时的初始化；4.2）在每个处理机Pj上，寻找任务i的合适处理机；4.3）如果任务i没有可行的处理机，则调度失败；4.4）将处理机分配给任务i；4.5）将任务i的空闲后续放入到α中；4.6）更新U；5）调度结束，调度成功。本发明通过有效的容错调度提高了系统的服务质量。

主权项

1.一种基于可靠性驱动的云资源容错调度方法，其特征在于：包括以下步骤：1）初始化，包含如下过程：1.1）将系统支持的最大处理机失败的数量赋值给ε；1.2）确定系统的处理机集P={P₁,P₂,…,P_m}，任务的计算时间用ε:V×P→R来模拟，ε(i,P_j),1≤j≤m表示系统中每个任务在每个处理机上的执行时间；任务间的通信时间用W(i,j)=v(i,j)×d(P_k,P_b)来表示，其中，任务i映射到处理机P_k上，任务j映射到处理机P_b上，d(P_k,P_b)表示发送单位长度数据所需的时间；如果任务部署到同一个处理机上，则通信时间为零；1.3）初始化调度任务集合未调度任务集合U=V，设S是调度任务集合，U是未调度任务集合，一旦一个任务i∈S调度到处理机P_j上，则会得到它的开始时和完成时间利用无回路有向图DAG来模拟任务模型中的任务以及它们之间的关系，用T=(V,E)表示，其中V是一个节点集合对应所有非周期、非抢占性的实时任务；E是一个边集合对应所有任务之间的优先关系以及任务之间的通信；对于一个任务i，S_dp(i)表示任务i的直接前续集合，S_ds(i)表示任务i的直接后续集合；v(i,j)表示任务i发送给任务j的数据量；1.4）初始化空闲任务优先列表该表利用平衡搜索树去执行任务；2）计算无回路有向图DAG中的每个任务i的bl(i)和初始化每个开始任务i的tl(i)＝0；tl(i)表示动态高位水平，bl(i)表示静态低位水平；其中tl(i)依赖于映射过程中己经部署的任务，bl(i)根据DAG的拓扑结构将保持不变；其中，bl(i)的求解步骤如下：2.1）：对于如果任务i的后续集合为空，即则其中是任务的平均执行时间，即否则转到2.2)；2.2）：$\mathrm{bl}\left(i\right)={\max }_{j\in S_{\mathrm{ds}}\left(i\right)}\{\overline{ϵ\left(I\right)}+\overline{W(I,J)}+\mathrm{bl}\left(j\right)\},$表示任务间的平均通信时间，求解公式为：其中表示系统中处理机间发送单位长度数据的平均延迟；3）将开始任务插入α中；4）开始调度，任务的调度过程如下4.1）调度时的初始化，包含以下过程：4.1.1）：选择优先权最高的任务，并将H(α)赋值给i；一个任务的优先权由tl(i)+bl(i)来决定，H(α)返回有序队列α中的第一个任务，即是带有最高优先权的任务；4.1.2）：初始化可靠性r为0；4.1.3）：最早完成时间初始化4.2）对于每个处理机P_j按如下步骤Step1~Step3进行操作，从第一个处理开始处理，直至将所有的处理机都处理完毕；4.2.1）：计算最早完成时间具体的求解公式如下：$t_i^{P\left(j\right),\mathrm{ef}}=ϵ(i,j)+\max \left\{{\max }_{u\in S_{\mathrm{dp}}\left(i\right)}\right\{{\min }_{k=1}^{ϵ+1}\{t_{u^k}^{P\left(u^k\right),f}+W(u,i)\}\},{\max }_{i\in S}(x_{\mathrm{ij}}\times t_i^{P\left(j\right),f})\}$其中，为任务u的第k个副本u^k在所在的服务器的处理完成时间；x_ij=1表示任务i映射到处理机P_j上，否则为x_ij=0；4.2.2）：如果任务i能够在处理机P_(ε+1)上达到最早完成时间，且在t_r-a(i)之前完成，则确定此时系统的可靠度r_j。否则，返回结束此次循环，对下一个处理器进行操作，返回4.2.1）；t_r-a(i)的作用是限制任务的响应时间，其求解公式为：$t_{r-a}\left(i\right)={\min }_{j\in S_{\mathrm{ds}}}\left\{{\max }_{q\in S_{\mathrm{dp}\left(j\right)}}\right\{t_q^{P\left(q\right),d}+W(q,j)\left\}\right\};$对于容错调度每个任务有一个调度矩阵假设系统中一个任务I的ε+1个副本分派到m个处理机上，当任务的副本i分派到处理机P_j时，否则其中i＝1,2,…,(ε+1)，j=1,2,…,m；系统的可靠度的求解公式为：r_j=exp(-PR)，其中为副本i在处理机P_j的可靠性，是由事先给定的处理机失败比率λ_j和i在处理机P_j上的执行时间c_ij共同决定的；4.2.3）：如果满足以下两个条件之一：①r_j>r；②r_j=r且则调度任务i到这ε+1个处理机上，然后返回Step1去处理下一个处理机，直至将所有的处理机都处理完毕；4.3）如果对于任务i没有可行的处理机，则返回调度失败；4.4）将处理机分配给任务i；当任务i在处理机上的可靠性最大时；则将任务i放入S中，并同时更新任务i的后续的优先权；4.5）将任务i的空闲后续放入到α中；4.6）更新U，U=U(i)；4.7）当未调度任务集合U不为空时，即则按步骤4.1）到4.6）进行循环操作，直至U为空。