Page 323 - 《软件学报》2020年第12期

周墨颂 等:一种云环境中的动态细粒度资源调度方法 3989

调度中,算法首先检查服务器空闲资源和该服务器调度策略,如果不可调度,则结束调度(第 1 行~第 3 行).
服务器空闲资源元组内各项资源值 r 按照公式(14)计算:
n
r = (r × ∑ i i ) t T (14)
i= 1
其中,r i 为第 i 次采样的资源量,t i 为第 i 次采样的持续时间,T 为采样计算的总时间.
如果满足调度条件,则算法按照公平性策略 P f 排序待调度集合 T s ,以保证资源分配公平性(第 4 行).之后,算
法遍历待调度集合 T s ,检查数据本地性,根据服务器资源调度策略和资源需求推测情况,分别按照不同匹配策略
进行调度.如果推测信息不足或需求不可推测,则算法按照资源申请量进行资源匹配(第 8 行、第 9 行);如果服务
器调度策略为细粒度,则使用细粒度资源匹配算法匹配资源需求和可用资源(第 11 行、第 12 行),具体匹配算法
如算法 2 所示;如果服务器不支持细粒度匹配,则按照粗粒度策略进行资源匹配(第 12 行~第 16 行).在粗粒度匹

配中,资源需求元组 M 中包含所需 CPU、内存资源的最大值,而可用资源元组 A 包含服务器 CPU、内存资源
x
x

在[0,T]区间(以当前时刻为 0 点,T 为任务持续时间)内的最小可用量.如果 A < M 比较关系成立,即有资源需求
x x
未得到满足,则匹配失败.如果资源匹配成功,算法会调用 checkQoS(⋅)检查该分配决策是否影响服务器上运行中
任务的服务质量(第 19 行).如果分配决策通过所有检查,则算法分配资源,并检查是否剩余足够资源进入下一轮
调度(第 20 行~第 23 行).
目前,细粒度资源调度算法中,服务质量检查默认检查任务截止时间约束,该检查只在服务器存在资源压缩
时进行.截止时间检查时,假设本轮资源分配已经生效,并在此基础上计算分析服务器上所有运行中任务是否能
在截止时间内完成,以保证服务质量.在资源压缩情况下,任务的理论持续时间 D t 可以按公式(15)计算:
n
D = t (D i /(1 r− ∑ ci )) (15)
i= 1
其中,D i 为不压缩资源需求时任务第 i 段的持续时间,r ci 为任务第 i 段在运行中各种可压缩资源压缩率的最大值.
细粒度资源匹配算法如算法 2 所示,算法以执行阶段为单位匹配资源需求与可用资源,并在匹配中应用资
源可压缩特性.算法遍历任务的所有执行阶段进行匹配,如果任务所有阶段的各种资源需求均得到满足,则匹配

成功(第 4 行~第 20 行).细粒度匹配算法在匹配中区分计算可用资源中的可压缩资源 n 和不可压缩资源 n :对
c
n
于不可压缩资源,算法直接比较可用资源元组与需求元组;而对于可压缩资源,算法将可用资源元组加上总资源

量元组 N 与该阶段允许的最大压缩率元组 r 的乘积之后,再与可压缩资源需求元组 s 进行比较.服务器某个阶
c
c
段允许的某种资源最大压缩率,依据该服务器该阶段已分配任务和当前匹配任务相关信息,通过等式(7)分析得
到,其值还受到服务器调度策略的影响.
算法 2. Fine-grain Matching.
Input:n s :服务器可用资源阶段集合;
t s :推测得出的任务 t 执行阶段集合;

N :服务器资源总量元组;
Output:匹配结果.
1. n←the first stage in n s ;

2. n ←the tuple of compressible resource of the stage n;
c

3. n ←the tuple of non-compressible resource of the stage n;
n
4. for s in t s do

5. s ←the tuple of compressible resource of the stage s;
c

6. s ←the tuple of non-compressible resource of the stage s;
n
7. while n.startTime<s.endTime do

8. if n +× N < s or n < s then
r
c
c
c
n
n
9. return false; //匹配失败