LEC 01 Asst Prof Md Samin Rahman

TO BE EMBEDDED IS …
A Compute Node That Provides Specific Services by Processing Inputs and
Producing Required Responses
 Provides Specific Services Rather than General Purpose Computing
 Often Limited or No Direct Connection to User Input/Output (e.g. Antilock brakes)
 Contained within a Larger System as a Sub-system (flight control on aircraft)
TO BE REAL-TIME IS …
Definition: Real-time systems must respond to service requests within a specific time
frame.
Tasks and Timing Constraints: Each service request imposes a task (job) with a real-
time computing constraint, known as a timing constraint.
Services that must be provide upon request prior to a deadline
 A deadline is a constraint for processing
 If no deadline constraint exists for a system, it is not real-time
 Most real-time systems handle requests on a periodic basis
 Some real-time systems require deterministic response before a deadline
 Some required predictable response (some missed deadlines are allowed)
Well-know Real-Time Services: Digital video, Digital audio, Digital control, Monitoring
(sensor networks)
TO BE REAL-TIME IS …
Types of Timing Constraints
 Hard Timing Constraints: (“Failure is NOT an option.”)
 Definition: Missing a deadline is fatal; the task’s late completion is unacceptable.
 Example: Systems where a delay can cause severe consequences (e.g., medical devices, airbags in cars).
 Loss of property, life, financial, or system itself
 Soft Timing Constraints: (“I’ll try really hard!”)
 Definition: Missing a deadline is undesirable but tolerable within a certain range.
 Loss of service, quality of that service, and annoyance
 No deadline constraint - BE (Best Effort) (“I’ll try!”)
 Desktop systems are interactive, low latency response, but no response constraint
 May be responsive, but in a best effort fashion (some waiting… hourglass) (as long as the waiting is not
too long or not too often, we are ok)
MANY EXAMPLES OF REAL -TIME EMBEDDED
SYSTEMS
▪Real Time – Must Respond to Requests for Service by a Deadline relative to
request
▪Failure to Respond Prior to Deadline Results in a System Failure
▪Request Rate for Service Driven by Real -World Events
▪Controls Processes and Delivers Deadline Driven Services
▪Specific Examples (with deadline constraints): Medical Devices (e.g. Pulse
Oximeter), Unmanned Aerial Systems, Anti -Lock Braking, Streaming Media
(Video and Audio), Process Control, Aircraft Flight Control, Robotic Systems
EXAMPLE REAL-TIME EVENT RATES
WHY ARE RT EMBEDDED SYSTEMS A CHALLENGE?
1. Correct results on time – Deadlines (constraint)
2. Multi-service Concurrency - Multi-threaded Software
3. Multiple interfaces to service concurrently
4. Function and Service Allocation – CPU Software, HW Coprocessor (e.g. FGPA, MPEG
decoder), or Software Coprocessing (e.g. DSP, GP-GPU)
5. Management of CPU, IO, and Memory Resources
6. Modern architecture – high throughput, less deterministic
7. Sensors / Actuators (control Physical Process)
8. Networks (Latency and QoS)
9. Persistent Memory Devices (e.g. Flash, EEPROM)
10. Memory Hierarchy (Register, Cache, RAM, Flash)
SIMPLIFYING REAL-TIME SYSTEMS AND ENSURING
SUCCESS
1. RT Service and CPU Resource Management Policies (e.g. Rate Monotonic, EDF (Earliest
Deadline First))
2. RT Theory and Best Practices (Theory, Analysis, Models, System, Verification)
Hardware (HW) = Physical
3. RMA (Rate Monotonic Analysis) Resource Theory (proof of feasibility of design) components (e.g., CPU,
keyboard, screen).
4. Performance Prediction and Measurement (predicted to actual comparison) Software (SW) =
Programs/apps that run on
5. When to Allocate Services/Functions to HW, FW, or SW hardware (e.g., Windows,
Chrome, games).
6. Multi-threaded RTOS (Real Time Operating System) and Real-Time Linux Systems Firmware (FW) = Software
embedded into hardware
7. RTOS or POSIX RT Mechanisms (e.g. message queue, signal, semaphore) to control it (e.g., BIOS,
8. Analysis and Debug Tools router firmware).

The term “abstracted” here means the file system hides the complex details of how
9. I/O Device Interfaces and Driver the hardware (e.g., SSDs) physically stores data, so you (or apps) can interact with
simple, familiar concepts like files and folders instead of worrying about bytes,
10. Abstracted Non-Volatile Memory File systems memory cells, or hardware quirks.
Rate Monotonic Concept:
 A way to prioritize tasks in systems (e.g., robots, planes)
where tasks that repeat more frequently get higher
priority.
 Example: If Task A runs every 2 seconds and Task B
every 5 seconds, Task A gets priority.
 The time chart we have on the bottom, which shows
different services is actually of a VxWorks or RTOS
system and is a real example, and here's the theoretical
model that goes with it. We need to understand what we
need to model and what we need to verify. So as it best
effort is it soft real-time, as hard real-time?
 Best Effort - Non-RT processing (Windows, desktop Linux, AOS, iOS,
etc.)
 Soft Real-Time - predictable response (Netflix, SmartTV, MPEG
video, digital video games, etc.)
 Hard Real-Time - Commercial aviation FCS (Flight Control System),
Anti-lock braking, Heart-lung machine, Air Traffic Control, etc.
 Your model can have even the combination of all these three.
Scheduling of Services (Concurrency)
 Math Models - Rate Monotonic Analysis (RMA) of fixed priority, Adaptive Analysis
of dynamic priority
 Rate Monotonic Analysis (RMA): Math to check if tasks with fixed priorities (e.g., Task A always first)
can finish on time.
 Adaptive Analysis: Priorities change dynamically (e.g., emergencies first).
 Feasibility - determined by manual analysis or mathematical feasibility tests
(algorithms) - can concurrent services meet deadlines (constraint)
 What: Checking if tasks can actually meet deadlines.
 How: Use math or tests to ask: “Can all these tasks finish without crashing the system?”
 Specification of RT constraints - Si , Ti , Ci , Di
 Si = Start time (when task begins). Ti = Period (how often it repeats, e.g., every 10 seconds). Ci =
Compute time (how long it takes to finish). Di = Deadline (must finish by this time).
 Schedulers and Hardware vs. Software RT Services
 What: The “boss” that decides which task runs next.
 Hardware RT: Built into devices (e.g., car brakes) – super fast, no delays.
 Software RT: Runs on normal computers (e.g., video games) – flexible but slower.
RATE MONOTONIC SCHEDULING (RMS)
Rate Monotonic Scheduling (RMS) is a technique used in real-time systems to schedule
tasks that repeat periodically (tasks with shorter periods (T) get higher priority). Each
task must complete before its deadline (usually the same as the task’s period). This is
essential in systems where missing deadlines could lead to catastrophic failures, such
as in flight control or medical devices. To guarantee that all tasks can meet their
deadlines, RMS uses a mathematical utilization bound to calculate whether the system
can handle all the tasks safely.
RATE MONOTONIC SCHEDULING (RMS)
The term 21/𝑚 arises because each
additional task splits the available CPU time
exponentially. For 𝑚 tasks, the fraction of
CPU time available for each task decreases
geometrically. This is similar to dividing time
into 𝑚 exponentially shrinking slots.

For a small number of tasks ( 𝑚 ), the CPU

can handle a higher utilization. But as the
number of tasks grows: The CPU spends
more time managing task transitions. Tasks
with different periods and deadlines become
harder to schedule without overlaps. The
bound shrinks because it accounts for this
growing complexity.
RATE MONOTONIC SCHEDULING (RMS)
 What History
Teaches Us

The rate monotonic least upper bound was introduced by two NASA researchers, one from MIT, one in residence at the Jet Propulsion
Lab, in 1973. NASA landed on the moon July 16th 1969 with Apollo 11. And on descent, the lunar module experienced a computer
overload. This was indicated by alarm 1201, which became alarm 1202, which meant there was a CPU overload. So the sum of the Ci
over the Ti was actually greater than 1. Not only greater than the least upper bound, but greater than 100%, which we certainly know
is not possible. Buzz Aldrin was wise enough to just shut off the computer. And what happened was, every time the radar was turned on,
the radar was needed to control the descent of the lunar lander, the computer became overloaded. So he manually landed the lunar
lander without assistance from the computer. So he could use the radar to properly adjust the descent rate of the lunar lander module.
And so keep in mind that in 1960, rate monotonic theory was not yet formalized, there was no model. And so it's not surprising that there
was a CPU overload. You might ask, well, wasn't this tested? It was, but conditions were slightly different on the moon, this is a theme
that'll come up again. So we have to be very careful, we want to have a model that'll tell us whether we're going to have a CPU
overload in advance, right? And we want to know if it's theoretically possible we could have a CPU overload.