We present a pragmatic methodology for designing nonblocking real-time systems. Our methodology uses a combination of lock-free and wait-free synchronization techniques and clearly states which technique should be applied in which situation. This paper reports novel results in various respects: We restrict the usage of lock-free mechanisms to cases where the widely available atomic singleword compare-and-swap operation suffices. We show how Brinch Hansen’s monitors (alias Java’s synchronized methods) can be implemented on top of our mechanisms, thereby demonstrating their versatility. We describe in detail how we used the mechanisms for a full reimplementation of a popular microkernel interface (L4). Our kernel— in contrast to the original implementation—bounds execution time of all operations. We report on a previous implementation of our mechanisms in which we used Massalin’s and Pu’s single-server approach, and on the resulting performance, which lead us to abandon this well-known scheme. Our microkernel implementation is in daily use with a user-level Linux server running a large variety of applications. Hence, our system can be considered as more than just an academic prototype. Still, and despite its implementation in C++, it compares favorably with the original, highly optimized, non-real-time, assembly-language implementation.
['Michael Hohmuth', 'Hermann Härtig']
Pragmatic Nonblocking Synchronization for Real-Time Systems