Semi-Extended Tasks: Efficient Stack Sharing Among Blocking Threads

• Authors: Christian Dietrich, Daniel Lohmann
• Project: AHA

Abstract

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, 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.

In a Nutshell

Semi-Extended Tasks start on a private stack and switch, if possible, to the shared stack. The stack switching does not involve the RTOS and is done on the granularity of functions.

Artifacts

The artifact evaluation is bundleded as a VirtualBox Appliance. Inside the Virtual Machine, you will find a README that points you to the Jupyter File. The Jupyter File documents the artifact evaluation and will give you detailed instructions what to do to reproduce our result.

Our original evaluation was done on real hardware with a four CPU/32 GB machine. If you import the OVA, you probably want to use as many processor as you have to speed up the reproduction. Memory, if it is over 8 Gb, probably won't be an issue. Furthermore, you will be asked to get an academic Gurobi 8.0 license (for free). So you probably want to have some connectivity to an university network.

• VirtualBox OVA File: Semi-Extended Tasks VM.ova (5.5 Gb)
• dOSEK Source Code

Publication

RTSS Conference A*
Semi-Extended Tasks: Efficient Stack Sharing Among Blocking Threads

Christian Dietrich, Daniel LohmannProceedings of the 39th IEEE Real-Time Systems Symposium 2018IEEE Computer Society Press2018.
PDF Details Slides Raw Data 10.1109/RTSS.2018.00049 [BibTex]

×

BibTex Entry

@inproceedings{dietrich:18:rtss,
location = {Nashville, Tennessee, USA},
author = {Christian Dietrich and Daniel Lohmann},
booktitle = {Proceedings of the 39th IEEE Real-Time Systems Symposium 2018},
doi = {10.1109/RTSS.2018.00049},
editor = {Sebastian Altmeyer},
entrysubtype = {Conference},
publisher = {IEEE Computer Society Press},
title = {Semi-Extended Tasks: Efficient Stack Sharing Among Blocking Threads},
year = {2018},
}

Close

Bibtex

  @inproceedings{dietrich:18:rtss,
location = {Nashville, Tennessee, USA},
author = {Christian Dietrich and Daniel Lohmann},
booktitle = {Proceedings of the 39th IEEE Real-Time Systems Symposium 2018},
doi = {10.1109/RTSS.2018.00049},
editor = {Sebastian Altmeyer},
entrysubtype = {Conference},
publisher = {IEEE Computer Society Press},
title = {Semi-Extended Tasks: Efficient Stack Sharing Among Blocking Threads},
year = {2018},
}