Real-time Task Assignment in Rechargeable Multiprocessor Systems

This paper introduces the scheduling of frame-based real-time tasks in partitioning schemes for multiprocessor systems powered by rechargeable batteries. In frame-based real-time systems, a set of tasks must execute in a frame, and the whole frame is repeated. This system model is widely used in real-time communication, real-time imaging and a lot of other real-time/embedded systems. Nowadays, many of these systems are powered by rechargeable batteries. Scheduling real-time tasks on these rechargeable systems is an important yet largely ignored issue. The problem for uniprocessor systems had been studied in [1], in which an algorithm of complexity O(N) was proposed for determining the feasibility of the task set. However, it poses a challenge when doing so in a rechargeable multiprocessor system considering different characteristics of the batteries. In this paper, we first show this problem to be NP-Hard, and then propose efficient algorithms to overcome it. The simulation results have shown that our algorithms exhibit very good behaviors and they can be considered as solutions to the problem.