Monday, May 6 • 14:30 - 16:00
A Multithreaded, Transaction-Based Read/Write Locking Strategy for Containers

Log in to save this to your schedule, view media, leave feedback and see who's attending!

Feedback form is now closed.
With the multithreading tools available in the modern C++ standard library, it is easier than ever to create multithreaded programs. When we write such applications, there are sometimes cases in which a container simply must be shared among multiple threads. Of course, sharing is trivial if the only operations on the container are reads. In the case where reads greatly outnumber writes, acceptable performance is often attainable with a reader/writer mutex type, like std::shared_mutex. But suppose that the number of writes is similar to, or even greater than, the number of reads -- how does one then perform simultaneous reads and writes on a single container?

One common usage pattern is that, for a given operation, sets of related records are read and updated together. In order to prevent data races and inconsistent views of the data, such sets must be locked together as a unit before any of them can actually be read or updated. Further, it is very easy to accidentally create deadlocks by choosing a seemingly correct locking order. In order to avoid these problems, we require that our locking algorithm provide three important properties: atomicity, consistency, and isolation.

This talk will describe an algorithm, implemented in C++, that performs such locking based on the concept of strict timestamp ordering. Using only facilities from the C++17 standard library, it employs a straightforward and novel approach to multi-threaded, transactional record locking that requires minimal spatial overhead and yet fulfills the requirements of atomicity, consistency, and isolation. We'll discuss the pros, cons, and limitations of the algorithm, and provide some measurements comparing the algorithm's performance to that of other techniques.

avatar for Bob Steagall

Bob Steagall

Chief Cook and Bottle Washer, KEWB Computing

Monday May 6, 2019 14:30 - 16:00 MDT
Flug Auditorium