Real-Time System Design

This course will also be cross-listed with CPEN 432 -- Real-time System Design.

Cyber-Physical Systems (CPS) are ubiquitous, with examples ranging from industrial robot arms to autonomous home vacuum cleaners. Unlike a personal computer or a cloud server, CPS interact directly with the physical world and control physical processes. Their correctness criteria are determined as much by the physics of their environment as by the internal state of their program. For example, an engine control unit in a car, which decides the amount of fuel to be injected, must adapt its decision logic and frequency with the engine RPM.

Many CPS, such as those used in fully autonomous systems, can require nontrivial amounts of computation and physical sensing and actuation every few milliseconds, and even a single faulty or delayed actuation can be fatal. Real-time computing is about ensuring that an implementation of such CPS on specific hardware always complies with the timing requirements, e.g., the software processes responsible for sensing, control, and actuation must be activated every T_time-period milliseconds, and, upon activation, their combined execution must finish within T_deadline milliseconds. This is challenging because on most platforms, right from the microarchitecture to programming languages, operating systems, and networking protocols, timing is a performance metric, not a safety property. Engineers thus rely on timer interrupts and priorities to control timing in software and schedulability analyses to determine if timing requirements will always be met.

The focus of this course is to explore the design principles that allow the construction of analytically sound and temporally safe real-time computing systems, which are integral to a plethora of safety-critical CPS. To this end, we will reason about, compare, and contrast different scheduling algortihms and mathematical analyses techniques from the real-time systems literature.

Learning objectives

• Compare and contrast design principles for general-purpose systems with those for special-purpose real-time or cyber-physical systems
• Become familiar with key algorithms and mathematical analyses for hard real-time scheduling
• Get a preview of state-of-the-art research on mechanizing scheduling analyses using the Coq interactive theorem prover (tentative)
• Learn to read, critique, write about, and present systems or theory research in the field of real-time systems
• Design and conduct a research project related to scheduling or real-time computing in operating or distributed systems (broadly construed)
• Understand the internals of FreeRTOS through a set of well-defined programming assignments (optional, in lieu of a research project)

Prerequisites

This is a research-oriented course intended for Masters and Ph.D. students in Computer Science. Students are expected to have at least an undergraduate-level understanding of systems, such as operating systems, computer networks, or distributed systems. Prior exposure to real-time computing, embedded systems, or cyber-physical systems is recommended but not required. Enterprising Bachelors students who fulfill the above pre-requisites, i.e., CPSC 313, CPSC 317 or CPSC 416, are welcome to participate. In addition, a certain level of proficiency in discrete mathematics and probability, and some background in algorithms and complexity of computation, typically at the level of CPSC 320, is also expected.

If you do not satisfy the necessary prerequisites but would still like to take the course, send me an email summarizing your interest in the course, your experience working on any related topic, and, if you are from another department, a list of courses related to computer science that you have taken.

---

Grading (tentative)

Main Components

This is a graduate course. The primary goal is to prepare you to do research, by encouraging you to read and discuss research papers, and by giving you an opportunity to carry out an open-ended course project in the broad areas of distributed and real-time computing. For students who are new to real-time computing or to software systems research (especially undergraduates), I will also cover the basics of real-time scheduling over a series of lectures during the first half of the course. Therefore, the evaluation for this course consists of three main components.

Assignments (10%)

For the first half of the course, I will create few take-home assignments to ensure that you all understand the basic material taught in the class. Assignments are to be handed in individually. See the Assignments section for detailed instructions.

Paper presentation and participation (30%)

During the second half of the course, we will discuss several research papers on various topics in the field of real-time systems. We will discuss one (occassionally, two) papers per day. Each paper will be assigned a discussion lead who is expected to read and understand the paper in detail, and who is resonsible for presenting the key ideas of the paper. Students who are not the discussion lead for a paper are expected to read the paper beforehand (at the very least, skim through its key sections) and come prepared with questions. You will be graded based on the quality of your presentation and your participation. The relative weightage is given below.

• Paper presentation (20%)
• Participation (10%)

See the Interesting Papers section for a list of recent papers.

Research / FreeRTOS project (60%)

The research project must be done in teams of 1-3. The goal of the research project is to conduct original research. You may talk to the instructor for some ideas that are well-scoped for a course project. You may also undertake a project overlapping with your own research, if you can demonstrate how it is related to and/or influenced by some topic from this course. The deliverables for a research project and their relative weightage is given below. You must submit a fully functional and reproducible artifact along with the final report.

• Proposal presentation (5%)
• Proposal report (15%)
• Final presentation (10%)
• Final report and artifact (30%)

You may choose to do the FreeRTOS project instead of a research project. Undergraduates, especially, may decide to (and are recommended to) choose this option. This will involve understanding the internals of the FreeRTOS real-time operating system kernel, extending it to support the Earliest Deadline First dynamic-priority scheduling algorithm, the Stack Resource Policy for real-time locking, and the Constant Bandwidth Server for co-scheduling real-time periodic and non-real-time aperiodic tasks. The underlying scheduling theory for each of the assignments will be taught during the first half of the course, or else extensive documentation and help will be provided. These tentative programming assignments and their relative weightage is summarized below. Like the research project, you must also submit a fully functional and reproducible artifact along with each assignment submission.

• Presentation on FreeRTOS internals (5%)
• Earliest Deadline First (EDF) (15%)
• Stack Resource Policy (SRP) (15%)
• Constant Bandwidth Server (CBS) (15%)
• Final Demo (10%)

See the Project section for detailed instructions.

---

Schedule (tentative)

Lectures on Hard Real-Time Scheduling

Textbook: Giorgio C. Buttazzo, Hard Real-Time Computing Systems, 3rd edition. The electronic version is accessible via UBC Library.

Date	Reading Material / Topic	Milestone
02/09, Mon	No class, public holiday -- Labour Day
04/09, Wed	A General View and Basic Concepts. Buttazzo 2011 (Chapters 1 and 2). Slides
09/09, Mon	Aperiodic Task Scheduling. Buttazzo 2011 (Chapter 3). Slides
11/09, Wed	^ (continued). Slides	Assignment 1
16/09, Mon	Periodic Task Scheduling. Buttazzo 2011 (Chapter 4). Slides	Drop Deadline
18/09, Wed	^ (continued). Slides, notes
23/09, Mon	Resource Access Protocols. Buttazzo 2011 (Chapter 7). Slides	Assignment 3
25/09, Wed	Fixed-Priority Servers. Buttazzo 2011 (Chapters 5). Slides

Presentations (mainly)

Date	Reading Material / Topic	Milestone
30/09, Mon	No class, regional holiday -- National Day for Truth and Reconciliation
02/10, Wed	Project proposal presentations by Erik and Mayant + Periodic Task Scheduling: Deadline Monotonic. Buttazzo 2011 (Chapter 4, Section 4.5). Slides, notes
07/10, Mon	FreeRTOS internals presentations by Adarsh and Luca + Discussion of DM scheduling (continued)
09/10, Wed	FreeRTOS internals presentations by Mark and Sam + Discussion of DM scheduling (continued)	Proposals Reports Due EOW
14/10, Mon	No class, regional holiday -- Thanksgiving Day
16/10, Wed	Earliest Eligible Virtual Deadline First: A Flexible and Accurate Mechanism for Proportional Share Resource Allocation. Technical report, RTSS 1996 paper Presenter / Discussion Lead: Mayant
21/10, Mon	Real-Time Object Detection System with Multi-Path Neural Networks. PDF Presenter / Discussion Lead: Erik

Advanced Topics

Date	Reading Material / Topic	Milestone
23/10, Wed	Coq overview by Philip.
28/10, Mon	Response-Time Analysis for Globally Scheduled Symmetric Multiprocessor Platforms. PDF
30/10, Wed	Prosa: A Case for Readable Mechanized Schedulability Analysis. PDF, artifact
04/11, Mon	^
06/11, Wed	^
11/11, Mon	No class, midterm break
13/11, Wed	No class, midterm break
18/11, Mon	^
20/11, Wed	^
25/11, Mon	A Stack-Based Resource Allocation Policy for Real-time Processes. PDF Presenter / Discussion Lead: Sam
27/11, Wed	Paper title: TBD Presenter / Discussion Lead: Luca
02/12, Mon	Transferring Real-Time Systems Research into Industrial Practice: Four Impact Case Studies. PDF Presenter / Discussion Lead: Adarsh
04/12, Wed	Integrating Multimedia Applications in Hard Real-Time Systems. PDF Presenter / Discussion Lead: Mark	Last Day of Teaching

Final Exams Period

Date	Reading Material / Topic	Milestone
09/12	No classes during final exams
11/12	No classes during final exams
16/12	No classes during final exams
18/12	Final project presentations / FreeRTOS project demos (date tentative)	Final Reports and Artifacts Due

---

Interesting Papers

Following is a list of recent papers in the field of real-time systems, grouped by topics. You may decide to present one of these papers, or a different paper (maybe on a different topic) after consulting with me.

TBD

(While I prepare the new list, you may check out the list of papers discussed last year to get an idea.)

---

Assignments

TBD

---

Project

Research Project (Option 1)

You must propose a research project with a problem statment and a research plan, conduct the research, and write up your research results and experience. If you need any specific equipment, software, or tools for your project, please speak to us as soon as possible.

It is okay if you do not complete a full-fledged project by the end of the term. The goal is to learn how to go from a one-line problem to a fully scoped out research problem, then try and identify potential solutions. If a topic is difficult and you do not reach the practical implementation stage, that will be fine.

There are four deliverables in the project. Each written component must be formatted using the LIPIcs style template. You are strongly encouraged to use LaTeX for typesetting.

Research Proposal

The proposal should be minimally four pages (excluding references) and must include the following sections.

• Introduction: Explain what is the problem, why is it an important problem, and why are you interested in this problem? Describe the background and motivation for the problem you are interested in, and pose a concrete research question.
• Related work: Do a brief survey of related work in the problem space. This includes papers that solve the same problem but with a different approach and papers whose ideas you build upon in your own work. Compare and contrast your own proposed solution with each related work. If you have not read all the related work by the time of proposal submission, make a list of papers that you will be covering by the final report submission.
• Proposed solution: Describe your proposed solution and planned methodology to answer the research question at a high level.
• Evaluation: Describe how you plan to evaluate your proposed solution. What kind of data, plots, or proofs artifacts would you generate from the evaluation?

Proposal Presentation

Each group will give a short presentation followed by Q&A and feedback from the class. Focus on presenting:

• Problem: What is the problem they are working on? (Include the basic context that is required to understand the problem statement.)
• Motivation: Why is an important problem and why did you choose to work on this problem?
• Key idea: What is the key idea of your solution?
• Deliverable: What is the expected final deliverable?

Final Presentation

Each group will give a short presentation followed by Q&A from the class. The presentation would be similar to a conference or workshop talk. Focus on presenting the motivation, the problem, one key idea of your project, and the results.

Final Report

The final report must include similar sections as in the proposal but written in a way to describe what has been done. Additionally, add a section describing the limitations of your work and how the research can be extended (by you or someone else) in the future.

FreeRTOS Project (Option 2)

TBD