cs554 lect06

CS 554Introduction to Real-Time Embedded SystemsProfessor Kyoung Don KangLecture 6September 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?