Real Time Concepts and Terms

Topics

• terminology from Liu, Chapter 2
• Baker's terminology about time, clocks, and events

WARNING:

The meanings of many of the terms used in publications about real-time systems varies widely from author to author.

Whenever you start a conversation or read a new book or paper, you will have to check on the local terminology, or risk misunderstanding.

Examples of problem terms

job, task, process, activity, action, procedure, event, time, deadline, latency, slack time, execution time, aperiodic, sporadic, jitter, priority

In this course, we will try to use terminology consistent with that of Jane Liu's book on real-time systems.

Jobs and Processors

• Job = unit of work that is scheduled and executed in the system, e.g.,
  • control law computation, or FFT on sensor data
  • transmission of data packet
  • retrieval of a file
• Task = set or sequence of related jobs
• Processor = the primary resource needed to execute a job
  • CPU
  • bus, or network
  • disk drive

Release Times, Deadlines, Timing Constraints

• release time = time at which job becomes available for execution
• completion time = time at which execution of job completes
• response time =
  length of time between release and completion times
• deadline (absolute) =
  time by which execution of job is required to complete
• deadline (relative) =
  length of time between release time and absolute deadline
• timing constraint =
  length of time between release time and absolute deadline

Example - Furnace Controller

• read each temperature sensor every 100ms
• use the sensor value to recompute the control law of each furnace every 100ms,
  to determine flow rates of fuel, air, and coolant
• control-law computations are jobs: J₀, ¼, J_k, ¼
• suppose release time of J₀is time 20ms.
• release time of job J_k = 20 + k·100ms, for k = 1,2,¼.
• deadline of job J_k, for k = 1,2,¼, might be
  20 + k·100 + 100 ms
• if jittermust be controlled, deadline of job J_kmight be shorter
  20 + k·100 + 30 ms

Hard and Soft Timing Constraints

• harddeadline = late result is little or no value,
  or may even lead to disaster
• softdeadline = late result may still be useful

Liu: How serious is serious?

Baker: A deadline is hard if we are unhappy enough about the possibility that it might be missed to pay the cost of prevention.

Attempts to Quantify Hard/Soft Notion

• tardiness = min{ 0, deadline - completion time }
• usefulness = function of tardiness

This is nice for academic work, but has no demonstrated relation to anything in practice.

Validation of Constraint Satisfaction

• Hard - requires validation
• demonstration that timing constraints are satisfied
• may be by formal method
• may be by exhaustive simulation and testing
• Soft - requires no validation
  • statistical constraint may be demonstrated by profiling

How hard is a constraint?

• response time of jobs that sense stop signal and activate brake on train
• periodic completion of flight controller computation
• reconfiguration and recovery of database server or network router
• transmission of digitized voice/video data

Too-early completion may be as bad as too-late.

Good desigers may find ways to soften timing constraints, but burden of proving safety is on the designer.

Examples of Hard Timing Constraints

• deterministic = relative deadline of control-law computation is 50ms
  response time of at most one out of 5 consecutive control-law computations exceeds 50 ms
• probabilistic = probability of response time exceeding 50ms is less than 0.2
• usefulness = usefulness of every control-law computation exceeds 0.8

Deterministic timing constraints are the norm.

Soft Real-Time Systems

• timing can be traded off against other factors
• requirements are stated in soft terms
• timing requirements if any, stated probabilistically
• occasional missed timing constraints are tolerated
• validation is soft -- via simulation or trial use observations
• examples:
  • telephone switch connects in 10s 95%, 20s 99.95%
  • multimedia transmission loses averages less than 2 lost frames per minute

Points vs.Lengths of Time

point in time = "time", "instant", "point", "absolute time"

length of time = "time", "duration", "distance", "span", "interval" (a misuse)

Are times integers, or a real numbers?

• reals: fit conventional scientific and engineering world models
• integers: fit CPU cycle model

Open vs.Closed Intervals

• half-open: (t₁, t₂]
  = [t₁+ e, t₂] if time is discrete and eis the granularity of time
• closed: [t₁, t₂]

Events vs.Conditions

State

values of all variables in system, viewed as aggregate

Condition

predicate, whose value depends on some attributes of state

Event

particular change in state; may imply change in some conditions

(e.g., voltage on input wire goes from 0v to 5v)

At What Time does an Event Occur?

It is not realistic to speak of the time at which an event occurs, as a point on a real-number time line, since changes of state take time. The best we can do is to specify bounds of a time interval in which an event is known to occur.

Detecting Events

The precision with which we can bound the time interval of an event is limited by our time measurement tools, and sometimes by how frequently we are willing to ``poll'' for the event.

Polling Interval

There is a maximum polling interval
beyond which we may miss an event.

Polling Interval Assumptions

Polling requires making some assumption
about the minimum separation of events.

Kinds of Events

• Clock-based:
  e.g. ``clock tick N''
• Computation-based:
  e.g. ``execution of action A''
• Input:
  e.g. ``input I is received''
• Output:
  e.g. ``output O is produced''

Clock-Based Events

• absolute:
  e.g. ``at time T''
• relative:
  e.g. ``D seconds after event E''

These are the only kind we can predict reliably.

Computation-Based Events

• beginning of action
  (to insure action's effect is not too soon)
• end of action
  (to insure action's effect is not too late)

For these, we may be able to predict the earliest point, but not always the latest point.

Computational Timing Uncertanties

• dynamic memory refresh
• memory contention from DMA I/O
• address translation buffer misses
• cache misses
• interrupts
• OS activities (if there is an OS)
  including process interleaving and overhead

These are just examples.

Input Events

• interrupt-based:
  e.g. ``interrupt I occurs''
• passive:
  e.g. ``pin P changes state to high''

These are generally not predictable,
except where the hardware providing the input is clocked.

Output Events

• happen some time during/after computational action

These are generally not directly observable.

Detectable Events

• computation-based events
• interrupt-based events
  (really are FORCED computation-based events)

This means that if an external input or clock event does not cause an interrupt, we must poll for it, repeatedly.

Intervals Related to Events

• interval between (similar) events
• interval during which event can be detected
• interval during which event is known to lie

Critical Numbers Related to Events

• Bounds on interval during which event occurred.
  e.g. ``Event E occurred after time tand before time t+D''
  • must be known to do subsequent computations, if the time at which the event occurs is important
  • accuracy depends on how event is detected
• Lower bound on interval during which event can be detected.
  e.g. ``Event E can be detected if we check the state every Dseconds''
  • must be known to avoid missing the event, if we are polling
  • actually, a bound between an event and the next canceling event
• Lower bound on interval between similar events.
  e.g. ``If event E happens at time t, a similar event will not happen before time t+D.''
  • must be known to schedule work: to predict the maximum load, and determine the deadline

Clock Value vs.Time

Fine-Grained Clock & Polling

Clock-Driven Polling

Limiting Effect of Clock Granularity

Limiting Effect of Time Representaton

Discrete time representation may add additional uncertainty.