|
Integrated Control and Scheduling
Project Status Summer 2000
Overview
The focus of the ARTES project "Integrated Control and Scheduling" is
practical management of hard real-time demands in embedded software
for real-time control. The project is based on two key ideas. The
first idea is to combine control theory and scheduling theory in such
a way that the nominal requirements on hard deadlines for control
systems can be relieved. The approach taken is based on using dynamic
feedback from scheduler to the controllers and from the controllers to
the scheduler. The second, complementary, idea is to use attribute
grammars and incremental semantic analysis to carry out on-line
interactive analysis of worst-case timing of software and generation
of exception handling code for coping with unexpected delays.
Combining these ideas forms a more complete and practical methodology
than available today.
The project started in May 1998 and is planned for five years (80%
activity level). The first half of the project has been very
successful, and a number of results have been obtained in the two
parts of the project:
Feedback Scheduling and Interactive Execution Time
Analysis. The two involved PhD students, Patrik Persson and Anton
Cervin, have both presented their licentiate theses
during the spring of 2000.
Project partners
|
Department of Automatic Control,
Lund Institute of Technology |
PhD student: |
Anton Cervin (funded by ARTES)
|
Senior researchers: |
Karl-Erik Årzén,
Johan Eker,
Bo Bernhardsson
|
|
Department of Computer Science, Lund
Institute of Technology |
PhD student: |
Patrik
Persson (funded by ARTES) |
Senior researchers: |
Klas Nilsson,
Boris Magnusson |
|
Sigma Exallon Systems AB, Malmö
|
Contact person: | Jan Johansson Enejder |
|
DDA Consulting, Malmö
|
|
Software Engineering Institute, Carnegie Mellon University
|
Department of Computer Science,
University of Illinois at Urbana-Champaign
|
|
|
Results
Feedback Scheduling:
An in-depth state-of-the-art survey of the field has been written. A
first prototype of a simulator that allows co-simulation of control
algorithms and feedback scheduling strategies has been developed. The
scheduling of different parts of a control algorithm has been
investigated and a new iterative deadline-based priority assignment
scheme has been developed. The performance of different scheduling
strategies under overload conditions and its influence on control
performance have been studied. Experiments with feedback and
feedforward-based scheduling strategies have been performed. A special
invited session for the CDC 2000 in Sydney (Conference on Decision and
Control, the most prominent annual major control conference), on
Integrated Control and Scheduling has been organized and
accepted.
Interactive Execution Time Analysis:
A declarative way of implementing WCET has been developed based on
reference attribute grammars. To correctly schedule automatic memory
management in hard real-time systems, we have presented a live
memory analysis that allows this information to be automatically
determined based on straight-forward programmer annotations. The
WCET analysis and the required annotations have also been extended to
cope with virtual method calls and dynamic class loading, which is
needed when developing flexible object-oriented real-time systems.
Finally, for such system development, a first prototype of an
interactive development environment (called Skånerost) utilizing
the proposed techniques has been developed. Although much of our
research is not restricted to any particular language, we use Java as
our target language due to its popularity, portability, safety, and
built-in support for concurrency (to which we add real-time
support).
Industrial relevance
Embedded real-time control systems are of great importance
to Swedish industry. There is currently a trend towards on-line scheduling
in favor of static scheduling. There is also a trend towards using off-the-shelf
computing platforms also for real-time control applications. As the embedded
systems grow more complex due to customer demands, the need for using high-level
languages for time-critical systems increases. Real-time Java plays a key
role in this development. The interactive timing analysis in this project
is an important prerequisite for this. In related projects work on real-time
garbage collection and real-time Java run-time systems are performed, partly
in collaboration with ABB, Ericsson, and Sun Microsystems.
All together this means that the results that have and
will be developed in the project are very relevant for important parts
of Swedish industry. The co-design and simulation environment, and the
interactive WCET tool for obtaining the timing of specific control blocks,
clearly are candidates for industrial application.
Future work
The main activities during the remainder of the
project will be
refinements of the developed theory and techniques and implementation of
software tools. During this second half of the full project more emphasis
will be put on integrating the two subprojects and the software tools.
The integration will be done in two ways. First, the Skånerost interactive
timing analysis environment will be interfaced with the co-simulation toolbox.
Second, a Java-based real-time kernel with support for feedback scheduling
will be developed.
The planned research topics are the following:
Feedback Scheduling:
-
Real-time co-simulation of distributed systems. The real-time control
simulator will be further extended. Special emphasis will be put on support
for simulation of distributed real-time control systems.
-
Control performance with feedback scheduling. In a feedback scheduling
based control system the scheduler dynamically adjusts the control task
attributes, e.g., the task periods. We will study how this influences the
control performance and stability.
-
Dynamic tradeoffs between execution time and control performance.
Certain common control technologies are based on iterative on-line
optimization in every sample. One example of this is model-predictive control.
This makes it possible for a feedback scheduler to assign varying execution
time quotas to the different controller tasks. We will study this and how
it influences the control performance.
-
Feedback scheduling implementation. Implementation of feedback scheduling-based
control systems will be performed. The main environment will be a Java-based
kernel.
Interactive Execution
Time Analysis:
-
Practical evaluation. Our analysis techniques and the Skånerost
environment should be evaluated for realistic code examples. This requires
support for a fuller Java subset, and also collaboration with the IVM (Infinitesimal
Virtual Machine) project in Lund, where a Java virtual machine with small
memory footprint is being developed. It further requires the development
of a timing model of the hardware platform in question.
-
Further development of live memory analysis. Our present techniques
for live memory analysis support a number of types of data structures.
To make these techniques more generally applicable, the algorithms should
be extended to handle more general data structures.
-
Using information from an object-oriented design in scheduling analysis.
The scheduling analysis requires some information about the structure of
the code, such as which parts are to be executed as sequential or periodic
processes. Such information is typically expressed in an object-oriented
design. We plan to investigate how this design information can be automatically
exploited by scheduling analysis, and how an API (Application Programmer's
Interface) can support the expression of this information.
-
Expressing timing information in the byte code. By generating platform
independent WCET information along with the generated byte code, we can
facilitate an on-line platform-specific WCET analysis in the virtual machine.
This also allows quality-of-service (QoS) applications to monitor their
execution time requirements. Steps have been taken for cooperation with
the Computer Science department at the University of York on this subject.
Publications
Theses
P. Persson: Predicting Time and Memory Demands of
Object-Oriented Programs. Licentiate thesis, Department of Computer
Science, Lund Institute of Technology, April 2000. |
A. Cervin: Towards the Integration of Control and
Real-Time Scheduling Design. Licentiate thesis, Department of Automatic
Control, Lund Institute of Technology, May 2000. |
Journal Articles
K.-E. Årzén and A. Cervin: A Simple Event-Based
PID Controller. Accepted for Control Engineering Practice, 2000. |
J. Eker, P. Hagander, and K.-E. Årzén: A
Feedback Scheduler for Real-time Controller Tasks. To appear in
Control
Engineering Practice, 2000. |
K.-E. Årzén, A. Cervin, J. Eker, B. Bernhardsson,
L. Sha: Towards the Integration of Control and Real-Time Scheduling
Design. In journal submission, 2000. |
Conference Publications
P. Persson and G. Hedin: Interactive Execution Time
Predictions using Reference Attributed Grammars. In Proceedings
of WAGA '99, Second Workshop on Attribute Grammars and their Applications,
Amsterdam, The Netherlands, March 1999. |
P. Persson: Live Memory Analysis for Garbage Collection
in Embedded Systems. In Proceedings of the ACM SIGPLAN 1999 Workshop
on Languages, Compilers, and Tools for Embedded Systems, Atlanta, GA,
May 1999. |
A. Cervin: Improved Scheduling of Control Tasks.
In Proceedings of the 11th Euromicro Conference on Real-Time Systems,
York, England, June 1999. |
P. Persson: Using Aliasing Information to Predict
Real-Time Garbage Collection in Embedded Systems. Position paper presented
at the Intercontinental Workshop on Aliasing in Object-Oriented Systems,
Lisbon, Portugal, June 1999. |
K.-E. Årzén: A Simple Event-Based PID
Controller. In Proceedings of the IFAC World Congress, Beijing,
China, July 1999. |
J. Eker and A. Cervin: A Matlab Toolbox for Real-Time
and Control Systems Co-Design. In Proceedings of the 6th International
Conference on Real-Time Computing Systems and Applications, Hong Kong,
China, December 1999. |
P. Persson and G. Hedin: An Interactive Environment
for Real-Time Software Development. In Proceedings of the 33rd International
Conference on Technology of Object-Oriented Languages and Systems,
St. Malo, France, June 2000. |
K.-E. Årzén, A. Cervin, J. Eker, and L.
Sha: An Introduction to Control and Real-Time Scheduling Co-Design.
39th
IEEE Conference on Decision and Control, Sydney, Australia, December
2000. |
A. Cervin and J. Eker: Feedback Scheduling of Control
Tasks. 39th IEEE Conference on Decision and Control, Sydney,
Australia, December 2000. |
Technical Reports
K.-E. Årzén, B. Bernhardsson, J. Eker, A.
Cervin, K. Nilsson, P. Persson, and L. Sha: Integrated Control and Scheduling.
Internal report TFRT-7582, Department of Automatic Control, Lund Institute
of Technology, August 1999. |
A. Cervin: The Real-Time Control Systems Simulator---Reference
Manual. Internal Report TFRT-7592, Department of Automatic Control,
Lund Institute of Technology, April 2000. |
P. Persson, A. Cervin, and J. Eker: Execution-Time
Properties of a Hybrid Controller. Internal report TFRT-7591, Department
of Automatic Control, Lund Institute of Technology, April 2000. |
Karl-Erik Arzen and Klas
Nilsson
|
|