This paper introduces read-log-update (RLU), a novel extension of the popular read-copy-update (RCU) synchronization mechanism that supports scalability of concurrent code by allowing unsynchronized sequences of reads to execute concurrently with updates. RLU overcomes the major limitations of RCU by allowing, for the first time, concurrency of reads with multiple writers, and providing automation that eliminates most of the programming difficulty associated with RCU programming. At the core of the RLU design is a logging and coordination mechanism inspired by software transactional memory algorithms. In a collection of micro-benchmarks in both the kernel and user space, we show that RLU both simplifies the code and matches or improves on the performance of RCU. As an example of its power, we show how it readily scales the performance of a real-world application, Kyoto Cabinet, a truly difficult concurrent programming feat to attempt in general, and in particular with classic RCU.
%0 Conference Paper
%1 Matveev:2015:RLS:2815400.2815406
%A Matveev, Alexander
%A Shavit, Nir
%A Felber, Pascal
%A Marlier, Patrick
%B Proceedings of the 25th Symposium on Operating Systems Principles
%C New York, NY, USA
%D 2015
%I ACM
%K concurrency
%P 168--183
%R 10.1145/2815400.2815406
%T Read-log-update: A Lightweight Synchronization Mechanism for Concurrent Programming
%U http://doi.acm.org/10.1145/2815400.2815406
%X This paper introduces read-log-update (RLU), a novel extension of the popular read-copy-update (RCU) synchronization mechanism that supports scalability of concurrent code by allowing unsynchronized sequences of reads to execute concurrently with updates. RLU overcomes the major limitations of RCU by allowing, for the first time, concurrency of reads with multiple writers, and providing automation that eliminates most of the programming difficulty associated with RCU programming. At the core of the RLU design is a logging and coordination mechanism inspired by software transactional memory algorithms. In a collection of micro-benchmarks in both the kernel and user space, we show that RLU both simplifies the code and matches or improves on the performance of RCU. As an example of its power, we show how it readily scales the performance of a real-world application, Kyoto Cabinet, a truly difficult concurrent programming feat to attempt in general, and in particular with classic RCU.
%@ 978-1-4503-3834-9
@inproceedings{Matveev:2015:RLS:2815400.2815406,
abstract = {This paper introduces read-log-update (RLU), a novel extension of the popular read-copy-update (RCU) synchronization mechanism that supports scalability of concurrent code by allowing unsynchronized sequences of reads to execute concurrently with updates. RLU overcomes the major limitations of RCU by allowing, for the first time, concurrency of reads with multiple writers, and providing automation that eliminates most of the programming difficulty associated with RCU programming. At the core of the RLU design is a logging and coordination mechanism inspired by software transactional memory algorithms. In a collection of micro-benchmarks in both the kernel and user space, we show that RLU both simplifies the code and matches or improves on the performance of RCU. As an example of its power, we show how it readily scales the performance of a real-world application, Kyoto Cabinet, a truly difficult concurrent programming feat to attempt in general, and in particular with classic RCU.},
acmid = {2815406},
added-at = {2016-10-17T21:14:14.000+0200},
address = {New York, NY, USA},
author = {Matveev, Alexander and Shavit, Nir and Felber, Pascal and Marlier, Patrick},
biburl = {https://www.bibsonomy.org/bibtex/2f21fb9f4f5acd2f099f3238f162b1942/sunjae0802},
booktitle = {Proceedings of the 25th Symposium on Operating Systems Principles},
description = {Read-log-update},
doi = {10.1145/2815400.2815406},
interhash = {0f9f4015c56d1ee10ce74661f8f65b6d},
intrahash = {f21fb9f4f5acd2f099f3238f162b1942},
isbn = {978-1-4503-3834-9},
keywords = {concurrency},
location = {Monterey, California},
numpages = {16},
pages = {168--183},
publisher = {ACM},
series = {SOSP '15},
timestamp = {2016-10-17T21:14:14.000+0200},
title = {Read-log-update: A Lightweight Synchronization Mechanism for Concurrent Programming},
url = {http://doi.acm.org/10.1145/2815400.2815406},
year = 2015
}