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 in the 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.
- David Klaftenegger, Konstantinos Sagonas, and Kjell Winblad. Queue Delegation Locking. In IEEE Transactions on Parallel and Distributed Systems. 2017. [BibTeX citation]
- David Klaftenegger, Konstantinos Sagonas, and Kjell Winblad. Brief Announcement: Queue Delegation Locking. In Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 70-72, June 2014. ACM Press. [BibTeX citation]
- David Klaftenegger, Konstantinos Sagonas, and Kjell Winblad. Delegation Locking Libraries for Improved Performance of Multithreaded Programs In Euro-Par 2014, Proceedings of the 20th International Conference, pp. 572-583, Volume 8632 in LNCS, August 2014. Springer. [BibTeX citation]
Libraries for C and C++
- Library for C The QD locking library for C is a complete locking library designed with QD locking in mind. This tutorial is a good introduction to the API of the library. More information can be found on the library's website.
- 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.
- 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.