Department of Information Technology

Queue Delegation Locking

Queue Delegation (QD) Locking is an efficient delegation technique for synchronization in multi-threaded programs. QD locking significantly outperforms traditional locking libraries (e.g., pthreads locks) and performs better than delegation mechanisms that have been proposed in the literature. An advantage of all delegation algorithms is that the lock holding thread can execute many critical sections in sequence while it has the data protected by the critical section in its fast private cache. In most applications, QD locks can be used as a drop-in replacement of traditional locks, by delegating the critical operation and waiting for its result. However, QD locks also offer threads the possibility to do detached execution: i.e., for threads to delegate their critical sections to the current lock holder and continue their execution without waiting for the result of the delegated operation. Of course, to get the benefits of detached execution, our QD locking libraries also provide a lock interface which differs from that provided by traditional locks.

The idea, algorithms and properties of QD locking as well as extensive comparisons with similar algorithms can be found in an article that will appear in IEEE Transactions on Parallel and Distributed Systems journal. An unedited pre-print version of that article can also found in the list of publications below. The main idea of QD locking has also been described in a SPAA'2014 brief announcement. The interface of the queue delegation libraries we provide as well as experiences from using them in code bases of significant size are described in a paper that has been published in the proceedings of EuroPar'2014. See the list of publications below for more information about the publications.

Publications

Libraries for C and C++

  • Library for C++ This github repository contains the header files needed for a C++ version of QD locking. It differs from the C version in its more accessible interface that makes it easier to use in C++ code, while also providing type safety.

Automatic Code Transformation

This tool can be used to automatically transform C source code that use pthread mutex locks to instead use QD locks from the C library above.

The tool is still a prototype, but can already be used for code bases of limited complexity. The tool has been developed by Robert Markovski as his bachelor thesis project.

Benchmarks

  • Benchmarking for Queue Delegation Locks This github repository contains benchmarking code that we used to evaluate QD locking. The necessary locking code is included in this repository, so neither of the libraries needs to be downloaded together with this.
Updated  2017-11-28 10:36:06 by Konstantinos Sagonas.