隨著應用程式的複雜化及運算能力的增加，在嵌入式系統中省電的設計已經是一個相當重要的議題，這個情況在由電池供電的裝置上尤其明顯。因為要同時兼顧即時排程及省電是一個NP-hard的問題，因此到目前為止都還沒有一個最佳解。而許多相關的研究大多使用以RM為基礎的方法來達到省電的效果，但是在每個任務中工作間的距離將會不固定，而這樣的現象會造成即時系統可預測度的下降。因此若是我們改用時輪排程模型將可以解決這些問題。根據之前的研究，時輪排程演算法是應用於解決有時距限制任務集的問題。也因為倍數關係的特性，每個任務中工作間的距離將會固定不變，進而提高了系統的可預測度。在本篇論文中，我們討論了將時輪排程演算法應用在功率知曉即時排程裡的優點，以及它能夠容易地應用到不同的省電技術上。在實驗中我們得知在應用了時輪排程演算法之後，在任務中需要重新排程的時間點減少了，而功率知曉即時排程法使用時輪排程模式能夠獲得很多好處，並且能有效地省電。

As applications become increasingly sophisticated and computing power increases, energy consumption is now a critical design issue in embedded systems, especially in battery-operated systems. However, there is still no optimal solution, because the real-time scheduling problem with power optimization constraints is NP-hard. Many related works use RM-based heuristic to obtain more power saving, but the distance of jobs in each tasks is irregular, which decreases the system predictability. Fortunately, pinwheel model can overcome
these di±culties. Based on previous work, pinwheel algorithm is applied to solve scheduling problem on distance constrained task set. With the nature of harmonic numbers, the temporal distance of each tasks are ‾xed, and predictability is also increased. In this paper, we discuss the advantages of applying
pinwheel model to power-aware real-time scheduling, and show that pinwheel model is easily applied to various power-aware techniques. Simulations show that by the help of pinwheel algorithm, rescheduling points of a given task set is massively reduced, and the power-aware real-time scheduling bene‾ts from
pinwheel model with signi‾cant reduction in energy consumption.

1 Introduction
2 Background
2.1 Real-Time Scheduling Algorithm
2.1.1 Rate Monotonic
2.1.2 Pinwheel Model
2.2 DVS and DFS
2.3 Power-Aware Real-Time Scheduling Algorithm
2.3.1 ccRM
2.3.2 LPFPS
3 Power-Aware Real-Time Scheduling Algorithm using Pinwheel Model
3.1 Bene‾t of using Pinwheel Model
3.2 Retain Original Period in Pinwheel Model
3.3 POP-G
3.4 POP-LP
4 Simulation Result
5 Conclusion and Future Work
Bibliography

[1] N. AbouGhazaleh, D. Mosse, B. Childers, R. Melhem, and Matthew Craven. Collaborative operating system and compiler power management for real-time applications. In IEEE Real-Time Embedded Technology and Applications Symposium (RTAS), 2003.
[2] T. D. Burd and R. W. Brodersen. Energy e±cient CMOS microprocessor design. In Hawaii Intel Conference System Sciences, pages 288{297,January 1995.
[3] A. Chandrakasan, S. Sheng, and R. Brodersen. Low-power cmos digital design. IEEE Journal of Solid-State Circuit, 27(4):473{484, April 1992.
[4] K. Chen and P. Muhlethaler. A scheduling algorithm for tasks described by time value function. Journal of Real-Time Systems, 10(3):293{312, May 1996.
[5] Pai H. Chou, Jinfeng Liu, Dexin Li, and Nader Bagherzadeh. Impacct:Methodology and tools for power-aware embedded systems. In Design Au-tomation For Embedded Systems, Special Issue on Design Methodologies and Tools for Real-Time Embedded Systems, April 2002.
[6] Thomash H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction To Algorithms, Second Edition. The Mit Press,Cambridge, Massachusetts London, England, 2001.
[7] Bini. E., Buttazzo. G.C., and Buttazzo. G.M. Rate monotonic analysis:the hyperbolic bound. IEEE Transactions on Computers, 52:933{942, Jul 2003.
[8] R. Ernst and W. Ye. Embedded program timing analysis based on path clustering and architecture classi‾cation. In DIEEE/ACM International Conference on Computer-Aided Design, pages 598{604, 1997.
[9] T.M. Ghazalie and T.P. Baker. Aperiodic servers in a deadline scheduling environment. Real-Time Systems, 9:21{36, 1995.
[10] Kinshuk Govil, Edwin Chan, and Hal Wasserman. Comparing algorithm for dynamic speed-setting of a low-power cpu. In ACM International Conference on Mobile Computing and Networking, pages 13{25, 1995.
[11] Kinshuk Govil, Edwin Chan, and Hal Wasserman. Comparing algorithm for dynamic speed-setting of a low-power CPU. In ACM International Conference on Mobile Computing and Networking, pages 13{25, 1995.
[12] C.-C. Han and K.J. Lin. Scheduling jobs with temporal consistency constraints. In Proc. of the 6th IEEE Workshop on Real-Time Operating Systems and Software, pages 18{23, May 1989.
[13] Ching-Chih Han and Kwei-Jay Lin. Scheduling distance-constrained real-time tasks. In Proc. IEEE Real-Time Systems Symposium, pages 300{308,December 1992.
[14] R. Holte, A. Mok, L. Rosier, I. Tulchinsky, and D. Varvel. The pinwheel:A real-time scheduling problem. In Proc. of the 22nd Hawaii International Conference on System Science, pages 693{702, January 1989.
[15] Advanced Micro Devices. Internet homepage. http://www.amd.com/us-en/. 2004.
[16] Intel Corporation. Internet homepage. http://www.intel.com/index.htm.2004.
[17] Transmeta Corporation. Internet homepage. http://www.transmeta.com/index.html. 2004.
[18] I. Hong, G. Qu, M. Potkonjak, and M. Srivastava. Synthesis techniques for low-power hard real-time systems on variable voltage processors. In proceedings of the IEEE Real-Time systems Symposium, 1998.
[19] C. L. Liu and J. Layland. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of the ACM, 10(1):46{61, 1973.[20] Jane W.S. Liu. Real-Time Systems. Prentice Hall, 2000.
[21] Klein. M.H., Lehoczky. J.P., and Rajkumar. R. Rate-monotonic analysis for real-time industrial computing. IEEE Transactions on Computers, 27:24{33, Jan 1994.
[22] Unsal. O.S. and Koren. I. System-level power-aware design techniques in real-time systems. Proceddings of the IEEE, 91:1055{1069, Jul 2003.
[23] Huang. S., Chen. C., Ahmadi. M., and Mokrian. P. An optimal variable voltage scheduling. In Circuits and Systems, 2002. MWSCAS-2002. The 2002 45th Midwest Symposium on, pages I { 479{82, 2002.
[24] Youngsoo Shin and Kiyoung Choi. Power conscious ‾xed priority scheduling for hard real-time systems. In Design Automation Conference, pages 134{139, 1999.
[25] Osman S. Unsal and Israel Koren. System-level power-aware design tech-niques in real-time systems. Proceedings of the IEEE, 91(7):1055{1069,July 2003.
[26] Mark Weiser, Brent Welch, Alan J. Demers, and Scott Shenker. Scheduling for reduced cpu energy. In Operating Systems Design and Implementation, pages 13{23, 1994.[27] Mark Weiser, Brent Welch, Alan J. Demers, and Scott Shenker. Scheduling for reduced CPU energy. In Operating Systems Design and Implementation, pages 13{23, 1994.
[28] Chih wen Hsueh and Kwei-Jay Lin. Scheduling real-time systems with end-to-end timing constraints using the distributed pinwheel model. IEEE Transactions on Computers (SCI), 50(1), January 2001.http://www.cs.ccu.edu.tw/ chsueh/papers/DSr.ps.
[29] F. Yao, A. Demers, and S.Shankar. A scheduling model for reduced cpu energy. In IEEE Annual Foundations of Computer Science, pages 374{382,1995.