基于响应时间最优化的云计算任务调度方法

摘要

本发明涉及基于响应时间最优化的云计算任务调度方法，包括：构造一个基于响应时间最优化的云计算系统，计算任务分片的传输时间，计算任务分片在计算节点上的平均处理时间，计算任务分片的总处理时间，计算任务响应时间，构造云计算任务调度问题的目标函数，计算调度器的任务分片方案。本发明从任务分片的并行处理出发，以任务分片执行最长的时间作为任务的响应时间，各调度器均以其任务响应时间最小为目标建模，得到新的任务调度方法。本发明更能反映任务并行处理的特性。实验表明：无论是调度器的响应时间值还是目标函数值，本发明均优于博弈算法和均衡调度算法，当系统规模增加和负载加大时，本发明较其它两种算法也均有明显的优势。

主权项

1.基于响应时间最优化的云计算任务调度方法，其特征在于包括以下步骤：步骤1，构造一个基于响应时间最优化的云计算系统；所述基于响应时间最优化的云计算系统由用户、面向各用户的各调度器i以及面向各调度器i的计算节点j以及调度方案计算器组成，其中i＝1,2,...,n，n为所述系统中调度器的数量，j＝1,2,...,m，m为系统中所有计算节点的数目；在忽略调度器内部处理代价前提下，假设任务分片的执行代价和任务分片在网络上的传输代价是任务执行代价的关键；所述调度器在进行任务分片时的条件如下：各个调度器从各用户接受任务，各个调度器发出任务的平均速率λ_i的加和应该小于所述系统所有计算节点对任务的平均执行速率u_j的加和，速率的单位是单位时间内的任务数，即：$\underset{i=1}{\overset{n}{\Sigma }}{\lambda }_i<\underset{j=1}{\overset{m}{\Sigma }}{u}_j---\left(1\right)$各个调度器发到第j个计算节点上任务分片的速率的加和应该小于第j个计算节点对任务分片的平均执行速率u_j，称为计算能力，即：$\underset{i=1}{\overset{n}{\Sigma }}{\lambda }_i{a}_{\mathrm{ij}}<u_j---\left(2\right)$步骤2，计算任务分片a_ij的传输时间L_ij：$L_{\mathrm{ij}}=e_{\mathrm{ij}}+\frac{b\times a_{\mathrm{ij}}}{c_{\mathrm{ij}}}---\left(3\right)$其中，L_ij是调度器i的任务分片到计算节点j的传输时间，j＝1,2,...,m，b为所有任务的平均数据长度，单位：位，e_ij为调度器i到计算节点j之间的线路传输延迟，c_ij为调度器i到计算节点j之间线路的传输速率；根据计算节点的数量，调度器i将用户的请求分解为m个任务分片，a_ij为第i个调度器的任务分配到第j个计算节点的比例，满足以下的约束：a_ij≥0，且$\underset{j=1}{\overset{m}{\Sigma }}{a}_{\mathrm{ij}}=1---\left(4\right)$步骤3，计算任务分片a_ij在计算节点j上的平均处理时间F_ij：$F_{\mathrm{ij}}=(\frac{1}{{\mu }_j}+\frac{\underset{k=1}{\overset{n}{\Sigma }}{\lambda }_k{a}_{\mathrm{kj}}}{{\mu }_j({\mu }_j-\underset{k=1}{\overset{n}{\Sigma }}{\lambda }_k{a}_{\mathrm{kj}})})\times a_{\mathrm{ij}}---\left(5\right)$其中，计算节点被认为是一个M/G/1排队系统，服务时间服从负指数分布；步骤4，计算任务分片a_ij的总处理时间；任务分片a_ij的总处理时间等于线路传输时间与计算节点j上的处理时间的和，即：$F_{\mathrm{ij}}+L_{\mathrm{ij}}=(\frac{1}{{\mu }_j}+\frac{\underset{k=1}{\overset{n}{\Sigma }}{\lambda }_k{a}_{\mathrm{kj}}}{{\mu }_j({\mu }_j-\underset{k=1}{\overset{n}{\Sigma }}{\lambda }_k{a}_{\mathrm{kj}})})\times a_{\mathrm{ij}}+e_{\mathrm{ij}}+\frac{b\times a_{\mathrm{ij}}}{c_{\mathrm{ij}}}---\left(6\right)$其中，i＝1,2,...,n,j＝1,2,...,m；步骤5，计算任务响应时间；各个任务分片被调度到计算节点上以后，任务分片被计算节点独立执行，各个任务分片之间是并行执行的关系，任务的响应时间FL_i(a_i)为：${\mathrm{FL}}_i\left(a_i\right)=\underset{j=1}{\overset{m}{\mathrm{Max}}}(F_{\mathrm{ij}}+L_{\mathrm{ij}})=\underset{j=1}{\overset{m}{\mathrm{Max}}}((\frac{1}{{\mu }_j}+\frac{\underset{k=1}{\overset{n}{\Sigma }}{\lambda }_k{a}_{\mathrm{kj}}}{{\mu }_j({\mu }_j-\underset{k=1}{\overset{n}{\Sigma }}{\lambda }_k{a}_{\mathrm{kj}})})\times a_{\mathrm{ij}}+e_{\mathrm{ij}}+\frac{b\times a_{\mathrm{ij}}}{c_{\mathrm{ij}}})---\left(7\right)$步骤6，构造云计算任务调度问题的目标函数；每个调度器在对任务进行分解调度时，总是希望其任务的响应时间最小，基于响应时间最优化的云计算任务调度问题的目标函数为：$\min \underset{j=1}{\overset{m}{\mathrm{Max}}}(F_{\mathrm{ij}}+L_{\mathrm{ij}})=\min \underset{j=1}{\overset{m}{\mathrm{Max}}}((\frac{1}{{\mu }_j}+\frac{\underset{k=1}{\overset{n}{\Sigma }}{\lambda }_k{a}_{\mathrm{kj}}}{{\mu }_j({\mu }_j-\underset{k=1}{\overset{n}{\Sigma }}{\lambda }_k{a}_{\mathrm{kj}})})\times a_{\mathrm{ij}}+e_{\mathrm{ij}}+\frac{b\times a_{\mathrm{ij}}}{c_{\mathrm{ij}}})---\left(8\right)$步骤7，调度方案计算器计算调度器的任务分片方案；定义u_ji为计算节点j为调度器i提供的计算能力，代入（8）式得：$\min \underset{j=1}{\overset{m}{\mathrm{Max}}}(F_{\mathrm{ij}}+L_{\mathrm{ij}})\text{=min}\underset{j=1}{\overset{m}{\mathrm{Max}}}((1+\frac{u_j-{\mu }_{\mathrm{ji}}+{\lambda }_i{a}_{\mathrm{ij}}}{{\mu }_{\mathrm{ji}}-{\lambda }_i{a}_{\mathrm{ij}}})\times \frac{a_{\mathrm{ij}}}{{\mu }_j}+e_{\mathrm{ij}}+\frac{b\times a_{\mathrm{ij}}}{c_{\mathrm{ij}}}---\left(9\right)$该优化问题通过一种改进的极大熵函数法进行求解，用该极大熵函数来逼近优化函数FL_i(a_i)，表达式如下：$F_p(x,u)=\frac{1}{p}\ln \left|\underset{j=1}{\overset{m}{\Sigma }}{u}_j\exp \right\{p((1+\frac{u_j-{\mu }_{\mathrm{ji}}+{\lambda }_i{a}_{\mathrm{ij}}}{{\mu }_{\mathrm{ji}}-{\lambda }_i{a}_{\mathrm{ij}}})\times a_{\mathrm{ij}}/{\mu }_j+e_{\mathrm{ij}}+\frac{b\times a_{\mathrm{ij}}}{c_{\mathrm{ij}}})\left\}\right|---\left(10\right)$通过调节p和u，使F_p(x,u)的极小点能更快地收敛于式（9）的解。