Information Technology Reference
In-Depth Information
The shared objects described in Chapter ?? provide a key building block for
writing multi-threaded programs, but many such programs must address several
additional issues.
The first set of issues arise because many programs comprise multiple shared
objects, and we need to reason about the interactions among these pieces. Un-
fortunately, these interactions can break modularity; in some cases when one
module calls another, you literally have to know about the modules' internal
implementation details to make sure that both modules' synchronization mesh.
There are two issues: safety and liveness.
1. Safety: Multi-object synchronization. For programs with multiple
shared objects, we face a problem similar to what we faced when reasoning
about atomic loads and stores: even if each individual operation on a
shared object is atomic, we need to reason about interactions of sequences
of operations across objects.
2. Liveness: Deadlock. One way to help reason about sequences of oper-
ations on multiple objects is to hold multiple locks. This approach raises
the issue of deadlock where a set of threads get permanently stuck waiting
for each other in a cycle.
The bad news here is that there is no cookbook recipe that always works for
dealing with these challenges. In particular, current techniques for addressing
these problems have two basic limitations. First, there are engineering trade-
offs among them. Some solutions are general but complex or expensive; others
are simple but slow; and still others are simple and cheap but not general. Sec-
ond, many of the solutions are inherently non-modular. They require reasoning
about the global structure of the system and internal implementation details of
modules to understand or restrict how different modules can interact.
In addition to discussing the challenges that arrive when dealing with mul-
tiple objects and multiple locks, this chapter discusses one other issue: how to
construct shared objects that can be accessed without locks. We emphasize that
this is an advanced topic that should only be considered by programmers that
have mastered multi-threaded programming. The vast majority of the time, the
simple shared objects described in the last chapter will be all that is needed in
a multi-threaded program.
3. Synchronization with reduced locking. In the part of this chap-
ter, we briefly discuss two techniques for synchronizing access to shared
state without locking:
read-copy-update (RCU) and lock-free/wait-free
data structures.
