Home

Simple and Fast Biased Locks

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

Title:
Simple and Fast Biased Locks
Author(s):
Vasudevan, Nalini
Namjoshi, Kedar S.
Edwards, Stephen A.
Date:
Type:
Articles
Department:
Computer Science
Permanent URL:
Book/Journal Title:
PACT '10: Proceedings of the Nineteenth International Conference on Parallel Architectures and Compilation Techniques: September 11-15, 2010, Vienna, Austria
Publisher:
Association for Computing Machinery
Abstract:
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.
Subject(s):
Computer science
Publisher DOI:
10.1145/1854273.1854287
Item views:
110
Metadata:
text | xml

In Partnership with the Center for Digital Research and Scholarship at Columbia University Libraries/Information Services | Terms of Use