Academic Commons

Articles

Simple and Fast Biased Locks

Vasudevan, Nalini; Namjoshi, Kedar S.; Edwards, Stephen A.

Locks are used to ensure exclusive access to shared memory locations. Unfortunately, lock operations are expensive, so much work has been done on optimizing their performance for common access patterns. One such pattern is found in networking applications, where there is a single thread dominating lock accesses. An important special case arises when a single-threaded program calls a thread-safe library that uses locks. An effective way to optimize the dominant-thread pattern is to "bias" the lock implementation so that accesses by the dominant thread have negligible overhead. We take this approach in this work: we simplify and generalize existing techniques for biased locks, producing a large design space with many trade-offs. For example, if we assume the dominant process acquires the lock infinitely often (a reasonable assumption for packet processing), it is possible to make the dominant process perform a lock operation without expensive fence or compare-and-swap instructions. This gives a very low overhead solution; we confirm its efficacy by experiments. We show how these constructions can be extended for lock reservation, re-reservation, and to reader-writer situations.

Subjects

Files

Also Published In

Title
PACT '10: Proceedings of the Nineteenth International Conference on Parallel Architectures and Compilation Techniques: September 11-15, 2010, Vienna, Austria
DOI
https://doi.org/10.1145/1854273.1854287

More About This Work

Academic Units
Computer Science
Publisher
Association for Computing Machinery
Published Here
August 9, 2011
Academic Commons provides global access to research and scholarship produced at Columbia University, Barnard College, Teachers College, Union Theological Seminary and Jewish Theological Seminary. Academic Commons is managed by the Columbia University Libraries.