Introduction to Real-Time Systems

Topics

• What makes a system ``real time''?
• What else does this usually imply?
• Why is producing real-time software difficult?
• Why are real-time systems interesting?

What makes real-time software different?

• primarily: predicting and/or controlling timing is critical
• plus a collection of secondary characteristics

Central Problem: predicting and/or controlling timing

• timing is essential to correct functioning of system
  perhaps more important than I/O relationships
• analogy: intruments playing in a band
  timing is more important than missed notes
• examples of different kinds of timing requirements:
  • periodic (limited jitter)
  • from sporadic event to response (upper, lower)
  • between actions in sequence
  • absolute (time, date)

Secondary characteristics of Real Time Systems

• interaction (control)
  Computer continually responsds to and controls objects in the real world.
• high reliability, fault tolerance required
  • some controlled systems involve risk of massive loss
    e.g., chemical/nuclear/biological plant controls, missile defense
  • must safely handle all conceivable input conditions, plus hardware (and software) faults
• concurrency: to deal with multiple real-world activities
• economy: the product must be affordable
  • includes power, weight, heat dissipation.
  • "cheap hardware" is not cheap enough

Why is producing real-time software difficult?

• Traditional C.S. abstractions mostly throw out timing portability, e.g.,
  • machine-independence
  • abstraction
  • virtual machines
  • virtual memory

  This is true in programming languages, operating systems, even newer processor architectures (parallelism, caching).

  A new look at the basic abstractions is needed, to put time back in.

  Example:

  virtual machine, with time; based on time-slicing
  response time limited (below) by slicing period
  slicing period limited (below) by context-switching overhead

  Adding time back in introduces new problems and limitations.

• Concurrency makes programming subtle.
  • There are well-known problems, like deadlock, starvation, and inconsistency through concurrent update.
  • Traditional techniques for solving these problems sacrifice predictable timing, and sometimes efficiency.
• Performance and economy demands rule out some "elegant" simplifications
• We have very little means to control timing:
  1. timed code sections
  2. timed interrupts
  3. passive clocks

Why is real-time software interesting?

• It is subtle and challenging (see above)
• It has interesing applications
• It is profitable
  • economic demand, public expectations
  • success of technology promoters
    • every product must have a computer in it
    • every activity must be automated
    • every computer must be on the Internet
    • every software component must be able to be remotely reconfigured

I do not endorse the above view of technology.

Good Real-Time Applications

• scientific instruments
• music synthesizers
• airplanes
• cars
• microwave ovens
• robots
• radar tracking

Why they good?

• machines are FAST
• machines can repeate tasks flawlessly
• machines don't get bored
• machines don't fatigue
• machines can stand hostile environments
• machines don't need individual training
• machines are sometimes cheaper than humans

Reality Check

Technology promoters often tend to promise more than is deliverable. (See references to marketing vs. engineering departments in the Dilbert comic strip.)

Ambitious plans require distibuted solutions, with long lifetimes and complex algorithms, dynamically reconfigurable, with frequent software upgrades. All these things are already difficult, and adding the real-time element makes them harder.

Sometimes we become too eager to promise solutions to these problems, and set ourselves up for failure.

Limiting Theoretical Considerations

• Halting Problem → Can't predict execution time of subprogram
• NP-completeness → Can't do optimal scheduling, in general
  • NP-complete problems are provably ``equally hard'' to one another.
  • Examples of NP-complete problems include
    satisfiability, coloring, bin-packing, scheduling.
  • Less than exponential-time algorithms are unknown and unlikely to exist.
  • Practical solutions are suboptimal, or limited to very restricted (simplified) classes of problems. Heuristics are often used.
  • Do you also know the formal definition of NP and NP-complete?

Limiting Practical Considerations

• Humans can do the job better, cheaper, more reliably
• The job is too complicated, specialized, poorly understood
• Problem is not well defined
• Problem is not repetitive
• Algorithms are not well defined
• Requirements, inputs are dynamic and unpredictable
• System would need to be extremely large and complex