Real-Time System Design

This is the course webpage for both CPSC 538G and CPEN 432, which are cross-listed with each other this term.

This page is still under construction!

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 algorithms and mathematical analysis 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
• 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)
• Get a preview of state-of-the-art research on mechanizing scheduling analyses using the Coq interactive theorem prover (tentative)

Prerequisites

This is a beginner-friendly course intended to introduce you to the field of real-time systems. That said, 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.

---

Grading (tentative)

CPSC 538G

Take-home Homework Assignments (10%)

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

Paper Presentation (20%)

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 (occasionally, two) papers per day, some classical, some recent. Each paper will be assigned one or two discussion leads, who will be expected to read and understand the paper in detail, and who will be responsible for presenting the key ideas of the paper.

Participation (10%)

Participation includes engaging in discussion over Piazza, in the ``lectures'', and in presentations of your peers. Students are expected to read the assigned reading material before each class, post initial questions and discussion points on Piazza, and respond to others' questions on Piazza and in class. Please submit your questions and initial discussion points on Piazza by 11:00 AM one day before the class.

Research Project (60%)

The research project must be done in teams of 1-2. The goal of the research project is to conduct original research related to scheduling or real-time computing in operating or distributed systems (broadly construed). You may talk to the instructor for some ideas that are well-scoped for a course project. Your research project can have one of three flavors. (1) Exploration: You may 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. You may describe the design, implementation, and evaluation of your solution in the project report. You may optionally submit an artifact along with the report. (2) Replication: You may mechanize, verify, or reproduce the results of an existing real-time systems solution. In this case, you are expected to submit a functional artifact and results along with the project report. (3) Systematization: You may write an SoK (systematization-of-knowledge) paper on a topic, reviewing the literature and identifying potential directions for future research. Real SoKs tend to cover ~100 papers; an SoK in the course might cover at least 15-20 papers. The deliverables include:

• Project proposal (5%)
• Mid-term presentation (15%)
• Final report and artifact (40%)

Students enrolled in CPSC 538G may choose to do the CPEN 432 FreeRTOS Project (outlined below) instead of a research project. Undergraduates, especially, may decide to (and are recommended to) choose this option. Please consult with me before taking this decision, as we have limited embedded hardware available for the FreeRTOS Project.

CPEN 432

Take-home Homework Assignments (10%)

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

Mid-term Quiz (10%) and Final Exam (20%)

These will be written or CBTF exams covering all aspects of the course, including the fundamentals of real-time system design, advanced topics covered as part of the research paper discussions, and some aspects of the FreeRTOS project.

FreeRTOS Project (60%)

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 weights are summarized below.

• Earliest Deadline First (EDF) (15%)
• Stack Resource Policy (SRP) (15%)
• Constant Bandwidth Server (CBS) (15%)
• Multiprocessor Support (15%)

Like the research project, you must also submit a fully functional and reproducible artifact along with each assignment submission. You will be required to give a demo along with a presentation at the end. We will evaluate each assignment based on your submitted artifact (the README should clearly explain the design and the testing methodology) and the presentation (the demo should clearly showcase, through example workloads, why the specific algorithm works).

---

Schedule (tentative)

Module 1: Uniprocessor Hard Real-Time Scheduling

For this module, we will use the 4th edition of Giorgio Buttazzo's Hard Real-Time Computing Systems as the primary reference. Its electronic version can be downloaded from Springer and is also accessible via UBC Library. We will also refer to research papers when required, although they are optional.

Date / Day	Topic	Textbook Sections	Additional Readings
06/01, Tuesday	Overview and logistics	1	How to Read a Paper What is Real-Time Computing? A Personal View Modeling Cyber–Physical Systems
08/01, Thursday	Basic Concepts and Aperiodic Task Scheduling	2, 3	Response-Time Analysis of a Soft Real-time NVIDIA Holoscan Application (Sections I-IV)
13/01, Tuesday	Recurrent Real-Time Task Models (Implementation)	12	Liu and Layland and Linux: A Blueprint for “Proper” Real-Time Tasks
15/01, Thursday	Recurrent Real-Time Task Models (Extraction)		LiME: The Linux Real-Time Task Model Extractor Paper Presentation by TBD
20/01, Tuesday	Periodic Scheduling (TS, RM, EDF)	4.1 - 4.4
22/01, Thursday	Periodic Scheduling (DM, RTA)	4.5 - 4.7
27/01, Tuesday	Application of Periodic Schedulability Analysis		Controller Area Network (CAN) Schedulability Analysis: Refuted, Revisited and Revised Paper Presentation by TBD
29/01, Thursday	Resource Sharing (NPP, PIP, Mars)	7.1 - 7.6	What really happened on Mars Rover Pathfinder What the Media Couldn’t Tell You About Mars Pathfinder
03/02, Tuesday	Resource Sharing (PCP)	7.7
05/02, Thursday	Resource Sharing (SRP)	7.8
10/02, Tuesday	Fixed-priority Servers (BS, PS, DS, SS)	5
12/02, Thursday	Dynamic-priority Servers (DSS, CBS)	6	Deadline scheduling part 1 — overview and theory Deadline scheduler part 2 — details and usage The hierarchical constant bandwidth server scheduler

Mid-term Break, Project Presentations, and Quiz

Date / Day	Topic
17/02, Tuesday	No class, mid-term break
19/02, Thursday	No class, mid-term break
24/02, Tuesday	No class, mid-term project presentation for CPSC 538G and mid-term Quiz for CPEN 432

Module 2: Multiprocessor Hard Real-Time Scheduling

For this module, we will primarily use research papers as the reference, unless specified otherwise. However, we may also occasionally use the 1st edition of Baruah, Bertogna, and Buttazzo's Multiprocessor Scheduling for Real-Time Systems for reference. Its electronic version can be downloaded from Springer and is also accessible via UBC Library.

Date / Day	Topic	Additional Readings
26/02, Thursday	Basic Concepts	Scheduling and Locking in Multiprocessor Real-Time Operating Systems (Sections 2.1-2.3)
03/03, Tuesday	Partitioned Scheduling	Partitioned Scheduling of L&L Tasks
05/03, Thursday	Global Scheduling	Response-Time Analysis for Globally Scheduled Symmetric Multiprocessor Platforms
10/03, Tuesday	Schedule Abstraction Graphs	A Response-Time Analysis for Non-Preemptive Job Sets under Global Scheduling
12/03, Thursday	Semi-partitioned Scheduling	Global Scheduling Not Required: Simple, Near-Optimal Multiprocessor Real-Time Scheduling with Semi-Partitioned Reservations Paper Presentation by TBD

Module 3: Advanced Topics

In this module, we will spend some time understanding scheduling in Linux, and then discussing a few recent research papers on the design of learning-enabled components for real-time systems, especially automotive systems. Depending on the number of students enrolled in CPSC 538G, I may teach some of the topics, or we may schedule multiple paper presentations per day. Note: If you would like to discuss a specific topic that is not covered in the course, but still relevant to real-time systems research, e.g., security of embedded platforms or complexity and hardness analysis of real-time scheduling problems, I am happy to update the schedule.

Date / Day	Topic	Additional Readings
17/03, Tuesday	Temporal Interference in Linux	Interference-free Operating System: A 6 Years’ Experience in Mitigating Cross-Core Interference in Linux Paper Presentation by TBD
19/03, Thursday	Proportional Share Scheduling in Linux	Earliest Eligible Virtual Deadline First: A Flexible and Accurate Mechanism for Proportional Share Resource Allocation A proportional share resource allocation algorithm for real-time, time-shared systems An EEVDF CPU scheduler for Linux Paper Presentation by TBD
24/03, Tuesday	GPU Scheduling	XSched: Preemptive Scheduling for Diverse XPUs Paper Presentation by TBD
26/03, Thursday	TBD	Paper Presentation by TBD

Module 4: Mechanizing Schedulability Analyses

In this module, we will spend most of the time understanding the state-of-the-art research on mechanizing scheduling analyses using the Coq interactive theorem prover.

Date / Day	Topic	Additional Readings
31/03, Tuesday	TBD	PROSA: A Case for Readable Mechanized Schedulability Analysis
02/04, Thursday	TBD	TBD
07/04, Tuesday	TBD	TBD
09/04, Thursday	TBD	TBD