一种Kubernetes环境下面向复杂任务的组合优先级调度方法

摘要

本发明的Kubernetes环境下面向复杂任务的组合优先级调度方法具体通过以下步骤来实现：a).计算每组任务的实际并行度；b).获取任务关键程度；c).获取用户优先级；d).获取用户的动态优先级；e).计算任务紧急程度；f).并行度和紧急程度的归一化处理；g).求优先级数值；h).pod排序和调度。本发明的组合优先级调度方法，由于在设置优先级时考虑到了任务并行性，可以避免其他任务提前占用节点资源导致并行任务无法获得资源而造成的任务执行失败问题。其次，在设置优先级时考虑到了任务紧急程度，可以保证紧急任务在节点资源不足时对非紧急任务所占用的资源进行抢占，从而成功执行紧急任务。

权利要求

1.一种Kubernetes环境下面向复杂任务的组合优先级调度方法，设需要通过Kubernetes资源管理平台进行调度的任务分别为task1、task2、…、taskn，共计n个任务；这n个任务又分为q组，1≤q≤n，设第i组包含hi个任务，i≤q，hi≤n，即第i组任务的并行度为hi，第i组内hi个任务分别记为 其特征在于，Kubernetes环境下面向复杂任务的组合优先级调度方法具体通过以下步骤来实现：a).计算每组任务的实际并行度；设硬件资源所包含的工作节点的数量为m个，每个工作节点上用于任务计算的CPU核心数为c，则硬件资源所支持的最大任务并发量为m×c；对于每组的任务并行度hi和硬件资源支持的最大任务并发量m×c应当最小值优先，因此，第i组任务的实际并行度Pi通过公式(1)进行求取：Pi＝min(hi,m×c)  (1)直至所有任务组的实际并行度求取完毕；

b).获取任务关键程度；对所有任务task1、task2、…、taskn中的关键任务分配高关键系数H，其余任务分配低关键系数W，H＞W；对于第i组内的hi个任务利用选择函数(2)求取第i组内第j个任务taskij的任务关键程度kij：kij＝choice(H,W)  (2)* *

其中，i≤q，j≤hi，H∈N、W∈N；

c).获取用户优先级；为所有任务分配用户优先级U，设第i组内的hi个任务分别为则其分配的用户优先级依次为 利用公

式(3)获取第i组内第j个任务taskij的用户优先级：Uij＝Prij  (3)

*

其中，i≤q，j≤hi，Prij∈N；

d).获取用户的动态优先级；用户的动态优先级D由任务空闲时间L决定的，空闲时间越小的任务动态优先级越高；对于第i组内的hi个任务 利用公式(4)求取第i组内第j个任务taskij的动态优先级Dij：其中， 为向上取整函数，Lij第i组内第j个任务taskij的空闲时间，Lij的取值范围为：1≤Lij≤50；

e).计算任务紧急程度，根据公式(5)计算第i组内第j个任务taskij的任务紧急程度Jij：Jij＝kij+Uij+Dij  (5)f).并行度和紧急程度的归一化处理；设任务并行度的取值范围为[Pmin,Pmax]，紧急程度的取值范围为[Jmin,Jmax]，第i组任务的实际并行度Pi利用公式(6)进行归一化处理：Pi‑normal＝(Pi‑Pmin)/(Pmax‑Pmin)  (6)第i组内第j个任务taskij的紧急程度Jij利用公式(7)进行归一化处理：Jij‑normal＝(Jij‑Jmin)/(Jmax‑Jmin)  (7)g).求优先级数值；一个任务可映射为单个pod或者多个pod，多个pod即pod组，组内每个pod执行一个子任务，任务的优先级映射到Kubernetes中便是单个pod或pod组的优先级，对优先级数值适量扩大，利用公式(8)求取第i组内第j个任务taskij所对应的优先级Vij：Vij＝k′×(Pi‑normal+Jij‑normal)  (8)其中，k′为扩大倍数，Pi‑normal为归一化处理后的第i组任务的实际并行度，Jij‑normal为归一化处理后的第i组内第j个任务taskij的紧急程度；

h).pod排序和调度；第i组内第j个任务taskij所对应的单个pod或pod组，按照其对应任务的优先级Vij进行排序，优先级大的排在前面、优先级小的排在后面，排在前面的单个pod或pod组优先调度。

2.根据权利要求1所述的Kubernetes环境下面向复杂任务的组合优先级调度方法，其特征在于，步骤h)中，对于pod组来说，pod组内每个pod对应一个子任务，其优先级设定通过以下步骤来实现：

h‑1).首先根据子任务依赖关系建立组内pod间的有向无环图；

h‑2).在有向无环图中，从任一入度为0的顶点开始，沿着有向边随机寻找一个出度为0的顶点，将出度为0的顶点对应的pod放入栈中；执行步骤h‑3)；

h‑3).返回上一级顶点，若上一级顶点除已放入栈中的顶点之外出度为0，则将此顶点对应的pod放入栈；若上一级顶点除已放入栈中的顶点之外出度不为0，则沿不包含已放入栈中的顶点的有向边寻找下一个出度为0的点，并将出度为0的顶点对应的pod放入栈，重复执行该步骤，直至有向无环图所有顶点对应的pod均放入堆栈中；

h‑4).待所有的顶点都进入堆栈中，执行出栈操作，由于栈先进后出的原则，后入栈的pod优先级高于先入栈pod的优先级，得到的pod组内各pod的优先级序列。

3.根据权利要求1或2所述的Kubernetes环境下面向复杂任务的组合优先级调度方法，其特征在于，步骤h)中，存在两个任务的优先级数值相等，则按照如下规则进行排序：h‑1‑1).按关键系数进行排序，对于优先级数值相等的两个任务来说，首先比较其关键系数，如果关键系数不同，则将关键系数高的任务对应的单个pod或pod组排在前、将关键系数低的任务对应的单个pod或pod组排在后；如果关键系数相等，则执行步骤h‑1‑2)；

h‑1‑2).按用户优先级进行排序，对于优先级数值、关键系数均相等的两个任务来说，则比较其用户优先级，如果用户优先级不同，则将用户优先级高的任务对应的单个pod或pod组排在前、将用户优先级低的任务对应的单个pod或pod组排在后；如果用户优先级相等，则执行步骤h‑1‑3)；

h‑1‑3).按动态优先级进行排序，对于优先级数值、关键系数和用户优先级均相等的两个任务来说，则比较其动态优先级，如果动态优先级不同，则将动态优先级高的任务对应的单个pod或pod组排在前、将动态优先级的任务对应的单个pod或pod组排在后；如果动态优先级相等，则两任务一前一后随机排序。

4.根据权利要求1或2所述的Kubernetes环境下面向复杂任务的组合优先级调度方法，其特征在于：步骤g)中所述的扩大倍数k′为1000000。

说明书

一种Kubernetes环境下面向复杂任务的组合优先级调度方法

技术领域

[0001] 本发明涉及一种组合优先级调度方法，更具体的说，尤其涉及一种Kubernetes环境下面向复杂任务的组合优先级调度方法。

背景技术

[0002] 人工智能作为新时期最具发展潜力的技术已经在众多领域得以运用和发展，当前所有的人工智能计算并非都在严格意义上的云平台进行，但云计算仍是人工智能的基础计
算平台，也是人工智能的能力集成到千万应用中的便捷途径。云计算是与信息技术、软件、
互联网相关的一种服务，通过互联网来提供动态且易扩展的资源，通常这些资源都是虚拟
化的资源，云即指这种计算资源共享池。而人工智能不仅丰富了云计算服务的特性，更让云
计算服务更加符合业务场景的需求，并进一步解放人力。其中机器学习作为一种实现人工
智能的方法，是人工智能技术的重点。针对大规模数据和计算任务，机器学习通常需要成千
上万次的迭代计算，因此对云计算资源的需求量非常大，训练与优化模型的时间成本也比
较高。为了在有限资源内快速完成机器学习任务，需要合理有效地调度分配云计算资源。

[0003] Kubernetes是在云计算领域十分热门的一个开源容器集群管理平台，拥有非常完备的集群管理能力。pod是Kubernetes中能够创建和部署的最小单元，包含了一个或多个容
器。任务在Kubernetes中会被映射成为一个或多个pod，由于任务有先后顺序需要设置优先
级所以pod同样需要设置优先级。Kubernetes将pod分成了三个QoS(服务质量)等级：
Guaranteed：优先级最高；Best Effort：优先级最低；Burstable：优先级介于前两者之间。
除了QoS等级，Kubernetes还允许用户自定义pod的优先级。需要在Kubernetes里提交一个
优先级的定义，在定义里给属性value赋值。定义完优先级之后，pod即可以声明使用它。

[0004] Kubernetes默认的优先级定义中，value需要用户进行赋值，当面对较为复杂的任务时，需要考虑多种影响因子，如何赋予其适当的优先级成为关键。

发明内容

[0005] 本发明为了克服上述技术问题的缺点，提供了一种Kubernetes环境下面向复杂任务的组合优先级调度方法。

[0006] 本发明的Kubernetes环境下面向复杂任务的组合优先级调度方法，设需要通过Kubernetes资源管理平台进行调度的任务分别为task1、task2、…、taskn，共计n个任务；这
n个任务又分为q组，1≤q≤n，设第i组包含hi个任务，i≤q，hi≤n，即第i组任务的并行度为
hi，第i组内hi个任务分别记为taski1、taski2、…、 其特征在于，Kubernetes环境下面
向复杂任务的组合优先级调度方法具体通过以下步骤来实现：

[0007] a).计算每组任务的实际并行度；设硬件资源所包含的工作节点的数量为m个，每个工作节点上用于任务计算的CPU核心数为c，则硬件资源所支持m×c的最大任务并发量为
m×c；对于每组的任务并行度hi和硬件资源支持的最大任务并发量应当最小值优先，因此，
第i组任务的实际并行度Pi通过公式(1)进行求取：

[0008] Pi＝min(hi,m×c)  (1)

[0009] 直至所有任务组的实际并行度求取完毕；

[0010] b).获取任务关键程度；对所有任务task1、task2、…、taskn中的关键任务分配高关键系数H，其余任务分配低关键系数W，H＞W；对于第i组内的hi个任务taski1、taski2、…、
利用选择函数(2)求取第i组内第j个任务taskij的任务关键程度kij：

[0011] kij＝choice(H,W)  (2)

[0012] 其中，i≤q，j≤hi，H∈N*、W∈N*；

[0013] c).获取用户优先级；为所有任务分配用户优先级U，设第i组内的hi个任务分别为taski1、taski2、…、 则其分配的用户优先级依次为Pri1、Pri2、…、 利用公式(3)获
取第i组内第j个任务taskij的用户优先级：

[0014] Uij＝Prij  (3)

[0015] 其中，i≤q，j≤hi，Prij∈N*；

[0016] d).获取用户的动态优先级；用户的动态优先级D由任务空闲时间L决定的，空闲时间越小的任务动态优先级越高；对于第i组内的hi个任务taski1、taski2、…、 利用公式
(4)求取第i组内第j个任务taskij的动态优先级Dij：

[0017]

[0018] 其中， 为向上取整函数，Lij第i组内第j个任务taskij的空闲时间，Lij的取值范围为：1≤Lij≤50；

[0019] e).计算任务紧急程度，根据公式(5)计算第i组内第j个任务taskij的任务紧急程度Jij：

[0020] Jij＝kij+Uij+Dij  (5)

[0021] f).并行度和紧急程度的归一化处理；设任务并行度的取值范围为[Pmin,Pmax]，紧急程度的取值范围为[Jmin,Jmax]，第i组任务的实际并行度Pi利用公式(6)进行归一化处理：

[0022] Pi‑normal＝(Pi‑Pmin)/(Pmax‑Pmin)  (6)

[0023] 第i组内第j个任务taskij的紧急程度Jij利用公式(7)进行归一化处理：

[0024] Jij‑normal＝(Jij‑Jmin)/(Jmax‑Jmin)  (7)

[0025] g).求优先级数值；一个任务可映射为单个pod或者多个pod，多个pod即pod组，组内每个pod执行一个子任务，任务的优先级映射到Kubernetes中便是单个pod或pod组的优
先级，对优先级数值适量扩大，利用公式(8)求取第i组内第j个任务taskij所对应的优先级
Vij：

[0026] Vij＝k′×(Pi‑normal+Jij‑normal)  (8)

[0027] 其中，k′为扩大倍数，Pi‑normal为归一化处理后的第i组任务的实际并行度，Jij‑normal为归一化处理后的第i组内第j个任务taskij的紧急程度；

[0028] h).pod排序和调度；第i组内第j个任务taskij所对应的单个pod或pod组，按照其对应任务的优先级Vij进行排序，优先级大的排在前面、优先级小的排在后面，排在前面的单个
pod或pod组优先调度。

[0029] 本发明的Kubernetes环境下面向复杂任务的组合优先级调度方法，步骤h)中，对于pod组来说，pod组内每个pod对应一个子任务，其优先级设定通过以下步骤来实现：

[0030] h‑1).首先根据子任务依赖关系建立组内pod间的有向无环图；

[0031] h‑2).在有向无环图中，从任一入度为0的顶点开始，沿着有向边随机寻找一个出度为0的顶点，将出度为0的顶点对应的pod放入栈中；执行步骤h‑3)；

[0032] h‑3).返回上一级顶点，若上一级顶点除已放入栈中的顶点之外出度为0，则将此顶点对应的pod放入栈；若上一级顶点除已放入栈中的顶点之外出度不为0，则沿不包含已
放入栈中的顶点的有向边寻找下一个出度为0的点，并将出度为0的顶点对应的pod放入栈，
重复执行该步骤，直至有向无环图所有顶点对应的pod均放入堆栈中；

[0033] h‑4).待所有的顶点都进入堆栈中，执行出栈操作，由于栈先进后出的原则，后入栈的pod优先级高于先入栈pod的优先级，得到的pod组内各pod的优先级序列。

[0034] 本发明的Kubernetes环境下面向复杂任务的组合优先级调度方法，步骤h)中，存在两个任务的优先级数值相等，则按照如下规则进行排序：

[0035] h‑1‑1).按关键系数进行排序，对于优先级数值相等的两个任务来说，首先比较其关键系数，如果关键系数不同，则将关键系数高的任务对应的单个pod或pod组排在前、将关
键系数低的任务对应的单个pod或pod组排在后；如果关键系数相等，则执行步骤h‑1‑2)；

[0036] h‑1‑2).按用户优先级进行排序，对于优先级数值、关键系数均相等的两个任务来说，则比较其用户优先级，如果用户优先级不同，则将用户优先级高的任务对应的单个pod
或pod组排在前、将用户优先级低的任务对应的单个pod或pod组排在后；如果用户优先级相
等，则执行步骤h‑1‑3)；

[0037] h‑1‑3).按动态优先级进行排序，对于优先级数值、关键系数和用户优先级均相等的两个任务来说，则比较其动态优先级，如果动态优先级不同，则将动态优先级高的任务对
应的单个pod或pod组排在前、将动态优先级的任务对应的单个pod或pod组排在后；如果动
态优先级相等，则两任务一前一后随机排序。

[0038] 本发明的Kubernetes环境下面向复杂任务的组合优先级调度方法，步骤g)中所述的扩大倍数k′为1000000。

[0039] 本发明的有益效果是：本发明的Kubernetes环境下面向复杂任务的组合优先级调度方法，当面向例如机器学习等复杂任务时，由于在设置优先级时考虑到了任务并行性，可
以避免其他任务提前占用节点资源导致并行任务无法获得资源而造成的任务执行失败问
题。其次，在设置优先级时考虑到了任务紧急程度，可以保证紧急任务在节点资源不足时对
非紧急任务所占用的资源进行抢占，从而成功执行紧急任务。综合考虑了以上两点的优先
级设置方法，可以在复杂任务调度节点资源时有效提高任务执行成功率。另外在面向机器
学习任务的组调度时，另一层次的优先级设置方法解决了组内pod存在依赖关系的问题。

附图说明

[0040] 图1为本发明中Kubernetes中任务调度映射过程图；

[0041] 图2为本发明中任务整体结构图；

[0042] 图3为本发明中的任务并行图，A组任务包括task1至task3，B组任务包括task4至task8；

[0043] 图4为本发明中的pod组内依赖关系有向无环图。

具体实施方式

[0044] 下面结合附图与实施例对本发明作进一步说明。

[0045] 任务并行度：用于评价某一时刻并行执行的任务数。用户所指定的多个任务能否并发执行，依赖于工作节点的数量及每个工作节点上用于任务计算的CPU核心数。记当前执
行任务的工作节点数为m，每个工作节点上用于任务计算的CPU核心数为c，那么硬件资源支
持的最大任务并发量为m×c，取值范围为正整数。设任务的并行度为h，任务的并行度取决
于串行任务中，每个任务的子任务数，取值范围为正整数。对于任务并行度h和硬件资源支
持的最大任务并发量m×c应当小值优先，该小值为任务的实际并行度P。

[0046] 任务紧急程度：每个任务的任务紧急度为J，该任务紧急程度是一个固定优先级F和动态优先级D的结合,其中固定优先级F是由任务关键程度k和用户优先级U决定；动态优
先级D是由任务空闲时间L决定，空闲时间越小的任务动态优先级越高。给关键任务集分配
高关键系数H，其余任务分配低关键系数W，关键系数的取值范围为正整数，且必须H＞W。给
一批任务中的每个任务分配一个唯一的用户优先级U，U的取值为正整数，一组任务的用户
优先级可以从1开始依次递增分配。

[0047] 如图1所示，给出了本发明中Kubernetes中任务调度映射过程图，pod是Kubernetes中能够创建和部署的最小单元，包含了一个或多个容器，任务在Kubernetes中
会被映射成为一个pod或pod组。

[0048] 如图2所示，给出了本发明中任务整体结构图，其中task1、task2、task3为一组(记为第1组任务)，并行度为3；task4、task5、task6、task7、task8为一组(记为第2组任务)，并
行度为5。如图2，共有3个节点，每个节点核心数为2。

[0049] 利用公式(1)求取第1组任务的实际并行度P1：

[0050] P1＝min(h1，m×c)＝min(3，3×2)＝3

[0051] 同理，利用公式(1)求取第2组任务的实际并行度P2：

[0052] P2＝min(h2,m×c)＝min(5,3×2)＝5

[0053] 如表1所示，第1组并行的3个任务task1、task2、task3，用户优先级分别为1、2、3，设task1、task3为关键任务集配置高关键系数10，task2为非关键任务集配置低关键系数5，
其通过系统获得的空闲时间分别为6、3、2。在第2组并行的5个任务task4、task5、task6、
task7、task8中，用户优先级分别为1、2、3、4、5。设task4、task5为非关键任务集配置低关键
系数5，task6、task7、task8为关键任务集配置高关键系数10，其通过系统获得的空闲时间
分别为4、5、3、2、2。

[0054] 表1

[0055]  用户优先级U 关键系数k 空闲时间L 动态优先级D 优先级V
6
task1 1 H＝10 6 17 0.483333×10
6
task2 2 W＝5 3 34 0.766667×10
6
task3 3 H＝10 2 50 1.0×10
6
task4 1 W＝5 4 25 0.85×10
6
task5 2 W＝5 5 20 0.816667×10
6
task6 3 H＝10 3 34 1.116667×10
6
task7 4 H＝10 2 50 1.4×10
6
task8 5 H＝10 2 50 1.416667×10

[0056] 通过公式(4)可计算第一组中3个任务task1、task2、task3的动态优先级D11、D12、D13分别为17、34、50，可计算出第2组中5个任务task4、task5、task6、task7、task8的动态优
先级D21、D22、D23、D24、D25分别为25、20、34、50、50。

[0057] 然后，根据公式(5)可计算出第1组中3个任务task1、task2、task3的任务紧急程度J11、J12、J13分别为24、41、55，可计算出第2组中5个任务task4、task5、task6、task7、task8的
任务紧急程度J21、J22、J23、J24、J25分别为31、27、47、64、65。

[0058] 对并行度和紧急度进行归一化处理，设并行度的取值范围为Pmax＝9和Pmin＝1，紧急程度的取值范围为Jmin＝10和Jmax＝70，利用公式(6)可求得task1至task3的并行度归一
化值P1‑normal为0.25，task4至task8的并行度归一化值P2‑normal为0.5。

[0059] 利用公式(7)可求得task1至task3的紧急程度归一化值J11‑normal、J12‑normal、J13‑normal分别为0.233333、0.516667、0.750，task4至task8的紧急程度归一化值J21‑normal、
J22‑normal、J23‑normal、J24‑normal、J25‑normal分别为0.350、0.316667、0.616667、0.90、0.916667。

[0060] 利用公式(8)可求得task1至task8的优先级V11、V12、V13、V21、V22、V23、V24、V25分别为6 6 6 6 6 6
0.483333×10、0.766667×10、1.0×10、0.85×10、0.816667×10 、1.116667×10、1.4
6 6
×10 、1.416667×10 ，根据优先级数值的大小对任务的排序为：task8、task7、task6、
task3、task4、task5、task2、task1。

[0061] 至此，8个任务在Kubernetes上映射成为8个pod，8个pod将会按照此序列被依次调度到满足资源需求的工作节点上。

[0062] 在面向复杂任务时例如机器学习任务时，上文中的8个task中每个task会被映射为多个pod，每个pod对应task中的一个子任务，即一个task会映射为一个拥有多个pod的
pod组。设优先级最高的任务task8在执行时需要运行5个pod，即pod 8为pod组，其由5个pod
组成。如图4所示，给出了本发明中的pod组内依赖关系有向无环图。

[0063] 接下来单独考虑pod 8组内5个pod的优先级问题。此时该组内5个pod存在依赖关系，某些pod将会作为另一些pod的前提条件。如图4所示，默认的pod序列为：

[0064] pod1→pod2→pod3→pod4→pod5

[0065] 根据有向图计算它的拓扑序列。首先选取入度为0的顶点1为起点，沿任一有向边寻找出度为0的顶点，例如沿顶点1、2、3、4找到顶点4并放入栈中；返回上一级顶点3，发现顶
点3除了指向4的有向边之外已出度为0，于是将3放入栈中；返回顶点3的上一级顶点2，发现
顶点2出度不为0，由于顶点3已经放入栈中，于是沿有向边到达顶点5，又因顶点4已放入栈
中，所以顶点5出度为0，将顶点5放入栈中；再次返回上一级顶点2，此时顶点2的出度为0，放
入顶点2栈中；返回上一级顶点1，此时顶点1出度为0，将顶点1放入栈中。至此所有顶点已按
4、3、5、2、1的顺序全部放入栈中，根据栈先进后出的原则，出栈的顶点顺序为1、2、5、3、4，为
该有向图对应的拓扑序列。即优先级序列为：

[0066] pod1→pod2→pod5→pod3→pod4

[0067] 因此需按照该顺序为组内pod赋予由高至低的优先级。首先自定义pod优先级为a、b、c、d、e，在podGroup‑status的yaml文件中通过pod.spec.PriorityClassName指定要使用
的优先级名字完成声明使用。

[0068] 该优先级不参与并行度与紧急程度优先级设置的过程，仅适用于完成pod组之间的优先级调度后，pod组内存在依赖关系时的优先级排序。

[0069] 结合具体任务可以看出，由于在设置优先级时考虑到了任务并行度和任务紧急程度，可以使优先级的设定更加细化以及更加规范合理，在面对并行任务和紧急任务有资源
需求时可以有效提高任务执行成功率。另外在面向机器学习任务的组调度时，另一层次的
优先级设置方法解决了组内pod存在依赖关系的问题。