Introduction to

Real-time Operating Systems (RTOS) and

Scheduling Algorithms

Lecturer: Prof. Yifeng Zhu

Fall, 2010
 What is a Real-Time System?
  Real-timesystems 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 Real-Time Computing,"
IEEE Computer, 21(10), October 1988.
 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 recurring at regular intervals.
  Aperiodic: Event-driven.
Typical Real-Time Systems
Environment

Actuators

Controller
(Controlling System) Controlled
System Sensors
 Hard versus Soft
  Hard: failure to meet constraint is a fatal fault.Validated
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
Characteristics of Real-Time Operating Systems

Unique requirements in five general areas:

1.  Determinism
2.  Responsiveness
3.  User control
4.  Reliability
5.  Fail-soft operation
Characteristics of Real-Time Operating Systems

Unique requirements in five general areas:

1.  Determinism
–  No OS is fully deterministic due to resource competition
among multiple processes
–  Metrics: the maximum delay before acknowledging a high
priority device interrupt
–  In real-time OS, usually upper-bounded
–  In non-real-time OS, usually unbounded
–  In non-RT this delay may be in the order of 10’s and 100’s of
millisecs, whereas in an RT it may have an upper-bound of
few microsec to 1 millisec.
Characteristics of Real-Time Operating Systems

Unique requirements in five general areas:

1.  Determinism
2.  Responsiveness
–  Metrics: the time for servicing the interrupt once it has been
acknowledged.
–  Comprises:
»  Time to transfer control, (and context switch) and execute the
ISR
»  Time to handle nested interrupts, the interrupts that should be
serviced when executing this ISR. Higher priority Interrupts.

response time = f(responsiveness, determinism)

Characteristics of Real-Time Operating Systems

Unique requirements in five general areas:

1.  Determinism
2.  Responsiveness
3.  User control
–  User has a much broader control in RT-OS than in regular OS
  Priority
  Hard or soft deadlines
  Deadlines
  Memory Management: paging or swapping
  Name the processes to be resident in memory
  Scheduling policies
Characteristics of Real-Time Operating Systems

Unique requirements in five general areas:

1.  Determinism
2.  Responsiveness
3.  User control
4.  Reliability
–  Failure in RT-OS may be catastrophic: life and death, financial
loss, equipment damage.
–  In the event of a failure, immediate detection and correction is
important.
–  Notify user processes to rollback.
–  Apply compensation.
RTOS Characteristics
  Reliability

Number of 9s Downtime per yr Typical applications

3 Nines (99.9%) ~ 9 hrs Desktop
4 Nines (99.99%) ~ 1 hr Enterprise Servers
5 Nines (99.999%) ~ 5 min Carrier-Class Servers
6 Nines (99.9999%) ~ 31 sec Carrier Switch Equipment

Reliability / Availability Chart

Providing Open Architecture High Availability Solutions (HA Forum)

11
Characteristics of Real-Time Operating Systems

Unique requirements in five general areas:

1.  Determinism
2.  Responsiveness
3.  User control
4.  Reliability
5.  Fail-soft operation
–  the ability of a system to fail in such a way as to preserve as much
capability and data as possible
–  A real-time system is stable/fail-soft if, in cases where it is
impossible to meet all task deadlines, the system will meet the
deadlines of its most critical, highest-priority tasks, even if some
less critical task deadlines are not always met.
Characteristics of Real-Time Operating Systems

To meet these requirements, real-time OS typically include the following

features:
  Fast process or thread switch

  Small size (with corresponding minimal functionality)

  Ability to respond to external interrupts quickly
  Multitasking with interprocess communication tools such as semaphores,
signals, and events
  Use of sequential files that can accumulate data at a fast rate
  Preemptive scheduling based on priority
  Minimization of intervals during which interrupts are disabled
  Primitives to delay tasks for a fixed amount of time and to pause/resume
tasks
  Special alarms and time-outs
Comparisons
 

Time-Sharing Real-Time
Systems Systems
Capacity High throughput Schedulability
Responsiveness Fast average Ensured worst-
response case response
Overload Fairness Stability

•  Schedulability is utilization level at or below which

tasks can meet their deadlines
•  stability in overload means the system meets critical
deadlines even if all deadlines cannot be met (critical
tasks are assumed to be schedulable.)
Preemptive vs Non-preemptive scheduling

  Preemptive Scheduling
  Task execution is preempted and resumed later
  Preemption occurs to execute higher priority task.
  Offers higher schedulability
  Involves higher scheduling overhead due to context switching

  Non-preemptive Scheduling
  Once a task starts executing, it completes its full execution
  Offers lower schedulability
  Less overhead due to less context switching
 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.
Real-Time Workload

  Job (unit of work)

  a computation, a file read, a message transmission, etc
  Attributes
  Resources required to make progress
  Timing parameters
Absolute
Released deadline
Execution time

Relative deadline
Real-Time Task
  Task : a sequence of similar jobs
  Periodic task (p,e)
  Its jobs repeat regularly
  Period p = inter-release time (0 < p)
  Execution time e = maximum execution time (0 < e < p)
  Utilization U = e/p

0 5 10 15
Schedulability
  Property indicating whether a real-time system (a set of
real-time tasks) can meet their deadlines

(4,1)

(5,2)

(7,2)
Real-Time Scheduling
  Determines the order of real-time task executions
  Static-priority scheduling
  Dynamic-priority scheduling

(4,1)

(5,2)
5 10 15
(7,2)
5 10 15
 RM (Rate Monotonic)
  Optimal static-priority scheduling
  It assigns priority according to period
  A task with a shorter period has a higher priority
  Executes a job with the shortest period

T1 (4,1)

T2 (5,2)
5 10 15
T3 (7,2)
5 10 15
 RM (Rate Monotonic)
  Executes a job with the shortest period

T1 (4,1)

T2 (5,2)
5 10 15
T3 (7,2)
5 10 15
 RM (Rate Monotonic)
  Executes a job with the shortest period

Deadline Miss !

T1 (4,1)

T2 (5,2)
5 10 15
T3 (7,2)
5 10 15
 Response Time
  Response time
  Duration from released time to finish time

T1 (4,1)

T2 (5,2)
5 10 15
T3 (10,2)
5 10 15
 Response Time
  Response time
  Duration from released time to finish time

Response Time

T1 (4,1)

T2 (5,2)
5 10 15
T3 (10,2)
5 10 15
 EDF (Earliest Deadline First)

  Optimal dynamic priority scheduling

  A task with a shorter deadline has a higher
priority
  Executes a job with the earliest deadline

T1 (4,1)

T2 (5,2)
5 10 15
T3 (7,2)
5 10 15
 EDF (Earliest Deadline First)
  Executes a job with the earliest deadline

T1 (4,1)

T2 (5,2)
5 10 15
T3 (7,2)
5 10 15
 EDF (Earliest Deadline First)
  Executes a job with the earliest deadline

T1 (4,1)

T2 (5,2)
5 10 15
T3 (7,2)
5 10 15
 EDF (Earliest Deadline First)
  Executes a job with the earliest deadline

T1 (4,1)

T2 (5,2)
5 10 15
T3 (7,2)
5 10 15
 EDF (Earliest Deadline First)
  Optimal scheduling algorithm
  if there is a schedule for a set of real-time tasks,
EDF can schedule it.

T1 (4,1)

T2 (5,2)
5 10 15
T3 (7,2)
5 10 15
EDF & RM

  Real Time Scheduling algorithms

  RMS
  EDF
EDF & RM

Another example of real-time scheduling with RMS and EDF

Real-time Scheduling

  Dynamic planning-based scheduling

  After the task arrives before execution begins, a
schedule is prepared that includes the new as well
as the existing tasks.
  If the new one can go without affecting the existing
schedules than nothing is revised.
  Else schedules are revised to accommodate the
new task.
  Remember that sometimes new tasks may be
rejected if deadlines cannot be met.
Real-Time Scheduling
  Dynamic best-effort scheduling:
  used in most commercial RTs of today
  tasks are aperiodic, no static scheduling is possible
  some short-term scheduling such as shortest deadline first
is used.
  Until the task completes we do not know whether it has
met the deadline.
Acknowledgement

These slides are modified from the lecture slides of

Insup Lee @ University of Pennsylvania
http://www.cis.upenn.edu/~lee/home/home.html