Exploiting Gaps in Fixed-Priority Preemptive Schedules for Task Insertion

Thaden, Eike and Lipskoch, Henrik and Metzner, Alexander and Stierand, Ingo
Proceedings of the 16th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)
This paper addresses the problem of assigning tasks to embedded control units. The units are considered to be connected via a bus, and tasks may already be deployed onto the units. To save costs, the objective is to insert as many new tasks onto the system as possible. In this setting, to support early design decisions,we present an approximative and fast pre-analysis of the system. We introduce spare-time analysis and the analysis of maximal allowed worst-case execution time to simplify the problem and to achieve a fast solving algorithm, which we implement as mixed-integer linear problem.We conduct experiments to investigate the scalability of the approach with the result that for inputsizes of up to 160 tasks with up to 50\% not-yet-deployed tasks a solution is found in many cases within reasonable time, our machine needs in the average case 150s. With a reference example, taken from literature, we compare our approach with a similar method and show that our approach is faster.
08 / 2010
SPES 2020
Software Plattform Embedded Systems 2020