Real-time scheduling algorithms for maximum utilization of secondary battery in portable devices with discrete frequency control
✍ Scribed by Yukikazu Nakamoto; Yoshihiro Tsujino; Nobuki Tokura
- Publisher
- John Wiley and Sons
- Year
- 2002
- Tongue
- English
- Weight
- 352 KB
- Volume
- 33
- Category
- Article
- ISSN
- 0882-1666
- DOI
- 10.1002/scj.1112
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
The spread of portable devices has increased the importance of low‐power energy techniques. The authors have already proposed a real‐time scheduling algorithm which maximizes the utilization time of the secondary battery while preserving deadlines of real‐time tasks with arbitrary frequency control. This paper addresses a scheduling problem which maximizes the utilization time of the secondary battery with discrete frequency control. First, a decision problem corresponding to the scheduling problem is NP‐complete when the frequency can be changed on task switching. Second, when the frequency can be changed at an arbitrary time we propose an optimal scheduling algorithm which maximizes utilized time of the secondary battery under preserving a deadline of real‐time tasks, and demonstrate the correctness of the algorithm and its computation complexity. For each arrival task, the computation complexity of the algorithm is O(n) in general, where n is the number of tasks awaiting execution, and is O(1) in the amortized analysis when each task arrives in the order of its deadline. © 2002 Scripta Technica, Syst Comp Jpn, 33(3): 41–51, 2002