Embedded Software Engineering Course, Winter 2010/2011

Prof. Kirsch, Department of Computer Sciences, University of Salzburg

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

Brief Overview:

This course provides an introduction to advanced systems software engineering: the first part covers advanced operating-system-level aspects in scheduling, memory management, and 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 advanced 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). Memory management will be discussed from basic concepts to more advanced techniques such as Salzburg's Short-term Memory and Compact-fit systems. 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 modeling timed systems, and an overview of methods for their verification.

Goal of the course:

Learn how to design, implement, and evaluate systems software. Understand advanced communication protocols, programming paradigms, and runtime platforms. Implement applications with real-time requirements and verify their correctness.

Assignments:

  • There will be one exam (written test) on Tuesday, January 27, 2011 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:

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, October 5, 2010: Introduction slides. Thursday, October 7, 2010: Real-Time Scheduling slides.
  • Week 2, Tuesday, October 12, 2010: Real-Time Scheduling (continued) slides. Thursday, October 14, 2010: Earliest-Deadline-First Scheduling slides.
  • Week 3, Tuesday October 19, 2010: Rate-Monotonic Scheduling slides. Thursday, October 21, 2010: Variable-Bandwidth Servers (VBS) 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 4, Tuesday, October 26, 2010: No Class. Thursday, October 28, 2010: VBS (continued) slides.
  • Week 5, Tuesday, November 2, 2010: No Class. Thursday, November 4, 2010: Real-Time Memory Management (Introduction) slides.
  • Week 6, Tuesday, November 9, 2010: VBS Scheduler Overhead slides. Thursday, November 11, 2010: Power-aware Scheduling slides. Papers to read:
    • Silviu Craciunas, Christoph Kirsch, and Ana Sokolova, Response Time versus Utilization in Scheduler Overhead Accounting. In proceedings of RTAS'10, IEEE, 2010.
    • Silviu Craciunas, Christoph Kirsch, and Ana Sokolova, Power-Aware Temporal Isolation with Variable-Bandwidth Servers. In proceedings of EMSOFT'10, ACM, 2010.
  • Week 7, Tuesday, November 16, 2010: Explicit Dynamic Heap Management Systems slides. Thursday, November 18, 2010: 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 8, Tuesday, November 23, 2010: CF (continued) and Concurrent CF slides. Thursday, November 25, 2010: Short-term Memory slides. Papers 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.
    • Martin Aigner, Andreas Haas, Christoph Kirsch, and Ana Sokolova, Short-term Memory for Self-collecting Mutators - Revised Version. Technical report TR-2010-06, University of Salzburg, 34pp, 2010.
  • Week 9, Tuesday, November 30, 2010: Short-term Memory (continued). Thursday, December 2, 2010: Short-term Memory (continued).
  • Week 10, Tuesday, December 7, 2010: Giotto slides. Thursday, December 9, 2010: No Class. Paper to read:
    • T.A. Henzinger, B. Horowitz, and C.M. Kirsch: Giotto: A time-triggered language for embedded programming. In Proceedings of the IEEE, 91(1):84–99, January 2003.
  • Week 11, Tuesday, December 14, 2010: No Class. Thursday, December 16, 2010: Giotto (continued) slides, the Embedded Machine slides. Paper to read:
    • T.A. Henzinger and C.M. Kirsch: The Embedded Machine: Predictable, portable real-time code. In TOPLAS, 29(6):33–61, October 2007.
  • Week 12, Tuesday, December 21, 2010: The Hierarchical Timing Language (HTL) slides. Thursday, December 23, 2010: No Class. Paper to read:
    • Thomas A. Henzinger, Christoph M. Kirsch, Eduardo R.B. Marques, and Ana Sokolova: Distributed, Modular HTL. In Proc. RTSS, IEEE, 2009.
  • Week 13, Tuesday, January 11, 2011 and Thursday, January 13, 2011: 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 14, Tuesday, January 18, 2011: Real-time Communication (TTA). Thursday, January 20, 2011: Real-time Communication (CAN).
  • Week 15, Tuesday, January 25, 2011: Project Presentations. Thursday, January 27, 2011: Exam.

Grading: 25% exam, 75% project.

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

Course language: English.

Technical contact: Ana . Sokolova @ cs . uni-salzburg . at
Administrative contact: Petra . Kirchweger @ cs . uni-salzburg . at