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

a thread needs to execute on an operating system
are thus affected by:

1, which has only four independent threads, each
w i t h e i g h t e x e c u t i o n q u a n t a , t h e r e a r e 10 17 possible
interleavings for just one processor! Server-based
systems with hundreds of threads and tens of pro-
cessors are now common. Over the next decade
we expect tera-scale systems will have hundreds
of cores (Intel Corporation, 2006b).

• Thread priority, which determines the order

in which threads run;

• Processor affinity, which defines the proces-

sors that the thread may run on;

• Execution state, which defines whether the

thread is ready, waiting, or stopped; and approaches to extracting

multithreaded behavioral
characteristics

• Starvation time, which is caused by system

delay during peak load periods.

Switching execution context between multiple
threads results in an execution “interleaving” for
each processor in the system. In a single-processor
system, there is only one stage of scheduling:
the choice of deciding which runnable thread to
execute next. Systems that have multiple cores or
SMP processors require an additional stage that
maps the threads ready to run on to one of many
possibly available cores, as shown in Figure 1.
Even if we know exactly how long each thread
will have access to the processor (which ignores
any form of priority-driven pre-emption and
interthread dependency), the number of feasible
i in t e r l e a v i in g s t h a t c a in o c c u r i in t h e s y s t e m a r e s t a g -
gering. For example, using the criteria in Figure

There are two basic approaches to behavioral anal-
ysis: static and dynamic. Static analysis inspects
the underlying constituents of a system without
executing any program (Jackson & Rinard, 2000).
It therefore requires some “model” of the system
or implementation artifact that is correlated
directly with expected behavior. For example,
analysis of program source code is considered a
form of static analysis. This type of analysis has
the advantage that it can be performed without
running the system. In particular, it can explore
dimensions of behavior that are hard to stimulate
through manipulation of program input.
Static analysis tools typically construct
program execution models, potentially through

Figure 1. Interleavings caused by 1-stage and 2-stage scheduling