基于可靠性和合作博弈的计算网格均衡任务调度方法

摘要

基于可靠性和合作博弈的计算网格均衡任务调度方法属于网格任务调度领域，其特征在于是在基于可靠性和合作博弈的计算网格系统中实现的：在稳定状态下，根据各网格计算节点所允许提供的计算能力建立整个计算网格系统，可靠性优化目标函数是设定优化值，根据稳定状态下的参数值计算实际目标函数值，若与优化值的误差在设定的范围内，则按比例分配任务，否则，判断节点自身的任务可分配因子θ与从调度器向节点分配任务下限值α：当θ＜α时，不分配任务；当θ＞α时，删去分片任务平均到达速率等于零的节点，重新计算目标函数值，重复以上步骤，使余下节点尽力而为，达到可靠性和合作博弈的要求。随负载增加时，与非合作博弈与均衡算法比，使节点提供更高的计算能力。

主权项

基于可靠性和合作博弈的计算网格均衡任务调度方法，其特征在于，是在一个基于可靠性和合作博弈的计算网格系统中，以下简称系统，依次按以下步骤实现的：步骤(1)，构造一个基于可靠性和合作博弈的计算网格系统，其中包括：多个用户、面向各个用户的各调度器i、面向所述各调度器i的各网格计算节点j，以及一个调度方案计算器，其中：i＝1,2,…,i,…,I，I为调度器i的总数；j＝1,2,…,j…,J，J为网格计算节点的总数；设定：在忽略调度器i内部处理代价、任务传输时间的条件下：各调度器i输出分片任务的平均速率λ_i的加和小于所有网格节点对各自所收到的全部分片任务的平均执行速率u_j的加和，速率的单位为单位时间内的分片任务数，表示为：$\underset{i=1}{\overset{I}{\Sigma }}{\lambda }_i<\underset{j=1}{\overset{J}{\Sigma }}{u}_j---\left(1\right)$各调度器i发出的分片任务的平均速率λ_i的加和等于所有网格节点j的分片任务的平均到达速率φ_j的加和，表示为：0≤φ_j＜u_j且同时要满足：各网格计算节点j在保持服务质量前提下能够接受的最大分片任务到达速率大于网格计算节点j的分片任务平均达到速率φ_j，小于网格计算节点j对各自所收到的全部分片任务的平均执行速率u_j，表示为：${\phi }_j<{\phi }_j^{max}<u_j$步骤(2)，所述调度方案计算器按下式计算各网格计算节点j在稳定状态时允许提供的计算能力A_j,0＜A_j＜1：A_j＝1‑φ_jβ_1j(1+u'_jγ_j)   (3)其中，到达网格计算节点j的分片任务满足以分片任务平均到达速率φ_j为均值的泊松分布，β_1j为网格计算节点j的分片任务平均服务时间，u′_j为网格计算节点j忙时失败的平均速率，γ_j为网格计算节点j的平均重试时间；步骤(3)，所述调度方案计算器按下式根据输入的各网格计算节点j允许提供的计算能力A_j计算目标函数优化值D：$D=\underset{j=1}{\overset{J}{\Sigma }}\frac{1}{1-{\phi }_j{\beta }_{1j}(1+u_j^{\prime }{\gamma }_j)}---\left(4\right)$步骤(4)，所述调度方案计算器在设定的稳定状态下计算发送给各调度器i的任务调度方案：步骤(4.1)，系统参数初始化：调度器i发出分片任务的平均速率为λ_i(0)，i＝1,2,…,i,…,I，“0”符号表示稳定状态，下同，网格计算节点j的分片任务平均处理速率为u_j(0)，j＝1,2,…,j…,J；步骤(4.2)，所述调度方案计算器在收到在所述稳定状态(0)下由各调度器i和各网格计算节点j发来的步骤(4.1)中的数据后，设定：的初始化值为为网格计算节点j能够接受的最大分片任务到达速率，网格计算节点j的分片任务平均到达速率的初始化值为目标函数优化值D的误差精度ε(0)≤10^‑6；步骤(4.3)，利用步骤(3)的公式计算目标函数优化值D(0)＝latterD；步骤(4.4)，若D(0)＝latterD相对于D的优化目标值的误差ε(0)满足小于等于10^‑6，则按下式得到调度方案，求a_i,j，若不满足，执行步骤(4.5)；$a_{i,j}={\lambda }_i·\frac{{\phi }_j}{\underset{i=1}{\overset{I}{\Sigma }}{\lambda }_i}---\left(5\right)$其中，a_i,j为调度器i的分片任务分配到网格计算节点j的比例；步骤(4.5)，令formerD＝latterD，formerD用于暂存上一次调度方案下的目标函数值latterD；步骤(4.6)，按下式计算网格计算节点j在处于最大的分片任务到达速率时允许提供的单位分片任务计算能力θ_j，也称任务可分配调节因子；${\theta }_j=\frac{1}{{\phi }_j^{\max }}-{\beta }_{1j}(1+u_j^{\prime }{\gamma }_j)$并把各网格计算节点j对应的θ_j从小到大排序，排序的结果保存到变量index(J)中；步骤(4.7)，按下式计算分配临界因子α：$\underset{j=1}{\overset{m}{\Sigma }}\frac{1}{b_{index\left(j\right)}}\underset{j=1}{\overset{m}{\Sigma }}{\phi }_{index\left(j\right)}^{\max }-\underset{j=1}{\overset{m}{\Sigma }}\frac{\sqrt{\left(1-{\phi }_{index\left(j\right)}^{\max }{b}_{index\left(j\right)}\right)\left(\left(1-{\phi }_{index\left(j\right)}^{\max }{b}_{index\left(j\right)}\right)+\frac{4b_{index\left(j\right)}}{\alpha }\right)}}{b_{index\left(j\right)}}-2\underset{i=1}{\overset{I}{\Sigma }}{\lambda }_i=0$其中，index(j)表示按步骤(4.6)重新排序后网格计算节点j在index(J)中的位置，相对应的β₁、u'、γ分别表示为β_1index(j)、u′_index(j)和γ_index(j)，b_index(j)＝β_1index(j)(1+u′_index(j)γ_index(j))，α是调度器i判断是否向某个网格计算节点j分配任务的下限值；步骤(4.8)，判断任务可分配调节因子θ_j所对应的θ_index(j)大于α否，若θ_indx(j)＜α，则各调度器i不向网格计算节点index(j)分配任务；若θ_index(j)＞α，则各调度器i向网格计算节点index(j)分配任务；步骤(4.9)，从有可能从各调度器i中分配到任务的网格计算节点j中删去分片任务平均到达速率φ_index(j)＝0的节点；步骤(4.10)，在步骤(4.9)中所余下的网格计算节点按下式计算分片任务平均到达速率φ_index(j)，${\phi }_{index\left(j\right)}=\frac{1}{2b_{index\left(j\right)}}+\frac{{\phi }_{index\left(j\right)}^{\max }}{2}-\frac{\sqrt{\left(1-{\phi }_{index\left(j\right)}^{\max }{b}_{index\left(j\right)}\right)\left(\left(1-{\phi }_{index\left(j\right)}^{\max }{b}_{index\left(j\right)}\right)+\frac{4b_{index\left(j\right)}}{\alpha }\right)}}{2b_{index\left(j\right)}}$从所得到的φ_index(j)中，删去φ_index(j)＜0的网格计算节点；步骤(4.11)，对步骤(4.10)取得的结果，按步骤(4.3)所述的方法把所述目标函数值formerD与按步骤(3)所述方法得到的新的目标函数值latterD进行比较，ε＝|latterD‑formerD|，若ε≤10^‑6，则进行步骤(4.4)，由各调度器向步骤(4.10)中余下的网格计算节点分配分片任务；若ε＞10^‑6，则重复执行步骤(4.5)——步骤(4.11)，直到全部分片任务分配完毕，结束；步骤(4.12)，进入下一个新的稳定运行周期。