The Optimality of PFPasap Algorithm for Fixed-Priority Energy-Harvesting Real-Time Systems

The paper addresses the real-time fixed-priority scheduling problem for battery-powered embedded systems whose energy storage unit is replenished by an environmental energy source. In this context, a task may meet its deadline only if its cost of energy can be satisfied early enough. Hence, a scheduling policy for such a system should account for properties of the source of energy, capacity of the energy storage unit and tasks cost of energy. Classical fixed-priority schedulers are no more suitable for this model. Based on these motivations, we propose PFP_ASAP an optimal scheduling algorithm that handles both energy and timing constraints. Furthermore, we state the worst case scenario for non concrete task sets a non concrete task set is a set of real-time tasks whose offsets are known only at run-time scheduled with this algorithm and build a necessary and sufficient feasibility condition for non concrete task sets. Moreover, a minimal bound of the storage unit capacity that keeps a task set schedulable with PFP_ASAP is also proposed. Finally, we validate the proposed theory with large scale simulations and compare our algorithm with other existing ones.