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

3988 Journal of Software 软件学报 Vol.31, No.12, December 2020

2.3 细粒度资源调度算法

本文将一些资源相关的变量表示为元组形式,以精简算法的表达.等式(9)所示的元组 R 代表一组有序数
1
值,其中,R 为第 1 个数值,依此类推.

n
R =〈 R 1 ,...,R 〉 (9)

n
n
假设有元组 R =〈 R a 1 ,...,R 〉 和 R =〈 R b 1 ,...,R 〉 ,则两元组相加、相乘分别按公式(10)和公式(11)计算,元组与
a
b
b
a
常数 c 相乘按公式(12)计算:

n
1
n
R + R =〈 R + R 1 b ,...,R + R 〉 (10)
a
a
b
b
a

1
n
n
R × R =〈 R × R 1 ,...,R × R 〉 (11)
a b a b a b
c R× a =〈 cR× 1 a ,...,cR× n a 〉 (12)

两元组间的小于关系依据公式(13)判定,即 R 中有任意元素小于 R 中相应位置上的元素,则 R < R 关系
a
b
a
b
为真:

()(0i∃ < i < n i∧ ∈ Z ∧ R < i a R → b i R < a R b ) (13)
服务器上出现空闲计算资源时,细粒度资源调度算法开始筛选资源申请进行调度,见算法 1.
算法 1. Fine-grain Scheduling.
Input:T s :待调度任务集合;
P a :服务器调度策略;

I :服务器可用资源元组;

N :服务器资源总量元组;

1. if I < Th N× or isUnschedulable(P a ) then
2. return; //不可分配,直接返回
3. end if
4. sort(T s ,P f ); //按照公平性策略排序待调度集合
5. for t in T s do
6. check data locality of task t;
7. match←true;
8. if unpredictable(t) then //任务 t 为服务或暂无足够推测信息
9. match←allocRequestQuantity(⋅);
10. else if P a ==FineGrained then
11. match←fineGrainedMatching(⋅); //使用算法 2 所示的细粒度匹配算法
12. else

13. If A < M then
x
x
14. match←false;
15. end if
16. end if
17. if match and checkQoS(⋅) then
18. allocate(t); //分配计算资源给任务 t
19. if the resource is used up then
20. break;
21. end if
22. end if
23. end for