基于动态松弛时间回收的开销敏感节能实时调度算法

计算机工程与科学

基于动态松弛时间回收的开销敏感节能实时调度算法

张冬松1，王珏1，赵志峰1,吴飞2，孙宪坤2

（1.镇江船艇学院基础部,江苏镇江 212001;2.上海工程技术大学电子电气工程学院,上海 201620）

收稿日期:2016-04-01 修回日期:2016-06-17 出版日期:2016-08-25 发布日期:2016-08-25
基金资助:
国家自然科学基金（61402527,61272097）

An overhead-aware energy-efficient real-time scheduling algorithm based on dynamic slack reclamation

ZHANG Dong-song1，WANG Jue1，ZHAO Zhi-feng1，WU Fei2，SUN Xian-kun2

（1.Basic Department,Zhenjiang Watercraft College,Zhenjiang 212001;
2.College of Electronic and Electrical Engineering,Shanghai University of Engineering Science,Shanghai 201620,China）

Received:2016-04-01 Revised:2016-06-17 Online:2016-08-25 Published:2016-08-25

摘要/Abstract

摘要：

为适应实际系统中任务集的不断变化以及不可忽视状态切换开销的要求，针对多核多处理器系统中常见的周期任务模型，提出一种基于动态松弛时间回收的开销敏感节能实时调度算法DSROM，在每个TL面的初始时刻、任务提前完成时刻实现节能调度及动态松弛时间回收，在不违反周期任务集可调度性的基础上，达到实时约束与能耗节余之间的合理折衷。模拟实验结果表明，DSROM算法不仅保证了周期任务集的最优可调度性，而且当任务集总负载超过某一个值后，其节能效果整体优于现有方法，最多可节能近20%。

关键词: 动态松弛时间, 开销, 节能, 实时调度

Abstract:

To meet the changeable reality of task sets for the runtime system and needs of non-ignorable switching overhead for processor state, we propose an overhead-aware energy-efficient real-time scheduling algorithm called a dynamic slack reclamation based overhead-aware energy-efficient real-time scheduling in multiprocessor systems (DSROM) for periodic tasks deployed on multi-core and multiprocessor systems. The main idea of the algorithm is to implement energy-efficient scheduling for real-time tasks at the initial time of each TL plane, and to reclaim dynamic slack time at the earlier completion time of a periodic task in each TL plane. Consequently, the algorithm can obtain a reasonable tradeoff between real-time constraint and energy-saving while guaranteeing the optimal feasibility of periodic tasks. Extensive simulation results demonstrate that the DSROM can guarantee the optimal feasibility of periodic tasks and save more energy on average than the existing algorithms when the total workload of the system exceeds a threshold, saving energy by about 20% at most.

Key words: dynamic slack time, overhead, energy saving, real-time scheduling

张冬松1，王珏1，赵志峰1,吴飞2，孙宪坤2. 基于动态松弛时间回收的开销敏感节能实时调度算法[J]. 计算机工程与科学.

ZHANG Dong-song1，WANG Jue1，ZHAO Zhi-feng1，WU Fei2，SUN Xian-kun2. An overhead-aware energy-efficient real-time scheduling algorithm based on dynamic slack reclamation [J]. Computer Engineering & Science.

参考文献

［1］Chen J,Thiele L. Energy-efficient scheduling on homogeneous multiprocessor platforms ［C］∥Proc of the 25th ACM Symposium on Applied Computing,2010:542-549.
［2］Xu R,Zhu D, Rusu C, et al. Energy-efficient policies for embedded clusters［C］∥Proc of ACM SIGPLAN/SIGBED Conference on Languages,Compilers,and Tools for Embedded Systems,2005:1-10.
［3］Langen P,Juurlink B. Leakage-aware multiprocessor scheduling for low power［C］∥Proc of Parallel and Distributed Processing Symposium,2006:80-87.
［4］Huang H,Xia F, Wang J, et al. Leakage-aware reallocation for periodic real-time tasks on multicore processors［C］∥Proc of the 5th International Conference on Frontier of Computer Science and Technology,2010:85-91.
［5］Seo E,Jeong J,Park S,et al. Energy efficient scheduling of real-time tasks on multicore processors［J］. IEEE Transactions on Parallel and Distributed Systems,2008,19(11):1540-1552.
［6］Zhang D,Guo D, Chen F, et al. An energy-efficient multi-core real-time scheduling algorithm based on dynamic slack reclamation［J］. Journal of National University of Defense Technology, 2011,33(6): 7-16. (in Chinese)
［7］Zhu D. Reliability-aware dynamic energy management in dependable embedded real-time systems ［C］∥Proc of IEEE Real-time and Embedded Technology and Appl4ications Symposium,2006: 397-407.
［8］Ishihara T,Yasuura H. Voltage scheduling problems for dynamically variable voltage processors［C］∥Proc of the International Symposium on Low Power Electronics and Design,1998: 197-202.
［9］Funk S,Nadadur V. LRE-TL: An optimal multiprocessor algorithm for sporadic task sets ［C］∥Proc of Conference on Real-Time and Network Systems (RTNS),2009:159-168.
［10］Cho H,Ravindran B, Jensen E, et al. An optimal real-time scheduling algorithm for multiprocessors ［C］∥Proc of the 27th IEEE Real-Time System Symposium(RTSS),2006:101-110.
［11］Zhang D,Wu F, Chen F, et al. An overhead-aware optimal energy-efficient real-time scheduling algorithm on multiprocessors ［J］. Chinese Journal of Computers, 2012,35(6):1297-1312. (in Chinese)
［12］Funaoka K, Kato S, Yamasaki N. Energy-efficient optimal real-time scheduling on multiprocessors ［C］∥Proc of the 11th IEEE Symposium on Object Oriented Real-Time Distributed Computing (ISORC),2008:23-30.
［13］Bini E,Buttazzo G.C. Measuring the performance of schedulability tests ［J］. Journal of Real-Time Systems,2005,30(1-2):129-154.
［14］Nasri M,Fohler G, Kargahi M. A framework to construct customized harmonic periods for real-time systems［C］∥Proc of the 26th Euromicro Conference on Real-Time Systems (ECRTS),2014:211-220.
附中文参考文献：
［6］张冬松,郭得科,陈芳园,等. 多核系统中基于动态松弛时间回收的节能实时调度算法［J］. 国防科技大学学报,2011,33(6): 7-16.
［11］张冬松,吴飞,陈芳园,等. 开销敏感的多处理器最优节能实时调度算法［J］. 计算机学报,2012,35(6): 1297-1312.

[1]	叶琴, 陈才, 陈彪, 张坤. 基于某国产双路服务器的液冷散热性能实验研究[J]. 计算机工程与科学, 2023, 45(04): 607-612.
[2]	徐浩桐, 黄山, 孙国璋, 贺菲莉, 段晓东, . 面向云环境的Flink负载均衡策略[J]. 计算机工程与科学, 2022, 44(05): 779-787.
[3]	齐星云, 戴艺, 赖明澈, 常俊胜, 董德尊. 基于偏折路由的双环片上网络[J]. 计算机工程与科学, 2021, 43(03): 381-388.
[4]	衡红军, 戚馨桐. 考虑任务均衡的加油车动态调度问题[J]. 计算机工程与科学, 2020, 42(05): 923-930.
[5]	祝振凱1,2，黄传河1,2. 基于链路信息的卫星网络最优路径选择策略[J]. 计算机工程与科学, 2017, 39(03): 470-476.
[6]	顾鸿儒，孙连坤. 基于层次颜色Petri网的全感应控制交通信号灯建模与仿真[J]. 计算机工程与科学, 2016, 38(09): 1887-1892.
[7]	徐光宪，杨冬丽，高嵩，许春燕，金钰博. 联合编码开销与安全性能的网络编码优化方案[J]. 计算机工程与科学, 2016, 38(07): 1384-1390.
[8]	王菁，王岗，高晶，李寒，马倩. 面向高校教学云服务的虚拟机动态调度方法[J]. J4, 2015, 37(11): 2018-2024.
[9]	蔡钊，马林华，宋博，唐红. 基于ARIMA-ANN预测模型的能量感知路由算法[J]. J4, 2015, 37(06): 1064-1070.
[10]	赵新元. 无线传感器/反应器网络中反应节点优化重定位机制研究[J]. J4, 2015, 37(06): 1101-1108.
[11]	罗旭，吴晓军. 蚁群优化算法在WSN路由中的应用研究[J]. J4, 2015, 37(04): 740-746.
[12]	王盖，王永炎. 物联网环境下基于用户满意度的实时调度算法[J]. J4, 2015, 37(01): 184-190.
[13]	杨明英，雷斐，董德尊，沈胜宇，庞征斌. 一种新型混合互连网络拓扑结构的分析与优化[J]. J4, 2014, 36(12): 2400-2409.
[14]	王楠，孟庆丰. 节点位置固定的线性无线传感器网络节能路由[J]. J4, 2014, 36(11): 2087-2093.
[15]	王东，邓好. 优化目标可变的容错三维拓扑控制算法[J]. J4, 2014, 36(05): 842-848.