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 - http://www.scopus.com/inward/record.url?scp=85061550198&partnerID=8YFLogxK

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 -