The CS452 Journey - W23

https://student.cs.uwaterloo.ca/~cs452/W23/

I started writing this memo at May 28, 2023 - which is already one and a half months past the completion of the course. CS452 (Real-time Programming), widely acknowledged as the most challenging course in the Waterloo CS department, happens to cover right on the spot of my interest. Among all of the areas covered in my undergrad studies, operating system is absolutely the most intriguing to me. In CS452, one of the course objective is to write a microkernel from scratch. This is a must-take for me!

The desire to take the course is so strong that I aborted a great plan. Almost two years ago, I applied and planed for an exchange term to Singapore NUS in the winter of 2023. However, when the news came that I cannot take CS452 after coming back from the exchange, I am so lost. My mind is so entangled because I don’t know how to resolve this situation. Finally, after a month of consideration, I decide to give up the exchange just to do CS452.

A0

The first assignment is a week 1 assignment. The start of the term is January 9th, and the due date is 17th. The first assignment’s purpose is to let us get familiar with the hardware, like reading the docs for the board, the hat, and the tracks. The class starts with students exceeding the limit, like 50 some students.

The only given code is 200 lines of driver code for using the uart through spi. Our goal is to write a program to send simple commands to the track, like setting a train to a certain speed level and switch some turnouts. Here, we don’t have an OS yet, so the main program is structured as a big loop. Most of us implemented some sort of data structure for delaying tasks, because the hardware already demonstrates some real-time aspects. For example, each command to the track should be separated by a certain time interval. And for the turnouts solenoids, 150-500ms after switching one, the program needs to either switch another turnout, or send a special command so that the solenoids don’t burn out.

I implemted a small linked-list based scheduler to schedule subtasks with certain delay interval. In general, the software design isn’t too difficult, the major challenges were

• Hardware debugging: when things don’t work, it is difficult to debug, for example, the 200 lines of uart driver code has been intentionally left with two bugs. Among them, one bitshift bug is not easy to discover, because when the hardware doesn’t work, it doesn’t tell us what went wrong (unlike a website).
• Write a lot of code within a tight deadline. My A0 ends up with 2k sloc of C code. I think I must spent like 50 hours that week to complete this.

After A0 completion, a lot students dropped. The class went on with 20 students (10 groups) to begin the operating system journey.

Kernel

The first half of the course is designated to write a microkernel. The steps we took to implement it is 1) Context Switch 2) Message Passing, and 3) Hardware Interrupts. I spent like a week of time to make MMU working after step 2.

Train Control

In the second half of the course, we start to implement the train control software on top of our own OS. This is more intensive part. No control software is perfect, all suffer some kind of shortcoming. The challenge are splited into two parts that correlates with each other: 1) How to control one single train which has only 14 speed level and the few sensors on the track only sends a binary signal when something flips it (the program need to guess the train speed); 2) How to control multiple trains on the track moving at the same time (e.g. sensor attribution, intersection locks, deadlock resolution). Between the two parts, I did a 2000 line rewrite so that I sacrifice some stopping accuracy to be able to specify the time to arrive at the destination. This choice gave us a cool final project, but makes hardware failure (e.g. some sensor didn’t trigger when a train passes it) handling much more complicated.

Our OS plus train-control software is about 15k sloc of C & ASM code.