Share PowerPoint. Anywhere!
Attempted to read or write protected memory. This is often an indication that other memory is corrupt.

cs554 lect06

Uploaded from authorPOINT Lite
Download as Download Not Available PPT
Presentation Description

No description available

Like authorSTREAM?


You can vote once a day till December
10th, Vote Now!
Views: 45
Like it  ( Likes) Dislike it  ( Dislikes)
Added: January 10, 2008 This presentation is Public
Presentation Category :Education
Presentation StatisticsNew!
Views on authorSTREAM: 44 | Views from Embeds: 1
Others - 1 views
Presentation Transcript

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?