第2期 刘正：基于动态任务调度的STDS算法设计研究 ·327. 降低了调度器调度频率，而且中心调度器与各内核 式中：表示内核P的调度粒度，l表示粒度因子， 可以并行地运行。全局调度队列和局部调度队列结 sP表示内核P的处理速度。对于一个实际的处理 合的方式在整体上是全局队列方式，与集中式调度 器系统，内核速度是确定的已知量，调度粒度1的大 策略配合使用易于实现负载均衡：在底层实现上是 小，可以通过粒度因子1调节，粒度因子与具体的运 局部队列方式，降低了系统对队列共享性要求，克服 行状况有关，它起到将内核的计算速度转换为内核 了集中式调度模式的性能瓶颈问题。 调度任务数量功能。 文中通过重载和轻载阀值确定调度时机，当内 STDS算法通过限制内核任务队列长度实现负 核处于轻载状态时请求任务调度，处于重载时不允 载均衡，为有效发挥调度队列作用，算法引入2个负 许再向内核分配任务，这种策略在保证一定负载均 载因子，分别确定队列的上限和下限，具体定义如式 衡效果的同时提高了内核执行效率。 (3)~(5): l4-max=l,(1+6,) (3) 2任务优先级 l4-min=l(1-82) (4) 将任务分配到最合适的内核上是任务调度的核 61+62=1 (5) 心问题，而任务优先级计算是任务分配的关键，任务 0≤k≤m-1 优先级表明任务被优先调度程度。在多核环境下， 式中：δ，是负载上限因子，lk-max表示内核P的任 各内核的状态不尽相同，STDS算法为评价任务与内 务队列长度上限，δ，是负载下限因子，lmin表示 核的适合程度，首先计算任务相对于一个确定内核 内核P的任务队列长度下限。当|Tls|≤-min 的优先级T,然后取其在所有内核上的最大值作 时，内核P请求调度程序分配任务，而当T|≥ 为任务优先级T,表示为式(1)： l_max时，就不允许向内核P上分配任务，从而保 omax (1) 证内核P的任务队列长度满足：l-min≤|T.|≤ 式中：m为内核数量，T表示任务T,相对于内核P I_max。需要说明的是，在一些极端情况下，比如 的优先级。STDS算法在计算T.时，综合考虑等待 当有多个内核同时请求分配任务，或者暂时没有任 时间、任务间通信开销和内核负载状态因素。等待 务可分配时，调度程序无法及时响应内核任务调度 时间为当前时间与就绪时间的差值，任务间通信开 请求，而内核继续从其任务队列上取任务执行，此时 销是任务T,与其所有依赖任务T通信时间之和，而 会出现|Tl|<lmin的情况，但只要调度粒度设 置合理，这种情况不会频繁出现，所以不影响整体负 内核负载状态用于实现内核负载均衡。 多核处理器的负载均衡要求避免出现一个或多 载均衡。内核P的任务队列长度上限与下限之差 个内核负载较低甚至空闲，而其他内核处于高负载 l-max-l-min=(6,+8,),而式(5)设置约束条 状态的情况，从而充分发挥多核处理器优势。STDS 件8，+62=1，从而使得lk-max-l-min=l,内核 算法使用任务队列长度！TL:〡作为内核负载指标， P在其任务队列长度为lmin时请求分配任务，调 内核的任务队列越长，说明分配的任务越多，所以其 度程序响应请求并为P分配：（调度粒度）个任务， 负载越大。 此时内核P的任务队列长度为其上限值l,-max。 上述阐述了计算任务优先级时的内核队列上下 为实现负载均衡引入调度粒度，内核P的调度 限问题，式(6)~(10)则是对任务优先级计算时的 粒度定义为一次调度过程中为P分配的任务数量， 等待时间、通信开销和内核负载均衡因素的描述。 这里的一次调度过程是指一个内核请求调度，调度 STDS算法在计算任务优先级时，综合考虑等待时 算法为其分配任务的过程，在实际运行中，可能出现 间、通信开销和内核负载均衡因素，式(1)中Tt表 调度算法一次性处理多个内核调度请求，调度的任 示任务T分配到内核P适合程度，其计算公式为： 务数量等于为每个内核分配的任务数量之和。粒度 Tt=(PW:+PCa)·ld (6) 大小要根据系统模型而定，调度粒度过大，不能充分 PW;=B(t-T) (7) 发挥动态调度优势，而粒度过小，会引发频繁调度， 增大调度程序运行时间开销，降低处理器效率。对 PCk=- 0≤s≤m-1 (8) 于异构多核处理器，调度粒度与内核处理速度是正 m·Ct 比关系。STDS算法将调度粒度定义为式(2)： li ms -1 ThI (9) lk=l·sp4,0≤k≤m-1 (2) = lms-lki血降低了调度器调度频率，而且中心调度器与各内核 可以并行地运行。 全局调度队列和局部调度队列结 合的方式在整体上是全局队列方式，与集中式调度 策略配合使用易于实现负载均衡；在底层实现上是 局部队列方式，降低了系统对队列共享性要求，克服 了集中式调度模式的性能瓶颈问题。 文中通过重载和轻载阀值确定调度时机，当内 核处于轻载状态时请求任务调度，处于重载时不允 许再向内核分配任务，这种策略在保证一定负载均 衡效果的同时提高了内核执行效率。 ２ 任务优先级 将任务分配到最合适的内核上是任务调度的核 心问题，而任务优先级计算是任务分配的关键，任务 优先级表明任务被优先调度程度。 在多核环境下， 各内核的状态不尽相同，ＳＴＤＳ 算法为评价任务与内 核的适合程度，首先计算任务相对于一个确定内核 的优先级 Ｔｉｐｋ，然后取其在所有内核上的最大值作 为任务优先级 Ｔｉｐ，表示为式（１）： Ｔｉｐ ＝ ｍａｘ ０≤ｋ≤ｍ－１ Ｔｉｐｋ （１） 式中： ｍ 为内核数量，Ｔｉｐｋ 表示任务 Ｔｉ 相对于内核 Ｐｋ 的优先级。 ＳＴＤＳ 算法在计算 Ｔｉｐｋ 时，综合考虑等待 时间、任务间通信开销和内核负载状态因素。 等待 时间为当前时间与就绪时间的差值，任务间通信开 销是任务Ｔｉ 与其所有依赖任务Ｔｉｄ 通信时间之和，而 内核负载状态用于实现内核负载均衡。 多核处理器的负载均衡要求避免出现一个或多 个内核负载较低甚至空闲，而其他内核处于高负载 状态的情况，从而充分发挥多核处理器优势。 ＳＴＤＳ 算法使用任务队列长度 ｜ ＴＬｋ ｜ 作为内核负载指标， 内核的任务队列越长，说明分配的任务越多，所以其 负载越大。 为实现负载均衡引入调度粒度，内核 Ｐｋ的调度 粒度定义为一次调度过程中为 Ｐｋ分配的任务数量， 这里的一次调度过程是指一个内核请求调度，调度 算法为其分配任务的过程，在实际运行中，可能出现 调度算法一次性处理多个内核调度请求，调度的任 务数量等于为每个内核分配的任务数量之和。 粒度 大小要根据系统模型而定，调度粒度过大，不能充分 发挥动态调度优势，而粒度过小，会引发频繁调度， 增大调度程序运行时间开销，降低处理器效率。 对 于异构多核处理器，调度粒度与内核处理速度是正 比关系。 ＳＴＤＳ 算法将调度粒度定义为式（２）： ｌ ｋ ＝ ｌ·ｓｐｋ，０ ≤ ｋ ≤ ｍ － １ （２） 式中：ｌ ｋ表示内核 Ｐｋ 的调度粒度，ｌ 表示粒度因子， ｓｐｋ表示内核 Ｐｋ的处理速度。 对于一个实际的处理 器系统，内核速度是确定的已知量，调度粒度 ｌ ｋ的大 小，可以通过粒度因子 ｌ 调节，粒度因子与具体的运 行状况有关，它起到将内核的计算速度转换为内核 调度任务数量功能。 ＳＴＤＳ 算法通过限制内核任务队列长度实现负 载均衡，为有效发挥调度队列作用，算法引入 ２ 个负 载因子，分别确定队列的上限和下限，具体定义如式 （３） ～ （５）： ｌ ｋ＿ｍａｘ ＝ ｌ ｋ（１ ＋ δ１ ） （３） ｌ ｋ＿ｍｉｎ ＝ ｌ ｋ（１ － δ２ ） （４） δ１ ＋ δ２ ＝ １ （５） ０ ≤ ｋ ≤ ｍ － １ 式中： δ１ 是负载上限因子， ｌ ｋ＿ｍａｘ 表示内核 Ｐｋ的任 务队列长度上限， δ２ 是负载下限因子， ｌ ｋ＿ｍｉｎ 表示 内核 Ｐｋ 的任务队列长度下限。 当 Ｔｌ ｋ ≤ ｌ ｋ＿ｍｉｎ 时，内核 Ｐｋ 请求调度程序分配任务，而当 Ｔｌ ｋ ≥ ｌ ｋ＿ｍａｘ 时，就不允许向内核 Ｐｋ上分配任务，从而保 证内核 Ｐｋ的任务队列长度满足： ｌ ｋ＿ｍｉｎ ≤ Ｔｌ ｋ ≤ ｌ ｋ＿ｍａｘ 。 需要说明的是，在一些极端情况下，比如 当有多个内核同时请求分配任务，或者暂时没有任 务可分配时，调度程序无法及时响应内核任务调度 请求，而内核继续从其任务队列上取任务执行，此时 会出现 Ｔｌ ｋ ＜ ｌ ｋ＿ｍｉｎ 的情况，但只要调度粒度设 置合理，这种情况不会频繁出现，所以不影响整体负 载均衡。 内核 Ｐｋ的任务队列长度上限与下限之差 ｌ ｋ＿ｍａｘ － ｌ ｋ＿ｍｉｎ ＝ ｌ ｋ（δ１ ＋ δ１ ） ，而式（５）设置约束条 件 δ１ ＋ δ２ ＝ １，从而使得 ｌ ｋ＿ｍａｘ － ｌ ｋ＿ｍｉｎ ＝ ｌ ｋ ，内核 Ｐｋ在其任务队列长度为 ｌ ｋ＿ｍｉｎ 时请求分配任务，调 度程序响应请求并为 Ｐｋ分配 ｌ ｋ （调度粒度）个任务， 此时内核 Ｐｋ的任务队列长度为其上限值 ｌ ｋ＿ｍａｘ 。 上述阐述了计算任务优先级时的内核队列上下 限问题，式（６） ～ （１０）则是对任务优先级计算时的 等待时间、通信开销和内核负载均衡因素的描述。 ＳＴＤＳ 算法在计算任务优先级时，综合考虑等待时 间、通信开销和内核负载均衡因素，式（１）中 Ｔｉｐｋ表 示任务 Ｔｉ分配到内核 Ｐｋ适合程度，其计算公式为： Ｔｉｐｋ ＝ （ＰＷｉ ＋ ＰＣｉｋ）·ｌ ｋ ｊ （６） ＰＷｉ ＝ β ｔ － Ｔｉｔ ( ) （７） ＰＣｉｋ ＝ ０≤∑ｓ≤ｍ－１ Ｃｉｓ ｍ·Ｃｉｋ （８） ｌ ｋ ＝ ｌ ｋ ＿ｍａｘ －｜ Ｔｌ ｋ ｜ ｌ ｋ＿ｍａｘ － ｌ ｋ＿ｍｉｎ （９） 第 ２ 期 刘正：基于动态任务调度的 ＳＴＤＳ 算法设计研究 ·３２７·