一种面向云计算环境下的动态多资源公平分配方法

摘要

本发明公开了一种面向云计算环境下的动态多资源公平分配方法，本发明方法基于用户资源需求和用户共享资源量，通过构建线性规划模型保证资源分配的公平性，并应用快速的多项式时间复杂度算法，即二分法寻找一个用户τ对应的v_τ，求解最优分配方案来改进求解最优分配方案的算法运行效率问题；本发明能够准确而真实地反映云计算共享平台中资源分配的实际情况，解决了动态情形下多用户多资源分配的公平性和效率问题，改进了现有资源分配算法运行时间过长的问题。

主权项

一种面向云计算环境下的动态多资源公平分配方法，其特征在于包括如下步骤：(1)基于动态情形下用户资源需求和共享资源量，构建动态多资源公平分配线性优化模型，该线性规划模型为：$\left\{\begin{array}{c}Maximize{M}^k\\ x_i^k\ge M^k·w_i,\forall i\le k\\ x_i^k\ge x_i^{k-1},\forall i\le k-1\\ \underset{i=1}{\overset{k}{\Sigma }}{x}_i^k·d_{ij}\le \underset{i=1}{\overset{k}{\Sigma }}{w}_i,\forall j\end{array}\right.,$该线性规划模型中k为系统中用户数，表示用户i分配得到的优势资源份额数，w_i表示用户i对资源池中每种资源的共享资源量，d_ij表示用户i任务对资源j的需求量；该线性规划模型确定当系统中存在k个用户时，最大化M^k值，从而确定每个用户分配得到的优势资源份额数(2)基于上述线性规划模型，通过下述步骤求解最优分配方案步骤1：当系统中有k个用户时，对k‑1个值进行非递增排序(i＜k‑1)，即v₁≥…≥v_k‑1，并输入用户i对各个资源j需求向量d_i＝(d_i1,…,d_ij,…,d_im)；步骤2：计算用户i在每种资源上需求d_ij与第一个优势资源份额数乘积所得总资源分配量，即步骤3：判断总资源分配量是否超过系统中用户共享资源量，即对每种资源j，如果$\underset{i=1}{\overset{k}{\Sigma }}{v}_1·d_{ij}\le \underset{i=1}{\overset{k}{\Sigma }}{w}_i$成立，转到步骤6；步骤4：如果不成立，在排序后的优势资源份额数区间，即对任意i,i∈U，在区间[v₁,∞),[v₂,v₁],...,(0,v_k‑1]，利用二分法查找v_τ所在的区间[LB,UB]；步骤5：判断UB‑LB＞1，如果成立，跳转到步骤4，否则结束循环；步骤6：根据下述公式确定M^k取值，步骤7：通过计算每个用户i分配到的优势资源份额数步骤8：计算输出用户i在资源j上的分配方案