Information Technology Reference
In-Depth Information
derived from a number of factors, including thread
readiness, current system load (e.g., other threads
waiting to be run), priority, and starvation time
(i.e., how long a thread has been waiting to be
run). Many COTS operating systems use complex
scheduling algorithms to maintain appropriate
timeliness for time-sensitive tasks and also to
achieve optimal use of processing resources. From
the perspective of behavior analysis, however,
these types of scheduling algorithms make static
prediction of scheduling outcome infeasible in
practice. Certain properties, such as absence of
deadlock, can be checked effectively using static
analysis because all possibilities can be explored
explicitly. However, other properties, such as the
absolute time taken to execute given functionality,
can only be assessed practically using runtime
profiling.
behavioral characteristics relevant
to multithreaded programs
Certain elements of behavior result from, and
are thus pertinent to, the use of multithreaded
programming. Table 2 describes some different
characteristics that are commonly specified and
measured in real-time and safety-critical systems.
These are the types of characteristics that can be
analyzed using the profiling tools and technologies
discussed in this chapter.
To provide a sense of the necessary sam-
pling scale (i.e., frequency of events) in today's
COTS-based systems, we performed a number
of simple experiments to gather some system
measures. Understanding the expected sampling
rates is useful to understanding the viability
Table 2. Common characteristics of multithreaded systems
Behavioral
Characteristic
Description
Synchronization over-
head
The additional processing time incurred by the use of synchronization mechanisms, such as mutexes,
semaphores, and condition variables. Different mechanisms and topologies (e.g., inter- and intra-processor)
typically have different overhead.
Task latency and jitter
The time between a thread being released (e.g., by a lock being freed) and regaining access to the processor.
The task jitter is the observed variation in latency.
Task execution quanta
The length of time a thread executes for before either yielding access explicitly, or by being pre-empted by
the operating system scheduler.
Unsafe memory access
Data that is being shared between threads must be controlled carefully to avoid data corruption due to the
inability to modify data in one atomic action. To ensure the integrity of shared data is maintained, appropriate
synchronization mechanisms must be used.
Priority inversion
Priority inversion occurs when a lower priority task is preventing a higher priority task from executing by
being unable to execute and thus release a resource required by the higher priority task. A common solution
to the priority inversion problem is for the lower priority to temporarily inherit the higher (waiting) priority
so that it can release the resource.
Deadlock and livelock
Deadlock is a cyclic dependency between two or more threads. For example, thread A is waiting for a
resource R1 from thread B before it will give up R2, and thread B is waiting for resource R2 from thread A
before it will give up R1. In this condition both threads are blocked and cannot progress. Livelock is a similar
condition to deadlock, except that the interdependent threads cause each other to perform an infinite amount
of work before becoming free.
Effective parallelism
Effective parallelism is a measure of the ability of threads to perform work over time. For example, threads
that do not have data interdependencies have a very high effective parallelism, whereas threads that are
“lock-stepped” by a single shared resource have a low effective parallelism.
Worst-case execution
time
Worst-case execution time (WCET) relates to task latency and jitter caused by load on the system. WCET is
the maximum time a given thread or set of threads takes to perform some function. This measure is invalu-
able in building real-time systems that must adhere to strict deadlines.
Search WWH ::
Custom Search