Real Time Systems Design And Analysis

Chapter 7.1 - Performance Analysis And Optimization: Theoretical Preliminaries

7.1   THEORETICAL PRELIMINARIES

Of all the places where theory and practice never seem to coincide, none is
more obvious than in performance analysis. For all the well-written and well_
meaning research on real-time performance analysis, those that have built real
systems know that practical reality has the annoying habit of getting in the way
of theoretical results. Neat little formulas that ignore resource contention, use
theoretically artificial hardware, or have made the assumption of zero context
switch time are good as abstract art, but of little practical use. These observations,
however, do not mean that theoretical analysis is useless or that there are no
useful theoretical results. It only means that there are far less realistic, cookbook
approaches than might be desired.

7.1.1   NP-Completeness

The complexity class P is the class of problems that can be solved by an algorithm
that runs in polynomial time on a deterministic machine. The complexity class
NP is the class of all problems that cannot be solved in polynomial time by
a deterministic machine, although a candidate solution can be verified to be
correct by a polynomial time algorithm. A decision or recognition problem is
NP-complete if it is in the class NP and all other problems in NP are polynomial
transformable to it. A problem is NP-hard if all problems in NP are polynomial
transformable to that problem, but it hasn’t been shown that the problem is in
the class NP.

The Boolean Satisfiability Problem, for example, which arose during requirements
consistency checking in Chapter 4 is NP-complete. NP-complete problems
tend to be those relating to resource allocation, which is exactly the situation that
occurs in real-time scheduling. This fact does not bode well for the solution of
real-time scheduling problems.

UNLIMITED FREE
ACCESS
TO THE WORLD'S BEST IDEAS

SUBMIT
Already a GlobalSpec user? Log in.

This is embarrasing...

An error occurred while processing the form. Please try again in a few minutes.

Customize Your GlobalSpec Experience

Category: PCMCIA Memory Cards
Finish!
Privacy Policy

This is embarrasing...

An error occurred while processing the form. Please try again in a few minutes.