High precision automatic scheduling of periodic task sets for microcontrollers

ABSTRACT

In low-end microcontroller systems task scheduling is often not done, or using very ad-hoc methods, or using a high-overhead RTOS. In this paper we offer an alternative: the design-time generation of high-precision schedules which are then executed using a minimal scheduler on a microcontroller. The schedules are derived from a simple task modeling language that allows the specification of properties of tasks, constraints on task execution, as well as worst-case interrupt rates and interrupt service execution times. An off-line scheduling algorithm then computes a schedule for the tasks specified which is then compiled and linked with a simple execution kernel that performs the scheduling. The paper describes the modeling language, the schedule computation approach used, the run-time kernel, as well as experimental results.

REFERENCES

• 1: Jia Xu , David Parnas, Scheduling Processes with Release Times, Deadlines, Precedence and Exclusion Relations, IEEE Transactions on Software Engineering, v.16 n.3, p.360-369, March 1990 [doi>10.1109/32.48943]
• 2: Henzinger, T. A., Horowitz, B. and, Kirsch, C. M. Giotto: a time-triggered language for embedded programming. Proceedings of the IEEE. Volume 91, Issue 1, Jan. 2003 Page(s):84--99
• 3: Templ, J. TDL Specification and Report. Technical Report, University of Salzburg, Austria. Mar 2004, www.SoftwareResearch.net/site/publications/Co59.pdf
• 4: Gabor Karsai, A Configurable Visual Programming Environment: A Tool for Domain-Specific Programming, Computer, v.28 n.3, p.36-44, March 1995 [doi>10.1109/2.366147]
• 5: Agrawal A., Karsai G., Kalmar Z., Neema S., Shi F., Vizhanyo A.: The Design of a Language for Model Transformations, Journal of Software and System Modeling, 2005.
• 6: T. P. Baker, and A. Shaw, "The cyclic executive model and Ada," Journal of Real- Time Systems, vol. 1, June 1989.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Computer-aided software engineering (CASE)

General Terms:
Algorithms, Design, Experimentation, Performance, Verification

Keywords:
code generation, embedded systems, microcontrollers, model driven design, scheduling problem