Stack memory requirements of AUTOSAR/OSEK-compliant scheduling policies

Stack sharing between tasks may significantly reduce the amount of memory required in resource-constrained real-time embedded systems. Existing work on stack sharing mainly focused on stack sharing between tasks that neither leave any data on the stack from one instance to another nor suspend themselves, i.e. tasks with a so-called single-shot execution. In this paper, we consider stack memory requirements of AUTOSAR/OSEK-compliant scheduling policies for a mixed task set, consisting of so-called basic and extended tasks. Unlike basic tasks, that have a single-shot execution, extended tasks are allowed to leave data on the stack from one instance to another and to suspend themselves. We prove that minimizing the shared stack requirement for such a mixed task set is an NP-hard problem. We subsequently provide an heuristic-based algorithm to minimize stack usage of a mixed task set, and evaluate the algorithm through a case study of an implementation of an unmanned aerial vehicle. An extended version of the paper is available as technical report [5].