Article development led by
Exploring an alternative to
BY sam Y aL BahRa
avoiding the problems of lock-based
synchronization. This class of synchronization is not a silver bullet, especially outside of the abstract models
in which its performance properties
were originally defined. Several of the
performance bottlenecks and error
conditions associated with lock-based
synchronization remain (albeit in
more obfuscated forms); therefore, ensuring correctness requires more complex verification methods, and in some
cases nonblocking algorithms require
the adoption of complex support systems. Stemming from these complexities, nonblocking synchronization is
frequently the victim of hype, fear, uncertainty, and doubt. This article aims
to equip the reader with the knowledge
needed to identify situations that benefit from nonblocking synchronization.
real-World s Ystems With complicated quality-of-service guarantees may require a delicate balance
between throughput and latency in order to meet
operating requirements in a cost-efficient manner.
The increasing availability and decreasing cost of
commodity multicore and many-core systems make
concurrency and parallelism increasingly necessary
for meeting demanding performance requirements.
Unfortunately, the design and implementation
of correct, efficient, and scalable concurrent software
is often a daunting task.
Nonblocking synchronization may be used in
building predictable and resilient systems while
Before elaborating on typical motivations for adopting nonblocking data
structures, this section highlights
some important principles for understanding scalability on multiprocessor
systems in the traditional threading
model. Both lock-based and nonblocking synchronization have performance
characteristics that are a function of
these principles. Practitioners who are
already intimately familiar with cache
coherent multiprocessors, out-of-order
execution, and the design and implementation of lock-based synchronization objects may wish to skip this section. While this section is by no means
exhaustive, additional references have
been provided. Paul E. McKenney outlines a methodology for choosing appropriate lock-based synchronization
15 and other common
principles have been described in previous articles.
5, 13, 17,
Contention inhibits scalability.
Contention on shared objects in parallel applications is a primary impediment to scalability and predictability.
Regardless of the higher-level synchronization facilities being used, contention over a shared object involves some
form of serialization by the underlying