TY - GEN
T1 - Semi-Extended Tasks
T2 - 39th IEEE Real-Time Systems Symposium (RTSS)
AU - Dietrich, Christian
AU - Lohmann, Daniel
N1 - Funding information:
The authors thank the anonymous reviewers for their feedback. Furthermore, we thank Stefan Bader and Roman Sommer for the fruitful discussions about the initial implementation. This work has been supported by the German Research Foundation (DFG) under the grants no. LO 1719/4-1 and SFB/TR 89 (“Invasic”), Project C1.
PY - 2019/1/7
Y1 - 2019/1/7
N2 - Memory is an expensive and, therefore, limited resource in deeply embedded real-time systems. Thread stacks substantially contribute to the RAM requirements. To reduce the system's worst-case stack consumption (WCSC), it is state of the art to exploit thread-level preemption constraints to let multiple threads share the same stack. However, deriving a tight, yet correct bound for the shared stack is a difficult undertaking and stack sharing is currently restricted to run-to-completion threads, which are preemptable, but cannot block (i.e., passively wait for an event) at run time. With semi-extended tasks (SETs), we propose a solution for efficient stack sharing among blocking and non-blocking threads on the system level. For this, we refine the stack-sharing granularity from the thread to function level. We provide an efficient intra-thread stack-switch mechanism and an ILP-based WCSC analysis that considers fine-grained preemption constraints and possible function-level switching points from the private to the shared stack. A genetic algorithm then selects switching points that lead to the reduction of the overall WCSC. Compared to systems that run only non-blocking threads on the shared stack, semi-extended tasks decrease the WCSC in our benchmarks on average by 7 percent and up to 52 percent for some systems.
AB - Memory is an expensive and, therefore, limited resource in deeply embedded real-time systems. Thread stacks substantially contribute to the RAM requirements. To reduce the system's worst-case stack consumption (WCSC), it is state of the art to exploit thread-level preemption constraints to let multiple threads share the same stack. However, deriving a tight, yet correct bound for the shared stack is a difficult undertaking and stack sharing is currently restricted to run-to-completion threads, which are preemptable, but cannot block (i.e., passively wait for an event) at run time. With semi-extended tasks (SETs), we propose a solution for efficient stack sharing among blocking and non-blocking threads on the system level. For this, we refine the stack-sharing granularity from the thread to function level. We provide an efficient intra-thread stack-switch mechanism and an ILP-based WCSC analysis that considers fine-grained preemption constraints and possible function-level switching points from the private to the shared stack. A genetic algorithm then selects switching points that lead to the reduction of the overall WCSC. Compared to systems that run only non-blocking threads on the shared stack, semi-extended tasks decrease the WCSC in our benchmarks on average by 7 percent and up to 52 percent for some systems.
KW - Real-time operating system
KW - static analysis
KW - Worst-case stack consumption
UR - https://www.scopus.com/pages/publications/85061550198
U2 - 10.1109/rtss.2018.00049
DO - 10.1109/rtss.2018.00049
M3 - Conference contribution
AN - SCOPUS:85061550198
SN - 978-1-5386-7909-8
T3 - Proceedings Real-Time Systems Symposium
SP - 338
EP - 349
BT - 39th IEEE Real-Time Systems Symposium (RTSS)
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 11 December 2018 through 14 December 2018
ER -