Information Technology Reference
In-Depth Information
5. Suppose you build a system using a staged architecture with some fixed
number of threads operating on stage. Assuming each stage is individually
deadlock free, describe two ways to guarantee that your system as a whole
can not deadlock. Each of the ways should eliminate a different one of the
4 necessary conditions for deadlock.
6.3
Alternative approaches to synchronization
Chapter 5 described a core abstraction for synchronization|shared objects
with one lock per object. This abstraction is the right building block for multi-
threaded programs the vast majority of the time. Occasionally, as start of the
current chapter indicated, you need to resort to fine grained locking, a variation
of this basic approach that divides an object's state among dierent locks.
Even more rarely programmers resort to alternatives that avoid locks such as
read-copy-update (RCU) synchronization and lock-free and wait-free data struc-
tures. We emphasize that the cases when these approaches are warranted are
rare and that these advanced techniques should only be considered by experi-
enced programmers who have mastered the basic lock-based approaches. Many
readers will probably never need to use these techniques. If you do find yourself
tempted to do so, take extra care. Be sure to measure the performance of your
system to make sure that these techniques yield significant gains, and seek out
extra peer review from trusted colleagues to help make sure that the code works
as intended.
We caution that programmers are often tempted to assume that acquiring a
lock is an expensive operation and to therefore try to reduce locking throughout
their programs. The most likely result from this premature optimization mind-
set is a program that is buggy, hard to maintain, no faster than a clean imple-
mentation, and|ironically|harder to tune than a cleanly architected program.
On most platforms, acquiring or releasing a lock is a highly tuned primitive|
acquiring an uncontended lock is often nearly free (and if there is contention
then you probably need that lock!)
That said, although you may not often (or ever) write code that uses these
advanced techniques, it is important to understand them because they do get
used in critical parts of important systems such as the Linux kernel and some
Java Virtual Machine libraries and because in some cases they can provide
significant performance gains.
6.3.1
Read-Copy-Update (RCU)
The goal of read-copy-update (RCU) is to provide high performance synchro-
nization for data structures that are frequently read and occasionally updated.
