Scheduling Algorithms in
Real-Time Operating Systems
Shiva Sai Chandra Kanth Uppula
CDAC,Hyderabad.
Outline
Spectrum of Scheduling Problems
and Scheduling Algorithms
Easier vs. More difficult
Periodic / aperiodic tasks
Preemptive / non-preemptive
Static (at system build time) / dynamic (at run time)
Uni-processor / multiprocessor / distributed system
Independent / interdependent tasks
Off-line (all tasks initially given) / on-line (don’t
know future)
Handle transient overloads
Support fault tolerance
Intro
Real-time systems are systems in which the overall
correctness of the system depends on the both the functional
correctness and the timing correctness.
Characteristics:
Must produce correct result within a specified time
Late (and possibly early) actions are useless or harmful
Not simply a function of increasing system throughput
Requires timeliness and predictability
Do not have to be “fast systems”
A hard real-time system is a real-time system that must
meet its deadlines with a near-zero degree of flexibility.
deadline must be met or catastrophes occur.
Firm: late response is useless but some late
responses can be tolerated.
A soft real-time system is a real-time system that meets its
deadline with a degree of flexibility.
a missed deadline does not result in system failure; only
degradation in system performance.
Terminology
An “aperiodic task” has a deadline by which it
must finish or start, or it may have a constraint
on both start and finish time.
A “periodic task” require the CPU at constant
intervals.
Each periodic process has a fixed processing
time t once it acquires the CPU, a deadline d
when it must be serviced by the CPU, and a
period p.
0 <= t <= d <= p
Typical real-time application has many
tasks that need to be executed
periodically
Reading sensor data
Computation
Sending data to actuators
Communication
Classification of task timing
constraints
There are two types of timing constraints hard and soft.
if missing a deadline is a fatal error or has disastrous consequences
it is considered hard (missing an occasional deadline is not
acceptable)
otherwise (if some percentage of missed deadlines is acceptable) it
is soft.
Classic examples:
air traffic control , vehicle
braking systems controller,
subsystems control, medical systems => hard
multimedia streaming, multimedia transmission and reception,
networking, telecom (cellular) networks,
web sites and services, computer games.
=> soft
Scheduling in RTOS
More information about the tasks are known
Number of tasks
Resource Requirements
Release Time: the point in time from which the
task can be executed.
Execution time: the time the task takes to execute
Deadlines: the point in time by which the task
must complete.
Rate-Monotonic Scheduling
Proposed by Liu & Layland in 1973 (JACM)
Simple to understand and implement
For periodic tasks
scheduling decision made when a task finishes as well as when a
new task arrives.
Based on static(fixed) priorities
Processes with shorter period given higher priority
Tasks priority inversely proportional to it’s period
If there is fixed-priority schedule that meets all deadlines, then
RMS will produce a feasible schedule
If the required processor utilization is over 69%, RMS
might still give a valid schedule, but there is no
guarantee
Does not consider:
Context switch time
Resource contention
Clock variation
Generally, no deadline will be missed if the CPU
utilization is < 70%
If utilization is smaller than 0.7, then RMS is guaranteed
to find one
If utilization is between 0.7 to 1, RMS may or may not
succeed
Used by VxWorks and NASA for Apollo space missions
Liu and Leyland show that the
schedulable utilization of RM is bounded
by :
N
executioni
U N (2 1)
1/ N
i 1 periodi
where N is the number of real time tasks
lim(21/ N 1) ~ 0.69
n
Rate-Monotonic Scheduling
If we plot the priority of tasks as a function of
their rate, the result is a monotonically
increasing function; hence the name – Rate
Monotonic scheduling.
E.g.,
Period Priority
10 1 (highest)
12 2
15 3
20 4 (lowest)
Real-time scheduling depends on
1. Whether a system performs schedulability
analysis.
2. If it does, whether it is static or dynamic.
3. Whether the result of analysis produces a
schedule according to which tasks are
dispatched at run-time.
static - at design time
Dynamic - at runtime
Static scheduling is used for scheduling periodic tasks,
whereas dynamic scheduling is used to schedule both
periodic and aperiodic tasks
Classes of Real-time scheduling
algorithms
Static approaches
Static table-driven
Static priority-driven preemptive
Dynamic approaches
Dynamic planning-based
Dynamic best effort
Static table-driven scheduling
Applicable to periodic tasks.
Input -- Arrival time, Execution time, Deadline
and Priority of each task.
Output -- Schedule that meets requirements
of all periodic tasks.
Drawback – Inflexible.
Reason - Any change to any task
requirements requires that the schedule be
redone.
Static priority-driven
preemptive scheduling
Earliest Deadline First (EDF)
Based on dynamic priorities
Processes with soonest deadline given highest
priority
It may happen that a set of tasks is schedulable by
EDF, but not by RMS
EDF is complicated enough to have
unacceptable overhead
More complicated than RMS: harder to
analyze
Less predictable: can’t guarantee which
process runs when
Priorities must only be recalculated when a
new task arrives, as time advances equally for
all tasks
the algorithm behaves unpredictably at
overloads, and suffers more from overloads
than RM
A dynamic priority schedule exists if and only if utilization
is no greater than 100%
It places processes in a priority queue.
Whenever a scheduling event occurs
(task finishes, new task released, etc.)
the queue will be searched for the
process closest to its deadline.
EDF is not commonly found in industrial
real-time computer systems.
LST algorithm
The slack time of a task is the amount
of time until the task must be scheduled
or miss it’s deadline.
The least slack time algorithm is a
priority driven algorithm in which the
tasks receive priorities according the
their slack times. The shorter the slack
time the higher the priority.
slack = relative deadline – execution
left
Linux for Real Time Applications
Scheduling
Priority Driven Approach
Optimize average case response time
Interactive Processes Given Highest Priority
Aim to reduce response times of processes
Real Time Processes
Processes with high priority
No notion of deadlines
Problems with Linux
Processes are non preemtible in Kernel
Mode
System calls like fork take a lot of time
High priority thread might wait for a low
priority thread to complete it’s system call
Processes are heavy weight
Context switch takes several hundred
microseconds
Case study
We will go over how some actual
implementations of real time operating
systems tackled these problems.
Rt-Linux
Rialto
VxWorks
Rt-linux
RT-Linux is a system developed as a way to
adapt Linux to hard real time performance
and still give the user most of the advantages
of the Linux environment.
The main idea: add a hard real time
scheduler into (under) the kernel which will
schedule the real time tasks and will run the
rest of Linux as the lowest priority task.
the main philosophy is this:
Real time programs need to be split into parts
, a small light parts with hard real time
constraints and larger parts that do most of
the processing.
the light real time parts will be scheduled in
the real time scheduler, while the heavier
parts will run as normal processes under
Linux.
Real time tasks are implemented as kernel modules
whose init function sends the real time scheduler all
the information about their release times, periods and
deadlines.
Rt-Linux allows for swappable schedulers for the real
time tasks, a scheduler based on the EDF algorithm
and another based on the RM algorithm.
Linux is run as the lowest priority process in either
case and will only execute if the real time scheduler
has nothing else to do.
When Linux is running it uses it’s own scheduler to
schedule tasks running under it.
Rt-Linux - limitations
Doesn’t handle the problem of
scheduling dependant real time tasks.
Not all applications can be split into a
light real-time parts and non-real-time
parts.
Not suited for dynamic real time
systems.
Rialto
Rialto is a real time system developed at
Microsoft Research based on the windows NT
architecture.
The main idea: rewriting the kernel and
scheduler so that they support real time
deadlines.
Uses a novel scheduling approach, But
because it is complicated it is sensitive to
many implementation details.
Unlike rt-linux it doesn’t require the separation of
the hard real time functionality from the rest of the
code.
the scheduling in Rialto is quite complicated:
1. Tasks can be granted CPU time reservations. This is
the average amount of CPU time they should get.
2. The scheduler is based on a variation of preemptive
LST which uses the maximal amount of time before
a task has to start running (deadline-running time
estimate).
Rialto - limitations
The schedulability test was not fully
implemented originally.
VxWorks
VxWorks is a commercial hard real time
operating system developed by wind
river systems.
The main idea: use monolithic kernel to
schedule user tasks according to user
defined priorities. Maximize kernel
timing predictability.
Gives the users maximal control.
A dedicated real time system, not intended as
a general purpose OS.
lacks many modern os features that interfere
with real time performance (flat memory
model, no paging).
Scheduling is done using a preemptive priority
driven approach, priorities are chosen
arbitrarily by the user (0-256).
Priorities can be changed by the user at
runtime but this is discouraged.
A user can lock a task so that it can’t be
preempted even by higher priority tasks or
interrupts.
This allows the use of the fixed priority
response time analysis to check schedulability
offline.
Widely used in automobiles, consumer and
industrial devices, network switches, routers
etc.
VxWorks - limitations
Lacks many modern OS features.
Guaranteeing the deadlines is the
responsibility of the user at design time.
Doesn’t support most modern applications
and APIs (only a small subset of POSIX).
Despite the flat memory model dynamic
memory allocation still cases memory
fragmenting, which increases timing
unpredictability.
Summary
References
Questions
