|February 5, 2007|
|This article was contributed by Paul McKenney|
Read-copy update (RCU) is a synchronization API that is sometimes used
in place of reader-writer locks. RCU's read-side primitives offer
extremely low overhead and deterministic execution time.
These properties imply that RCU updaters cannot block RCU readers,
which means that RCU readers can be expensive, as they must leave
old versions of the data structure in place to accommodate pre-existing
Furthermore, these old versions must be reclaimed after all pre-existing
The Linux kernel offers a number of RCU implementations, the first
such implementation being called "Classic RCU".
The RCU implementation for the -rt patchset is unusual in that
it permits read-side critical
sections to be blocked waiting for locks and due to preemption.
If these critical sections are blocked for too long,
grace periods will be stalled,
and the amount of memory awaiting the end of a grace
period will continually increase, eventually resulting
in an out-of-memory condition.
This theoretical possibility was apparent from the start,
but when Trevor Woerner actually made it happen, it was
clear that something needed to be done.
Because priority boosting is used in locking, it seemed natural to
apply it to realtime RCU.
Unfortunately, the priority-boosting algorithm used for locking
could not be applied straightforwardly to RCU because this
algorithm uses locking, and the whole point of RCU is to
avoid common-case use of such heavy-weight operations
in read-side primitives.
In fact, RCU's read-side primitives need to avoid common-case
use of all
heavyweight operations, including atomic instructions,
memory barriers, and cache misses.
Therefore, bringing priority boosting to RCU turned out to
be rather challenging, not because the eventual solution is
all that complicated, but rather due to the large number of
seductive but subtly wrong almost-solutions.
This document describes a way of providing light-weight
priority boosting to RCU, and also describes several of the
number of seductive but subtly wrong almost-solutions.
This paper describes three approaches to priority-boosting blocked RCU
read-side critical sections.
The first approach minimizes scheduler-path overhead and uses locking
on non-fastpaths to decrease complexity.
The second approach is similar to the first, and was in fact a
higher-complexity intermediate point on the path to the first approach.
The third approach uses a per-task lock solely for its priority-inheritance
properties, which introduces the overhead of acquiring this lock into
the scheduler path, but avoids adding an "RCU boost" component to the
Unfortunately, this third approach also cannot be made to reliably
boost tasks blocked in RCU read-side critical sections, so the first
approach should be used to the exclusion of the other two.
Each of these approaches is described in a following section,
after which is a section enumerating other roads not taken.
[ Editor's note: this article is long - but worth the read. Please
go to the full article text
to learn more about this technique.]
to post comments)