Embedded Software Engineering Course, Winter 2009/2010

Prof. Kirsch and Dr. Sokolova, Department of Computer Sciences, University of Salzburg

Time, Location: Tue 3-4, Th 10-12 in T04, Techno-Z. First lecture on Tue, Oct 6, 3-4. Check schedule (iCal) for updates.

Brief Overview:

This course will provide an introduction to embedded software engineering: the first part covers operating-system-level aspects such as real-time scheduling, real-time memory management, and real-time communication; the second part focuses on higher-level aspects such as real-time programming languages, coordination languages, models for real-time and embedded systems and methods for their verification. The course begins with an introduction to real-time operating system concepts using Salzburg's Tiptoe system as example. Basic real-time scheduling techniques such as rate-monotonic (RMS) and earliest deadline first (EDF) scheduling will be illustrated, followed by more advanced techniques such as Salzburg's variable-bandwidth servers (VBS). Real-time memory management will be discussed from basic concepts to more advanced techniques such as Salzburg's Compact-fit system. Next are real-time communication protocols such as the time-triggered protocol (TTP) and the event-triggered CAN protocol. The second half of the course emphasizes real-time programming, coordination, and verification for real-time and embedded systems. The high-level embedded programming and coordination languages Lustre, Giotto, and Salzburg's HTL will be presented. Code generation for HTL will be discussed based on a virtual machine architecture called the Embedded Machine. The end of the course will focus on more formal aspects of real-time and embedded systems, in particular, timed automata and other formalisms for modelling timed systems, and an overview of methods for their verification.

Goal of the course:

Learn how to evaluate applications with real-time requirements, identify adequate programming paradigm and platform, implement applications with real-time requirements, and verify their correctness.

Assignments:

• Each student is expected to prepare for certain lectures by reading the papers listed below.
• There will be one exam (written test) on Tuesday, January 26, 2010 at 3pm.
• Teams of 2-3 students will develop and implement embedded software projects, e.g., on Motes or Gumstix, present and give demos of their projects at the end of the semester, and write project reports that could eventually result in publications. Each team creates a wiki page that describes the project.

List of Projects:

• VapsBee
• Rantanplan
• BenchGC
• AudioFX

Recommended Textbooks:

• Hard Real-Time Computing Systems: Predictable Scheduling Algorithms & Applications by Giorgio C. Buttazzo. Kluwer, 1997.
• Real-Time Systems: Design Principles for Distributed Embedded Applications by Hermann Kopetz. Kluwer, 1997.
• Reactive Systems: Modelling, Specification and Verification by Luca Aceto, Anna Ingolsfdottir, Kim G. Larsen and Jiri Srba. Cambridge University Press, 2007.

Schedule and slides:

• Week 1, Tuesday 6.10.09: Introduction slides. Thursday, 8.10.09: Scheduling slides.
• Week 2, Tuesday 13.10.09: Scheduling (continued) slides. Thursday, 15.10.09: no class.
• Week 3, Tuesday 20.10.09: The proof for EDF (blackboard) slides. Thursday, 22.10.09: Rate monotonic scheduling slides.
• Week 4, Tuesday 27.10.09: Variable Bandwidth Servers (VBS) slides. Thursday, 29.10.09: VBS (continued) slides. Download all VBS slides in open office format (with animations). Papers to read:
  • Silviu Craciunas, Christoph Kirsch, Hannes Payer, Harald Roeck, and Ana Sokolova, Programmable temporal isolation through variable-bandwidth servers. In proceedings of SIES'09, pp. 171-180, IEEE, 2009.
    An extended older version: Real-time scheduling for workload-oriented programming, Technical report TR-2008-02, University of Salzburg, 30pp, 2008.
  • Silviu Craciunas, Christoph Kirsch, Hannes Payer, Harald Roeck, and Ana Sokolova, Programmable temporal isolation in real-time and embedded execution environments. In proceedings of IIES'09, pp.19-24, ACM, 2009.
• Week 5, Tuesday 3.11.09: Workload oriented programming slides. Download the workload-oriented programming slides in open office format (with animations). Paper to read:
  • Silviu Craciunas, Christoph Kirsch, and Ana Sokolova, A workload-oriented programming model for temporal isolation with VBS. RePP Workshop'09, ESWeek, 2009.
  Thursday, 5.11.09: Real-time memory management (introduction) slides.
• Week 6, Tuesday 10.11.09: Explicit dynamic memory management systems slides. Thursday, 12.11.09: Compact fit (CF) slides. Paper to read:
  • Silviu Craciunas, Christoph Kirsch, Hannes Payer, Ana Sokolova, Horst Stadler, and Robert Staudinger, A compacting real-time memory management system. In proceedings of USENIX 2008, Annual Technical Conference, pp.349-363, 2008.
• Week 7, Tuesday 17.11.09: Concurrent CF slides. Thursday, 19.11.09: Concurrent CF slides. Paper to read:
  • Silviu Craciunas, Christoph Kirsch, Hannes Payer, Harald Roeck, and Ana Sokolova, Concurrency and scalability versus fragmentation and compaction with Compact-fit. Technical report TR-2009-02, University of Salzburg, 28pp, 2009.
• Week 8, Tuesday 24.11.09: Concurrent CF slides. Thursday, 26.11.09: Concurrent CF slides.
• Week 9, Tuesday 1.12.09: Giotto slides. Thursday, 3.12.09: Giotto slides. Paper to read:
  • T.A. Henzinger, B. Horowitz, and C.M. Kirsch: Giotto: A time-triggered language for embedded programming. In Proc. EMSOFT, LNCS 2211, 2001.
• Week 10, Thursday, 10.12.09: E-machine slides and HTL slides. Papers to read:
  • T.A. Henzinger and C.M. Kirsch: The Embedded Machine: Predictable, portable real-time code. In Proc. PLDI, ACM, 2002.
  • Thomas A. Henzinger, Christoph M. Kirsch, Eduardo R.B. Marques, and Ana Sokolova: Distributed, Modular HTL. In Proc. RTSS, IEEE, 2009.
• Week 11, Tuesday, 15.12.09 and Thursday 17.12.09: Lustre. Papers to read:
  • Paul Caspi, Daniel Pilaud, Nicolas Halbwachs, John Plaice: Lustre: A Declarative Language for Programming Synchronous Systems. In Proc. POPL, 1987.
  • N. Halbwachs, P. Caspi, P. Raymond, D. Pilaud: The synchronous data flow programming language LUSTRE. Proceedings of the IEEE, Volume 79, Issue 9, 1991.
• Week 12, Tuesday, 12.01.10 and Thursday 14.01.10: Real-time Communication (CAN and TTA).
• Week 13, Tuesday, 19.01.10 and Thursday 21.01.10: Timed Automata.
• Week 14, Tuesday, 26.01.10: exam test. Thursday 28.01.10: project presentations.

Grading: 25% exam, 75% project.

Prerequisites: programming experience, basic knowledge of operating system and programming language concepts.

Course language: English.