A Wait-Free Dynamic Storage Allocator by Adopting the Helping Queue Pattern - Stellwag, Philippe; Krainz, Jakob; Schröder-Preikschat, Wolfgang (Proceedings Parallel and Distributed Computing and Networks (PDCN 2010), 2010)
Most of the real-time applicable dynamic storage allocators rely on conventional locking strategies for protecting globally accessible data. But it is common that lock compositions do not scale well under high allocation and deallocation rates in parallel scenarios, as they lead to convoy effects. Furthermore, lock compositions lead to jitter, which is often a critical factor in real-time systems. Additionally, it is often desirable to guarantee progress of threads in order to be able to determine the worst-case execution time. This led us designing a wait-free dynamic storage allocator (DSA), which can guarantee progress of threads and does not influence other threads to make progress. Our DSA implementation relies on a kind of buddy strategy with approximate best-fit. Hence, it ensures for this kind of allocation strategy typical memory wastage as a result of internal fragmentation. Preliminary tests show that we can outperform established DSA implementations in terms of predictability, like the famous TLSF memory allocator. To the best of our knowledge, our DSA is the first known approach using a scalable and bounded nonblocking synchronization strategy. Our approach towards a wait-free DSA algorithm is applicable in real-time applications where adequate a priori knowledge about the memory requirements is available because it uses a statically allocated heap. We think that most real-time systems-especially ones with hard timing constraints-fulfill this precondition.
UnivIS-Import:2015-04-16:Pub.2010.tech.IMMD.IMMD4.awaitf
Keywords: pCtrl; storage allocator; malloc; wait-freedom; nonblocking; real-time systems

A Wait-Free NCAS Library for Parallel Applications with Timing Constraints - Stellwag, Philippe; Scheler, Fabian; Krainz, Jakob; Schröder-Preikschat, Wolfgang (Proceedings of the 16th ACM Symposium on Principles and Practice of Parallel Programming 2011 (PPoPP 2011), 2011)
We introduce our major ideas of a wait-free, linearizable, and disjoint-access parallel NCAS library, called RTNCAS. It focuses the construction of wait-free data structure operations (DSO) in real-time circumstances. RTNCAS is able to conditionally swap multiple independent words (NCAS) in an atomic manner. It allows us, furthermore, to implement arbitrary DSO by means of their sequential specification. Copyright © 2011 ACM.
UnivIS-Import:2015-04-16:Pub.2011.tech.IMMD.IMMD4.awaitf
Keywords: pCtrl; wait freedom; disjoint-access parallelism; NCAS; real-time systems

Diff Graphs for a fast Incremental Pointer Analysis - Krainz, Jakob; Philippsen, Michael (Proceedings of the 12th Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems (ICOOOLPS'17), 2017)
A wide range of optimizations and program analyses, including bug finding by means of escape or race analyses, need accurate pointer information. Since accuracy takes time, there is a need for a fast incremental pointer analysis that re-uses prior results and only re-analyzes program changes and their effects instead of the whole program. We present such an incremental pointer analysis that employs novel diff graphs to represent how a method accesses and/or modifies memory. Regardless of the number of call sites, we only need to analyze a method once; the resulting diff-graph is then used at every call site. If a method changes, we re-generate its diff-graph, and (unless its diff-graph stays the same) its callers' diff graphs, and so on. Our algorithm is flow sensitive and context insensitive, does not leak information between call sites, can perform strong updates (even for method calls), and is fast (14 000 LOC with 25 000 bytecode instructions in 3 minutes). When used incrementally for each of the commits of an open-source software repository our incremental approach derives more precise pointer information than established (full) analyses like Spark – albeit in about the same time.

Transformation von Datenstruktur-Operationen zu Wartefreien mithilfe einer wartefreien Multi-Word Compare-And-Swap Bibliothek - Krainz, Jakob (Friedrich-Alexander-Universität Erlangen-Nürnberg, 2010)