The paper “Lock Oscillation: Boosting the Performance of Concurrent Data Structures” by Panagiota Fatourou and Nikolaos D. Kallimanis from ExaNoDe partner FORTH has been accepted for the Conference on Principles of Distributed Systems (OPODIS 2017).
The paper is based on FORTH’s work in ExaNoDe on atomics and the GSAS environment.


In combining-based synchronization, two main parameters that affect performance are the combining degree of the synchronization algorithm, i.e., the average number of requests that each combiner serves, and the number of expensive synchronization primitives (like CAS, Swap, Fetch&Add, etc.) that it performs. The value of the first parameter must be high, whereas the second must be kept low.

In this paper, we present Osci, a new combining technique that shows remarkable performance when paired with cheap context switching. We experimentally show that Osci significantly outperforms all previous combining algorithms. Specifically, the throughput of Osci is higher than that of previously presented combining techniques by more than an order of magnitude. Notably, Osci’s throughput is much closer to the ideal than all previous algorithms, while maintaining the average latency in serving each request low. We evaluated the performance of Osci in two different multiprocessor architectures, namely AMD and Intel.

Based on Osci, we implement and experimentally evaluate implementations of concurrent queues and stacks. These implementations outperform by far all current state-of-the-art concurrent queue and stack implementations. Although the current version of Osci has been evaluated in an environment supporting user-level threads, it would run correctly on any threading library, preemptive or not (including kernel threads).