Energy-Efficient Real-Time Scheduling Algorithm with Accrual Utility under Energy Bounds

This paper presents an energy-efficient scheduling algorithm with accrual utility in battery-powered embedded real-time systems. The real-time tasks considered here synchronize to access the shared resources in a mutually exclusive manner. Under these constraints, the goal of a scheduling algorithm is to yield more utility within a supply of limited energy, while satisfying the timeliness and task synchronization requirements. We propose a two-step energy-efficient algorithm (TSEEA), which consists of two phases: a static algorithm, which runs offline and achieves the static execution speeds of all tasks under conservative conditions; and a dynamic one, which strives to release/reclaim slack times and to effectively tune the executing speeds of candidate task in a timely manner by synthesizing the static information and dynamic behaviors of performance demands at runtime. Compared with other algorithms, it is guaranteed that any task can meet its deadline constraint by our approach if the system energy supply is sufficient. Consequently, our algorithm can fully exploit the limited energy supply while yielding a high utility to the system. Further, our algorithm tries to reduce the time complexity. The experiments validate our analytical results and demonstrate that the proposed algorithm outperforms other existing algorithms in terms of accrual utility.