The labs revolve mostly around the course project, which comprises writing a simple but working operating system. The lab sessions are held in a lecture room (instead of a computer lab) and are intended for discussion about tasks in the past, ongoing and upcoming project milestones. Some of the labs will be held as debugging sessions where we expect the teams to bring their laptops so that we can help debug or refactor their code.
Whenever a new milestone is published, you are expected to familiarize yourself with the milestone tasks so that we can focus on particular problems or pitfalls.
Even though the tasks in the initial (individual) milestones are fairly simple, the tasks in the team milestones will get gradually more difficult. Part of the complexity is due to the cumulative nature of the tasks in the project — your solution to tasks from a particular milestone will be built on top of previous code.
Because you will have to live with your code for most of the semester, you should strive to make the code readable and easy to understand. To this end, pay attention to use of higher-level abstractions, functional decomposition, and proper naming.
Milestones
The following table lists the milestones that you will need to complete, along with the deadlines for extra points. The download information refers to a directory in the individual or team repository in which you will find the specification of milestone tasks along with a skeleton implementation.
In general, you should start working on milestone tasks as soon as possible. If you discover the difficult parts early on, there is time to discuss them within the team and during the lab sessions. Getting support few hours before the deadline is much harder. Use the calendar on the schedule page to keep track of the deadlines and plan your work accordingly.
| Date | Title | Repository |
|---|---|---|
| 2024-09-23 – 2024-10-13 | C Language Refresher | student / m00-c-language |
| 2024-09-30 – 2024-10-20 | Introduction to kernel | student / m01-kernel-intro-{mips,riscv} |
| 2024-10-14 – 2024-11-03 | Kernel memory management | team-{mips,riscv} / README-m02.md |
| 2024-10-28 – 2024-11-17 | Threads, cooperative scheduler | team-{mips,riscv} / README-m03.md |
| 2024-11-11 – 2024-12-01 | Preemptive scheduler | team-{mips,riscv} / README-m04.md |
| 2024-11-25 – 2024-12-22 | Virtual memory management | team-{mips,riscv} / README-m05.md |
| 2024-12-09 – 2025-01-12 | Userspace | team-{mips,riscv} / README-m06.md |
The storyline
While the topics listed in the table above might seem disconnected, together they will lead your project from virtually zero to a pretty decent operating system.
Their ordering ensures that you build from solid foundations and allows us to assign the milestones in an incremental fashion. The ordering is also aligned with lectures so that you will first hear the about the theoretical concepts and then you will recast (some of) them into a working implementation.
In all of the milestone we will provide you a set of tests to check your
implementation. The tests are provided as a sources to be linked with your
code and you are free encouraged to inspect them. It is even allowed to modify them,
e.g. when you want to add more logging prints to them. However, your solution
must pass even with unmodified tests.
The zeroth milestone is a C language refresher to get you going. You can work with any decent compiler to get it running and you will have the comfort of using your favourite tools. And in this safe environment you will build foundations for your kernel: you will have tools to print something from a kernel (it does not sound like much but it is the easiest way of output). We will also touch on using a special kind of a linked list that is also present in Linux or HelenOS.
In milestone M01 you will move this code into kernel space. You will need
a special compiler to cross-compile your code for MIPS and/or RISC-V
architecture and then you will run your code in a simulator of a simple
MIPS/RISC-V board. If your printing functions from M00 are fine the transition
to kernel space and MIPS/RISC-V should be a painless experience. The biggest
surprise might be that in your new kernel, you are starting from scratch.
You will get from us literally only about 10 lines of assembly code for booting
and the rest you will implement yourself (or reuse from M00).
There will be no safety net of a standard library: if you want something,
you need to add it yourself.
Having a well-designed and bug-free printing function – we will call
it printk for obvious reasons – is a good start.
In M02 you will start working in teams and the first task will be to merge
your implementations of printk (or you might simple choose the best one).
But in M02 you will have one more task: add functions for dynamic memory
allocation so that you can create objects dynamically on demand. Your are
in kernel, hence the whole RAM is yours and you will need to decide how
to partition it for your users and how to implement the malloc-style API.
Your printk will become your main debugging aid as it will help you print
on which addresses you are operating and how your heap is behaving.
Following milestone (M03) will add support for threads. Until M03, all the code was using one stack and was structured sequentially. Adding threads will allow you to split the work performed by kernel into multiple independent units, each executing its own code on its own stack. To simplify things a bit, your system will be running always on a single CPU machine (in all the milestones) and the threads will need to voluntarily yield (give up) the CPU to let other threads run (for now).
In the next milestone, M04, you will add the ability to preempt the threads
and thus make your kernel responsive even when one thread enters an endless
loop. That is extremely important for running userspace (i.e., end-user)
applications. You certainly do not want to render your system inoperable
by a user that compiles a while (1) {} program and runs it.
M05 requires that you setup virtual memory (paging) and support it in your system. That will be needed to run userspace code as you do not want to let two different applications access the same memory (in layman terms we can say that while M04 ensured that CPU is protected, M05 ensures the memory is protected against a bad code). Unfortunately, M05 is usually considered as the worst milestone – probably because paging itself is (wrongly!) considered a terrifying topic and also because any technological debt from previous milestones tend to demonstrate itself in this milestone. Do not be discouraged: the kernel will be almost done by that time and you will have a ton of experience to overcome any difficulties.
The last milestone adds a support for running simple end user applications in userspace. While your kernel code has full control over the CPU and can perform even privileged operations, userspace applications are much more limited. They will need to ask your kernel to perform for them some special operations. In your kernels, this will include writing to the screen as that is actually a device access and has to be controlled by the kernel. The last milestone is actually quite short as most of the heavy-lifting was already done in M04 and M05. It is time to get proud of your work :-).
Labs
The following table lists preliminary content of the labs. The labs are intended mostly as Q&A sessions so the title is just a pointer in the general direction of the discussions.
As usual, coming prepared – either with a specific question or a particular broken test case that needs debugging – is the best use of your time.
| Week | Date | Content |
|---|---|---|
| #1 | 2024-10-03 | Introduction, M00 discussion |
| #2 | 2024-10-11 | Teams, M01 discussion |
| #3 | 2024-10-17 | M02 discussion |
| #4 | 2024-10-24 | Code review (debugging session) |
| #5 | 2024-10-31 | M03 discussion |
| #6 | 2024-11-07 | Code review (debugging session) |
| #7 | 2024-11-14 | M04 discussion |
| #8 | 2024-11-21 | Code review (debugging session) |
| #9 | 2024-11-28 | M05 discussion |
| #10 | 2024-12-05 | Code review (debugging session) |
| #11 | 2024-12-12 | M06 discussion |
| #12 | 2024-12-19 | Code review (debugging session) |
| #13 | 2025-01-09 | Code review (debugging session) |