Lock Free Data Structures
Lock-Free Data Structures
Andrei Alexandrescu
December 17, 2007
After Generic Programming has skipped one instance (it’s quite na¨ıve, I know, to think that grad school asks for anything less than 100% of one’s time), there has been an embarrassment of riches as far as topic candidates for this article go. One topic candidate was a discussion of constructors, in particular forwarding constructors, handling exceptions, and two-stage object construction. One other topic candidate—and another glimpse into the Yaslander technology [2]—was creating containers (such as lists, vectors, or maps) of incomplete types, something that is possible with the help of an interesting set of tricks, but not guaranteed by the standard containers.
While both candidates were interesting, they couldn’t stand a chance against lock-free data structures, which are all the rage in the multithreaded programming community. At this year’s PLDI conference (http://www.cs.umd.edu/∼pugh/pldi04/),
Michael Maged presented the world’s first lock-free memory allocator [7], which surpasses at many tests other more complex, carefully-designed lock-based allocators. This is the most recent of many lock-free data structures and algorithms that have appeared in the recent past. . . but let’s start from the beginning.
1
operations that change data must appear as atomic such that no other thread intervenes to spoil your data’s invariant. Even a simple operation such as
++count_, where count_ is an integral type, must be locked as “++” is really a three steps (read, modify, write) operation that isn’t necessarily atomic.
In short, with lock-based multithreaded programming, you need to make sure that any operation on shared data that is susceptible to race conditions is made atomic by locking and unlocking a mutex. On the bright side, as long as the mutex is locked, you can perform just about any operation, in confidence that no other thread will trump on your shared state.
It is exactly this “arbitrary”-ness
Andrei Alexandrescu
December 17, 2007
After Generic Programming has skipped one instance (it’s quite na¨ıve, I know, to think that grad school asks for anything less than 100% of one’s time), there has been an embarrassment of riches as far as topic candidates for this article go. One topic candidate was a discussion of constructors, in particular forwarding constructors, handling exceptions, and two-stage object construction. One other topic candidate—and another glimpse into the Yaslander technology [2]—was creating containers (such as lists, vectors, or maps) of incomplete types, something that is possible with the help of an interesting set of tricks, but not guaranteed by the standard containers.
While both candidates were interesting, they couldn’t stand a chance against lock-free data structures, which are all the rage in the multithreaded programming community. At this year’s PLDI conference (http://www.cs.umd.edu/∼pugh/pldi04/),
Michael Maged presented the world’s first lock-free memory allocator [7], which surpasses at many tests other more complex, carefully-designed lock-based allocators. This is the most recent of many lock-free data structures and algorithms that have appeared in the recent past. . . but let’s start from the beginning.
1
operations that change data must appear as atomic such that no other thread intervenes to spoil your data’s invariant. Even a simple operation such as
++count_, where count_ is an integral type, must be locked as “++” is really a three steps (read, modify, write) operation that isn’t necessarily atomic.
In short, with lock-based multithreaded programming, you need to make sure that any operation on shared data that is susceptible to race conditions is made atomic by locking and unlocking a mutex. On the bright side, as long as the mutex is locked, you can perform just about any operation, in confidence that no other thread will trump on your shared state.
It is exactly this “arbitrary”-ness
References: Addison-Wesley Longman, 2001. Addison-Wesley, Reading, Massachusetts, USA, 1997. symposium on Principles of distributed computing, pages 190–199. ACM Press, 2001. ISBN 158113-383-9.