第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.第 １０ 卷第 ２ 期 智 能 系 统 学 报 Ｖｏｌ．１０ №．２ ２０１５ 年 ４ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｐｒ． ２０１５ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１５０３０１３ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１５０４１３．１５０５．００１．ｈｔｍｌ 基于动态任务调度的 ＳＴＤＳ 算法设计研究 刘正 （哈尔滨工程大学 计算机科学与技术学院，黑龙江 哈尔滨 １５０００１） 摘 要：任务调度是计算机多核处理器系统获得高性能的关键，而现有的多核任务调度算法研究，大多侧重于静态 调度下的算法优化和负载均衡，对动态调度及动态负载均衡研究较少。 针对动态调度，并结合异构多核的特点，提 出一种基于核负载均衡的动态任务调度算法 ＳＴＤＳ。 算法通过合理设定调度粒度，降低调度频率，从而减少调度消耗 时间；根据异构多核处理器各核处理性能的差异，设置内核负载上下限值，控制内核负载保持在同一水平，以达到负 载均衡效果。 算法依据等待时间长短、任务间通信大小和内核负载轻重因素对任务进行实时调度，并可通过实时因 子、负载因子等参数设置 ３ 种因素的影响比重，以满足系统的不同需求。 仿真实验显示，在内核数目较多的系统中， ＳＴＤＳ 算法更加高效，在保证任务处理速度的同时有较好负载均衡。 关键词：动态任务调度；负载均衡；调度粒度；等待时间；异构多核系统 中图分类号：ＴＰ３１６．４ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１５）０２⁃０３２４⁃０９ 中文引用格式：刘正． 基于动态任务调度的 ＳＴＤＳ 算法设计研究［Ｊ］． 智能系统学报， ２０１５， １０（２）： ３２４⁃３３２． 英文引用格式：ＬＩＵ Ｚｈｅｎｇ． Ｒｅｓｅａｒｃｈ ｏｎ ＳＴＤＳ ａｌｇｏｒｉｔｈｍ ｄｅｓｉｇｎｉｎｇ ｂａｓｅｄ ｏｎ ｄｙｎａｍｉｃ ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎ⁃ ｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１５， １０（２）： ３２４⁃３３２． Ｒｅｓｅａｒｃｈ ｏｎ ＳＴＤＳ ａｌｇｏｒｉｔｈｍ ｄｅｓｉｇｎｉｎｇ ｂａｓｅｄ ｏｎ ｄｙｎａｍｉｃ ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ ＬＩＵ Ｚｈｅｎｇ （Ｃｏｌｌｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｈａｒｂｉｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ， Ｈａｒｂｉｎ １５０００１， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｅｆｆｉｃｉｅｎｔ ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ ｉｓ ｔｈｅ ｋｅｙ ｆｏｒ ｍｕｌｔｉ⁃ｃｏｒｅ ｓｙｓｔｅｍｓ ｔｏ ａｃｈｉｅｖｅ ｈｉｇｈ ｐｅｒｆｏｒｍａｎｃｅ． Ｈｏｗｅｖｅｒ， ｍｏｓｔ ｏｆ ｔｈｅ ｅｘｉｓｔｉｎｇ ｍｕｌｔｉ⁃ｃｏｒｅ ｒｅｓｅａｒｃｈｅｓ ｏｎ ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｆｏｃｕｓ ｏｎ ａｌｇｏｒｉｔｈｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｎｄ ｌｏａｄ ｂａｌａｎｃｉｎｇ ｕｎｄｅｒ ｔｈｅ ｓｔａｔｉｃ ｓｃｈｅｄｕｌｉｎｇ ｒａｔｈｅｒ ｔｈａｎ ｄｙｎａｍｉｃ ｓｃｈｅｄｕｌｉｎｇ ａｎｄ ｄｙｎａｍｉｃ ｌｏａｄ ｂａｌａｎｃｉｎｇ． Ｓｃａｌａｂｌｅ ｔａｓｋ ｄｕｐｌｉｃａｔｉｏｎ ｂａｓｅｄ ｓｃｈｅｄｕｌｉｎｇ （ＳＴＤＳ） ｉｓ ａ ｎｅｗ ｄｙｎａｍｉｃ⁃ｂａｌａｎｃｅｄ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｃｏｒｅ ｌｏａｄ ｂａｌａｎｃｉｎｇ． ＳＴＤＳ ｗａｓ ｐｕｔ ｆｏｒ⁃ ｗａｒｄ ｓｐｅｃｉｆｉｃａｌｌｙ ｆｏｒ ｄｙｎａｍｉｃ ｓｃｈｅｄｕｌｉｎｇ ａｎｄ ｉｎｔｅｇｒａｔｉｎｇ ｔｈｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｍｕｌｔｉ⁃ｃｏｒｅ． Ｉｔ ｓｈｏｒｔｅｎｓ ｓｃｈｅｄｕｌｉｎｇ ｔｉｍｅ ｂｙ ｒｅａｓｏｎａｂｌｙ ｓｅｔｔｉｎｇ ｔｈｅ ｓｃｈｅｄｕｌｉｎｇ ｇｒａｎｕｌａｒｉｔｙ ａｎｄ ｒｅｄｕｃｉｎｇ ｔｈｅ ｆｒｅｑｕｅｎｃｙ ｏｆ ｓｃｈｅｄｕｌｉｎｇ． ＳＴＤＳ ｓｅｔｓ ｔｈｅ ｍａｘｉｍｕｍ ａｎｄ ｍｉｎｉｍｕｍ ｒａｎｇｅｓ ｏｆ ｔｈｅ ｋｅｒｎｅｌ ｌｏａｄ ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｄｉｆｆｅｒｅｎｔ ｐｒｏｃｅｓｓｉｎｇ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｅａｃｈ ｃｏｒｅ ｏｆ ｔｈｅ ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｍｕｌｔｉ⁃ｃｏｒｅ ｐｒｏｃｅｓｓｏｒ， ｔｈｅｒｅｆｏｒｅ ｃｏｎｔｒｏｌｌｉｎｇ ｔｈｅ ｃｏｒｅ ｌｏａｄ ａｔ ｔｈｅ ｓａｍｅ ｌｅｖｅｌ ａｎｄ ａｃｈｉｅｖｉｎｇ ｔｈｅ ｅｆｆｅｃｔ ｏｆ ｌｏａｄ ｂａｌａｎｃｅ． Ｔｈｅ ｗａｉｔ ｔｉｍｅ ｏｆ ｔａｓｋ ａｎｄ ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｂｅｔｗｅｅｎ ｔａｓｋｓ ａｎｄ ｋｅｒｎｅｌ ｌｏａｄ ｗｉｌｌ ｂｅ ｃｏｎｓｉｄ⁃ ｅｒｅｄ ｔｏｇｅｔｈｅｒ ｔｏ ｐｉｃｋ ｕｐ ｔｈｅ ｍｏｓｔ ａｐｐｒｏｐｒｉａｔｅ ｔａｓｋ ｄｕｒｉｎｇ ｓｃｈｅｄｕｌｉｎｇ． Ｔｈｅ ｉｍｐｏｒｔａｎｃｅ ｏｆ ｅａｃｈ ｅｌｅｍｅｎｔ ｃａｎ ｂｅ ａｄｊｕｓ⁃ ｔｅｄ ｂｙ ａｓｓｉｇｎｉｎｇ ａｎｏｔｈｅｒ ｖａｌｕｅ ｔｏ ｔｈｅ ｒｅａｌ⁃ｔｉｍｅ ｆａｃｔｏｒ ａｎｄ ｌｏａｄ ｆａｃｔｏｒ ｅｎａｂｌｉｎｇ ｉｔ ｔｏ ａｄａｐｔ ｔｏ ｖａｒｉｏｕｓ ｅｎｖｉｒｏｎｍｅｎｔ． Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｖｅｒｉｆｉｅｄ ｔｈａｔ ｔｈｅ ＳＴＤＳ ａｌｇｏｒｉｔｈｍ ｉｓ ｍｏｒｅ ｅｆｆｉｃｉｅｎｔ ｉｎ ｔｈｅ ｓｙｓｔｅｍ ｗｉｔｈ ｔｈｅ ｍｏｓｔ ｋｅｒｎｅｌｓ． Ｉｔ ａｌｓｏ ｋｅｅｐｓ ａ ｇｏｏｄ ｌｏａｄ ｂａｌａｎｃｅ ｗｈｉｌｅ ｍａｉｎｔａｉｎｉｎｇ ｔｈｅ ｓｐｅｅｄ ｏｆ ｔａｓｋ ｅｘｅｃｕｔｉｏｎ ｐｒｏｃｅｓｓｉｎｇ． Ｋｅｙｗｏｒｄｓ： ｄｙｎａｍｉｃ ｔａｓｋ ｓｃｈｅｄｕｌｉｎｇ； ｌｏａｄ ｂａｌａｎｃｉｎｇ； ｓｃｈｅｄｕｌｉｎｇ ｇｒａｎｕｌａｒｉｔｙ； ｗａｉｔｉｎｇ ｔｉｍｅ； ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｍｕｌｔｉ⁃ ｃｏｒｅ ｓｙｓｔｅｍ 收稿日期：２０１５⁃０３⁃０９． 网络出版日期：２０１５⁃０４⁃１３． 基金项目：国家自然科学基金资助项目（６１００３０３６）；中央高校基本科研 业务费专项资金资助项目（ＨＥＵＣＦ１００６０６）． 通信作者：刘正．Ｅ⁃ｍａｉｌ：ｌｉｕｚｈｅｎｇ５２８＠ ｈｒｂｅｕ．ｅｄｕ．ｃｎ． 动态任务调度可以根据运行的时情况动态 地将任务分配到各个内核上，由于需要实时地收 集、存储并分析状态信息，动态调度的实施有一