第10卷第2期 智能系统学报 Vol.10 No.2 2015年4月 CAAI Transactions on Intelligent Systems Apr.2015 D0:10.3969/j.issn.1673-4785.201503013 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20150413.1505.001.html 基于动态任务调度的STDS算法设计研究 刘正 (哈尔滨工程大学计算机科学与技术学院，黑龙江哈尔滨150001) 摘要：任务调度是计算机多核处理器系统获得高性能的关键，而现有的多核任务调度算法研究，大多侧重于静态 调度下的算法优化和负载均衡，对动态调度及动态负载均衡研究较少。针对动态调度，并结合异构多核的特点，提 出一种基于核负载均衡的动态任务调度算法STDS。算法通过合理设定调度粒度，降低调度频率，从而减少调度消耗 时间：根据异构多核处理器各核处理性能的差异，设置内核负载上下限值，控制内核负载保持在同一水平，以达到负 载均衡效果。算法依据等待时间长短、任务间通信大小和内核负载轻重因素对任务进行实时调度，并可通过实时因 子、负载因子等参数设置3种因素的影响比重，以满足系统的不同需求。仿真实验显示，在内核数目较多的系统中， STDS算法更加高效，在保证任务处理速度的同时有较好负载均衡。 关键词：动态任务调度：负载均衡：调度粒度：等待时间：异构多核系统 中图分类号：TP316.4文献标志码：A文章编号：1673-4785(2015)02-0324-09 中文引用格式：刘正.基于动态任务调度的STDS算法设计研究[J].智能系统学报，2015,10(2)：324-332. 英文引用格式：LIU Zheng.Research on STDS algorithm designing based on dynamic task scheduling[J].CAAI Transactions on In- telligent Systems,2015,10(2):324-332. Research on STDS algorithm designing based on dynamic task scheduling LIU Zheng (College of Computer Science and Technology,Harbin Engineering University,Harbin 150001,China) Abstract:Efficient task scheduling is the key for multi-core systems to achieve high performance.However,most of the existing multi-core researches on task scheduling algorithms focus on algorithm optimization and load balancing under the static scheduling rather than dynamic scheduling and dynamic load balancing.Scalable task duplication based scheduling (STDS)is a new dynamic-balanced algorithm based on core load balancing.STDS was put for- ward specifically for dynamic scheduling and integrating the characteristics of heterogeneous multi-core.It shortens scheduling time by reasonably setting the scheduling granularity and reducing the frequency of scheduling.STDS sets the maximum and minimum ranges of the kernel load according to the different processing performance of each core of the heterogeneous multi-core processor,therefore controlling the core load at the same level and achieving the effect of load balance.The wait time of task and communications between tasks and kemnel load will be consid- ered together to pick up the most appropriate task during scheduling.The importance of each element can be adjus- ted by assigning another value to the real-time factor and load factor enabling it to adapt to various environment.The experimental results verified that the STDS algorithm is more efficient in the system with the most kernels.It also keeps a good load balance while maintaining the speed of task execution processing. Keywords:dynamic task scheduling;load balancing;scheduling granularity;waiting time;heterogeneous multi- core system 动态任务调度可以根据运行的时情况动态 收稿日期：2015-03-09.网络出版日期：2015-04-13. 基金项目：国家自然科学基金资助项目(61003036)：中央高校基本科研 地将任务分配到各个内核上，由于需要实时地收 业务费专项资金资助项目(HEUCF100606). 集、存储并分析状态信息，动态调度的实施有一 通信作者：刘正.E-mail:liuzheng528@hrbeu.cdu.cn
第 １０ 卷第 ２ 期 智 能 系 统 学 报 Ｖｏｌ．１０ №．２ ２０１５ 年 ４ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｐｒ． ２０１５ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１５０３０１３ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１５０４１３．１５０５．００１．ｈｔｍｌ 基于动态任务调度的 ＳＴＤＳ 算法设计研究 刘正 （哈尔滨工程大学 计算机科学与技术学院，黑龙江 哈尔滨 １５０００１） 摘 要：任务调度是计算机多核处理器系统获得高性能的关键，而现有的多核任务调度算法研究，大多侧重于静态 调度下的算法优化和负载均衡，对动态调度及动态负载均衡研究较少。 针对动态调度，并结合异构多核的特点，提 出一种基于核负载均衡的动态任务调度算法 ＳＴＤＳ。 算法通过合理设定调度粒度，降低调度频率，从而减少调度消耗 时间；根据异构多核处理器各核处理性能的差异，设置内核负载上下限值，控制内核负载保持在同一水平，以达到负 载均衡效果。 算法依据等待时间长短、任务间通信大小和内核负载轻重因素对任务进行实时调度，并可通过实时因 子、负载因子等参数设置 ３ 种因素的影响比重，以满足系统的不同需求。 仿真实验显示，在内核数目较多的系统中， ＳＴＤＳ 算法更加高效，在保证任务处理速度的同时有较好负载均衡。 关键词：动态任务调度；负载均衡；调度粒度；等待时间；异构多核系统 中图分类号：ＴＰ３１６．４ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１５）０２⁃０３２４⁃０９ 中文引用格式：刘正． 基于动态任务调度的 ＳＴＤＳ 算法设计研究［Ｊ］． 智能系统学报， ２０１５， １０（２）： ３２４⁃３３２． 英文引用格式：ＬＩＵ Ｚｈｅｎｇ． Ｒｅｓｅａｒｃｈ ｏｎ ＳＴＤＳ ａｌｇｏｒｉｔｈｍ ｄｅｓｉｇｎｉｎｇ ｂａｓｅｄ ｏｎ ｄｙｎａｍｉｃ ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎ⁃ ｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１５， １０（２）： ３２４⁃３３２． Ｒｅｓｅａｒｃｈ ｏｎ ＳＴＤＳ ａｌｇｏｒｉｔｈｍ ｄｅｓｉｇｎｉｎｇ ｂａｓｅｄ ｏｎ ｄｙｎａｍｉｃ ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ ＬＩＵ Ｚｈｅｎｇ （Ｃｏｌｌｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｈａｒｂｉｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ， Ｈａｒｂｉｎ １５０００１， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｅｆｆｉｃｉｅｎｔ ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ ｉｓ ｔｈｅ ｋｅｙ ｆｏｒ ｍｕｌｔｉ⁃ｃｏｒｅ ｓｙｓｔｅｍｓ ｔｏ ａｃｈｉｅｖｅ ｈｉｇｈ ｐｅｒｆｏｒｍａｎｃｅ． Ｈｏｗｅｖｅｒ， ｍｏｓｔ ｏｆ ｔｈｅ ｅｘｉｓｔｉｎｇ ｍｕｌｔｉ⁃ｃｏｒｅ ｒｅｓｅａｒｃｈｅｓ ｏｎ ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｆｏｃｕｓ ｏｎ ａｌｇｏｒｉｔｈｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｎｄ ｌｏａｄ ｂａｌａｎｃｉｎｇ ｕｎｄｅｒ ｔｈｅ ｓｔａｔｉｃ ｓｃｈｅｄｕｌｉｎｇ ｒａｔｈｅｒ ｔｈａｎ ｄｙｎａｍｉｃ ｓｃｈｅｄｕｌｉｎｇ ａｎｄ ｄｙｎａｍｉｃ ｌｏａｄ ｂａｌａｎｃｉｎｇ． Ｓｃａｌａｂｌｅ ｔａｓｋ ｄｕｐｌｉｃａｔｉｏｎ ｂａｓｅｄ ｓｃｈｅｄｕｌｉｎｇ （ＳＴＤＳ） ｉｓ ａ ｎｅｗ ｄｙｎａｍｉｃ⁃ｂａｌａｎｃｅｄ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｃｏｒｅ ｌｏａｄ ｂａｌａｎｃｉｎｇ． ＳＴＤＳ ｗａｓ ｐｕｔ ｆｏｒ⁃ ｗａｒｄ ｓｐｅｃｉｆｉｃａｌｌｙ ｆｏｒ ｄｙｎａｍｉｃ ｓｃｈｅｄｕｌｉｎｇ ａｎｄ ｉｎｔｅｇｒａｔｉｎｇ ｔｈｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｍｕｌｔｉ⁃ｃｏｒｅ． Ｉｔ ｓｈｏｒｔｅｎｓ ｓｃｈｅｄｕｌｉｎｇ ｔｉｍｅ ｂｙ ｒｅａｓｏｎａｂｌｙ ｓｅｔｔｉｎｇ ｔｈｅ ｓｃｈｅｄｕｌｉｎｇ ｇｒａｎｕｌａｒｉｔｙ ａｎｄ ｒｅｄｕｃｉｎｇ ｔｈｅ ｆｒｅｑｕｅｎｃｙ ｏｆ ｓｃｈｅｄｕｌｉｎｇ． ＳＴＤＳ ｓｅｔｓ ｔｈｅ ｍａｘｉｍｕｍ ａｎｄ ｍｉｎｉｍｕｍ ｒａｎｇｅｓ ｏｆ ｔｈｅ ｋｅｒｎｅｌ ｌｏａｄ ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｄｉｆｆｅｒｅｎｔ ｐｒｏｃｅｓｓｉｎｇ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｅａｃｈ ｃｏｒｅ ｏｆ ｔｈｅ ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｍｕｌｔｉ⁃ｃｏｒｅ ｐｒｏｃｅｓｓｏｒ， ｔｈｅｒｅｆｏｒｅ ｃｏｎｔｒｏｌｌｉｎｇ ｔｈｅ ｃｏｒｅ ｌｏａｄ ａｔ ｔｈｅ ｓａｍｅ ｌｅｖｅｌ ａｎｄ ａｃｈｉｅｖｉｎｇ ｔｈｅ ｅｆｆｅｃｔ ｏｆ ｌｏａｄ ｂａｌａｎｃｅ． Ｔｈｅ ｗａｉｔ ｔｉｍｅ ｏｆ ｔａｓｋ ａｎｄ ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｂｅｔｗｅｅｎ ｔａｓｋｓ ａｎｄ ｋｅｒｎｅｌ ｌｏａｄ ｗｉｌｌ ｂｅ ｃｏｎｓｉｄ⁃ ｅｒｅｄ ｔｏｇｅｔｈｅｒ ｔｏ ｐｉｃｋ ｕｐ ｔｈｅ ｍｏｓｔ ａｐｐｒｏｐｒｉａｔｅ ｔａｓｋ ｄｕｒｉｎｇ ｓｃｈｅｄｕｌｉｎｇ． Ｔｈｅ ｉｍｐｏｒｔａｎｃｅ ｏｆ ｅａｃｈ ｅｌｅｍｅｎｔ ｃａｎ ｂｅ ａｄｊｕｓ⁃ ｔｅｄ ｂｙ ａｓｓｉｇｎｉｎｇ ａｎｏｔｈｅｒ ｖａｌｕｅ ｔｏ ｔｈｅ ｒｅａｌ⁃ｔｉｍｅ ｆａｃｔｏｒ ａｎｄ ｌｏａｄ ｆａｃｔｏｒ ｅｎａｂｌｉｎｇ ｉｔ ｔｏ ａｄａｐｔ ｔｏ ｖａｒｉｏｕｓ ｅｎｖｉｒｏｎｍｅｎｔ． Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｖｅｒｉｆｉｅｄ ｔｈａｔ ｔｈｅ ＳＴＤＳ ａｌｇｏｒｉｔｈｍ ｉｓ ｍｏｒｅ ｅｆｆｉｃｉｅｎｔ ｉｎ ｔｈｅ ｓｙｓｔｅｍ ｗｉｔｈ ｔｈｅ ｍｏｓｔ ｋｅｒｎｅｌｓ． Ｉｔ ａｌｓｏ ｋｅｅｐｓ ａ ｇｏｏｄ ｌｏａｄ ｂａｌａｎｃｅ ｗｈｉｌｅ ｍａｉｎｔａｉｎｉｎｇ ｔｈｅ ｓｐｅｅｄ ｏｆ ｔａｓｋ ｅｘｅｃｕｔｉｏｎ ｐｒｏｃｅｓｓｉｎｇ． Ｋｅｙｗｏｒｄｓ： ｄｙｎａｍｉｃ ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ； ｌｏａｄ ｂａｌａｎｃｉｎｇ； ｓｃｈｅｄｕｌｉｎｇ ｇｒａｎｕｌａｒｉｔｙ； ｗａｉｔｉｎｇ ｔｉｍｅ； ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｍｕｌｔｉ⁃ ｃｏｒｅ ｓｙｓｔｅｍ 收稿日期：２０１５⁃０３⁃０９． 网络出版日期：２０１５⁃０４⁃１３． 基金项目：国家自然科学基金资助项目（６１００３０３６）；中央高校基本科研 业务费专项资金资助项目（ＨＥＵＣＦ１００６０６）． 通信作者：刘正．Ｅ⁃ｍａｉｌ：ｌｉｕｚｈｅｎｇ５２８＠ ｈｒｂｅｕ．ｅｄｕ．ｃｎ． 动态任务调度可以根据运行的时情况动态 地将任务分配到各个内核上，由于需要实时地收 集、存储并分析状态信息，动态调度的实施有一
第2期 刘正：基于动态任务调度的STDS算法设计研究 ·325· 定的系统开销，但这种开销和付出通常是有回报 负载平衡研究提供了理论指导：徐雨明等将遗传 的山。多核处理器系统中的任务调度已被证明 算法和启发式方法有机地结合，根据染色体双螺旋 是NP问题2)，除个别特殊情况外，目前尚未有一 结构模型，提出了一种异构系统中依赖任务调度的 种多项式时间算法可以求得最优解，只能得到一 双螺旋结构遗传算法。该算法首先采用启发式方 个最大限度接近最优解的解，因此改进算法的效 法，产生较佳的任务调度优先队列，然后模仿碱基互 率并构建任务调度实现机制成为研究重点，很多 补配对方法，提高算法的有效性和收敛速度；Vinay 学者在这方面做了大量工作。 等]提出一种多核处理器动态任务调度策略，调度 比较经典的调度算法有Min-Min)、Max- 思想是依据任务的执行时间和依赖此任务的任务数 Mim[4、MCT)、MET算法。Min-Min算法实现简 量确定此任务优先级，当某个内核空闲时，选择一个 单、执行速度快。算法首先通过计算待调度任务在 优先级最高且为就绪状态的任务分配给该内核。此 任一可用内核上的最早完成时间，取最小值作为该 策略结构简洁，算法复杂度低，但每个内核上只分配 任务的最早完成时间，然后选取所有待调度任务中 一个任务，且调度时需要对数据段加锁以保证数据 最早完成时间最小的一个任务进行调度。缺点是如 一致性，当内核数目较多时，经常发生多个内核同时 果任务集中存在过多的执行时间比较小的任务，那 申请分配任务的情况，所以不可避免出现内核空闲 么大任务将无法得到及时的执行。Max-Min算法同 等待现象，不能完全发挥多核处理器优势。 Min-Min算法类似，同样需要计算每一任务的最早 文中对文献[11]的动态调度策略进行改进，克 完成时间，不同的是Max-Min算法首先调度最早完 服内核可能空闲等待问题，并综合负载均衡策略，提 成时间最大的任务，将其分配到对应的内核上。缺 出多核动态任务调度算法(shared task data struc- 点是小任务等待时间过长、影响执行效率，也可能造 ture,STDS)。算法通过分析任务等待时间、任务间 成负载不均衡。MCT算法以任务完成时间最早为 通信开销和内核负载等因素，确定任务优先级，并据 目标进行调度，每次将到达的任务分配到完成时间 此分配任务。通过仿真实验验证，该算法在保证任 最早的内核上，但该算法忽略了任务的执行时间，可 务处理速度的同时有较好负载均衡，比较适用于内 能将任务分配到执行时间较长的处理机上运行。 核数目较多的系统。 MET算法以任务执行时间最短为目标进行调度，每 1 模型 次将到达的任务分配到执行时间最短的内核上，其 缺点是易造成较强内核负载过多任务，导致内核间 在多核任务调度研究中，为便于研究理解，通常 负载不均衡，降低系统性能。 用抽象的任务调度模型描述任务调度系统。多核任 清华大学的石威等)提出了一种相关任务图 务调度模型通常由系统模型、任务模型、任务调度算 的均衡动态关键路径调度算法，采用动态关键路径 法和任务映射图组成。 技术并均衡考虑关键路径结点和非关键路径结点， 1.1系统模型 优先调度对相关任务图调度长度影响最大的就绪结 系统模型是指依据系统硬件环境构建出可 点，从而极大地缩短任务图的调度长度。李仁发) 进行数学量化分析的数学模型，文中用二元组 对多核处理器系统任务调度研究进展进行讨论，对 SM(system model)={P,Rate}表示，其中：SM表 不同模型下的多核系统任务调度算法相关研究进行 示系统模型；P={P。,P,…,P,…,P-1}为处 了分析总结，从调度算法分析和调度实现框架2个 理器内核集合，P表示第k个处理器内核，P= 方面探讨了近年来多核任务调度的国内外研究进展 m为处理器中内核的总个数。多核处理器根据 情况。文中对任务分配、任务模型优化、调度器实现 内核在执行能力方面的差别可划分为同构和异 和任务迁移等当前亟待解决的问题，进行了深入探 构2类，同构多核处理器通过增加同种处理器内 讨，并指出了下一步主要的研究方向，为多核处理器 核数量提升性能，而异构多核处理器通过集成不 相关研究提供参考。吉林大学的耿晓中提出了一种 同计算能力的内核来优化处理器，实现多核处理 动态负载均衡模型[⑨，将影响多核处理器负载均衡 器性能发挥的最大化，在能耗、面积等方面有着 的因素分为5类：多核系统的负载均衡环境、用户提 巨大的优势【2)。文中以有限数目的异构多核处 交的任务属性、系统的负载评价、系统所采用的调度 理器为研究基础，集合P中处理器内核速度并不 策略以及系统的调度评价指标，为多核动态调度的 完全相同，用sP4表示内核P的处理速度
定的系统开销，但这种开销和付出通常是有回报 的［ １］ 。 多核处理器系统中的任务调度已被证明 是 ＮＰ 问题［ ２］ ，除个别特殊情况外，目前尚未有一 种多项式时间算法可以求得最优解，只能得到一 个最大限度接近最优解的解，因此改进算法的效 率并构建任务调度实现机制成为研究重点，很多 学者在这方面做了大量工作。 比 较 经 典 的 调 度 算 法 有 Ｍｉｎ⁃Ｍｉｎ ［３］ 、 Ｍａｘ⁃ Ｍｉｎ ［４］ 、ＭＣＴ ［５］ 、ＭＥＴ ［６］ 算法。 Ｍｉｎ⁃Ｍｉｎ 算法实现简 单、执行速度快。 算法首先通过计算待调度任务在 任一可用内核上的最早完成时间，取最小值作为该 任务的最早完成时间，然后选取所有待调度任务中 最早完成时间最小的一个任务进行调度。 缺点是如 果任务集中存在过多的执行时间比较小的任务，那 么大任务将无法得到及时的执行。 Ｍａｘ⁃Ｍｉｎ 算法同 Ｍｉｎ⁃Ｍｉｎ 算法类似，同样需要计算每一任务的最早 完成时间，不同的是 Ｍａｘ⁃Ｍｉｎ 算法首先调度最早完 成时间最大的任务，将其分配到对应的内核上。 缺 点是小任务等待时间过长、影响执行效率，也可能造 成负载不均衡。 ＭＣＴ 算法以任务完成时间最早为 目标进行调度，每次将到达的任务分配到完成时间 最早的内核上，但该算法忽略了任务的执行时间，可 能将任务分配到执行时间较长的处理机上运行。 ＭＥＴ 算法以任务执行时间最短为目标进行调度，每 次将到达的任务分配到执行时间最短的内核上，其 缺点是易造成较强内核负载过多任务，导致内核间 负载不均衡，降低系统性能。 清华大学的石威等［７］ 提出了一种相关任务图 的均衡动态关键路径调度算法，采用动态关键路径 技术并均衡考虑关键路径结点和非关键路径结点， 优先调度对相关任务图调度长度影响最大的就绪结 点，从而极大地缩短任务图的调度长度。 李仁发［８］ 对多核处理器系统任务调度研究进展进行讨论，对 不同模型下的多核系统任务调度算法相关研究进行 了分析总结，从调度算法分析和调度实现框架 ２ 个 方面探讨了近年来多核任务调度的国内外研究进展 情况。 文中对任务分配、任务模型优化、调度器实现 和任务迁移等当前亟待解决的问题，进行了深入探 讨，并指出了下一步主要的研究方向，为多核处理器 相关研究提供参考。 吉林大学的耿晓中提出了一种 动态负载均衡模型［９］ ，将影响多核处理器负载均衡 的因素分为 ５ 类：多核系统的负载均衡环境、用户提 交的任务属性、系统的负载评价、系统所采用的调度 策略以及系统的调度评价指标，为多核动态调度的 负载平衡研究提供了理论指导；徐雨明等［１０］ 将遗传 算法和启发式方法有机地结合，根据染色体双螺旋 结构模型，提出了一种异构系统中依赖任务调度的 双螺旋结构遗传算法。 该算法首先采用启发式方 法，产生较佳的任务调度优先队列，然后模仿碱基互 补配对方法，提高算法的有效性和收敛速度；Ｖｉｎａｙ 等［１１］提出一种多核处理器动态任务调度策略，调度 思想是依据任务的执行时间和依赖此任务的任务数 量确定此任务优先级，当某个内核空闲时，选择一个 优先级最高且为就绪状态的任务分配给该内核。 此 策略结构简洁，算法复杂度低，但每个内核上只分配 一个任务，且调度时需要对数据段加锁以保证数据 一致性，当内核数目较多时，经常发生多个内核同时 申请分配任务的情况，所以不可避免出现内核空闲 等待现象，不能完全发挥多核处理器优势。 文中对文献［１１］的动态调度策略进行改进，克 服内核可能空闲等待问题，并综合负载均衡策略，提 出多核动态任务调度算法（ ｓｈａｒｅｄ ｔａｓｋ ｄａｔａ ｓｔｒｕｃ⁃ ｔｕｒｅ，ＳＴＤＳ）。 算法通过分析任务等待时间、任务间 通信开销和内核负载等因素，确定任务优先级，并据 此分配任务。 通过仿真实验验证，该算法在保证任 务处理速度的同时有较好负载均衡，比较适用于内 核数目较多的系统。 １ 模型 在多核任务调度研究中，为便于研究理解，通常 用抽象的任务调度模型描述任务调度系统。 多核任 务调度模型通常由系统模型、任务模型、任务调度算 法和任务映射图组成。 １．１ 系统模型 系统模型是指依据系统硬件环境构建出可 进行数学量化分析的数学模型，文 中 用 二 元 组 ＳＭ（ ｓｙｓｔｅｍ ｍｏｄｅｌ） ＝ ｛ Ｐ， Ｒａｔｅ｝表示，其中：ＳＭ 表 示系统模型； Ｐ ＝ ｛ Ｐ０ ，Ｐ１ ，…，Ｐｋ，…， Ｐ ｍ － １ ｝为处 理器内核集合，Ｐｋ表示第 ｋ 个处理器内核， ｜ Ｐ ｜ ＝ ｍ 为处理器中内核的总个数。 多核处理器根据 内核在执行能力方面的差别可划分为同构和异 构 ２ 类，同构多核处理器通过增加同种处理器内 核数量提升性能，而异构多核处理器通过集成不 同计算能力的内核来优化处理器，实现多核处理 器性能发挥的最大化，在能耗、面积等方面有着 巨大的优势［ １２］ 。 文中以有限数目的异构多核处 理器为研究基础，集合 Ｐ 中处理器内核速度并不 完全相同，用 ｓｐｋ表示内核 Ｐｋ的处理速度。 第 ２ 期 刘正：基于动态任务调度的 ＳＴＤＳ 算法设计研究 ·３２５·
·326· 智能系统学报 第10卷 Rate={…,Rate,…}表示处理器内核间数据 务T,与T的通信时间就可用Data:,/Rate,表示； 传输速率集合，元素Rate,表示处理器内核P,与P, T。={…,T,…}:依赖任务T:的任务集合，也 间的数据传输速率。 叫后继任务集合，只有T执行完成后，其后继任务 核间互连技术是多核处理器设计的关键，当前多 才有机会变为就绪状态，从而调度执行。当T:完成 核处理器核间互连方式主要有总线共享、交叉开关互 后，需要将集合T。中所有任务的T属性值减一； 连和片上网络3种。文中对多核处理器核间互连技 T。:任务优先级，表示任务优先调度程度，任务 术不做具体研究，默认任意2个处理器内核间均存在 优先级越高，被优先调度的可能性越大。任务优先 数据通信通路，即对于任意的s(0≤s≤m-1)和 级取决于任务就绪时间、通信开销以及内核负载等 t(0≤s≤m-1),Rate≠0。为简化环境模型，假 因素。系统运行过程中，就绪时间和内核负载等是 设同一时刻，内核P只能与一个内核进行通信。 动态变化的，所以任务优先级不是某一定值，它随着 1.2任务模型 系统状态的改变而动态变化： 任务模型是描述任务属性和特征的一种数学模 T:任务就绪时间，即任务满足调度条件变为 型，它包含任务调度过程中的状态和控制等信息。 就绪状态的时间。如果用t表示现在时间，则等待 STDS算法构建了一个可以共享访问的TDS(ask 时间就是(t-T),为避免存在长时间未能调度执 data structure)结构，TDS由若千数据项构成，每个数 行的就绪任务，算法应优先调度等待时间长的任务； 据项唯一对应一个任务，数据项记录该任务的相关 T:任务映射，表示任务和内核的对应关系，即 信息，其定义如图1所示。 任务T:分配到哪个内核上执行。STDS算法用-1 表示任务尚未分配内核资源，用整数0,1，…，m-1 分别表示在内核P。,P,…,Pm-1上执行。 图1数据项定义 1.3调度器模型 Fig.I Definition of data element 文中设计的调度器模型采用集中式调度模式， 图1中，T为任务编号，唯一标识任务；T为任务状 如图2所示。图中指定了一个内核专门执行调度程 态，STDS算法将任务状态分为等待、就绪和已执行 序，称为中心调度器，中心调度器负责收集调度信息 3种，用1表示等待，0表示就绪，2表示已执行。如 和执行任务调度，其余内核只负责执行任务。 果任务处于就绪态，说明已分配除CPU外所有必要 TDS 资源，允许调度程序将其调度分配：等待状态的任务 就绪队列 等待队列 因需要等待某一事件的发生，比如等待其前驱任务 执行完毕，而暂不能被调度程序调度：任务执行完毕 后的状态为已执行状态，此状态下，如果其他所有任 中心调度器 信息更新 务都不再需要此任务信息，就将其对应的数据项删 除，以节省内存空间： Ta={…,T,…:依赖任务集合，也叫前驱任 P 务集合，任务T必须在其依赖任务全部执行完成之 后执行： T：依赖任务剩余数量，表示任务T,的依赖任 务队列 务队列 务队 务集合中尚未执行完毕的任务数量，即依赖任务集 图2调度器模型 合T中，还有多少依赖任务没有执行完成。其初值 Fig.2 Scheduler model 是集合Ta的长度，即T=Tal,每当一个依赖任 建立维护等待队列和就绪队列2个全局任务列 务执行完毕，T油值减1，直到T=0,而T血=0是 表，调度器在任务调度时只需要检索就绪任务队列， T.=0(就绪)的必要条件： 节省了调度时间开销，等待队列中的任务满足就绪 Ta={…,Data,…}:与依赖任务通信数据量 条件时可以变为就绪态等待调度。每个内核都有一 集合，记录任务T:与其依赖任务T通信的数据大 个可以缓存一定数目任务的局部队列，当内核需要 小，Data,表示任务T:与依赖任务T通信的数据大 调度任务时直接从缓存中获取：而当局部队列中的 小，如果任务T:、T分别分配到内核P,、P上，则任 任务过少时开始请求调度器为局部队列分配任务
Ｒａｔｅ ＝ ｛…，Ｒａｔｅｓ，ｔ，…｝表示处理器内核间数据 传输速率集合，元素 Ｒａｔｅｓ，ｔ表示处理器内核 Ｐｓ 与 Ｐｔ 间的数据传输速率。 核间互连技术是多核处理器设计的关键，当前多 核处理器核间互连方式主要有总线共享、交叉开关互 连和片上网络 ３ 种。 文中对多核处理器核间互连技 术不做具体研究，默认任意 ２ 个处理器内核间均存在 数据通信通路，即对于任意的 ｓ（ ０ ≤ ｓ ≤ ｍ － １）和 ｔ（０ ≤ ｓ ≤ ｍ － １）， Ｒａｔｅｓ，ｔ ≠ ０。 为简化环境模型，假 设同一时刻，内核 Ｐｋ只能与一个内核进行通信。 １．２ 任务模型 任务模型是描述任务属性和特征的一种数学模 型，它包含任务调度过程中的状态和控制等信息。 ＳＴＤＳ 算法构建了一个可以共享访问的 ＴＤＳ （ ｔａｓｋ ｄａｔａ ｓｔｒｕｃｔｕｒｅ）结构，ＴＤＳ 由若干数据项构成，每个数 据项唯一对应一个任务，数据项记录该任务的相关 信息，其定义如图 １ 所示。 图 １ 数据项定义 Ｆｉｇ．１ Ｄｅｆｉｎｉｔｉｏｎ ｏｆ ｄａｔａ ｅｌｅｍｅｎｔ 图 １ 中，Ｔｉ为任务编号，唯一标识任务； Ｔｉｓ 为任务状 态，ＳＴＤＳ 算法将任务状态分为等待、就绪和已执行 ３ 种，用 １ 表示等待，０ 表示就绪，２ 表示已执行。 如 果任务处于就绪态，说明已分配除 ＣＰＵ 外所有必要 资源，允许调度程序将其调度分配；等待状态的任务 因需要等待某一事件的发生，比如等待其前驱任务 执行完毕，而暂不能被调度程序调度；任务执行完毕 后的状态为已执行状态，此状态下，如果其他所有任 务都不再需要此任务信息，就将其对应的数据项删 除，以节省内存空间； Ｔｉｄ ＝ ｛…，Ｔｊ，…｝： 依赖任务集合，也叫前驱任 务集合，任务 Ｔｉ 必须在其依赖任务全部执行完成之 后执行； Ｔｉｄｎ ： 依赖任务剩余数量，表示任务 Ｔｉ的依赖任 务集合中尚未执行完毕的任务数量，即依赖任务集 合 Ｔｉｄ 中，还有多少依赖任务没有执行完成。 其初值 是集合 Ｔｉｄ 的长度，即 Ｔｉｄｎ ＝｜ Ｔｉｄ ｜ ， 每当一个依赖任 务执行完毕， Ｔｉｄｎ 值减 １， 直到 Ｔｉｄｎ ＝ ０， 而 Ｔｉｄｎ ＝ ０ 是 Ｔｉｓ ＝ ０（就绪）的必要条件； Ｔｉｄｄ ＝ ｛…，Ｄａｔａｉ，ｊ，…｝：与依赖任务通信数据量 集合，记录任务 Ｔｉ 与其依赖任务 Ｔｉｄ通信的数据大 小， Ｄａｔａｉ，ｊ 表示任务 Ｔｉ 与依赖任务 Ｔｊ 通信的数据大 小，如果任务 Ｔｉ、Ｔｊ 分别分配到内核 Ｐｓ、Ｐｔ 上，则任 务 Ｔｉ 与 Ｔｊ 的通信时间就可用 Ｄａｔａｉ，ｊ ／ Ｒａｔｅｓ，ｔ 表示； Ｔｉａ ＝ ｛…，Ｔｊ，…｝：依赖任务 Ｔｉ 的任务集合，也 叫后继任务集合，只有 Ｔｉ 执行完成后，其后继任务 才有机会变为就绪状态，从而调度执行。 当 Ｔｉ 完成 后， 需要将集合 Ｔｉａ 中所有任务的 Ｔｉｄｎ 属性值减一； Ｔｉｐ ：任务优先级，表示任务优先调度程度，任务 优先级越高，被优先调度的可能性越大。 任务优先 级取决于任务就绪时间、通信开销以及内核负载等 因素。 系统运行过程中，就绪时间和内核负载等是 动态变化的，所以任务优先级不是某一定值，它随着 系统状态的改变而动态变化； Ｔｉｔ： 任务就绪时间，即任务满足调度条件变为 就绪状态的时间。 如果用 ｔ 表示现在时间，则等待 时间就是（ｔ － Ｔｉｔ）， 为避免存在长时间未能调度执 行的就绪任务，算法应优先调度等待时间长的任务； Ｔｉｃ：任务映射，表示任务和内核的对应关系，即 任务 Ｔｉ 分配到哪个内核上执行。 ＳＴＤＳ 算法用 － １ 表示任务尚未分配内核资源，用整数 ０，１，…，ｍ － １ 分别表示在内核 Ｐ０ ， Ｐ１ ，…， Ｐｍ－１ 上执行。 １．３ 调度器模型 文中设计的调度器模型采用集中式调度模式， 如图 ２ 所示。 图中指定了一个内核专门执行调度程 序，称为中心调度器，中心调度器负责收集调度信息 和执行任务调度，其余内核只负责执行任务。 图 ２ 调度器模型 Ｆｉｇ．２ Ｓｃｈｅｄｕｌｅｒ ｍｏｄｅｌ 建立维护等待队列和就绪队列 ２ 个全局任务列 表，调度器在任务调度时只需要检索就绪任务队列， 节省了调度时间开销，等待队列中的任务满足就绪 条件时可以变为就绪态等待调度。 每个内核都有一 个可以缓存一定数目任务的局部队列，当内核需要 调度任务时直接从缓存中获取；而当局部队列中的 任务过少时开始请求调度器为局部队列分配任务， ·３２６· 智 能 系 统 学 报 第 １０ 卷
第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血
降低了调度器调度频率，而且中心调度器与各内核 可以并行地运行。 全局调度队列和局部调度队列结 合的方式在整体上是全局队列方式，与集中式调度 策略配合使用易于实现负载均衡；在底层实现上是 局部队列方式，降低了系统对队列共享性要求，克服 了集中式调度模式的性能瓶颈问题。 文中通过重载和轻载阀值确定调度时机，当内 核处于轻载状态时请求任务调度，处于重载时不允 许再向内核分配任务，这种策略在保证一定负载均 衡效果的同时提高了内核执行效率。 ２ 任务优先级 将任务分配到最合适的内核上是任务调度的核 心问题，而任务优先级计算是任务分配的关键，任务 优先级表明任务被优先调度程度。 在多核环境下， 各内核的状态不尽相同，ＳＴＤＳ 算法为评价任务与内 核的适合程度，首先计算任务相对于一个确定内核 的优先级 Ｔｉｐｋ，然后取其在所有内核上的最大值作 为任务优先级 Ｔｉｐ，表示为式（１）： Ｔｉｐ ＝ ｍａｘ ０≤ｋ≤ｍ－１ Ｔｉｐｋ （１） 式中： ｍ 为内核数量，Ｔｉｐｋ 表示任务 Ｔｉ 相对于内核 Ｐｋ 的优先级。 ＳＴＤＳ 算法在计算 Ｔｉｐｋ 时，综合考虑等待 时间、任务间通信开销和内核负载状态因素。 等待 时间为当前时间与就绪时间的差值，任务间通信开 销是任务Ｔｉ 与其所有依赖任务Ｔｉｄ 通信时间之和，而 内核负载状态用于实现内核负载均衡。 多核处理器的负载均衡要求避免出现一个或多 个内核负载较低甚至空闲，而其他内核处于高负载 状态的情况，从而充分发挥多核处理器优势。 ＳＴＤＳ 算法使用任务队列长度 ｜ ＴＬｋ ｜ 作为内核负载指标， 内核的任务队列越长，说明分配的任务越多，所以其 负载越大。 为实现负载均衡引入调度粒度，内核 Ｐｋ的调度 粒度定义为一次调度过程中为 Ｐｋ分配的任务数量， 这里的一次调度过程是指一个内核请求调度，调度 算法为其分配任务的过程，在实际运行中，可能出现 调度算法一次性处理多个内核调度请求，调度的任 务数量等于为每个内核分配的任务数量之和。 粒度 大小要根据系统模型而定，调度粒度过大，不能充分 发挥动态调度优势，而粒度过小，会引发频繁调度， 增大调度程序运行时间开销，降低处理器效率。 对 于异构多核处理器，调度粒度与内核处理速度是正 比关系。 ＳＴＤＳ 算法将调度粒度定义为式（２）： ｌ ｋ ＝ ｌ·ｓｐｋ，０ ≤ ｋ ≤ ｍ － １ （２） 式中：ｌ ｋ表示内核 Ｐｋ 的调度粒度，ｌ 表示粒度因子， ｓｐｋ表示内核 Ｐｋ的处理速度。 对于一个实际的处理 器系统，内核速度是确定的已知量，调度粒度 ｌ ｋ的大 小，可以通过粒度因子 ｌ 调节，粒度因子与具体的运 行状况有关，它起到将内核的计算速度转换为内核 调度任务数量功能。 ＳＴＤＳ 算法通过限制内核任务队列长度实现负 载均衡，为有效发挥调度队列作用，算法引入 ２ 个负 载因子，分别确定队列的上限和下限，具体定义如式 （３） ～ （５）： ｌ ｋ＿ｍａｘ ＝ ｌ ｋ（１ ＋ δ１ ） （３） ｌ ｋ＿ｍｉｎ ＝ ｌ ｋ（１ － δ２ ） （４） δ１ ＋ δ２ ＝ １ （５） ０ ≤ ｋ ≤ ｍ － １ 式中： δ１ 是负载上限因子， ｌ ｋ＿ｍａｘ 表示内核 Ｐｋ的任 务队列长度上限， δ２ 是负载下限因子， ｌ ｋ＿ｍｉｎ 表示 内核 Ｐｋ 的任务队列长度下限。 当 Ｔｌ ｋ ≤ ｌ ｋ＿ｍｉｎ 时，内核 Ｐｋ 请求调度程序分配任务，而当 Ｔｌ ｋ ≥ ｌ ｋ＿ｍａｘ 时，就不允许向内核 Ｐｋ上分配任务，从而保 证内核 Ｐｋ的任务队列长度满足： ｌ ｋ＿ｍｉｎ ≤ Ｔｌ ｋ ≤ ｌ ｋ＿ｍａｘ 。 需要说明的是，在一些极端情况下，比如 当有多个内核同时请求分配任务，或者暂时没有任 务可分配时，调度程序无法及时响应内核任务调度 请求，而内核继续从其任务队列上取任务执行，此时 会出现 Ｔｌ ｋ ＜ ｌ ｋ＿ｍｉｎ 的情况，但只要调度粒度设 置合理，这种情况不会频繁出现，所以不影响整体负 载均衡。 内核 Ｐｋ的任务队列长度上限与下限之差 ｌ ｋ＿ｍａｘ － ｌ ｋ＿ｍｉｎ ＝ ｌ ｋ（δ１ ＋ δ１ ） ，而式（５）设置约束条 件 δ１ ＋ δ２ ＝ １，从而使得 ｌ ｋ＿ｍａｘ － ｌ ｋ＿ｍｉｎ ＝ ｌ ｋ ，内核 Ｐｋ在其任务队列长度为 ｌ ｋ＿ｍｉｎ 时请求分配任务，调 度程序响应请求并为 Ｐｋ分配 ｌ ｋ （调度粒度）个任务， 此时内核 Ｐｋ的任务队列长度为其上限值 ｌ ｋ＿ｍａｘ 。 上述阐述了计算任务优先级时的内核队列上下 限问题，式（６） ～ （１０）则是对任务优先级计算时的 等待时间、通信开销和内核负载均衡因素的描述。 ＳＴＤＳ 算法在计算任务优先级时，综合考虑等待时 间、通信开销和内核负载均衡因素，式（１）中 Ｔｉｐｋ表 示任务 Ｔｉ分配到内核 Ｐｋ适合程度，其计算公式为： Ｔｉｐｋ ＝ （ＰＷｉ ＋ ＰＣｉｋ）·ｌ ｋ ｊ （６） ＰＷｉ ＝ β ｔ － Ｔｉｔ ( ) （７） ＰＣｉｋ ＝ ０≤∑ｓ≤ｍ－１ Ｃｉｓ ｍ·Ｃｉｋ （８） ｌ ｋ ＝ ｌ ｋ ＿ｍａｘ －｜ Ｔｌ ｋ ｜ ｌ ｋ＿ｍａｘ － ｌ ｋ＿ｍｉｎ （９） 第 ２ 期 刘正：基于动态任务调度的 ＳＴＤＳ 算法设计研究 ·３２７·
.328. 智能系统学报 第10卷 3)任务不可抢占。 Rate a Ct=】 Dataij (10)》 系统运行时首先将任务初始化，构造TDS,由于 0≤k≤m-1,0≤s≤m-1,0≤i<|Ta1 算法中大多计算只针对就绪任务，特别是任务分配 式中：PW代表任务T的等待时间所占优先级比重， 时，所以为了节约计算开销，算法初始化时会生成一 PC代表通信时间所占优先级比重，L为内核P:的 个就绪任务列表和一个等待任务列表。当内核P: 负载状态。t是当前时间，1-T表示任务T的等待时 任务队列长度ITLI≤l时，就向调度程序请求分 间，等待时间越长的任务优先级相对越高，同等条件 配任务，调度程序遍历就绪列表，计算相对于内核 下，调度程序优先调度等待时间长的任务，避免存在 P的优先级，选择优先级T值最大的任务分配到P 就绪任务长时间等待的“饥饿”现象，B是实时性因 上，重复执行此过程，直到内核P任务队列长度 子，用来调节等待时间在优先级中所占比重。C表 ITLI≥。若同时有多个内核请求任务分配，调度 示任务T,的通信时间，STDS算法假设同一内核内的 程序分配任务时需要响应这几个内核的请求，计算 任务通信开销忽略不计，C:值即任务T,与除内核P 优先级时需要计算相对于这几个内核的优先级，然 以外的其他内核P,上依赖任务通信的时间之和，用 后取最大值作为最终优先级，调度程序选择优先级 Daau表示，下标s即任务T,的T,属性值， 最大的任务分配到对应的内核。 jeTe+Rate. 值得注意的是在动态调度过程中，为了保证数 据实时有效，STDS算法在每个任务分配完成或执行 表示任务T分配给内核P。s-1 一表示平均通信 结束时对数据进行更新。当任务T分配给内核P m 后，需要将任务T对应数据项中的T置为k,此时内 时间，通信时间越小，PC值越大，优先级也相应越 核P负载也相应改变；当任务T执行完成时，如果 大，对于C4相同的任务，若任务的∑C。值较 任务T依赖任务T,需要将任务T的T值减1，若 0≤s≤m-1 大，则说明此任务如果分配到内核P上节省的通信 减1后T:=0,将任务T状态置为就绪态并从等待 开销更多，相应的其优先级也较高。在实际计算时， 列表移到就绪列表。为了降低复杂度节省时间， 因为任务T的依赖任务已经全部分配执行，所以若 STDS算法采用先记录再批量执行的方式，即在任务 分配在内核P:上，通信开销是个定值，因此PC.只 执行期间暂时将完成的任务编号记录，在任务调度 程序执行时批量更新数据：如果任务T执行完毕且 需计算一次。少尼 一反应了内核的负载状 所有依赖T的任务也执行完毕，就将任务T的信息 态，ITLI是内核P当前任务队列长度，当1TL:I= 从TDS中删除，从而释放内存节省空间。 lm时其值为0，从而T=0为最小值，则当前状态 如果就绪列表为空，调度程序不会响应内核的 下不能向内核P分派任务。在一次调度过程中，调 任务分配请求，当就绪列表和等待列表全为空时，说 度程序可能需要响应多个内核的调度请求，对于 明任务全部执行完毕，调度结束。 |TLI较小的内核，其L较大，从而实现优先将任务 STDS算法实现步骤： 分配到负载较轻的内核，并进而达到负载均衡效果。 Procedure STDS(SM,TDS,PL,TL)/*SM 综上所述，任务优先级值的计算，是对等待时 示处理器内核系统；TDS是所有任务信息；Pm是需 间、通信开销和内核负载3个因素综合考量的过程， 要分配任务的内核列表，T。是执行完毕但还未进 其结果可能不是单一因素中最优的，但一定是综合 行信息更新的任务列表*/ 考虑全部3种因素后最优的选择。 1)for each Te TL 2){Ta[]-T:; 3算法实现 3) for each T∈Ta 在上节中详细介绍了任务优先级的计算，本节 4) T←T-1;/*执行完毕的任务信息 将介绍STDS算法的具体实现过程。 更新，将其后继任务的依赖任务数量减一*/ 为了使任务调度算法得到较理想的实现，STDS /end for each Tie TLee * 算法的研究基于以下假设条件： 5)TLa助[]←-TDS;/*就绪任务放入就绪队列*/ 1)假设任务间的依赖关系固定不变： 6)for each TiTLready 2)同一内核上任务间通信开销忽略不计； 7){for each P&∈Pia
Ｃｉｋ ＝ ｊ∈Ｔ∑ｉｄｄ＆＆ｓ≠ｋ Ｄａｔａｉ，ｊ Ｒａｔｅｓ，ｋ （１０） ０ ≤ ｋ ≤ ｍ － １，０ ≤ ｓ ≤ ｍ － １，０ ≤ ｉ ＜ ｜ ＴＬｉｓｔ ｜ 式中：ＰＷｉ代表任务 Ｔｉ的等待时间所占优先级比重， ＰＣｉｋ代表通信时间所占优先级比重，Ｌｋ为内核 Ｐｋ的 负载状态。 ｔ 是当前时间，ｔ－Ｔｉｔ表示任务 Ｔｉ的等待时 间，等待时间越长的任务优先级相对越高，同等条件 下，调度程序优先调度等待时间长的任务，避免存在 就绪任务长时间等待的“饥饿”现象， β 是实时性因 子，用来调节等待时间在优先级中所占比重。 Ｃｉｋ表 示任务 Ｔｉ的通信时间，ＳＴＤＳ 算法假设同一内核内的 任务通信开销忽略不计，Ｃｉｋ值即任务 Ｔｉ与除内核 Ｐｋ 以外的其他内核 Ｐｓ上依赖任务通信的时间之和，用 ｊ∈Ｔ∑ｉｄｄ＆＆ｓ≠ｋ Ｄａｔａｉ，ｊ Ｒａｔｅｓ，ｋ 表示，下标 ｓ 即任务 Ｔｊ的 Ｔｊｃ属性值， 表示任务 Ｔｊ分配给内核 Ｐｓ。 ０≤∑ｓ≤ｍ－１ Ｃｉｓ ｍ 表示平均通信 时间，通信时间越小，ＰＣｉｋ值越大，优先级也相应越 大，对于 Ｃｉｋ 相同的任务，若任务的 ０≤∑ｓ≤ｍ－１ Ｃｉｓ 值较 大，则说明此任务如果分配到内核 Ｐｋ上节省的通信 开销更多，相应的其优先级也较高。 在实际计算时， 因为任务 Ｔｉ的依赖任务已经全部分配执行，所以若 分配在内核 Ｐｋ上，通信开销是个定值，因此 ＰＣｉｋ只 需计算一次。 ｌ ｋ ＿ｍａｘ －｜ Ｔｌ ｋ ｜ ｌ ｋ＿ｍａｘ － ｌ ｋ＿ｍｉｎ 反应了内核的负载状 态， ｜ ＴＬｋ ｜ 是内核 Ｐｋ当前任务队列长度，当 ｜ ＴＬｋ ｜ ＝ ｌ ｋ＿ｍａｘ时其值为 ０，从而 Ｔｉｐｋ ＝ ０ 为最小值，则当前状态 下不能向内核 Ｐｋ分派任务。 在一次调度过程中，调 度程序可能需要响应多个内核的调度请求，对于 ｜ ＴＬｋ ｜较小的内核，其 Ｌｋ较大，从而实现优先将任务 分配到负载较轻的内核，并进而达到负载均衡效果。 综上所述，任务优先级值的计算，是对等待时 间、通信开销和内核负载 ３ 个因素综合考量的过程， 其结果可能不是单一因素中最优的，但一定是综合 考虑全部 ３ 种因素后最优的选择。 ３ 算法实现 在上节中详细介绍了任务优先级的计算，本节 将介绍 ＳＴＤＳ 算法的具体实现过程。 为了使任务调度算法得到较理想的实现，ＳＴＤＳ 算法的研究基于以下假设条件： １）假设任务间的依赖关系固定不变； ２）同一内核上任务间通信开销忽略不计； ３）任务不可抢占。 系统运行时首先将任务初始化，构造 ＴＤＳ，由于 算法中大多计算只针对就绪任务，特别是任务分配 时，所以为了节约计算开销，算法初始化时会生成一 个就绪任务列表和一个等待任务列表。 当内核 Ｐｋ 任务队列长度｜ Ｔｌ ｋ ｜ ≤ｌ ｋ＿ｍｉｎ时，就向调度程序请求分 配任务，调度程序遍历就绪列表，计算相对于内核 Ｐｋ的优先级，选择优先级 Ｔｉｐ值最大的任务分配到 Ｐｋ 上，重复执行此过程，直到内核 Ｐｋ 任务队列长度 ｜ Ｔｌ ｋ ｜≥ｌ ｋ。 若同时有多个内核请求任务分配，调度 程序分配任务时需要响应这几个内核的请求，计算 优先级时需要计算相对于这几个内核的优先级，然 后取最大值作为最终优先级，调度程序选择优先级 最大的任务分配到对应的内核。 值得注意的是在动态调度过程中，为了保证数 据实时有效，ＳＴＤＳ 算法在每个任务分配完成或执行 结束时对数据进行更新。 当任务 Ｔｉ分配给内核 Ｐｋ 后，需要将任务 Ｔｉ对应数据项中的 Ｔｉｃ置为 ｋ，此时内 核 Ｐｋ负载也相应改变；当任务 Ｔｉ执行完成时，如果 任务 Ｔｊ依赖任务 Ｔｉ，需要将任务 Ｔｊ的 Ｔｉｄｎ值减 １，若 减 １ 后 Ｔｉｄｎ ＝ ０，将任务 Ｔｊ状态置为就绪态并从等待 列表移到就绪列表。 为了降低复杂度节省时间， ＳＴＤＳ 算法采用先记录再批量执行的方式，即在任务 执行期间暂时将完成的任务编号记录，在任务调度 程序执行时批量更新数据；如果任务 Ｔｉ执行完毕且 所有依赖 Ｔｉ的任务也执行完毕，就将任务 Ｔｉ的信息 从 ＴＤＳ 中删除，从而释放内存节省空间。 如果就绪列表为空，调度程序不会响应内核的 任务分配请求，当就绪列表和等待列表全为空时，说 明任务全部执行完毕，调度结束。 ＳＴＤＳ 算法实现步骤： Ｐｒｏｃｅｄｕｒｅ ＳＴＤＳ（ＳＭ，ＴＤＳ， ＰＬｉｓｔ，ＴＬｅｘｅ ） ／ ∗ＳＭ 表 示处理器内核系统；ＴＤＳ 是所有任务信息； ＰＬｉｓｔ 是需 要分配任务的内核列表， ＴＬｅｘｅ 是执行完毕但还未进 行信息更新的任务列表∗／ １）｛ｆｏｒ ｅａｃｈ Ｔｉ∈ ＴＬｅｘｅ ２） ｛ Ｔｉａ ［］←Ｔｉ； ３） ｆｏｒ ｅａｃｈ Ｔｊ∈Ｔｉａ ４） Ｔｊｄｎ←Ｔｊｄｎ －１； ／ ∗执行完毕的任务信息 更新，将其后继任务的依赖任务数量减一∗／ ｝ ／ ∗ ｅｎｄ ｆｏｒ ｅａｃｈ Ｔｉ∈ ＴＬｅｘｅ ∗／ ５）ＴＬｒｅａｄｙ［］←ＴＤＳ；／ ∗就绪任务放入就绪队列∗／ ６） ｆｏｒ ｅａｃｈ Ｔｉ∈ＴＬｒｅａｄｙ ７）｛ ｆｏｒ ｅａｃｈ Ｐｋ∈ ＰＬｉｓｔ ·３２８· 智 能 系 统 学 报 第 １０ 卷