Real-Time Software

Home| Course

Schedule

See Calendar

The schedule is preliminary and can be changed.
The main lecturers are Alexandre David [AD] and René Rydhof Hansen [RRH].
The guest lecturers are Brian Nielsen [BN] and Jens Alsted [JA].

As you asked, the lectures and exercises are swapped from the 5/10.

Lecture 1: Welcome, Introduction to Real-Time Systems, Fault Tolerance

[Alexandre] Abstract:

Reading: Chapters 1 and 2.

Slides: Introduction, Fault tolerance.

Exercises: Discuss exercises 1.2, 1.4, 1.5, 2.1, 2.2, and 2.5. Discuss the concepts of chapter 2 apply to your projects, in particular reliability, safety, fault-tolerance, redundancy etc...

Lecture 2: NXT Sensors and Actuators

[Brian] lecture

Lecture 3: Real-Time Facilities, Scheduling

[René] Abstract: We covered (philosophical) notions of time, properties of (real-world) time, access to time/clock in a programming language, basic clock use (delays, timeouts), and temporal scopes.

Reading: Chapters 9 and 11.

Slides: Real-time facilities.

Exercises: Exercises 9.1 and 9.2; discuss the different notions of time.

Lecture 4: OSEK on the NXT, Balancing Robot Case-Study

[Jens] Abstract: An introduction to OSEK is given, which covers the basics of the API, how to setup your environment, and compile. The balancing robot (segway) is presented as a case-study.

Slides: OSEK.

Exercises: See end of slides.

Lecture 5: Response Time Analysis (cont.)

[René] Abstract: Basic scheduling algorithms (FPS, EDF, VBS), utilisation analysis (for FPD and EDF), response-time analysis (for the simple process model).

Reading: Chapter 11.

Slides: Basic scheduling and RTA.

Exercises: Exercises 11.1, 11.2, 11.3, 11.7, 11.8, 11.9, 11.10.

Lecture 6: Project Presentations: Choices, UPPAAL

[Alexandre and René] Abstract: In the first 1/2h, each group has approx. 5 min to present his project. That means the context, the requirements, and some preliminary analysis on the real-time aspects of the project, i.e., which tasks are necessary, which deadlines you are likely to have, what defines reliability and safety. Then I will start an introduction to UPPAAL from a user's perspective. You will get more on the theory later in the curriculum.

Reading: Tutorial on UPPAAL.

Slides: Introduction to UPPAAL.

Exercises:

• Checking schedulability with UPPAAL.
  • Download UPPAAL.
  • There is a research tool being developed to do multiprocessor schedulability analysis that compiles task descriptions into UPPAAL models. Download it here. Do it on the system (Linux) if you do not have Linux.
  • Model the task sets of tables 11.15 and 11.16 and check for schedulability. You can experiment different task sets and try with different cores if you want. The syntax for the input file is a sequence of rows where you specify period wcet deadline offset. A typical call in your case is done with ./converter -t tab11.15 -c 1 -p gedf -m uppaal. The property you want to verify is typically A[] not sched_gedf.Loc_Unhappy.
  • Exercise 19.
  • Exercise 2.

  Lecture 7: UPPAAL (cont.), Times Tool

  [Alexandre] Abstract: I finish on UPPAAL, giving you some modeling patterns, and I show you some alternative models that you can use in the tool. Then I'll present you Times and make a short demo.

  Reading: Tool paper.

  Slides: Times tool.

  Exercises:

  • UPPAAL exercises. You will need to download the development version of UPPAAL (4.1.x) You will also need to download UPPAAL-TIGA to try its Gantt chart. UPPAAL-TIGA is a tool for timed games. You will not need to use the time game feature but the Gantt chart is useful to visualize schedules.
    • Download these model and query files. It is a more advanced model for scheduling with shared resources using the ceiling protocol. The model corresponds to Figure 11.9. Check with the Gantt chart that it behaves as expected (the Gantt chart is already configured). Check the properties and get the WCRT for the different tasks. There is also a property to check that the tasks have exclusive access of the shared resources.
      You can use UPPAAL (dev) to check and get symbolic traces. You can use TIGA to check without traces and visualize Gantt charts.
    • Change the configuration of the model to the set of tasks of table 11.23. Use 18 as periods and deadlines. Redo exercise 11.5 with this model. You can also ask for WCRT.
      This can be done with UPPAAL (dev) or TIGA.
  • Times exercises. You will need to download the times tool.
    • Model the examples of table 11.7, 11.15, and 11.16. Simulate, check for schedulability, and WCRT. Check that what you get conforms with the expected results in the book.
    • Do exercise 11.15 with Times.

  Lecture 8: Concurrent Programming and Process Synchronization

  [Alexandre] Abstract: Alexandre presents concepts of concurrent programming and message-based process synchronization.

  Reading: Chapters 4 and 6.

  Slides: Concurrent programming, Message-based process synchronization.

  Exercises: We start with the exercises this time so you will continue the exercises from last time. Finish the exercises on UPPAAL and OSEK.

  Lecture 9: Synchronization, Atomicity, Deadlocks

  [René] Abstract:

  Reading: Chapters 5, 7 (cursorily), and 8 (only section about deadlocks).

  Slides: Communication and Synchronisation via Shared Memory.

  Exercises: 4.5, 4.7, 4.11, 4.12

  Lecture 10: Programming Real-Time Systems

  [René] Abstract: Implementing periodic tasks, aperiodic/sporadic tasks, real-time event handlers, and controlling I/O jitter.

  Reading: Chapters 10 and 12.

  Slides: Programming Real-Time Abstractions.

  Exercises:

  • Show how the test-and-set instruction can be used to implement semaphores.
  • Show how the swap instruction can be used to implement semaphores.
  • Examine if/why Peterson's algorithm is correct in the case(s) where interleaving occurs in conditionals.
  • Exercise 5.1
  • Exercise 5.3
  • Exercise 5.4
  • Exercise 5.5
  • Exercise 5.6

  Lecture 11: Programming Real-Time Systems (cont.)

  [René] Abstract: Implementing cyclic executive, priority-based scheduling in POSIX and real-time Java, interrupt handling in real-time Java.

  Reading: Chapters 10 and 12 (cont.).

  Slides: Programming Real-Time Abstractions.

  Exercises: No exercises today

  Lecture 12: Timing Faults

  [René] Abstract: Detecting and handling timing faults: missed deadline detection, wcet overrun, sporadic overrun, damage confinement, execution time servers, error recovery, and mode change.

  Reading: Chapter 13.

  Slides: Timing faults.

  Exercises:

  1. Make an overview of the tasks in your project and specify the corresponding temporal constraints.
  2. Perform a response time analysis (RTA) under the aasumption that your project complies with the simple process model.
  3. Investigate and describe how your project and chosen platform differs from the simple process model.
  4. Discuss how the above differences may influence the RTA.

  Lecture 13: Exceptions, Low-level Programming

  [René] Abstract: Brief overview of standard notions of exception and exception handling; overview of mechanisms for low-level programming in general and I/O, interrupts, and memory management in particular.

  Reading: Chapters 3 and 14.

  Slides: Timing faults.

  Exercises:

  1. Exercise 13.2
  2. Exercise 13.4
  3. Make a list of expected/potential sources for timing faults in your project and prioritise the sources by potential impact.
  4. For all of the above listed timing faults, argue how you could perform error recovery or why it is not possible/sensible.
  5. For all aperiodic/sporadic tasks in your project, discuss how to calculate/guesstimate the MIT and discuss potential impact of a wrong calculation/guesstimate.
  6. Discuss potential mitigation/handling strategies for the sporadic and aperiodic events listed above.

  Lecture 14: RTA Advanced

  [René] Abstract: Extending the simple process model and corresponding RTA: aperiodic and sporadic processes, cooperating processes (blocking), priority inheritance protocols (simple, OCPP, ICPP), release jitter, arbitrary deadlines, fault handling, interrupts, context switches.

  Reading: Chapter 11 (again) and RTA for arbitrary deadlines (example)

  Slides: Advanced RTA.

  Exercises:

  1. Exercise 3.15
  2. Describe and discuss how you handle exceptions in your project. In particular:
     1. Do you assume/depend on termination or resumption model?
     2. What exceptions in your project code can you meaningfully handle inside the code?
     3. How can you ensure that you catch all exceptions?
  3. Describe and discuss the low-level aspects of your projects. In particular:
     1. How do you manipulate the device registers
     2. Which (if any) interrupts do you (have to) handle
     3. How do you manage memory? Garbage collection?
  4. Perform a stack usage analysis of your program, i.e., calculate how much stack space is needed to run your program.

  Lecture 15: Project Presentations: Achievements and Discussions

  We hope you got useful feedback at your presentations. Here are links to your videos/presentations:

  • Group s502a. YouTube video. The video shows the final version of the "RTSorter" which is designed to sort white and blue candy by color in real-time. The RTSorter is written in C, using nxtOSEK and is executed on two LEGO NXTs.
  • Who's next?