Elastic Task Model for Adaptive Rate Control : Elastic Task Model for Adaptive Rate Control Giorgio Buttazzo, Giuseppe Lipari, Luca Abeni, Elastic Task Model For Adaptive Rate Control, RTSS 1998.
Outline : Outline Introduction
Elastic Model
Compressing Task Utilization
Theoretical Validation
Experimental Results
Conclusions
Motivation : Motivation Classic real-time task models are too rigid
For a task i is defined by constant period Ti & exec time Ci in RM & EDF
Schedulability guarantee
Necessary for stability of critical hard real-time systems
Motivation : Motivation More flexibility is required by multimedia & adaptive control applications
MPEG encoding/decoding time may vary from frame to frame
A deadline miss can degrade QoS but doesn’t cause any catastrophic result
Considering as hard real-time task is too pessimistic
Underutilize the CPU as WCET >> average exec time
Elastic Task Model (ETM) : Elastic Task Model (ETM) Treat task periods as springs with given elastic coefficients
Increase/decrease task periods to control QoS considering the current load
Allow tasks to intentionally change their execution rates to provide different levels of QoS
Handle overload situations in a more flexible way
Imprecise computation, (m,k) firm deadlines, and ETM: Which is best? : Imprecise computation, (m,k) firm deadlines, and ETM: Which is best? Review
Imprecise computation can reduce task exec time by skipping (or spending fewer CPU cycles for) optional parts
(m,k) model can drop jobs, i.e., task instances, in a controlled manner
Which is best? Always out perform the others? We don’t know.
Imprecise computation, (m,k) firm deadlines, and ETM: Which is best? : Imprecise computation, (m,k) firm deadlines, and ETM: Which is best? One model may not work best for every application
For even one application, e.g., video streaming, one or the other may show better performance under certain circumstances
Which model work best in certain situations?
This can be a good course proejct topic (More topics at the end of the talk)
Can we develop any model that outperforms these models (in even some specific application)?
Outline : Outline Introduction
The Elastic Model
Compressing Task Utilization
Theoretical Validation
Experimental Results
Conclusions
Task Parameters : Task Parameters Computation time Ci (fixed)
Nominal period Ti0
Minimum period Timin
Maximum period Timax
Elastic coefficient ei >= 0
A task = i(Ci, Ti0, Timin, Timax, ei)
Parameter Constraints : Parameter Constraints Ti: actual period of task i
Ti [Timin, Timax]
Any variation is subject to an elastic guarantee and is accepted only if there exists a feasible schedule in which all the other periods are within their range
Slide11 : Schedulable by EDF
Up = 10/20 + 10/40 + 15/70 = 0.964 < 1
3 reduces its period to 50
Up = 10/20 + 10/40 + 15/50 = 1.05 > 1
Not schedulable
Change T1 to 22 and T2 to 45
Up = 0.977
Schedulable!
Example Cont. : Example Cont. 3 reduces its period to 40
Schedulable
T1 = 35 must be rejected, since there’s no feasible schedule with T1 and T2 within their (min, max) period ranges
Configuration Policy : Configuration Policy Implicitly encoded in the elastic coefficients provided by the user
Each task is varied based on its current elastic status under the condition that a feasible configuration is found (if there exists one)
More Features : More Features The other direction (decompressoin): Task terminates or decreases its rate.
Other tasks gain back bandwidth – Increase their rates, if necessary, to improve QoS
Hard real-time tasks
Ti0 = Timin = Timax
Outline : Outline Introduction
The Elastic Model
Compressing Task Utilization
Theoretical Validation of the Model
Experimental Results
Conclusions
Compressing Task Utilization : Compressing Task Utilization Set of periodic task Γ can be divided into:
Γf: Set of fixed tasks in which an arbitrary task i in the set consumes it minimum utilization, i.e., its current period Tf = Tfmin
Γv: Set of variable tasks that can be still compressed
For task v in Γv its current period Tv > Tvmin
Period can be increased to reduce utilizaiton
U0: Sum of all the nominal utilization (Ci/ Ti0) for the tasks in Γv
Uf: Total utilization of the tasks in Γf
Compressing Task Utilization : Compressing Task Utilization To achieve the desired utilization Ud < U0, each task in Γv has to be compressed to the following utilization:
Decompression : Decompression A task decreases its rate or returns to its nominal period
Compressed tasks expand their utilizations according to their elastic coefficients
If total utilization is less than utilization bound, then all tasks can return to their nominal periods
Outline : Outline Introduction
The Elastic Model
Equivalence with a Spring System
Compressing Tasks’ Utilizations
Theoretical Validation of the Model
Experimental Results
Conclusions
Theoretical Validation: Key Idea : If tasks’ periods are changed at opportune instants, the task set remains schedulable and no deadline is missed → Find out when is the opportune time!!!
The following lemmas state two properties of the EDF algorithm that are useful for proving the main theorem Theoretical Validation: Key Idea
Lemma 1 : Lemma 1 In any feasible EDF schedule , the following condition holds:
t >0 i[1,n] ri (t)/t >= Up
Where Up = i[1,n] Ci / Ti and ri (t) is the cumulative time executed by all the instances of task i up to t
Processor demand analysis
Lemma 2 : Lemma 2 In any feasible EDF schedule , the following condition holds:
t >0 i[1,n] ci(t) ≤ i[1,n] [vi(t) – t]Ui
Where Ui = Ci / Ti, ci (t) is the remaining execution time of the current instance of task i at time t, and vi (t) is the next release time of i greater than or equal to t
Theorem 1 : Theorem 1 Given a feasible task set Γ, with total utilization factor Up = i[1,n] Ci/Ti ≤ 1, if at time t all the periods are increased from Ti to T’i ≥ Ti, then for all L > 0,
D(t, t+L) ≤ LU’ p
Where D(t1, t2) is the total processor demand of Γ in [t1, t2] and U’p = i[1,n] Ci/T’i
What does the theorem mean? : What does the theorem mean? Periods can be increased immediately, but
The period of a task can be decreased only at its next release time
Example in the next slide
Slide26 : D Miss! Orignally, 3/10 + 2/3 = 0.96 < 1
After changing periods at t =14: 3/5 + 2/6 = 0.96
If T1 is immediately changed at t = 14, D miss at t = 16
Outline : Outline Introduction
The Elastic Model
Equivalence with a Spring System
Compressing Tasks’ Utilizations
Theoretical Validation of the Model
Experimental Results
Conclusions
Outline : Outline Introduction
The Elastic Model
Equivalence with a Spring System
Compressing Tasks’ Utilizations
Theoretical Validation of the Model
Experimental Results
Conclusions
Conclusions : Conclusions Periodic tasks can change their execution rates to adapt QoS
Remaining tasks can canautomatically adapt their peroids to keep the system underloaded
Policy is encoded in the elastic coefficient
Useful for supporting both multimedia and adaptive control applications, in which the execution rates of some computational activities have to be dynamically tuned as a function of the current system
Single Semester-Long Prject vs. Programming Assignments : Single Semester-Long Prject vs. Programming Assignments Students can work in teams for projects
Programming assignments are individual – No teamwork is allowed
1st programming assignment will be available in this week
If it’s your first time to real-time emebedded systems or your are under pressure, it will be safer to do programming assignments
If you are interested in RT research, do a project
Pick a topic among the ones to be discussed today (or identify your own topic), find a team if possible, and discuss with me
Single Semester-Long Prject vs. Programming Assignments : Single Semester-Long Prject vs. Programming Assignments Decide whether you will do a project or programming assignments by Sept 26 and let the TA and me know about your decision
If you are doing a project, let the TA and me knwo about your topic, team members, etc.
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 – How does configurability make a RTOS better? Performance optimization & memory footprint minimization
http://ecos.sourceware.org/
uc/OS-II
Commercial, open-source RT kernel
Easy to use and runs in Windows environment
http://www.ucos-ii.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 Compare imprecise computation model, (m,k) firm deadline model & ETM for a multimedia application
Qualitative analysis: Which is more applicable? Why?
Experiments to support your arguments
DSRT: Dynamic Soft Real Time CPU Scheduler 2.0
http://cairo.cs.uiuc.edu/software/DSRT-2/dsrt-2.html
Middleware that works with either 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 testbed implemented on top of an open source DB called Berkeley DB
Choose to do a simulation or real DB implementation
1. Make the home-made simulator or testbed more structured/easier-to-use or make one of them to support distributed RT transaction processing; OR
2. Make the RTDB testbed to interact with wireless sensors; OR
3. How to handle RTDB specific issues such as data freshness or data conflicts properly, while supporting timing guarantees?;
Project Idea 4 : Project Idea 4 Power-aware real-time routing
Shortest path to minimize the delay
No need for a packet to arrive at the destination earlier than the deadline
Take an alternate path to reduce power consumption given enough slack – Just-in-time scheduling + power management
You can use network simulation in ns-2
Project Idea 5 : Project Idea 5 Differentiated real-time routing
Initially assign a deadline for a packet based on distance or number of hops
Define the criticality for each periodic data flow
Criticality could be indicated by an elastic cofficient such that less critical flows are more elastic
Schedule packets in an EDF manner
When a router is backlogged, adapt the deadlines of elastic packets (according to the elasticity constraints)
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 Remote control of robots on Mars (simulation)
You can find the problem description and simulator here!
Any Questions? : Any Questions?