第2期 吴俊伟，等：负载敏感的云任务三支聚类评分调度研究 ·317· 据对象属性对兼具多标签对象作出进一步的划 以利等根据作业长短及重要性聚类任务，构建 分，其中，三支决策理论源于Yao对概率粗糙集 LPM模型，追求最大化的任务完成数，文献[9]采 和决策粗糙集3个域的合理解释1).是一种更 用层级聚类对云任务进行预处理，以最小化任务 为一般，有效的决策方法。本文将其引入云计 完成时间为目标函数调度任务，兼顾资源负载与 算，为任务调度问题提供新的解决方案。 系统吞吐量，在满足服务质量的同时，缩短任务 完成时间。高正九等提出了一种基于任务分类 1相关工作 的延迟调度算法，根据任务长度聚类，并依据该 作为一种有效的问题解决手段，三支决策的 类别调整任务等待时间阈值。相比于DS、FIFO 基本思想是通过一对阈值（α，B)将一个全集U划分 算法，该算法有效缩短了任务响应时间。 成3个独立的部分，然后针对各个区域设置相应 三支决策理论体系的引入，将对任务调度提 的策略。其特征是使用三支方法进行问题解决和 供新思路。本文提出的三支聚类评分(three-way 信息处理。三支决策基于启发式方法，将复杂问 clustering weight,.TWCW)算法，对任务进行三支 聚类划分，追求最大化资源使用，根据聚类结果 题利用分治策略转化为简单问题，其定义为 中核心态与模糊态任务偏好设置调度策略。 ca9:T:U→{S1,S2,S3} (1) 式中：基于条件集C,三支决策通过映射x将实体 2TWCW算法 集U分成3个两两互不相交的S1、S2、S,然后根 据3个区域的特点，有针对性的设计策略和动作， 2.1任务模型 以期达到某种收益的最大化。关于三支决策的理 在2011公布的Google Cluster Trace中，作业 论，模型与应用研究已经取得了较大进展，如垃 由一个或多个任务构成，与任务相关的属性有优 圾邮件过滤研究，、代价敏感的三支决策模型研 先级、资源请求(resource request)与限制条件等。 究、三支决策和博弈论1%、多粒度三支决策n 从任务优先级的角度观察，Google设置了任务的 序列三支决策8劉、动态三支决策例、三支决策与 12个优先级，并将其依次划分为高优先级(9-11)、 逻辑20等。 中优先级(2-8)与低优先级(0-1)三类。优先级越 作为三支决策在聚类算法方面的有效应用， 高，意味着成功调度的几率更大，拥有更高的服 三支聚类2122拓展了对象与集合的隶属关系。给 务质量。且各优先级作业，其运行时长，资源使 用特征存在异构性。在资源请求的维度上，任务 定对象集合U={1,x2,…,xn,n表示对象数。以二 请求的资源主要有CPU与内存空间，通过对 支聚类的思想判定，对象x,要么属于集合c,要 CPU与内存在请求率上的回归分析得出，两者存 么不属于集合c5,其聚类的结果为CS={cS1,cs2,…c5b 在关联，但关联性较弱(R≈0.14)。在任务的限制 k为类别数。而以三支的角度观察，对象x:与集合 条件中，通常是由用户为作业指定主机性能或是 cs,的所属关系有：x属于cS,x可能属于cs,x不属 其他关联性任务，限制条件数量与任务的延迟调 于cs,因此集合cs,被划分为互不相交的L域、M域 度并不存在明显关联关系，例如，对于只有一个 和R域，其中L域表示该类簇的核心对象集合， 限制条件的任务集合，与同时拥有6个限制条件 M域为边缘对象集合。其聚类结果为CS={(L(cs), 的任务集合，其平均调度延迟差值较小。 M(cs1),(L(cs2),M(cs2),·,(L(cs),M(cs)川。三支聚 在trace数据中，作业可分为面向用户的交互 类算法根据簇间离散度与簇内聚合度，对类中对 式作业与批处理作业，它们对资源的请求存在多 象之间的紧密程度作进一步划分。 样化特性，且主要体现为对计算、内存与带宽资 传统的二支聚类算法在云计算中被广泛应 源的请求。因此本文选择在资源请求的维度为任 用。文献[5]使用k-means算法将任务聚类为计 务建模，以(id,mips,mem,bw)元组的形式描述任务 算、存储与网络类型，引入权重因子调整属性间 的资源请求，其中，id表示任务标识，mips表示任 优先级，根据任务类型调度任务。刘家志6将 务请求的计算资源，执行任务指令。mem表示任 FCM算法引入到任务调度中，根据CPU、内存 务请求的内存资源，用于构建程序数据结构， IO与带宽等属性为任务建模并聚类，根据类簇特 bw表示请求的带宽资源，用于访问任务链接的外 征为任务设置调度函数。文献[7]根据集群资源 部资源。 的多维属性定义资源可见度，通过静态阈值划分 2.2调度模型 可见度等级，在PSO调度中以该等级与任务执行 调度器是集群的核心，负责任务的调度与资 时间作为适应性函数，提高集群负载均衡度。张 源的合并、迁移，其调度方式与效率将极大影响据对象属性对兼具多标签对象作出进一步的划 分，其中，三支决策理论源于 Yao 对概率粗糙集 和决策粗糙集 3 个域的合理解释[11-13] ，是一种更 为一般，有效的决策方法。本文将其引入云计 算，为任务调度问题提供新的解决方案。 1 相关工作 (α, β) U 作为一种有效的问题解决手段，三支决策的 基本思想是通过一对阈值 将一个全集 划分 成 3 个独立的部分，然后针对各个区域设置相应 的策略。其特征是使用三支方法进行问题解决和 信息处理。三支决策基于启发式方法，将复杂问 题利用分治策略转化为简单问题，其定义为 c(α,β) : τ : U → {S 1,S 2,S 3} (1) C τ U S 1、S 2、S 3 式中：基于条件集 ，三支决策通过映射 将实体 集 分成 3 个两两互不相交的 ,然后根 据 3 个区域的特点，有针对性的设计策略和动作， 以期达到某种收益的最大化。关于三支决策的理 论，模型与应用研究已经取得了较大进展，如垃 圾邮件过滤研究[14] 、代价敏感的三支决策模型研 究 [15] 、三支决策和博弈论[16] 、多粒度三支决策[17] 、 序列三支决策[18] 、动态三支决策[19] 、三支决策与 逻辑[20]等。 U = {x1, x2,··· , xn} n xi csi csi CS ={cs1, cs2,··· csk} k xi csi xi csi xi csi xi csi csi L M R L M CS = {(L(cs1), M(cs1)),(L(cs2), M(cs2)),··· ,(L(csk), M(csk))} 作为三支决策在聚类算法方面的有效应用， 三支聚类[21-22]拓展了对象与集合的隶属关系。给 定对象集合 ， 表示对象数。以二 支聚类的思想判定，对象 ，要么属于集合 ，要 么不属于集合 ，其聚类的结果为 ， 为类别数。而以三支的角度观察，对象 与集合 的所属关系有： 属于 ， 可能属于 ， 不属 于 ，因此集合 被划分为互不相交的 域、 域 和 域，其中 域表示该类簇的核心对象集合， 域为边缘对象集合。其聚类结果为 。三支聚 类算法根据簇间离散度与簇内聚合度，对类中对 象之间的紧密程度作进一步划分。 传统的二支聚类算法在云计算中被广泛应 用。文献[5]使用 k-means 算法将任务聚类为计 算、存储与网络类型，引入权重因子调整属性间 优先级，根据任务类型调度任务。刘家志[ 6 ]将 FCM 算法引入到任务调度中，根据 CPU、内存、 IO 与带宽等属性为任务建模并聚类，根据类簇特 征为任务设置调度函数。文献[7]根据集群资源 的多维属性定义资源可见度，通过静态阈值划分 可见度等级，在 PSO 调度中以该等级与任务执行 时间作为适应性函数，提高集群负载均衡度。张 以利等[8]根据作业长短及重要性聚类任务，构建 LPM 模型，追求最大化的任务完成数，文献[9]采 用层级聚类对云任务进行预处理，以最小化任务 完成时间为目标函数调度任务，兼顾资源负载与 系统吞吐量，在满足服务质量的同时，缩短任务 完成时间。高正九等[10]提出了一种基于任务分类 的延迟调度算法，根据任务长度聚类，并依据该 类别调整任务等待时间阈值。相比于 DS、FIFO 算法，该算法有效缩短了任务响应时间。 三支决策理论体系的引入，将对任务调度提 供新思路。本文提出的三支聚类评分 (three-way clustering weight，TWCW) 算法，对任务进行三支 聚类划分，追求最大化资源使用，根据聚类结果 中核心态与模糊态任务偏好设置调度策略。 2 TWCW 算法 2.1 任务模型 R ≈ 0.14 在 2011 公布的 Google Cluster Trace 中，作业 由一个或多个任务构成，与任务相关的属性有优 先级、资源请求 (resource request) 与限制条件等[3]。 从任务优先级的角度观察，Google 设置了任务的 12 个优先级，并将其依次划分为高优先级 (9-11)、 中优先级 (2-8) 与低优先级 (0-1) 三类。优先级越 高，意味着成功调度的几率更大，拥有更高的服 务质量。且各优先级作业，其运行时长，资源使 用特征存在异构性。在资源请求的维度上，任务 请求的资源主要有 CPU 与内存空间，通过对 CPU 与内存在请求率上的回归分析得出，两者存 在关联，但关联性较弱 ( )。在任务的限制 条件中，通常是由用户为作业指定主机性能或是 其他关联性任务，限制条件数量与任务的延迟调 度并不存在明显关联关系，例如，对于只有一个 限制条件的任务集合，与同时拥有 6 个限制条件 的任务集合，其平均调度延迟差值较小。 (id,mips,mem,bw) id mips mem bw 在 trace 数据中，作业可分为面向用户的交互 式作业与批处理作业，它们对资源的请求存在多 样化特性，且主要体现为对计算、内存与带宽资 源的请求。因此本文选择在资源请求的维度为任 务建模，以 元组的形式描述任务 的资源请求，其中， 表示任务标识， 表示任 务请求的计算资源，执行任务指令。 表示任 务请求的内存资源，用于构建程序数据结构， 表示请求的带宽资源，用于访问任务链接的外 部资源。 2.2 调度模型 调度器是集群的核心，负责任务的调度与资 源的合并、迁移，其调度方式与效率将极大影响 第 2 期 吴俊伟，等：负载敏感的云任务三支聚类评分调度研究 ·317·