CS 554 Introduction to Real-Time Embedded Systems Professor Kyoung Don Kang Lecture 6 September 14, 2006 : CS 554 Introduction to Real-Time Embedded Systems Professor Kyoung Don Kang Lecture 6 September 14, 2006
Single Semester-Long Prject vs. Programming Assignments : Single Semester-Long Prject vs. Programming Assignments Students can work in teams for projects
No teamwork is allowed for programming assignments
1st programming assignment will be available in a few days
If you are under pressure, it will be safer to do programming assignments
If you are interested in RT research including sensor networks, do a project
Pick a topic among the ones to be discussed today (or find your own topic), find a team if possible, and discuss with me
Single Prject vs. Programming Assignments : Single Prject vs. Programming Assignments Decide whether you will do a project or programming assignments and email the TA and me your decision by Sept 26
If you are doing a project, let Ke and me know your topic and team members
Project Idea 1 : Project Idea 1 Verify if real-time scheduling theory, e.g., RM, EDF, priority inheritance/ceiling, really works
Tweak a RT kernel in your way to improve schedulability, reduce overhead/kernel complexity, or make it more configurable...
Some open source real-time embedded kernels are in the next slide
Prject Idea 1 : Prject Idea 1 Open source RT/embedded kernels
eCos (embedded configurable OS)
Open source, royalty-free RTOS
Can be installed in Linux or Windows (with Cygwin)
Highly configurable
http://ecos.sourceware.org/
uc/OS-II
Commercial, open-source RT kernel
Easy to use and runs in Windows environment
http://www.ucos-i.com/products/rtos/kernel/rtos.html
Book: http://www.amazon.com/MicroC-OS-II-Kernel-CD-ROM/dp/1578201039
L4 Kernel
http://l4ka.org/projects/pistachio/ia32/gettingstarted.php
Project Idea 2 : Project Idea 2 Tweak a soft real-time middleware
For example, you can apply imprecise computation, (m,k) firm deadline, or elastic task model to handle dynamic workloads and QoS requirements
DSRT: Dynamic Soft Real Time CPU Scheduler 2.0 (middleware)
http://cairo.cs.uiuc.edu/software/DSRT-2/dsrt-2.html
Runs in Windows or Linux
Project Idea 3: Real-Time Database : Project Idea 3: Real-Time Database We have a home-made simulator written in C++
We also have a preliminary version of a RTDB testbed implemented on top of an open source embedded DB called Berkeley DB
Possible projects (Pick one)
1. Make the home-made simulator or testbed more structured/easier-to-use;
2. Support distributed RT transaction processing;
3. Make the RTDB testbed to interact with wireless sensors; OR
4. Investigate how to handle RTDB specific issues such as data freshness or data conflicts properly, while supporting timing guarantees? (PhD level project)
Project Idea 4 : Project Idea 4 Power-aware real-time routing in wireless sensor networks
Usually a packet takes the shortest path to the destination
No need for a packet to arrive at the destination earlier than its deadline
Take an alternate path to reduce power consumption when there’s enough slack
Network simulation in ns-2
Project Idea 5 : Project Idea 5 Differentiated real-time routing in WSNs
Initially assign a deadline for a packet based on distance or number of hops
Define the criticality for each periodic data flow
e.g., less critical flows can be more elastic
Schedule packets in a velocity monotonic manner
Maximum (#hops/deadline) → Highest priority
Project Idea 5 : Project Idea 5 When a router is backlogged, adapt the deadlines according to the elastic coefficients
Piggyback the adaptation info as part of ACK message
Eventually propagate to the source
Forward less urgenet packets through an alternate path
Network simulation via ns-2
Project Idea 6 : Project Idea 6 Play with TinyOS or TinySec
Try to extend or implement your protocol on top of it
You can use TOSSIM even if you don’t have access to real sensors
Project Idea 7 : Project Idea 7 Remote control of robots on Mars (simulation)
You can find the problem description and simulator here! (RTSS 2005 Programming Competition)
Feedback Control Real-Time Scheduling : Feedback Control Real-Time Scheduling C. Lu, J.A. Stankovic, G. Tao, and S.H. Son, Design and Evaluation of a Feedback Control EDF Scheduling Algorithm, IEEE Real-Time Systems Symposium (RTSS'99), December 1999.
Motivation for Feedback control Scheduling : Motivation for Feedback control Scheduling Open-loop scheduling paradigms perform perform poorly in unpredictable dynamic systems where the workload cannot be accurately modeled
Many complex applications, e.g., robotics and agile manufacturing, are dynamic and operate in a non-deterministic environment where precise workload is not known
Challenging to build real-time systems providing predictable performance in a highly uncertain environment
Feedback control can support the target performance even when the workload varies dynamically via graceful QoS degradation in a feedback loop
Motivation : Motivation Apply control theoretic approaches to real-time performance management
Feedback control is well known for its robustness, e.g., cruise control or chemical reactor control, in the presence of disturbances
Doesn’t need a precise system model
If the precise system model is known, feedback control is not necessary
Dynamically adapt the system behavior to achieve the targe performance (also called set point) in the feedback loop
Feedback Control Concepts : Feedback Control Concepts Set-point: Target performance to achieve, e.g., 1% deadline miss ratio
Measured perf: Actual perf, e.g., actual (deadline) miss ratio, measured at the current sampling period
Error = set-point – measured perf = target miss ratio – current miss ratio Controller Controlled
RT System + - Setpoint Measured
Perf. Error Control
Signal
Feedback Control Loop : Feedback Control Loop Periodically measure and compare the perf to the set point to determine the error
Controller computes the control signal based on the error and controlled system model
Actuator, e.g., admission controller or QoS manager, change the value of the manipulated variable to control the system
FC-EDF Architecture : FC-EDF Architecture
Miss Ratio Control Model : Miss Ratio Control Model At kth sampling instant, miss ratio is:
m(k) = m(k-1) + g(k) ∆u(k-1) where
m(k-1) is the miss ratio at the (k-1)th sampling period, g(k) is the miss ratio gain, and ∆u(k-1) is the utilization adjustment by admission control and QoS adaptation at the (k-1)th sampling period
Miss Ratio Control Model : Miss Ratio Control Model Instead of considering time-varying miss ratio gain g(k), they took G = maximum (miss ratio/unit load increase) 0.9 1 1.1 1.2 1.3 ... Load Miss
Ratio
Miss Ratio Control Model : Miss Ratio Control Model Replace g(k) with G
m(k) = m(k-1) + g(k)∆u(k-1) → m(k) = m(k-1) + G∆u(k-1)
Take z-transform to convert to frequency domain
M(z) = z-1M(z) + z-1∆U(z)
M(z) = (G/z-1) ∆U(z)
Transfer function T(z) = output/input = M(z)/U(z) = G/z-1
Utilization Control Model : Utilization Control Model Miss ratio controller itself is not stable
MR controller is saturated when utilization is less than 1 when EDF is used
In their later work, they added utilization controller
Utilization controller works when U ≤ 1, miss ratio controller works when U > 1
Turn on/off util/MR controller when U ≤ 1
Turn on/off MR/util controller when U > 1
Controller Tuning : Controller Tuning Given the control model shown in the previous slide, apply Root Locus model to graphically tune the controller in Matlab to support the stability & specified transient performance such as the overshoot and settling time
We will fully discuss techniques for feedback control of QoS next time
Any Questions? : Any Questions?