Transcript Introduction to Real

Introduction to Real-Time
Systems
Fred Kuhns
Computer Science Dept.
Washington University
Fred Kuhns ()
CS523S: Operating Systems
What is a Real-Time System?
• Real-time systems have been defined as:
"those systems in which the correctness of
the system depends not only on the logical
result of the computation, but also on the
time at which the results are produced";
 J. Stankovic, "Misconceptions About RealTime Computing," IEEE Computer, 21(10),
October 1988.
Fred Kuhns ()
CS523S: Operating Systems
Real-Time Characteristics
• Real-time systems often are comprised of a
controlling system, controlled system and
environment.
 Controlling system: acquires information about
environment using sensors and controls the environment
with actuators.
• Timing constraints derived from physical impact of
controlling systems activities. Hard and soft
constraints.
 Periodic Tasks: Time-driven recuring at regular intervals.
 Aperiodic: event-driven.
Fred Kuhns ()
CS523S: Operating Systems
Typical Real-Time System
Con trolled System
Controlling
System
Fred Kuhns ()
sensor
sensor
sensor
sensor
actuator
actuator
actuator
actuator
CS523S: Operating Systems
Environment
Some Definitions
• Timing constraint: constraint imposed on timing
behavior of a job: hard or soft.
• Release Time: Instant of time job becomes available
for execution. If all jobs are released when the system
begins execution, then there is said to be no release
time
• Deadline: Instant of time a job's execution is required
to be completed. If deadline is infinity, then job has
no deadline. Absolute deadline is equal to release time
plus relative deadline
• Response time: Length of time from release time to
instant job completes.
Fred Kuhns ()
CS523S: Operating Systems
Hard versus Soft
• Hard: failure to meet constraint is a fatal fault.
Validation system always meets timing constraints.
 Deterministic constraints
 Probabilistic constraints
 Constraints in terms of some usefulness function.
• Soft: late completion is undesirable but generally not
fatal. No validation or only demonstration job meets
some statistical constraint. Occasional missed
deadlines or aborted execution is usually considered
tolerable. Often specified in probabilistic terms
Fred Kuhns ()
CS523S: Operating Systems
Validating Constraints
• Validation: Demonstration by a provably
correct, efficient procedure or by exhaustive
simulation and testing. Involves three steps:
1. timing constraints of each application and
corresponding components are consistent,
2. each component can meet its timing constraints
if executed alone and required resources are
available,
3. The underlying scheduling algorithm(s), all
timing constraints are met
Fred Kuhns ()
CS523S: Operating Systems
Developing a Reference Model
• Modeling the system to focus on timing properties and
resource requirements. Composed of three elements:
 workload model - describes applications supported by
system
 Temporal parameters
 Precedence constraints and dependencies
 Functional parameters
 resource model - describes system resources available to
applications
 Modeling resources (Processors and Resources)
 Resource parameters
 algorithms - defines how application uses resources at all
times.
 Scheduling Hierarchy
Fred Kuhns ()
CS523S: Operating Systems
Tasks and Jobs: Definitions
• Task (Ti): Set of related jobs jointly provide
function.
• Job (Jij): Unit of work, scheduled and executed
by system. characterized by the following
parameters:
Temporal parameters: timing constraints and
behavior
Functional parameters: intrinsic properties of the job.
Resource parameters: resource requirements.
Interconnection parameters: how it depends on other
jobs and how other jobs depend on it
Fred Kuhns ()
CS523S: Operating Systems
Resources
• Resources can be divided into passive and
active:
Active resources == Processors (Pi): they execute
jobs.
Every job must have one or more processors
Same type if functionally identical and used
interchangeably.
Passive resource == Resource (Ri):
job may require Resources in addition to processor.
reusable resources are not consumed
Fred Kuhns ()
CS523S: Operating Systems
Job/Task Temporal Parameters
• Hard real-time: number and parameters of tasks
are known at all time.
• for Job Ji:
ri - release time, may know range [r-, r+] (jitter). For
aperiodic/sporadic release or interrelease time is a
random variable.
di - absolute deadline
Di - relative deadline
(ri, di] - feasible interval
ei - Execution time. May know range [e-, e+]. Most
deterministic models use e+.
Fred Kuhns ()
CS523S: Operating Systems
Periodic Task Model
• Jobs repeated at regular or semi-regular intervals
modeled as periodic.
• Task Ti is a serious of periodic Jobs Jij.
 pi - period, minimum interrelease interval between jobs in
Task Ti. Must be bounded from below.
 ei - maximum execution time for jobs in task Ti.
 rij - release time of the jth Job in Task i (Jij in Ti).
 i - phase of Task Ti, equal to ri1.
 H - Hyperperiod = Least Common Multiple of pi for all i: H
= lcm(pi), for all i.
 ui - utilization of Task Ti.
 U - Total utilization = Sum over all ui.
Fred Kuhns ()
CS523S: Operating Systems
Aperiodic and Sporadic Tasks
• A periodic or Sporadic task is a stream of
aperiodic or sporadic jobs.
• Jobs with a task have similar statistical
behavior and timing requirements
• Assumed system is stationary within the
hyperperiod
• Aperiodic: jobs have soft or no deadlines.
Want responsiveness.
• Sporadic: jobs have hard deadlines
Fred Kuhns ()
CS523S: Operating Systems
Precedence Constraints and Task Graphs
• Jobs are either precedence constrained or
independent.
• Precedence relation: partial ordering operator <
Ji < Jk : Ji is predecessor of Jk, Jk is successor of Ji
directed graph G = (J,<)
• Task graph is an extended precedence graph.
Fred Kuhns ()
CS523S: Operating Systems
Functional Parameters
• Preemptivity
 Preemption: suspend job then dispatch different job to
processor. Cost includes context switch overhead.
 Non-preemptable task - must be run from start to completion.
• Criticalness - positive integer indicating the relative
importance of a job. Useful during overload.
• Optional Executions - jobs or portions of jobs may be
declared optional. Useful during overload.
• Laxity - Laxity type => hard or soft timing constraints.
Supplemented by a usefulness function. Useful during
overload.
Fred Kuhns ()
CS523S: Operating Systems
Resource Parameters
• Job resource parameters indicate processor
and resource requirements.
• Preemptivity of resources
non-preemptive: serial access, typical case.
preemptive - jobs can interleave access.
• Resource Graph:
vertex for processors (Pi) and resources (Ri)
is-a-part-of edge: Ri -> Rk, Rk is a part of Ri
accessibility edge: Pi -> Pk, cost of Pi accessing
Pk
Fred Kuhns ()
CS523S: Operating Systems
Schedules and Scheduling
• Jobs scheduled and allocated resources based on a set of
scheduling algorithms and access control protocols.
• Scheduler: Module implementing scheduling algorithms
• Schedule: assignment of all jobs to available processors,
produced by scheduler.
• Valid schedule:
 every processor assigned to at most one job at a time
 every job assigned to at most one processor at a time
 no job scheduled before its release time
 Total amount of processor time assigned to every job is equal to
its maximum or actual execution time
Fred Kuhns ()
CS523S: Operating Systems
Definitions
• Feasible schedule: Every job starts at or after release
time and completes by deadline
• Schedulable: set of jobs schedulable according to an
algorithm if the it always produces a feasible schedule.
• Optimal: Scheduling algorithm optimal if it always
produces a feasible schedule if such a schedule exists
• Tardiness: Zero if completion time <= deadline,
otherwise > 0 (complete - deadline).
• Lateness: difference between completion time and
deadline, can be negative if early.
Fred Kuhns ()
CS523S: Operating Systems
Performance Measures
• Miss rate: percentage of jobs executed but
completed late
• Loss rate: percentage of jobs discarded
• Invalid rate: sum of miss and loss rate.
• makespan : If all jobs have same release time
and deadline, then makespan = response time
of the last job to execute.
• Max or average response times
• Max or average tardiness/lateness
Fred Kuhns ()
CS523S: Operating Systems