Dynamic Analysis and Profiling of Multithreaded Systems - Advanced Operating Systems and Kernel Applications - page 159

reverse engineering. These models can then be
analyzed to derive and ensure behavioral char-
acteristics. Model checking (Clarke, Grumberg,
& Peled, 2000) is a static analysis technique that
is often applied to multithreaded programs to
explore all feasible interleavings exhaustively to
ensure correctness properties, such as absence
of deadlock and livelock (Rinard, 2001). This
approach can check all feasible paths of execution
(and interleavings) and thus avoid leaving any
behavior unchecked.
In practice, model checking is computationally
expensive and limited in its applicability, due to
the vast number of feasible interleavings a large
multithreaded system may exhibit. Other forms
of static analysis, such as automated checking of
design intent (Greenhouse, 2003) and program
analysis driven theorem proving (Freund &
Qadeer, 2003), have also been applied to multi-
threaded systems to ensure correct behavior. Each
approach trades off analytical thoroughness and
computational cost. Static-analysis techniques
typically do a good job of modeling relative time
and temporal ordering. They do not, however,
model—and thus cannot reason about—absolute
(wall-clock) time.
The only practical approach to behavioral
analysis that can incorporate aspects of absolute
time is dynamic analysis, also known as profiling.
Profiling is inspection of behavior of a running
system. An advantage of this approach is that
it can measure aspects of the system and know
that they are exactly representative of the system.
Approaches to profiling can be classed as either
active or passive. Active profiling requires that the
application or system being measured explicitly
generates information about its execution. An
example of active profiling is the user of compiler-
based probe insertion, where the application makes
callbacks to the trace collection engine to record
execution behavior. Conversely, passive profiling
relies on explicit inspection of control flow and
execution state through an external entity, such
as a probe or modified runtime environ ment.

Passive profiling typically does not require any
modification of the measured system, but is harder
to implement and may require specialized tracing
hardware.
Profiling (whether active or passive) collects
precise and fine-grained behavioral data from a
running multithreaded systems, which can be
coupled with off-line analysis to help summarize
and reason about observed results. The collected
data is thus accurate and representative of system
execution, as long as the overhead of the mea-
surement has not un duly influenced the results.
Profiling can also only pro vide behavioral data
for control paths that actually execute, so success-
fully applying profiling tools depends largely on
analyzing multiple runs of the program that test
all relevant paths in the system. This coverage can
be achieved through careful selection of stimuli
(e.g., input data) to the system, as well as through
artificial fault injection.
Profiling is limited, however, to the inspection
of behavior that can be made to run by appropriate
stimulation of the system, for example, through
selection of input. This limitation means that
profiling is more useful for behavior analysis in
circumstances where a sampling of behavior is
sufficient. For example, profiling is useful for op-
timizations that aim to improve performance on
statistically frequent paths of execution. Profiling
is thus not well suited to ensure correct behavior
in a system when only one execution in a million
can lead to system failure.
Both static analysis and dynamic analysis have
their advantages and disadvantages. Advanced
behavioral analysis solutions (Nimmer & Ernst,
2001; Waddington, Amduka, DaCosta, Foster,
& Sprinkle, 2006) commonly use a combination
of static and dynamic analysis to provide a more
complete picture of system behavior. The re-
mainder of this chapter presents and evaluates
general approaches to profiling within the context
of multithreaded systems. We examine the type
and scale of behavioral data that can be collected
dynamically from running systems and review