Merge tag 'for-paul-2021.02.27b' of https://github.com/akiyks/perfbook
diff --git a/advsync/advsync.tex b/advsync/advsync.tex
index fc0736b..8cf1a70 100644
--- a/advsync/advsync.tex
+++ b/advsync/advsync.tex
@@ -366,17 +366,17 @@
probabilistic, as in the soft-real-time guarantee that
``at least 99.9\,\% of the time, scheduling latency must
be less than 100 microseconds.''
- In contrast, NBS's forward-progress
- guarantees have traditionally been unconditional.
+ In contrast, many of NBS's forward-progress guarantees are
+ unconditional.
\item Real-time forward-progress guarantees are often conditioned on
environmental constraints, for example, only being honored:
- (1)~for the highest-priority tasks,
- (2)~when each CPU spends at least a certain fraction of its time idle,
- or (3)~when I/O rates are below some specified maximum.
+ (1)~For the highest-priority tasks,
+ (2)~When each CPU spends at least a certain fraction of its time idle,
+ or (3)~When I/O rates are below some specified maximum.
In contrast, NBS's forward-progress
- guarantees are usually unconditional.\footnote{
- As we will see below, some recent NBS work relaxes
- this guarantee.}
+ guarantees are often unconditional, although recent NBS work
+ accommodates conditional
+ guarantees~\cite{DanAlitarh2013PracticalProgress}.
\item An important component of a real-time program's environment
is the scheduler.
NBS algorithms assume a worst-case \emph{demonic scheduler}.
@@ -390,9 +390,8 @@
NBS~\cite{DanAlitarh2013PracticalProgress,BjoernBrandenburgPhD}.
\item Real-time forward-progress guarantees usually apply only
in the absence of software bugs.
- In contrast, most NBS guarantees apply even in the face of
- fail-stop bugs.\footnote{
- Again, some recent NBS work relaxes this guarantee.}
+ In contrast, many classes of NBS guarantees apply even in the
+ face of fail-stop bugs.
\item NBS forward-progress guarantee classes imply linearizability.
In contrast, real-time forward progress guarantees are often
independent of ordering constraints such as linearizability.
@@ -408,22 +407,20 @@
otherwise), lock-free synchronization, obstruction-free synchronization,
and clash-free synchronization guarantee forward progress even in the
presence of fail-stop bugs.
-An example fail-stop bug would be a scheduler bug that causes a random
-thread to be preempted indefinitely.
+An example fail-stop bug might cause some thread to be preempted indefinitely.
As we will see, this fail-stop-tolerant property can be useful, but the
-fact is that composing a set of fail-stop-tolerate mechanisms does not
+fact is that composing a set of fail-stop-tolerant mechanisms does not
necessarily result in a fail-stop-tolerant system.
To see this, consider a system made up of a series of wait-free queues,
where an element is removed from one queue in the series, processed,
and then added to the next queue.
-If a thread is preempted in the midst of a queuing operation, all is well
-because the wait-free nature of the queue will guarantee forward progress.
-But suppose that preemption occurs not during the queuing, but instead
-during the between-queues processing.
-In this case, the element being processed is lost because
-the fail-stop-tolerant nature of the wait-free queues does not
-extend to the code using those queues.
+If a thread is preempted in the midst of a queuing operation, in theory
+all is well because the wait-free nature of the queue will guarantee
+forward progress.
+But in practice, the element being processed is lost because the
+fail-stop-tolerant nature of the wait-free queues does not extend to
+the code using those queues.
Nevertheless, there are a few applications where NBS's rather limited
fail-stop-tolerance is useful.
@@ -434,15 +431,15 @@
to the point where the scheduler can no longer provide any reasonable
fairness guarantee.
In constrast, if a thread fail-stops while holding a lock, the application
-will normally need to be restarted.
+might need to be restarted.
Nevertheless, NBS is not a panacea even within this restricted area,
due to the possibility of spurious retransmissions due to pure scheduling
delays.
In some cases, it may be more efficient to reduce the load to avoid
queueing delays, which will also improve the scheduler's ability to
-provide fair access, which might turn reduce or even eliminate the
-apparent fail-stop events, thus shedding the load due to the retry
-operations initiated by retransmissions.
+provide fair access, reducing or even eliminating the fail-stop events,
+thus reducing the number of retry operations, in turn further reducing
+the load.
\subsubsection{NBS Linearizability}
\label{sec:advsync:NBS Linearizability}
@@ -472,7 +469,7 @@
A few such proof techniques were discussed in
\cref{chp:Formal Verification}.\footnote{
A memorable verbal discussion with an advocate of linearizability
- resulted in this advocate being asked:
+ resulted in question:
``So the reason linearizability is important is to rescue 1980s
proof techniques?''
The advocate immediately replied in the affirmative, then spent
@@ -483,12 +480,11 @@
It is often asserted that linearizability maps well to sequential
specifications, which are said to be more natural than are concurrent
specifications~\cite{SergioRajsbaum2020HistoryLinearizability}.
-But this assertion flies in the face of reality in the form of a highly
-concurrent objective universe.
-Therefore, nature would be expected to select for beings able to cope
-with at least some level of concurrency, and anyone watching a team sport
-or a person successfully overseeing a number of small children would be
-hard-pressed to argue that nature has not done exactly that.
+But this assertion fails to account for our highly concurrent objective
+universe.
+This universe can only be expected to select for ability to cope with
+concurrency, especially for those participating in team sports or
+overseeing small children.
In addition, given that the teaching of sequential
computing is still believed to be somewhat of a black
art~\cite{ElizabethPatitsas2020GradesNotBimodal}, it is reasonable
@@ -532,31 +528,31 @@
algorithms that provide only non-blocking
synchronization, both in theory~\cite{DanAlitarh2013PracticalProgress}
and in practice~\cite{SamyAlBahra2013NBS}.
-Because a great many schedulers used in production do in fact
-provide fairness,
-the more-complex algorithms providing wait-free synchronization
-usually provide no practical advantages over their simpler
-and often faster non-blocking-synchronization counterparts.
+Because most schedulers used in production do in fact provide fairness,
+the more-complex algorithms providing wait-free synchronization usually
+provide no practical advantages over simpler and faster non-wait-free
+algorithms.
Interestingly enough, fair scheduling is but one beneficial
constraint that is often respected in practice.
Other sets of constraints can permit blocking algorithms to
achieve deterministic real-time response.
-For example, given fair locks that are granted to requesters in FIFO order at
-a given priority level,
-a method of avoiding priority inversion (such as priority
+For example, given:
+(1)~Fair locks granted in FIFO order within a given priority level,
+(2)~Priority inversion avoidance (for example, priority
inheritance~\cite{Takada:1995:RSN:527074.828566,Cai-DongWang1996PrioInherLock}
-or priority ceiling), a bounded number of threads,
-bounded critical sections,
-bounded load,
-and avoidance of fail-stop bugs,
+or priority ceiling),
+(3)~A bounded number of threads,
+(4)~Bounded critical section durations,
+(5)~Bounded load,
+and
+(6)~Absence of fail-stop bugs,
lock-based applications can provide deterministic
response times~\cite{BjoernBrandenburgPhD,DipankarSarma2004OLSscalability}.
This approach of course blurs the distinction between blocking and wait-free
synchronization, which is all to the good.
-Hopefully theoretical frameworks continue to grow, further increasing
-their ability to
-describe how software is actually constructed in practice.
+Hopefully theoretical frameworks will continue to improve their ability
+to describe software actually used in practice.
Those who feel that theory should lead the way are referred to the
inimitable Peter Denning, who said of operating systems:
@@ -565,10 +561,10 @@
``In all branches of engineering science, the engineering starts before
the science; indeed, without the early products of engineering, there
would be nothing for the scientist to
-study!''~\cite{RichardMorris2007TonyHoareInterview}
+study!''~\cite{RichardMorris2007TonyHoareInterview}.
However, once an appropriate body of theory becomes available,\footnote{
- Admittedly often much later than the first \emph{proposed}
- body of theory.}
+ However, the first \emph{appropriate} body of theory is often one
+ thing and the first \emph{proposed} body of theory quite another.}
it is wise to make use of it.
\input{advsync/rt}
diff --git a/advsync/rt.tex b/advsync/rt.tex
index 9b593dc..8a2c42c 100644
--- a/advsync/rt.tex
+++ b/advsync/rt.tex
@@ -5,7 +5,7 @@
\section{Parallel Real-Time Computing}
\label{sec:advsync:Parallel Real-Time Computing}
%
-\epigraph{One always has time enough if only one applies it well.}
+\epigraph{One always has time enough if one applies it well.}
{\emph{Johann Wolfgang von G\"othe}}
% \epigraph{The difference between you and me is that I was right in time.}
% {\emph{Konrad Adenauer}}
@@ -16,9 +16,9 @@
\Cref{sec:advsync:What is Real-Time Computing?}
looks at a number of definitions of ``real-time computing'', moving
beyond the usual sound bites to more meaningful criteria.
-\Cref{sec:advsync:Who Needs Real-Time Computing?}
+\Cref{sec:advsync:Who Needs Real-Time?}
surveys the sorts of applications that need real-time response.
-\Cref{sec:advsync:Who Needs Parallel Real-Time Computing?}
+\Cref{sec:advsync:Who Needs Parallel Real-Time?}
notes that parallel real-time computing is upon us, and discusses
when and why parallel real-time computing can be useful.
\Cref{sec:advsync:Implementing Parallel Real-Time Systems}
@@ -35,11 +35,10 @@
\subsection{What is Real-Time Computing?}
\label{sec:advsync:What is Real-Time Computing?}
-One traditional way of classifying real-time computing is into the categories
-of \emph{hard real time} and \emph{soft real time}, where the macho
-hard real-time applications never ever miss their deadlines, but the
-wimpy soft real-time applications might well miss their deadlines
-frequently and often.
+One traditional way of classifying real-time computing is into the
+categories of \emph{hard real time} and \emph{soft real time}, where
+the macho hard real-time applications never miss their deadlines, but
+the wimpy soft real-time applications miss their deadlines quite often.
\subsubsection{Soft Real Time}
\label{sec:Soft Real Time}
@@ -86,8 +85,8 @@
\begin{figure}[bt]
\centering
\resizebox{3in}{!}{\includegraphics{cartoons/realtime-smash}}
-\caption{Real-Time Response Guarantee, Meet Hammer}
-\ContributedBy{Figure}{fig:advsync:Hard Real-Time Response Guarantee; Meet Hammer}{Melissa Broussard}
+\caption{Real-Time Response, Meet Hammer}
+\ContributedBy{Figure}{fig:advsync:Hard Real-Time Response; Meet Hammer}{Melissa Broussard}
\end{figure}
In contrast, the definition of hard real time is quite definite.
@@ -96,10 +95,9 @@
Unfortunately, a strict application of this definition would mean that
there can never be any hard real-time systems.
The reason for this is fancifully depicted in
-\cref{fig:advsync:Hard Real-Time Response Guarantee; Meet Hammer}.
-It is true that you could construct a more robust system, perhaps even
-with added redundancy.
-But it is also true that I can always get a bigger hammer.
+\cref{fig:advsync:Hard Real-Time Response; Meet Hammer}.
+Yes, you could construct a more robust system, perhaps with redundancy.
+But your adversary can always get a bigger hammer.
\begin{figure}[bt]
\centering
@@ -155,8 +153,8 @@
\label{sec:advsync:Real-World Real Time}
Although sentences like ``Hard real-time systems \emph{always} meet
-their deadlines!'' can be catchy and are no doubt easy to memorize,
-something else is needed for real-world real-time systems.
+their deadlines!'' are catchy and easy to memorize, something else is
+needed for real-world real-time systems.
Although the resulting specifications are
harder to memorize, they can simplify construction of a real-time
system by imposing constraints on the environment, the workload, and
@@ -169,7 +167,7 @@
promises of response times implied by ``hard real time''.
These constraints might specify permissible operating temperatures,
air quality, levels and types of electromagnetic radiation, and, to
-\cref{fig:advsync:Hard Real-Time Response Guarantee; Meet Hammer}'s
+\cref{fig:advsync:Hard Real-Time Response; Meet Hammer}'s
point, levels of shock and vibration.
Of course, some constraints are easier to meet than others.
@@ -177,7 +175,7 @@
commodity computer components often refuse to operate at sub-freezing
temperatures, which suggests a set of climate-control requirements.
-An old college friend once had to meet the challenge of operating
+An old college friend once had the challenge of operating
a real-time system in an atmosphere featuring some rather aggressive
chlorine compounds, a challenge that he wisely handed off to his
colleagues designing the hardware.
@@ -197,21 +195,20 @@
And in this case, the resulting electromagnetic pulses were sufficient
to induce a quarter of a volt potential difference in the leads of
a small ``rubber ducky'' antenna located more than 400 meters away.
-This means that nearby conductors saw larger voltages, courtesy of the
-inverse-square law.
-This includes those
-conductors making up the computer controlling the sputtering process.
+This meant that nearby conductors experienced higher voltages, courtesy
+of the inverse-square law.
+This included those conductors making up the computer controlling the
+sputtering process.
In particular, the voltage induced on that computer's reset line was
-sufficient to actually reset the computer, to the consternation of everyone
-involved.
-In this case, the challenge was also met using hardware, including some
-elaborate shielding and a fiber-optic network with the lowest bitrate
-I have ever heard of, namely 9600 baud.
-That said, less spectacular electromagnetic environments can often be
-handled by software through use of error detection and correction codes.
+sufficient to actually reset the computer, mystifying everyone involved.
+This situation was addressed using hardware, including some elaborate
+shielding and a fiber-optic network with the lowest bitrate I have ever
+heard of, namely 9600 baud.
+Less spectacular electromagnetic environments can often be handled by
+software through use of error detection and correction codes.
That said, it is important to remember that although error detection and
correction codes can reduce failure rates, they normally cannot reduce
-them all the way down to zero, which can form yet another obstacle
+them all the way down to zero, which can present yet another obstacle
to achieving hard real-time response.
There are also situations where a minimum level of energy
@@ -223,9 +220,8 @@
But what about battery-powered systems?
They don't require energy flowing into the system as a whole.
}\QuickQuizAnswer{
- Sooner or later, either the battery must be recharged, which
- requires energy to flow into the system, or the system will
- stop operating.
+ Sooner or later, the battery must be recharged, which requires
+ energy to flow into the system.
}\QuickQuizEnd
A number of systems are intended to operate in environments with impressive
@@ -256,10 +252,9 @@
However, all of these methods have one thing in common: Although they
can reduce the probability of failure, they cannot reduce it to zero.
-Although these severe environmental conditions are often addressed by using
-more robust hardware, the
-workload and application constraints in the next two sections are often
-handled in software.
+These environmental challenges are often met via robust hardware, however,
+the workload and application constraints in the next two sections are
+often handled in software.
\paragraph{Workload Constraints}
\label{sec:advsync:Workload Constraints}
@@ -281,7 +276,7 @@
This approach also applies to storage and networking devices.
In some cases, separate storage and networking hardware might be reserved
for the sole use of high-priority portions of the real-time application.
-It is of course not unusual for this hardware to be mostly idle, given
+In short, it is not unusual for this hardware to be mostly idle, given
that response time is more important than throughput in
real-time systems.
@@ -297,9 +292,9 @@
Those queueing-theory results assume infinite ``calling populations'',
which in the Linux kernel might correspond to an infinite number
of tasks.
- As of mid-2016, no real system supports an infinite number of tasks,
- so results assuming infinite calling populations should be
- expected to have less-than-infinite applicability.
+ As of early 2021, no real system supports an infinite number of
+ tasks, so results assuming infinite calling populations should
+ be expected to have less-than-infinite applicability.
Other queueing-theory results have \emph{finite}
calling populations, which feature sharply bounded response
@@ -340,8 +335,8 @@
There might also be constraints on the non-real-time portions of the
application.
-For example, is the non-real-time application permitted to use CPUs used
-by the real-time portion?
+For example, is the non-real-time application permitted to use the CPUs
+intended for the real-time portion?
Are there time periods during which the real-time portion of the application
is expected to be unusually busy, and if so, is the non-real-time portion
of the application permitted to run at all during those times?
@@ -388,7 +383,7 @@
a thin sheet of wood (called ``veneer'') from a spinning log must:
(1)~Load the log into the lathe,
(2)~Position the log on the lathe's chucks so as to expose the largest
-cylinder contained in the log to the blade,
+cylinder contained within that log to the blade,
(3)~Start spinning the log,
(4)~Continuously vary the knife's position so as to peel the log into veneer,
(5)~Remove the remaining core of the log that is too small to peel, and
@@ -396,11 +391,12 @@
Each of these six phases of operation might well have its own set of
deadlines and environmental constraints,
for example, one would expect phase~4's deadlines to be much more severe
-than those of phase~6, milliseconds instead of seconds.
+than those of phase~6, as in milliseconds rather than seconds.
One might therefore expect that low-priority work would be performed in
phase~6 rather than in phase~4.
-That said, careful choices of hardware, drivers, and software configuration
-would be required to support phase~4's more severe requirements.
+In any case, careful choices of hardware, drivers, and software
+configuration would be required to support phase~4's more severe
+requirements.
A key advantage of this phase-by-phase approach is that the latency
budgets can be broken down, so that the application's various components
@@ -416,25 +412,25 @@
A successful validation effort will almost always include a good test
suite, which might be unsatisfying to the theorists, but has the virtue
of helping to get the job done.
-As a point of fact, as of early 2015, most real-world real-time system
+As a point of fact, as of early 2021, most real-world real-time system
use an acceptance test rather than formal proofs.
-That said, the widespread use of test suites to validate real-time systems
+However, the widespread use of test suites to validate real-time systems
does have a very real disadvantage, namely that real-time software is
validated only on specific hardware in specific hardware and software
configurations.
Adding additional hardware and configurations requires additional costly and
time-consuming testing.
Perhaps the field of formal verification will advance sufficiently to
-change this situation, but as of early 2015, rather
+change this situation, but as of early 2021, rather
large advances are required.
\QuickQuiz{
Formal verification is already quite capable, benefiting from
decades of intensive study.
- Are additional advances \emph{really} required, or is this
- just a practitioner's excuse to continue to be lazy and ignore
- the awesome power of formal verification?
+ Are additional advances \emph{really} required, or is this just
+ a practitioner's excuse to continue to lazily ignore the awesome
+ power of formal verification?
}\QuickQuizAnswer{
Perhaps this situation is just a theoretician's excuse to avoid
diving into the messy world of real software?
@@ -460,6 +456,11 @@
All that said, there is hope, given recent work formalizing
the memory models of real computer
systems~\cite{JadeAlglave2011ppcmem,Alglave:2013:SVW:2450268.2450306}.
+ On the other hand, formal verification has just as much trouble
+ as does testing with the astronomical number of variants of the
+ Linux kernel that can be constructed from different combinations
+ of its tens of thousands of Kconfig options.
+ Sometimes life is hard!
}\QuickQuizEnd
In addition to latency requirements for the real-time portions of the
@@ -477,12 +478,12 @@
It is hoped that this outline clearly demonstrates the inadequacy of
the sound-bite-based approach to real-time computing.
-\subsection{Who Needs Real-Time Computing?}
-\label{sec:advsync:Who Needs Real-Time Computing?}
+\subsection{Who Needs Real-Time?}
+\label{sec:advsync:Who Needs Real-Time?}
It is possible to argue that all computing is in fact real-time computing.
-For one moderately extreme example, when you purchase a birthday gift online,
-you would like the gift to arrive before the recipient's birthday.
+For one example, when you purchase a birthday gift online, you expect
+the gift to arrive before the recipient's birthday.
And in fact even turn-of-the-millennium web services observed sub-second
response constraints~\cite{KristofferBohmann2001a}, and requirements have
not eased with the passage of time~\cite{DeCandia:2007:DAH:1323293.1294281}.
@@ -507,9 +508,9 @@
easily developed using standard non-real-time approaches, or
whether the more difficult and expensive real-time approaches
are required.
- In other words, theory is quite important, however, for those
- of us who like to get things done, theory supports practice,
- never the other way around.
+ In other words, although theory is quite important, for those of
+ us called upon to complete practical projects, theory supports
+ practice, never the other way around.
}\QuickQuizEnd
Real-time computing is used in industrial-control applications, ranging from
@@ -519,7 +520,7 @@
large Earth-bound telescopes to de-twinkle starlight;
military applications, including the afore-mentioned avionics;
and financial-services applications, where the first computer to recognize
-an opportunity is likely to reap most of the resulting profit.
+an opportunity is likely to reap most of the profit.
These four areas could be characterized as ``in search of production'',
``in search of life'', ``in search of death'', and ``in search of money''.
@@ -544,8 +545,8 @@
need for real-time
computing~\cite{JeremyWPeters2006NYTDec11,BillInmon2007a}.
-\subsection{Who Needs Parallel Real-Time Computing?}
-\label{sec:advsync:Who Needs Parallel Real-Time Computing?}
+\subsection{Who Needs Parallel Real-Time?}
+\label{sec:advsync:Who Needs Parallel Real-Time?}
It is less clear who really needs parallel real-time computing, but
the advent of low-cost multicore systems has brought it to the fore
@@ -553,10 +554,10 @@
Unfortunately, the traditional mathematical basis for real-time
computing assumes single-CPU systems, with a few exceptions that
prove the rule~\cite{BjoernBrandenburgPhD}.
-That said, there are a couple of ways of squaring modern computing
+Fortunately, there are a couple of ways of squaring modern computing
hardware to fit the real-time mathematical circle, and a few Linux-kernel
hackers have been encouraging academics to make this
-transition~\cite{ThomasGleixner2010AcademiaVsReality}.
+transition~\cite{DanielBristot2019RTtrace,ThomasGleixner2010AcademiaVsReality}.
\begin{figure}[tb]
\centering
@@ -566,14 +567,15 @@
\end{figure}
One approach is to recognize the fact that many real-time systems
-reflect biological nervous systems, with responses ranging from
+resemble biological nervous systems, with responses ranging from
real-time reflexes to non-real-time strategizing and planning,
as depicted in
\cref{fig:advsync:Real-Time Reflexes}.
The hard real-time reflexes, which read from sensors and control
-actuators, run real-time on a single CPU, while the non-real-time
-strategy and planning portion of the application runs on the multiple
-remaining CPUs.
+actuators, run real-time on a single CPU or on special-purpose hardware
+such as an FPGA.
+The non-real-time strategy and planning portion of the application runs
+on the remaining CPUs.
Strategy and planning activities might include statistical analysis,
periodic calibration, user interface, supply-chain activities, and
preparation.
@@ -583,8 +585,7 @@
While one CPU is attending to the high-speed real-time computations
required to peel one log, the other CPUs might be analyzing the size
and shape of the next log in order to determine how to position the
-next log so as to obtain the greatest possible quantity of high-quality
-veneer.
+next log so as to obtain the largest cylinder of high-quality wood.
It turns out that many applications have non-real-time and real-time
components~\cite{RobertBerry2008IBMSysJ}, so this approach can
often be used to allow traditional real-time analysis to be combined
@@ -612,16 +613,16 @@
An event-driven real-time system remains idle much of the time, responding
in real time to events passed up through the operating system to the
application.
-Alternatively, the system could be running a background non-real-time
-workload instead of remaining mostly idle.
-A polling real-time system features a real-time thread that is CPU bound,
-running in a tight loop that polls inputs and updates outputs on each
-pass through the loop.
+Alternatively, the system could instead be running a background
+non-real-time workload.
+A polling real-time system features a real-time thread that is CPU
+bound, running in a tight loop that polls inputs and updates outputs on
+each pass.
This tight polling loop often executes entirely in user mode, reading from
and writing to hardware registers that have been mapped into the user-mode
application's address space.
Alternatively, some applications place the polling loop into the kernel,
-for example, via use of loadable kernel modules.
+for example, using loadable kernel modules.
\begin{figure}[tb]
\centering
@@ -656,7 +657,7 @@
latencies, but with all the same caveats as for the 2.6.x and 3.x kernels.
A Linux kernel incorporating the \rt\ patchset can provide latencies
well below 20 microseconds, and specialty real-time operating systems (RTOSes)
-running without memory translation can provide sub-ten-microsecond
+running without MMUs can provide sub-ten-microsecond
latencies.
Achieving sub-microsecond latencies typically requires hand-coded assembly
or even special-purpose hardware.
@@ -664,9 +665,9 @@
Of course, careful configuration and tuning are required all the way down
the stack.
In particular, if the hardware or firmware fails to provide real-time
-latencies, there is nothing that the software can do to make up the
+latencies, there is nothing that the software can do to make up for the
lost time.
-And high-performance hardware sometimes sacrifices worst-case behavior
+Worse yet, high-performance hardware sometimes sacrifices worst-case behavior
to obtain greater throughput.
In fact, timings from tight loops run with interrupts disabled can
provide the basis for a high-quality random-number
@@ -680,8 +681,6 @@
environments~\cite{ThomasGleixner2012KVMrealtime,JanKiszka2014virtRT}.
It is therefore critically important to evaluate your hardware's and
firmware's real-time capabilities.
-There are organizations who carry out such evaluations, including
-the Open Source Automation Development Lab (OSADL).
But given competent real-time hardware and firmware, the next
layer up the stack is the operating system, which is covered in
@@ -707,8 +706,8 @@
boxes represent real-time processes running on the RTOS.
This was a very popular approach before the Linux kernel gained
-real-time capabilities, and is still in use
-today~\cite{Xenomai2014,VictorYodaiken2004a}.
+real-time capabilities, and is still in
+use~\cite{Xenomai2014,VictorYodaiken2004a}.
However, this approach requires that the application be split into
one portion that runs on the RTOS and another that runs on Linux.
Although it is possible to make the two environments look similar,
@@ -724,7 +723,7 @@
In fact, these problems seem to be what drove the combination of
RTOSes with Linux, as this approach allowed access to the full real-time
capabilities of the RTOS, while allowing the application's non-real-time
-code full access to Linux's rich and vibrant open-source ecosystem.
+code full access to Linux's open-source ecosystem.
\begin{figure*}[p]
\centering
@@ -761,10 +760,12 @@
non-real-time Linux processes shown in the upper left anytime the
non-real-time process is executing in user mode.
-The preemptible kernels shown in the middle row of
+The middle row of
\cref{fig:advsync:Linux-Kernel Real-Time Implementations}
-are built with \co{CONFIG_PREEMPT=y}, so that most process-level code
-within the Linux kernel can be preempted.
+shows three stages (from left to right) in the development of Linux's
+preemptible kernels.
+In all three stages, most process-level code within the Linux kernel
+can be preempted.
This of course greatly improves real-time response latency, but
preemption is still disabled
within RCU read-side critical sections,
@@ -783,6 +784,18 @@
It will instead be discussed in
\cref{sec:advsync:Event-Driven Real-Time Support}.
+The bottom row of
+\cref{fig:advsync:Linux-Kernel Real-Time Implementations}
+shows the \rt\ patchset, which features threaded (and thus preemptible)
+interrupt handlers for many devices, which also allows the corresponding
+``interrupt-disabled'' regions of these drivers to be preempted.
+These drivers instead use locking to coordinate the process-level
+portions of each driver with its threaded interrupt handlers.
+Finally, in some cases, disabling of preemption is replaced by
+disabling of migration.
+These measures result in excellent response times in many systems running
+the \rt\ patchset~\cite{Reghenzani:2019:RLK:3309872.3297714,DanielBristot2019RTtrace}.
+
\begin{figure}[tb]
\centering
\resizebox{2.5in}{!}{\includegraphics{advsync/nohzfull}}
@@ -800,17 +813,15 @@
kernel daemons.
However, when there is only one runnable task on a given non-housekeeping CPU,
scheduling-clock interrupts are shut off on that CPU, removing an important
-source of interference and \emph{OS jitter}.\footnote{
- A once-per-second residual scheduling-clock interrupt remains
- due to process-accounting concerns.
- Future work includes addressing these concerns and eliminating
- this residual interrupt.}
+source of interference and \emph{OS jitter}.
With a few exceptions, the kernel does not force other processing off of the
non-housekeeping CPUs, but instead simply provides better performance
when only one runnable task is present on a given CPU.
+Any number of userspace tools may be used to force a given CPU to have
+no more that one runnable task.
If configured properly, a non-trivial undertaking, \co{CONFIG_NO_HZ_FULL}
-offers real-time threads levels of performance nearly rivaling that of
-bare-metal systems.
+offers real-time threads levels of performance that come close to those of
+bare-metal systems~\cite{AbdullahAljuhni2018nohzfull}.
There has of course been much debate over which of these approaches
is best for real-time systems, and this debate has been going on for
@@ -964,9 +975,17 @@
is good and sufficient.
Another key observation is that error-handling timeouts are normally
canceled very early, often before they can be cascaded.
-A final observation is that systems commonly have many more error-handling
-timeouts than they do timer events, so that an $\O{\log n}$
-data structure should provide acceptable performance for timer events.
+In addition, systems commonly have many more error-handling timeouts
+than they do timer events, so that an $\O{\log n}$ data structure should
+provide acceptable performance for timer events.
+
+However, it is possible to do better, namely by simply refusing to
+cascade timers.
+Instead of cascading, the timers that would otherwise have been cascaded
+all the way down the calendar queue are handled in place.
+This does result in up to a few percent error for the time duration,
+but the few situations where this is a problem can instead use tree-based
+high-resolution timers (hrtimers).
In short, the Linux kernel's \rt\ patchset uses timer wheels for
error-handling timeouts and a tree for timer events, providing each
@@ -1047,7 +1066,7 @@
threads from preempting it.
In the priority-inheritance solution, the high-priority thread attempting
-to acquire the lock donate its priority to the low-priority thread holding
+to acquire the lock donates its priority to the low-priority thread holding
the lock until such time as the lock is released, thus preventing long-term
priority inversion.
@@ -1125,7 +1144,7 @@
However, this approach clearly and severely limits read-side
scalability.
- The Linux kernel's \rt\ patchset has been able to live with this
+ The Linux kernel's \rt\ patchset was long able to live with this
limitation for several reasons: (1)~Real-time systems have
traditionally been relatively small, (2)~Real-time systems
have generally focused on process control, thus being unaffected
@@ -1133,12 +1152,45 @@
(3)~Many of the Linux kernel's reader-writer locks have been
converted to RCU.
- All that aside, it is quite possible that the Linux kernel
- will some day permit limited read-side parallelism for
- reader-writer locks subject to priority boosting.
+ However, the day came when it was absolutely necessary to
+ permit concurrent readers, as described in the text following
+ this quiz.
}\QuickQuizEnd
-In some cases, reader-writer lock priority inversion can be avoided by
+The no-concurrent-readers restriction eventually became intolerable, so
+the \rt\ developers looked more carefully at how the Linux kernel uses
+reader-writer spinlocks.
+They learned that time-critical code rarely uses those parts of the
+kernel that write-acquire reader-writer locks, so that the prospect
+of writer starvation was not a show-stopper.
+They therefore constructed a real-time reader-writer lock in which
+write-side acquisitions use priority inheritance among each other,
+but where read-side acquisitions take absolute priority over
+write-side acquisitions.
+This approach appears to be working well in practice, and is another
+lesson in the importance of clearly understanding what your users
+really need.
+
+One interesting detail of this implementation is that both the
+\co{rt_read_lock()} and the \co{rt_write_lock()} functions enter an RCU
+read-side critical section and both the \co{rt_read_unlock()} and the
+\co{rt_write_unlock()} functions exit that critical section.
+This is necessary because the vanilla kernel's reader-writer locking
+functions disable preemption across their critical sections, and
+there really are reader-writer locking use cases that rely on the fact
+that \co{synchronize_rcu()} will therefore wait for all pre-exiting
+reader-writer-lock critical sections to complete.
+Let this be a lesson to you:
+Understanding what your users really need is critically important to
+correct operation, not just to performance.
+Not only that, but what your users really need changes over time.
+
+This has the side-effect that all of a \rt\ kernel's reader-writer locking
+critical sections are subject to RCU priority boosting.
+This provides at least a partial solution to the problem of reader-writer
+lock readers being preempted for extended periods of time.
+
+It is also possible to avoid reader-writer lock priority inversion by
converting the reader-writer lock to RCU, as briefly discussed in the
next section.
@@ -1166,19 +1218,12 @@
void __rcu_read_unlock(void) \lnlbl[unl:b]
{
- struct task_struct *t = current;
-
- if (t->rcu_read_lock_nesting != 1) { \lnlbl[unl:chkn]
- --t->rcu_read_lock_nesting; \lnlbl[unl:dec]
- } else { \lnlbl[unl:els:b]
- barrier(); \lnlbl[unl:bar1]
- t->rcu_read_lock_nesting = INT_MIN; \lnlbl[unl:neg]
+ barrier(); \lnlbl[unl:bar1]
+ if (!--current->rcu_read_lock_nesting) \lnlbl[unl:decchk]
barrier(); \lnlbl[unl:bar2]
- if (READ_ONCE(t->rcu_read_unlock_special.s)) \lnlbl[unl:chks]
- rcu_read_unlock_special(t); \lnlbl[unl:unls]
- barrier(); \lnlbl[unl:bar3]
- t->rcu_read_lock_nesting = 0; \lnlbl[unl:zero]
- } \lnlbl[unl:els:e]
+ if (READ_ONCE(current->rcu_read_unlock_special.s)) { \lnlbl[unl:chks]
+ rcu_read_unlock_special(t); \lnlbl[unl:unls]
+ } \lnlbl[unl:if:e]
} \lnlbl[unl:e]
\end{VerbatimL}
\end{fcvlabel}
@@ -1211,23 +1256,16 @@
\end{fcvref}
\begin{fcvref}[ln:advsync:Preemptible Linux-Kernel RCU:unl]
-\Clnref{chkn} of \co{__rcu_read_unlock()} checks to see if the nesting
-level count is one, in other words, if this corresponds to the outermost
+\Clnref{bar1} of \co{__rcu_read_unlock()} prevents the compiler from
+reordering the code in the critical section with the remainder of
+this function.
+\Clnref{decchk} decrements the nesting count and checks to see if it
+has become zero, in other words, if this corresponds to the outermost
\co{rcu_read_unlock()} of a nested set.
-If not, \clnref{dec} decrements this count, and control returns to the caller.
-Otherwise, this is the outermost \co{rcu_read_unlock()}, which requires
-the end-of-critical-section handling carried out by \clnrefrange{els:b}{els:e}.
-
-\Clnref{bar1} prevents the compiler from reordering the code in the critical
-section with the code comprising the \co{rcu_read_unlock()}.
-\Clnref{neg} sets the nesting count to a large negative number
-in order to prevent
-destructive races with RCU read-side critical sections contained within
-interrupt handlers~\cite{PaulEMcKenney2011RCU3.0trainwreck},
-and \clnref{bar2} prevents the compiler from reordering this assignment with
-\clnref{chks}'s check for special handling.
-If \clnref{chks} determines that special handling is required, \clnref{unls}
-invokes \co{rcu_read_unlock_special()} to carry out that special handling.
+If so, \clnref{bar2} prevents the compiler from reordering this nesting
+update with \clnref{chks}'s check for special handling.
+If special handling is required, then the call to
+\co{rcu_read_unlock_special()} on \lnref{unls} carries it out.
There are several types of special handling that can be required, but
we will focus on that required when the RCU read-side critical section
@@ -1242,10 +1280,6 @@
attempt to acquire any locks.
In addition, if implemented carefully, locking can be used to synchronize
real-time software~\cite{BjoernBrandenburgPhD,DipankarSarma2004OLSscalability}.
-
-Whether or not special handling is required, \clnref{bar3} prevents the compiler
-from reordering the check on \clnref{chks} with the zeroing of the nesting
-count on \clnref{zero}.
\end{fcvref}
\QuickQuiz{
@@ -1266,28 +1300,74 @@
the context switch to complete.
}\QuickQuizEnd
-This preemptible RCU implementation enables real-time response for
+Another important real-time feature of RCU, whether preemptible or
+not, is the ability to offload RCU callback execution to a kernel
+thread.
+To use this, your kernel must be built with \co{CONFIG_RCU_NOCB_CPU=y}
+and booted with the \co{rcu_nocbs=} kernel boot parameter specifying
+which CPUs are to be offloaded.
+Alternatively, any CPU specified by the \co{nohz_full=} kernel boot parameter
+described in
+\cref{sec:advsync:Polling-Loop Real-Time Support}
+will also have its RCU callbacks offloaded.
+
+In short, this preemptible RCU implementation enables real-time response for
read-mostly data structures without the delays inherent to priority
-boosting of large numbers of readers.
+boosting of large numbers of readers, and also without delays due to
+callback invocation.
\paragraph{Preemptible spinlocks}
are an important part of the \rt\ patchset due to the long-duration
spinlock-based critical sections in the Linux kernel.
-This functionality has not yet reached mainline: Although they are a conceptually
-simple substitution of sleeplocks for spinlocks, they have proven relatively
-controversial.\footnote{
- In addition, development of the \rt\ patchset has slowed in recent
- years, perhaps because the real-time functionality that is already
- in the mainline Linux kernel suffices for a great many use
- cases~\cite{JakeEdge2013Future-rtLinux,JakeEdge2014Future-rtLinux}.
- However, OSADL (\url{http://osadl.org/}) is working to raise funds
- to move the remaining code from the \rt\ patchset to mainline.}
-However, they are quite necessary to the task of achieving real-time
-latencies down in the tens of microseconds.
+This functionality has not yet reached mainline: Although they are a
+conceptually simple substitution of sleeplocks for spinlocks, they have
+proven relatively controversial.
+In addition the real-time functionality that is already
+in the mainline Linux kernel suffices for a great many use
+cases, which limited \rt\ development rate around
+2014~\cite{JakeEdge2013Future-rtLinux,JakeEdge2014Future-rtLinux}.
+However, preemptible spinlocks are absolutely necessary to the task of
+achieving real-time latencies down in the tens of microseconds.
+Fortunately, Linux Foundation organized an effort to fund moving the
+remaining code from the \rt\ patchset to mainline.
+\paragraph{Per-CPU variables}\ are used heavily in the Linux kernel
+for performance reasons.
+Unfortunately for real-time applications, many use cases for per-CPU
+variables require coordinated update of multiple such variables,
+which is normally provided by disabling preemption, which in turn
+degrades real-time latencies.
+Real-time applications clearly need some other way of coordinating
+per-CPU variable updates.
+
+One alternative is to supply per-CPU spinlocks, which as noted above
+are actually sleeplocks, so that their critical sections can be
+preempted and so that priority inheritance is provided.
+In this approach, code updating groups of per-CPU variables must
+acquire the current CPU's spinlock, carry out the update, then
+release whichever lock is acquired, keeping in mind that a preemption
+might have resulted in a migration to some other CPU.
+However, this approach introduces both overhead and deadlocks.
+
+Another alternative, which is used in the \rt\ patchset as of early 2021,
+is to convert preemption disabling to migration disabling.
+This ensures that a given kernel thread remains on its CPU through
+the duration of the per-CPU-variable update, but could also allow some
+other kernel thread to intersperse its own update of those same variables,
+courtesy of preemption.
+There are cases such as statistics gathering where this is not a problem.
+In the surprisingly rare case where such mid-update preemption is a problem,
+the use case at hand must properly synchronize the updates, perhaps through
+a set of per-CPU locks specific to that use case.
+Although introducing locks again introduces the possibility of deadlock,
+the per-use-case nature of these locks makes any such deadlocks easier
+to manage and avoid.
+
+\paragraph{Closing event-driven remarks.}
There are of course any number of other Linux-kernel components that are
critically important to achieving world-class real-time latencies,
-most recently deadline scheduling,
+for example, deadline
+scheduling~\cite{DanielBristot2018deadlinesched-1,DanielBristot2018deadlinesched-2},
however, those listed in this section give a good feeling for the workings
of the Linux kernel augmented by the \rt\ patchset.
@@ -1309,8 +1389,8 @@
Although the reality is of course more complex, it is becoming
possible to do just that,
courtesy of the \co{NO_HZ_FULL} implementation led by
-Frederic Weisbecker~\cite{JonCorbet2013NO-HZ-FULL,FredericWeisbecker2013nohz} that has been
-accepted into version 3.10 of the Linux kernel.
+Frederic Weisbecker~\cite{JonCorbet2013NO-HZ-FULL,FredericWeisbecker2013nohz}
+that was accepted into version 3.10 of the Linux kernel.
Nevertheless, considerable care is required to properly set up such
an environment, as it is necessary to control a number of possible
sources of OS jitter.
@@ -1329,7 +1409,7 @@
housekeeping CPUs, and to force all interrupts to these CPUs.
The \path{Documentation/IRQ-affinity.txt} file in the Linux source tree
describes how to direct device interrupts to specified CPU,
-which as of early 2015 involves something like the following:
+which as of early 2021 involves something like the following:
\begin{VerbatimU}
$ echo 0f > /proc/irq/44/smp_affinity
@@ -1371,17 +1451,16 @@
\end{VerbatimU}
You will of course need to be running as root to execute this command,
-and you will also need to carefully consider the Spiderman principle.
+and you will also need to carefully consider the aforementioned Spiderman
+principle.
One way to minimize the risks is to offload interrupts and
kernel threads/daemons from all CPUs running CPU-bound real-time
threads, as described in the paragraphs above.
In addition, you should carefully read the material in the
\path{Documentation/scheduler} directory.
-The material in the \path{sched-rt-group.txt} file is particularly
+The material in the \path{sched-rt-group.rst} file is particularly
important, especially if you are using the \co{cgroups} real-time features
-enabled by the \co{CONFIG_RT_GROUP_SCHED} Kconfig parameter, in which
-case you should also read the material in the
-\path{Documentation/cgroups} directory.
+enabled by the \co{CONFIG_RT_GROUP_SCHED} Kconfig parameter.
A fourth source of OS jitter comes from timers.
In most cases, keeping a given CPU out of the kernel will prevent
@@ -1410,7 +1489,7 @@
workloads and fix any real-time bugs.\footnote{
If you take this approach, please submit your fixes upstream
so that others can benefit.
- Keep in mind that when you need to port your application to
+ After all, when you need to port your application to
a later version of the Linux kernel, \emph{you} will be one of those
``others''.}
@@ -1419,7 +1498,7 @@
the global TLB-flush algorithm.
This can be avoided by avoiding memory-unmapping operations, and especially
avoiding unmapping operations within the kernel.
-As of early 2015, the way to avoid in-kernel
+As of early 2021, the way to avoid in-kernel
unmapping operations is to avoid unloading kernel modules.
A seventh source of OS jitter is provided by
@@ -1453,8 +1532,6 @@
A ninth source of OS jitter is unfortunately the hardware and firmware.
It is therefore important to use systems that have been designed for
real-time use.
-OSADL runs long-term tests of systems, so referring to their
-website (\url{http://osadl.org/}) can be helpful.
\begin{listing}[tb]
\begin{fcvlabel}[ln:advsync:Locating Sources of OS Jitter]
@@ -1530,7 +1607,7 @@
As in all areas of engineering, a robust set of components is essential
to productivity and reliability.
This section is not a full catalog of real-time software components---such
-a catalog would fill an entire book---but rather a brief overview of the
+a catalog would fill multiple books---but rather a brief overview of the
types of components available.
A natural place to look for real-time software components would be
@@ -1538,10 +1615,9 @@
synchronization~\cite{Herlihy91}, and in fact lockless
algorithms are very important to real-time computing.
However, wait-free synchronization only guarantees forward progress in
-finite time, and real-time computing requires algorithms that meet the
-far more stringent guarantee of forward progress in bounded time.
-After all, a century is finite, but unhelpful when your deadlines are
-measured in milliseconds.
+finite time.
+Although a century is finite, this is unhelpful when your deadlines are
+measured in microseconds, let alone milliseconds.
Nevertheless, there are some important wait-free algorithms that do
provide bounded response time, including atomic test and set,
@@ -1553,15 +1629,13 @@
algorithms with lock-free guarantees\footnote{
Wait-free algorithms guarantee that all threads make progress in
finite time, while lock-free algorithms only guarantee that at
- least one thread will make progress in finite time.}
-provide the same latencies in practice assuming a stochastically
-fair scheduler and freedom from fail-stop
-bugs~\cite{DanAlitarh2013PracticalProgress}.\footnote{
- This paper also introduces the notion of \emph{bounded minimal
- progress}, which is a welcome step on the part of theory
- towards real-time practice.}
-This means that lock-free stacks and queues are appropriate
-for real-time use.
+ least one thread will make progress in finite time.
+ See \cref{sec:advsync:Non-Blocking Synchronization} for more details.}
+also provide the same latencies in practice (in the wait-free sense),
+assuming a stochastically fair scheduler and absence of fail-stop
+bugs~\cite{DanAlitarh2013PracticalProgress}.
+This means that many non-wait-free stacks and queues are nevertheless
+appropriate for real-time use.
\QuickQuiz{
But isn't correct operation despite fail-stop bugs
@@ -1665,12 +1739,11 @@
general-purpose operating system is to use the Linux kernel's
\co{NO_HZ_FULL} capability, described in
\cref{sec:advsync:Polling-Loop Real-Time Support}.
-This support first became available in version 3.10 of the Linux kernel.
\subsubsection{Streaming Applications}
\label{sec:advsync:Streaming Applications}
-A popular sort of big-data real-time application takes input from numerous
+One type of big-data real-time application takes input from numerous
sources, processes it internally, and outputs alerts and summaries.
These \emph{streaming applications} are often highly parallel, processing
different information sources concurrently.
@@ -1857,9 +1930,12 @@
the call to \co{malloc()}???
}\QuickQuizAnswerB{
In early 2016, situations forbidding runtime memory were
- also not so excited with multithreaded computing.
+ also not at all interested in multithreaded computing.
So the runtime memory allocation is not an additional
obstacle to safety criticality.
+
+ However, by 2020 runtime memory allocation in multi-core
+ real-time systems was gaining some traction.
}\QuickQuizEndB
%
\QuickQuizE{
@@ -1868,6 +1944,9 @@
}\QuickQuizAnswerE{
Indeed you do, and you could use any of a number of techniques
discussed earlier in this book.
+ One of those techniques is use of a single updater thread,
+ which would result in exactly the code shown in \co{update_cal()}
+ in \cref{lst:advsync:Real-Time Calibration Using RCU}.
}\QuickQuizEndE
}
@@ -1892,9 +1971,9 @@
\end{figure}
The choice between real-time and real-fast computing can be a difficult one.
-Because real-time systems often inflict a throughput penalty on non-real-time
-computing, using real-time when it is not required can cause problems,
-as fancifully depicted by
+Because real-time systems often inflict a throughput penalty on
+non-real-time computing, using real-time when it is not required is
+unwise, as fancifully depicted by
\cref{fig:advsync:The Dark Side of Real-Time Computing}.
On the other hand, failing to use real-time when it \emph{is} required
can also cause problems, as fancifully depicted by
diff --git a/bib/os.bib b/bib/os.bib
index b48afc4..38b8464 100644
--- a/bib/os.bib
+++ b/bib/os.bib
@@ -1332,7 +1332,7 @@
@unpublished{JonCorbet2013NO-HZ-FULL,
author="Jonathan Corbet",
- title="(Nearly) full tickless operation in 3.10",
+ title="{(Nearly)} full tickless operation in 3.10",
year="2013",
month="May",
day="8",
diff --git a/bib/realtime.bib b/bib/realtime.bib
index 01b2486..fc9c209 100644
--- a/bib/realtime.bib
+++ b/bib/realtime.bib
@@ -589,9 +589,29 @@
lastchecked="November 4, 2016",
}
+@unpublished{DanielBristot2018deadlinesched-1,
+ Author="Daniel Bristot de Oliveira",
+ Title="Deadline scheduling part 1 -- overview and theory",
+ month="January",
+ day="16",
+ year="2018",
+ note="URL: \url{https://lwn.net/Articles/743740/}",
+ lastchecked="February 26, 2021",
+}
+
+@unpublished{DanielBristot2018deadlinesched-2,
+ Author="Daniel Bristot de Oliveira",
+ Title="Deadline scheduler part 2 -- details and usage",
+ month="January",
+ day="19",
+ year="2018",
+ note="URL: \url{https://lwn.net/Articles/743946/}",
+ lastchecked="February 26, 2021",
+}
+
@article{Reghenzani:2019:RLK:3309872.3297714,
author = {Reghenzani, Federico and Massari, Giuseppe and Fornaciari, William},
- title = {The Real-Time Linux Kernel: A Survey on PREEMPT_RT},
+ title = {The Real-Time {Linux} Kernel: A Survey on {PREEMPT\_RT}},
journal = {ACM Comput. Surv.},
issue_date = {February 2019},
volume = {52},
@@ -612,7 +632,7 @@
@article{DanielBristot2019RTtrace,
author = {de Oliveira, Daniel Bristot and Cucinotta, Tommaso and de Oliveira, R\^{o}mulo Silva},
- title = {Modeling the Behavior of Threads in the {PREEMPT\_RT} Linux Kernel Using Automata},
+ title = {Modeling the Behavior of Threads in the {PREEMPT\_RT} {Linux} Kernel Using Automata},
year = {2019},
issue_date = {October 2019},
publisher = {Association for Computing Machinery},
diff --git a/formal/formal.tex b/formal/formal.tex
index a2c48b6..d2047c9 100644
--- a/formal/formal.tex
+++ b/formal/formal.tex
@@ -54,7 +54,7 @@
%
\epigraph{Western thought has focused on True-False;
it is high time to shift to Robust-Fragile.}
- {\emph{summarized from Nassim Nicholas Taleb}}
+ {\emph{Nassim Nicholas Taleb, summarized}}
% Full quote:
% Since Plato, Western thought and the theory of knowledge has focused on
% the notions of True-False; as commendable as that was, it is high time
