一种基于功耗敏感的实时调度算法的研究
|
摘要
随着电子器件的快速发展,嵌入式设备应用日益广泛。嵌入式系统功能越来越复杂,能耗随之大幅度增加并制约了嵌入式系统的发展。因此,降低系统功耗,节约能量成为嵌入式系统中一个重要的研究方向。
大多现有嵌入式处理器至少支持三种不同工作模式：运行模式,空闲模式和休眠模式,处理器在休眠模式的能量消耗远小于另外两种模式。Rowe等人提出了ESRHS节能调度算法,这种算法是在速率单调算法的基础上增加虚拟的休眠任务,消除空闲模式,使得处理器只需维护运行和休眠两种工作模式,从而降低系统功耗。然而,作者没有考虑模式切换需要消耗能量,ESRHS算法不符合实际。
本文针对ESRHS算法的不足做了改进并对其进行扩展。首先,详细分析了ESRHS算法中可调度测试条件“悲观性”的原因,提出了一种新的可调度测试条件,降低测试条件悲观性。其次,改进ESRHS算法。通过考虑模式切换存在系统开销,本文提出的算法减少了休眠任务的切换次数,达到更好的节能效果。第三,扩展ESRHS算法。提出一种更加高效的动态节能调度算法,不但节省更多的能量,而且能够处理休眠任务执行时间较长的情况,从而,该算法适用于更多类型的CPU。最后,进行了大量的模拟实验。本文的算法明显优于现有的节能算法,较ESRHS算法多节约17%-65%的功耗。
With the rapid development of electronic devices, embedded products are widely-used. Embedded systems are more and more complicated, and the increase of the energy consumption restricts the development of embedded systems. So, reducing power consumption and saving energy become an important research direction in embedded systems.
Many modern embedded processors at least have three operating modes:active mode, idle mode and sleep mode. A processor consumes much less energy in the sleep mode than that in other two modes. Rowe proposed an Energy Saving RateHarmonized Scheduling algorithm for energy saving which is based on rate monotonic algorithm and adding a virtual sleep task, through clustering task execution and lumping idle duration, and the processor only needs to support two modes and saving energy. However, the author didn't take into account of the energy consumptions of switching modes, the Energy Saving RateHarmonized Scheduling algorithm is not realistic.
This paper improves and extends the ESRHS algorithm. First, we analyse the reasons of the pessimism of the pessimism test of ESRHS algorithm and propose a new schedulabilty test which can reduce the pessimism. And then we improve the ESRHS algorithm. Thinking of the overhead of switching modes, we propose a better algorithm than ESRHS algorithm which can reduce the numbers of switching modes and saving energy. Third, we expand the ESRHS algorithm and propose another effect dynamic energysaving scheduling algorithm which can process a long execution time of sleep task and save more energy. So the algorithm we proposed in this paper is fit for more types of the CPU. At last we do plenty of simulation and the results indicate that our algorithm can save more power consumption by 17%-65%.
大多现有嵌入式处理器至少支持三种不同工作模式：运行模式,空闲模式和休眠模式,处理器在休眠模式的能量消耗远小于另外两种模式。Rowe等人提出了ESRHS节能调度算法,这种算法是在速率单调算法的基础上增加虚拟的休眠任务,消除空闲模式,使得处理器只需维护运行和休眠两种工作模式,从而降低系统功耗。然而,作者没有考虑模式切换需要消耗能量,ESRHS算法不符合实际。
本文针对ESRHS算法的不足做了改进并对其进行扩展。首先,详细分析了ESRHS算法中可调度测试条件“悲观性”的原因,提出了一种新的可调度测试条件,降低测试条件悲观性。其次,改进ESRHS算法。通过考虑模式切换存在系统开销,本文提出的算法减少了休眠任务的切换次数,达到更好的节能效果。第三,扩展ESRHS算法。提出一种更加高效的动态节能调度算法,不但节省更多的能量,而且能够处理休眠任务执行时间较长的情况,从而,该算法适用于更多类型的CPU。最后,进行了大量的模拟实验。本文的算法明显优于现有的节能算法,较ESRHS算法多节约17%-65%的功耗。
With the rapid development of electronic devices, embedded products are widely-used. Embedded systems are more and more complicated, and the increase of the energy consumption restricts the development of embedded systems. So, reducing power consumption and saving energy become an important research direction in embedded systems.
Many modern embedded processors at least have three operating modes:active mode, idle mode and sleep mode. A processor consumes much less energy in the sleep mode than that in other two modes. Rowe proposed an Energy Saving RateHarmonized Scheduling algorithm for energy saving which is based on rate monotonic algorithm and adding a virtual sleep task, through clustering task execution and lumping idle duration, and the processor only needs to support two modes and saving energy. However, the author didn't take into account of the energy consumptions of switching modes, the Energy Saving RateHarmonized Scheduling algorithm is not realistic.
This paper improves and extends the ESRHS algorithm. First, we analyse the reasons of the pessimism of the pessimism test of ESRHS algorithm and propose a new schedulabilty test which can reduce the pessimism. And then we improve the ESRHS algorithm. Thinking of the overhead of switching modes, we propose a better algorithm than ESRHS algorithm which can reduce the numbers of switching modes and saving energy. Third, we expand the ESRHS algorithm and propose another effect dynamic energysaving scheduling algorithm which can process a long execution time of sleep task and save more energy. So the algorithm we proposed in this paper is fit for more types of the CPU. At last we do plenty of simulation and the results indicate that our algorithm can save more power consumption by 17%-65%.
引文
1. 桑楠,嵌入式系统原理及应用开发技术[M],北京：北京航空航天大学出版社,2008,17-20.
2.李亚伯,数字电路与系统[M],北京：电子工业出版社,1998,322-325.
3.2009 国际节能电子新技术研讨会[EB/OL] http://www.epc.com.cn/meeting/2009/save/save.htm,2009-01-05.
4. Aydin H, Melhem R, Mosse D, et al. Power aware scheduling for periodic real time tasks [J]. IEEE Transactions on Computers,2004,53(5):584-600.
5. Liu J W S. Real-Time systems [M], Beijing:Higher Education Press,2002,26-68.
6. Bellaouar A, Elmasry M I. Low-power Digital VLSI Design:Circuits and Systems [M], Boston:Kluwer Academic Publishers,1995,178-181.
7. Small C H. Shrinking devices put the squeeze on system packaging [J], EDN.1994, 39(4):41-54.
8. Intel, Microsoft, Toshiba. Advanced Configuration and Power Interface Specification. Revision [M],1996,176-185.
9. Intel, Microsoft, Toshiba. Advanced Configuration and Power Interface Specification Revision 2.0b [M].2002,98-105.
10. Rowe A, Lakshmanan K, Zhu H, et al. Rate-Harmonized Scheduling for Saving Energy [A]. In Real-Time Systems Symposium [C],2008,113-122.
11. Burchard A, Liebeherr J, Oh Y, et al. New strategies for assigning real-time tasks to multiprocessor systems [J]. IEEE Trans. On Computers,1995,44(12):1429-1442.
12. Liu C L, Layland J W. Scheduling algorithms for multiprogramming in a hard real-time environment [J]. Journal of ACM,1973,20(1):174-189.
13. Lehoczky J, Ding Y, Sha L. The rate monotonic scheduling algorithm:Exact characterization and average case behavior [A]. In Proc. of the 10th IEEE Real-Time Systems Symp [C],1989,166-171.
14. Han C C, Lin K J, Hou C J. Distance constrained scheduling and its anplcations to real-time systems [J]. IEEE Trans.on Computers,1996,45(7):814-826.
15. Han C C, Tyan H. A better polynomialtime schedulability test for real-time fixed priority scheduling algorithms [A]. In:Proc. of the 18th IEEE Real-Time Systems Symp[C].1997,36-45.
16. LeungJ.Y.T, Whitehead J. On the Complexity of Fixed priority scheduling of Periodic Real-time Tasks [J], Performance Evaluation,1982,2(4):237-250.
17. Audsley N C. Deadline Monotomonic Seheudlnig [A], YCS146, Technical Report of Department of Computer Science, University of York [C],1990,15-20.
18. Audsley N C, Burns A, Richardson M F, et al. Hard Real-time Scheduling:the Deadline Monotonic Approach [A], Proceedings of the 8th RTOSS [C],1991, 125-133.
19. Klaus H. Kim G, Arne S. Formal Verification of a Power Controller Using the Real-Time Model Checker Uppaal, Formal Methods for Real-Time and Probabilistic Systems[M], Springer Berlin Heidelberg,1999,277-298.
20. Mok, AK. Fundamental design problems of distributed systems for hard real-time environment [D], Ph.D. thesis MIT,1983,78-90.
21. Joseph M, Pandya P. Finding Response Times in a Real-Time System [J]. The Computer Journal,1986,29(5):390-395.
22. Tindell K W. An Extensible Approach for Analysing Fixed Priority Hard Real-Time Tasks [M]. Department of Computer Science, University of York, UK,1992,39-50.
23. Gerd B, Alexandre D, Kim G L. A tutorial on UPPaal [EB/OL]. http://www.uppaal.com,2007-09-08.
24. Sprunt B, Sha L, Lehoczky J. Scheduling Sporadic and Aperiodic Events in a Hard Real-Time System [M], CMU/SEI89TR11 Carnegie Mellon University,1989,
153-162.
25. Pering T, Brodersen R. Energy efficient voltage scheduling for real-time operating systems [A]. In Proceedings of the 4th IEEE Real-Time Technology and Applications Symposium RTAS98, Work in Progress Session [C],1998,138-142.
26. Lu Z, Zhang Y, Stan M, et al. Procrastinating voltage scheduling with discrete frequency sets [A]. In Proceedings of the conference on Design, automation and test in Europe, Proceedings [C],2006,456-461.
27. Sha L., Rajkumar R, Lehoczky J P. Priority inheritance protocols:An approach to realtime synchronization [J], IEEE Transactions on Computers,1990,39(9): 1175-1185.
28. Goraczko M, Liu J, Lymberopoulos D, et al. Energy optimal software partitioning in heterogeneous multiprocessor embedded systems [A]. In Design Automation Conference[C],2008. DAC 2008.45th ACM/IEEE,2008,191-196.
29. Aydin H, Yang Q. Energy responsiveness tradeoffs for real-time systems with mixed workload [A]. In 10th IEEE Real-Time and Embedded Technology and Applications Symposium [C],2004, Proceedings. RTAS 2004,74-83.
30. Weiser M, Welch B, Demers A, et al. Scheduling for reduced CPU energy [J]. KLUWER INTERNATIONAL SERIES IN ENGINEERING AND COMPUTER SCIENCE,1996,449-472.
31. Saksena M, Wang Y. Scalable real-time system design using preemption thresholds [A]. In Proceedings of the IEEE RTSS [C], IEEE Computer Society Press,2000, 25-34.
32. Abbott R, GarciaMolina H. Scheduling real-time transactions:A performance evaluation [J]. ACM Transactions on Database Systems,1992,17(3):513-560.
33. Andersson B, Jonsson J. Preemptive multiprocessor scheduling anomalies [A], In Proceedings of the 16th International Parallel and Distributed Processing Symposium [C],2002,12-19.
34. Lehoczky J. Fixed priority scheduling of periodic task sets with arbitrary deadlines [A]. In Proceedings of the Real-Time Systems Symposium [C],1990,201-209.
35. Thorsten G, Rachel C. Analysis of Scheduling Behaviour using Generic Timed Automata [J]. Electronic Notes in Theoretical Computer Science,2001,42:143-157.
36. Libor W, Zdenek H. Analysis of Real Time Operating System Based Applications [J]. FORMATS,2003,219-233.
37. Alexandre D, Wang Y. Modelling and Analysis of a Commercial Field Bus Protocol [A], In Proceedings of the 12th Euromicro Conference on Real-Time System [C], 2000,165-172.
38. Torsten K, Iversen, Kare J. ModelChecking Real-Time Control Programs [A], In Proceedings of the 12th Euromicro Conference on RealTime Systems [C],2000, 147-155.
39. Edmund M C, Orna G, David E L. Verification Tools for Finite State Concurrent Systems [A], A Decade of Concurrency, Reflections and Perspectives, REX School/Symposium [C],1993,124-175.
40. Holzmann G. The SPIN Model Checker, Primer and Reference Manual [M]. Addison Wesley,2004,135-143.
2.李亚伯,数字电路与系统[M],北京：电子工业出版社,1998,322-325.
3.2009 国际节能电子新技术研讨会[EB/OL] http://www.epc.com.cn/meeting/2009/save/save.htm,2009-01-05.
4. Aydin H, Melhem R, Mosse D, et al. Power aware scheduling for periodic real time tasks [J]. IEEE Transactions on Computers,2004,53(5):584-600.
5. Liu J W S. Real-Time systems [M], Beijing:Higher Education Press,2002,26-68.
6. Bellaouar A, Elmasry M I. Low-power Digital VLSI Design:Circuits and Systems [M], Boston:Kluwer Academic Publishers,1995,178-181.
7. Small C H. Shrinking devices put the squeeze on system packaging [J], EDN.1994, 39(4):41-54.
8. Intel, Microsoft, Toshiba. Advanced Configuration and Power Interface Specification. Revision [M],1996,176-185.
9. Intel, Microsoft, Toshiba. Advanced Configuration and Power Interface Specification Revision 2.0b [M].2002,98-105.
10. Rowe A, Lakshmanan K, Zhu H, et al. Rate-Harmonized Scheduling for Saving Energy [A]. In Real-Time Systems Symposium [C],2008,113-122.
11. Burchard A, Liebeherr J, Oh Y, et al. New strategies for assigning real-time tasks to multiprocessor systems [J]. IEEE Trans. On Computers,1995,44(12):1429-1442.
12. Liu C L, Layland J W. Scheduling algorithms for multiprogramming in a hard real-time environment [J]. Journal of ACM,1973,20(1):174-189.
13. Lehoczky J, Ding Y, Sha L. The rate monotonic scheduling algorithm:Exact characterization and average case behavior [A]. In Proc. of the 10th IEEE Real-Time Systems Symp [C],1989,166-171.
14. Han C C, Lin K J, Hou C J. Distance constrained scheduling and its anplcations to real-time systems [J]. IEEE Trans.on Computers,1996,45(7):814-826.
15. Han C C, Tyan H. A better polynomialtime schedulability test for real-time fixed priority scheduling algorithms [A]. In:Proc. of the 18th IEEE Real-Time Systems Symp[C].1997,36-45.
16. LeungJ.Y.T, Whitehead J. On the Complexity of Fixed priority scheduling of Periodic Real-time Tasks [J], Performance Evaluation,1982,2(4):237-250.
17. Audsley N C. Deadline Monotomonic Seheudlnig [A], YCS146, Technical Report of Department of Computer Science, University of York [C],1990,15-20.
18. Audsley N C, Burns A, Richardson M F, et al. Hard Real-time Scheduling:the Deadline Monotonic Approach [A], Proceedings of the 8th RTOSS [C],1991, 125-133.
19. Klaus H. Kim G, Arne S. Formal Verification of a Power Controller Using the Real-Time Model Checker Uppaal, Formal Methods for Real-Time and Probabilistic Systems[M], Springer Berlin Heidelberg,1999,277-298.
20. Mok, AK. Fundamental design problems of distributed systems for hard real-time environment [D], Ph.D. thesis MIT,1983,78-90.
21. Joseph M, Pandya P. Finding Response Times in a Real-Time System [J]. The Computer Journal,1986,29(5):390-395.
22. Tindell K W. An Extensible Approach for Analysing Fixed Priority Hard Real-Time Tasks [M]. Department of Computer Science, University of York, UK,1992,39-50.
23. Gerd B, Alexandre D, Kim G L. A tutorial on UPPaal [EB/OL]. http://www.uppaal.com,2007-09-08.
24. Sprunt B, Sha L, Lehoczky J. Scheduling Sporadic and Aperiodic Events in a Hard Real-Time System [M], CMU/SEI89TR11 Carnegie Mellon University,1989,
153-162.
25. Pering T, Brodersen R. Energy efficient voltage scheduling for real-time operating systems [A]. In Proceedings of the 4th IEEE Real-Time Technology and Applications Symposium RTAS98, Work in Progress Session [C],1998,138-142.
26. Lu Z, Zhang Y, Stan M, et al. Procrastinating voltage scheduling with discrete frequency sets [A]. In Proceedings of the conference on Design, automation and test in Europe, Proceedings [C],2006,456-461.
27. Sha L., Rajkumar R, Lehoczky J P. Priority inheritance protocols:An approach to realtime synchronization [J], IEEE Transactions on Computers,1990,39(9): 1175-1185.
28. Goraczko M, Liu J, Lymberopoulos D, et al. Energy optimal software partitioning in heterogeneous multiprocessor embedded systems [A]. In Design Automation Conference[C],2008. DAC 2008.45th ACM/IEEE,2008,191-196.
29. Aydin H, Yang Q. Energy responsiveness tradeoffs for real-time systems with mixed workload [A]. In 10th IEEE Real-Time and Embedded Technology and Applications Symposium [C],2004, Proceedings. RTAS 2004,74-83.
30. Weiser M, Welch B, Demers A, et al. Scheduling for reduced CPU energy [J]. KLUWER INTERNATIONAL SERIES IN ENGINEERING AND COMPUTER SCIENCE,1996,449-472.
31. Saksena M, Wang Y. Scalable real-time system design using preemption thresholds [A]. In Proceedings of the IEEE RTSS [C], IEEE Computer Society Press,2000, 25-34.
32. Abbott R, GarciaMolina H. Scheduling real-time transactions:A performance evaluation [J]. ACM Transactions on Database Systems,1992,17(3):513-560.
33. Andersson B, Jonsson J. Preemptive multiprocessor scheduling anomalies [A], In Proceedings of the 16th International Parallel and Distributed Processing Symposium [C],2002,12-19.
34. Lehoczky J. Fixed priority scheduling of periodic task sets with arbitrary deadlines [A]. In Proceedings of the Real-Time Systems Symposium [C],1990,201-209.
35. Thorsten G, Rachel C. Analysis of Scheduling Behaviour using Generic Timed Automata [J]. Electronic Notes in Theoretical Computer Science,2001,42:143-157.
36. Libor W, Zdenek H. Analysis of Real Time Operating System Based Applications [J]. FORMATS,2003,219-233.
37. Alexandre D, Wang Y. Modelling and Analysis of a Commercial Field Bus Protocol [A], In Proceedings of the 12th Euromicro Conference on Real-Time System [C], 2000,165-172.
38. Torsten K, Iversen, Kare J. ModelChecking Real-Time Control Programs [A], In Proceedings of the 12th Euromicro Conference on RealTime Systems [C],2000, 147-155.
39. Edmund M C, Orna G, David E L. Verification Tools for Finite State Concurrent Systems [A], A Decade of Concurrency, Reflections and Perspectives, REX School/Symposium [C],1993,124-175.
40. Holzmann G. The SPIN Model Checker, Primer and Reference Manual [M]. Addison Wesley,2004,135-143.