Project 2: Processes and Time-Sharing the CPU

At the end of Project 1, your operating system could load a program into memory, run it, and—once that program was finished—load and run the next one. That is batch processing, and it is how computers worked until the early 1960s. It has one serious problem: at any moment, exactly one program exists, and while it runs, nothing else can happen. If that program stops to wait for a slow event, the CPU waits with it.

In this project, you will fix that. By the end, your OS will hold several processes in memory at the same time and switch the CPU between them—first when a process politely asks (cooperative concurrency), and then whether it likes it or not (preemptive concurrency). You will write the code that takes a running program’s registers off the CPU, puts another program’s registers on, and resumes it as if nothing had happened. You will also program the CPU’s hardware exception handlers and set up a hardware timer so that your kernel gets control back periodically, even from a program that never gives it up voluntarily.

This is the point in the course where your OS starts to look like a real one. The mechanism you are about to build—the context switch—is the beating heart of every multitasking operating system ever written. Linux does it a few thousand times a second per core; so will yours.

Learning objectives

After completing this project, you will be able to:

1. Explain one major reason why an operating system runs multiple programs at once. Hardware devices are slow compared to the CPU. If only one program can exist at a time, the CPU sits idle whenever that program waits for I/O. Running several programs concurrently lets the OS multiplex a fast CPU across slow devices.
2. Explain how a context switch is implemented in a kernel, and implement one: what exactly constitutes a process’s “context”, where it is stored, and what it takes to take it off and put it back on the CPU.
3. Explain how cooperative concurrency works via a yield() call, and implement it—including why a process that calls yield() eventually returns from it as though nothing had happened.
4. Explain why preemption is necessary. A program that never yields would otherwise run forever; and when a device finishes an I/O operation, something must respond promptly. Both require a way to interrupt a running program.
5. Explain how preemptive concurrency works, and implement it: how a hardware timer is programmed, what happens in hardware when it fires, and how the kernel turns that event into a scheduling decision.
6. Explain the difference between a synchronous exception and an interrupt, and describe precisely what the CPU does—and, crucially, what it does not do—when either occurs. You will also learn what an exception vector table is and why a kernel must program one into the hardware before it can handle anything.
7. Explain that different scheduling algorithms exist and that they trade off against each other. You will implement round-robin scheduling; students in CS 1690/2670 will implement something more sophisticated and argue about what it optimizes for.

CS 1670 vs. 1690/2670

As in Project 1, all students share the same core project, but students in CS 1690/2670 complete extra work and run their code on real hardware.

Here is a summary of the quests you must complete for this project, based on which course you’re enrolled in:

Roadmap

The project has five quests, which build on each other. Quests 1–4 are required for everyone; quest 5 is for CS 1690/2670 only.

Read the Background section before you start: it gives you the conceptual foundation that all five quests build on. Each quest then opens with its own background material—the concepts and ARM64 details that quest specifically needs. Work through the quests in order; each one depends on the one before it.

Assignment Installation

You will keep working in the same private GitHub repository you used for Project 1.

To pull in the new files for this project (new empty source files and an updated build system), run the following in your project directory:

git pull handout main

If this reports an error about an unknown remote, run:

git remote add handout git@github.com:csci1670/cs1670-f26-projects.git

and then git pull handout main again.

Code Structure

As in Project 1, you write all the significant code yourself; we provide a build system and a skeleton of (mostly empty) files that suggests how to organize it. Here is what is new or changes in this project:

.
├── Makefile
├── kernel/
│   ├── aarch64.h              Quest 1: SCTLR/HCR/SPSR constants (we provide these)
│   ├── boot.S                 Quest 1: move from EL3 to EL1
│   ├── debug.h                DEBUG() and CHECK() macros (we provide these)
│   ├── constant.h             Quest 2: the size of a saved context
│   ├── context.S              Quest 2/3: save_context, restore_context, yield_entry
│   ├── context.h              Quest 2: declarations for the above
│   ├── proc.c, proc.h         Quest 1: struct proc, the process table, allocproc()
│   ├── limits.h               Quest 1: NPROC, PROC_START, PROC_SIZE
│   ├── scheduling.c, .h       Quest 3: yield(), scheduler(), pick_next()
│   ├── exceptions.S           Quest 4: the exception vector table
│   ├── exceptions.h           Quest 4: exception_init(), exception_vector_table
│   ├── interrupts.c           Quest 4: interrupt dispatch and DAIF helpers
│   ├── interrupts.h           Quest 4: interrupt controller registers to fill in
│   ├── drivers/
│   │   ├── timer.c, timer.h   Quest 4: the timer device driver
│   │   ├── uart.c, uart.h     (yours, from Project 1)
│   │   └── gpio.h             (yours, from Project 1)
│   ├── elf.c, elf.h           (from Project 1; Quest 1 changes the loader)
│   ├── init.c                 Quest 1: create and load all processes
│   ├── kernel.c               Quests 1--4: kernel_main
│   ├── memlayout.h            Quest 3: add F_YIELD
│   └── ...
└── user/
    ├── hello.c                 provided: prints, then yields, forever
    ├── counter.c               provided: prints a counter, then yields, forever
    │                           (both: uncomment their yield() call in Quest 3)
    ├── primecheck.c           (from Project 1) never yields: a CPU hog
    ├── u_common.h             Quest 3: add the user-side yield()
    └── ...

Building and running

Nothing changes from Project 1: the build system uses make, and the important targets are

$ make qemu        # build the image and run it in QEMU
$ make qemu-gdb    # same, but pause and wait for a debugger to attach
$ make clean       # remove build artifacts

Remember that to quit QEMU you type Ctrl-a then x. You will be doing this a lot in this project, because a broken context switch usually manifests as a hang.

while (/* the transmit FIFO is full */) {
    // spin
}

Quest 1: Many processes in memory

Files: kernel/boot.S, kernel/aarch64.h, kernel/proc.c, kernel/proc.h, kernel/limits.h, kernel/elf.c, kernel/init.c, kernel/kernel.c.

Overview

Before you can switch between kernel processes, you need more than one process to switch between. In this quest you will:

1. Change the bootup code to move your CPU into the right “exception level” (EL), from EL3 to EL1. This is needed so that the exception machinery you need in the rest of the project is available to you.
2. Introduce the data structure that represents a process: a process descriptor (struct proc), a process ID (PID), and a process table.
3. Change your ELF loader so that it can load several programs into different regions of physical memory, and load three of them.

At the end of the quest, your OS will hold three kernel processes, all of them loaded and ready to run, and it will run one of them. It cannot yet switch between processes—that’s Quests 2 and 3—but everything a switch needs will be in place.

Why are we doing this?

Batch processing lets you get away with a beautiful simplification: since only one program existed at a time, it could always be loaded at the same address, and the kernel needed to remember essentially nothing about it. Multiprogramming changes this: several programs must be resident simultaneously, which means they must be at different addresses, which means the kernel must decide on those addresses and remember them. And once the kernel is remembering things about a program, it needs somewhere to put them. This is what a process descriptor is for.

This is a pattern you will see repeatedly in OS design: a new capability forces the kernel to start tracking state, and that state becomes a data structure that the rest of the kernel is organized around. struct proc is the most important such structure in any kernel.

What you need to do

Part A: more bootup configuration

When a machine starts up, the hardware is generally in the most privileged state possible. Early code running during bootup then reduces privilege levels, until eventually unprivileged user processes can run. On ARM64, there are four privilege levels, called exception levels (EL0–EL3). The CPU starts in EL3, where your bootup code runs. You will now drop it two more levels, to EL1.

When QEMU (or the Raspberry Pi’s firmware) starts your kernel image, it hands control to you at EL3.¹ Your Project 1 boot.S never changed that, so your kernel has been running in EL3 this whole time (see the background above). This didn’t matter, because nothing you did in Project 1 cared. But you need it at EL1 now: everything in this project is built on the EL1 registers,² and Project 4 needs EL1 so that your processes can drop to EL0 and finally be isolated.

The transition happens at the end of your bootup code, before you jump into C, and it involves configuring a bunch of system registers. The details aren’t super important at this point, so we provide you with a code snippet to do this. If you are curious, you can read the details below.

Here’s the code you need to add to kernel/boot.S to do this. It goes after the code that parks the non-boot cores, but before you set up the stack and jump into C. You should move the code that sets up the stack and jumps into C to a new label, el1_entry, which is where the CPU will jump after the eret instruction.

This code refers to constants like SCTLR_VALUE_MMU_DISABLED that we define for you in aarch64.h, so you will need to add a #include "aarch64.h" to the top of boot.S. Recall that #include merely copies the file’s contents into the assembly file, so all this does is adding the contents of aarch64.h here. A C header included from assembly can only contain constants and function declarations; it cannot contain actual C code as the assembler would not know how to compile it.

// Only processor 0 runs this code
processor0_el3:
    // Switch from EL3 to EL2
    ldr  x0, =SCR_VALUE_EL3  // Set values in System Control Register; see aarch64.h.
                             // NS=1 (non-secure), RW=1 (EL2 runs AArch64)
    msr  SCR_EL3, x0
    ldr  x0, =SPSR_VALUE_EL3 // Set values in the Saved Program Status Register (SPSR); see aarch64.h.
                             // return to EL2h, DAIF masked (no interrupts)
    msr  SPSR_EL3, x0
    adr  x0, processor0_el2
    msr  ELR_EL3, x0         // Store the address of processor0_el2 into the exception link register
                             // for EL3, meaning that `eret` will use it as the return address and
                             // jump to it.
    eret                     // Exception return; changes the exception level from EL3 to EL2 and
                             // jumps to the address in the ELR_EL3 register (which is processor0_el2)

processor0_el2:
    ldr   x0, =SCTLR_VALUE_MMU_DISABLED
    msr   SCTLR_EL1, x0  // Set values in System Control Register; see aarch64.h.

    ldr   x0, =HCR_VALUE_EL2
    msr   HCR_EL2, x0    // Set values in Hypervisor Configuration Register (HCR); see aarch64.h.

    ldr   x0, =SPSR_VALUE_EL2
    msr   SPSR_EL2, x0   // Set values in the Saved Program Status Register (SPSR); see aarch64.h.

    adr   x0, el1_entry
    msr   ELR_EL2, x0    // Store the address of el1_entry into the exception link register
                         // for EL2, meaning that `eret` will use it as the return address
                         // and jump to it.

    eret                 // Exception return; changes the exception level from EL2 to EL1 and jumps
                         // to address in the ELR_EL2 system register.

To check that the exception level transition worked, you can do one of the following:

• In GDB, p/x $cpsr shows PSTATE. Its lowest four bits are the mode: 0b1001 is EL2h, 0b0101 is EL1h. Watch it change across your eret by single-stepping the assembly code.
• Run with make qemu-verbose, which has QEMU print all exception level changes. You should see output along the lines of “Exception return from AArch64 EL2 to AArch64 EL1 PC 0x8003c”.
• You can write small helper, current_exception_level(), that returns the exception level the CPU is currently at. The CurrentEL system register holds it in bits 3:2, so use mrs and some bit-shifting assembly to extract the number and return it. The function needs to be written in assembly, either directly in boot.S or as inline assembly in C (use AI to help you with the syntax). You can use your helper function print your exception level from kernel_main.

If your kernel dies right after the eret, the two overwhelmingly likely causes are (a) you forgot either SCR_EL3.RW or HCR_EL2.RW, so you are now running in 32-bit mode, or (b) sp is garbage because you set it before the eret.

Part B: the process table

In the next step, you will define some data structures necessary for running multiple processes. You will define a process descriptor (struct proc), a process table (an array of descriptors), and a current process pointer.

Part C: load several programs

Your Project 1 loader always loaded a program to the same place, because there was only ever one. Now it needs to load a program into a particular kernel process’s memory region.

PROC_START + pid * PROC_SIZE

In addition to process location, which is a choice for your OS design, we’ll introduce another convention to tell your kernel about the available executables. This one is not really a design choice: instead, it helps us make debugging easier and allows our autograder to check your work.

In a nutshell, we ask that you change your kernel to have two global arrays:

1. An array called executables, which holds the linker-provided symbols for all executables that you will load and run, in the order in which you will load/run them. The last element of this array must be a nullptr sentinel, so that your init function can iterate through it without needing a separate count.
2. An array called executable_names, which holds the names of those executables, in the same order. Similarly, the last element of this array must be a nullptr sentinel.

Our build system uses these arrays to extract debug symbols for your processes (so that you can step through process code with GDB), and our grading server may at times replace your executables with a different set for testing. So, please use the names we provide, and no longer hardcode addresses or names in your loader or init function.

For example, your initial code that sets up these arrays and runs the processes could look like this:

extern char _binary_user_squares_elf_start[];    // Linker-generated, already exists in `init.c`
extern char _binary_user_pi_elf_start[];         // same
extern char _binary_user_primecheck_elf_start[]; // same

// All executables available
char* executables[] = {
    _binary_user_squares_elf_start,
    _binary_user_pi_elf_start,
    _binary_user_primecheck_elf_start,
    nullptr
};

// Names of the programs for debug output
char* executable_names[] = {
    "squares",
    "pi",
    "primecheck",
    nullptr
};

void init() {
    // [...]
    for (int i = 0; executables[i] != nullptr; i++) {
        struct proc* p = allocproc();
        strcpy(p->name, executable_names[i]);
        load_elf_into_proc(executables[i], p);
        p->state = RUNNABLE;
    }
    // [...]
}

This is one of the few places in the course where we actually establish a convention for your kernel’s design, primarily to simplify debugging. Please respect our convention; it will help you.

warning: 'executables' symbol not found in kernel ELF. Make sure the executables array is a global variable.
GDB user-space symbol loading will not be available.

Check your work

Run make qemu. You should see your kernel start, list three loaded kernel processes at three different addresses, and then run one of them:

Hello world from MyOS!

Process table:
pid 0  "hello"       load 0x000A0000  entry 0x000A0000  RUNNABLE
pid 1  "counter"     load 0x000B0000  entry 0x000B0000  RUNNABLE
pid 2  "primecheck"  load 0x000C0000  entry 0x000C0000  RUNNABLE

starting pid 2 (primecheck)...
Process primecheck: Found another 1000 primes; last one was 7919!
Process primecheck: Found another 1000 primes; last one was 17389!
...

Two things worth verifying in gdb, because they will save you time later:

1. All three programs really are in memory, at the right places. Break after loading the ELF executables and disassemble at each kernel process’s entry point: x/8i 0xA0000, x/8i 0xB0000, x/8i 0xC0000. You should see three plausible-looking sequences of assembly instructions, not zeroes.
2. You are at EL1. p/x $cpsr and check that the low four bits are 0x5 (EL1h).

Quest 2: Saving and restoring a context

Files: kernel/constant.h, kernel/context.S, kernel/context.h, kernel/proc.h, kernel/elf.c, kernel/kernel.c.

Overview

The notion of a context switch is the heart of the project and creates the magic that lets a computer run one process, then run another for a while, and continue the first process as if nothing had happened. You will define what a saved context looks like in memory, write the two functions that save and restore one, and then use the restore half to start a process. This makes for a satisfying way to test your work, because starting a process from nothing is just restoring a context you made up.

Why are we doing this?

Every operating system on every architecture contains a function like the one you are about to write, and it is always in assembly, because it is the one piece of a kernel that manipulates the very registers a compiler assumes it owns. You cannot write it in C: the moment you have loaded another process’s registers, the C compiler’s assumptions about what is in them are false, and there is no way to express “and now change the program counter too” in C at all.

This is also where the abstract idea of “a process” becomes 272 concrete bytes that you can look at in a debugger!

We have to store the saved registers somewhere. There are two obvious choices, and the one we recommend you choose is less obvious but much nicer:

• Inside the process descriptor. struct proc gets a struct context field, and save_context writes the registers into it. Straightforward, but it means the stack pointer must be saved and restored explicitly, and it does not generalize well to interrupts.
• On the process’s own stack. Just before saving, you subtract the size of a context from sp to make room, and then write the registers into that space. struct proc stores only a pointer to it.

We recommend the second. Here is what this looks like:

The trick that makes it elegant is that the saved context always sits immediately to the left (i.e., at lower addresses) than the stack pointer the process had, so you never need to save sp at all, because you can compute it. Restoring is:

sp = (address of the saved context) + (size of a context)

In other words, the context’s own location in memory helps you determine where the stack pointer was, since that location must be one context’s worth beyond the address where the context was saved on the stack. This also provides the right structure for interrupt handling, where the hardware has already switched to the process’s stack by the time your code runs (as you’ll see in Quest 4).

So how do we store the context in memory? The answer is: however you like, there is no single right way as long as save_context and restore_context agree. You must include all of the information mentioned above, though! In addition, the ARM64 architecture requires the start and end of the stored context to be aligned with a 16-byte boundary. Think about this on your own a bit and come up with a memory layout and matching struct definition. If you’re stuck or are looking for inspiration, we provide a recommended example layout below.

What you need to do

Part A: define the context

In the first step, we will define a data structure to represent a saved context in C. This data structure must have exactly the memory layout you choose for your context (e.g., the one we suggest above). It must also be 16-byte aligned, because it will be stored on the stack and sp must always be 16-byte aligned on ARM64.

_Static_assert(sizeof(context_t) == S_FRAME_SIZE, "context_t must be S_FRAME_SIZE");

Part B: save_context and restore_context

Now we will write the assembly code for the actual context switch. This is the heart of this project and where all the magic comes from! You’ll write two functions, save_context and restore_context in assembly. We recommend putting both functions into kernel/context.S.

Writing this code is tricky. The assembly itself is mechanical, but you must think carefully about the state of the CPU, the order of operations, and the invariants you must maintain. One important complexity is that calling a function itself changes the state of the CPU registers (e.g., the return address in lr/x30, the stack pointer in sp, and the values of registers that hold arguments).

There are several canonical ways you can write this code. The main ones are:

1. Use an assembly macro. Rather than writing callable functions save_context and restore_context, you can write an assembly macro that expands to the code for saving or restoring a context inside the functions that need to do so. This avoids the problem of clobbering registers when calling a function, but it can make the code harder to read and maintain. If you want to use this approach, you will need to learn about ARM64 assembly macros.
2. Split save_context into two parts. You can first save the registers that will be clobbered by a function call inside the function that calls save_context, and then save the rest of the context inside save_context, which you call as a normal function (e.g., via the bl assembly instruction). There are only a handful of places in the kernel that call save_context, so this is a reasonable approach. This is the approach we recommend.

In the following, we describe the contracts for the two functions, with notes for how save_context differs if you follow the second (recommended) approach.

save_context takes no arguments in the ordinary sense, since its job is to faithfully store the exact CPU state at the moment it happens. Here’s what it needs to do:

• subtract a context’s worth of bytes (S_FRAME_SIZE or 272) from sp, making room for the context on the stack;
• store registers x0–x30 into the right offsets inside this space;
• copy ELR_EL1, and SPSR_EL1 into the right places inside this space to store pc and PSTATE values;
• set ELR_EL1 and SPSR_EL1 to the values that should be saved (in Quest 4 the hardware will have done this part) and return normally.

If you are following our recommended approach (2) above, you should assume that by convention, the caller of save_context has already:

• subtracted S_FRAME_SIZE or 272 from sp, making room for the context;
• stored fp and lr (at sp + 0 and sp + 8 if following our recommended layout);
• set ELR_EL1 and SPSR_EL1 to the values that should be saved (again, in Quest 4 the hardware will have done this part).

save_context then merely stores x0–x28, copies ELR_EL1, and SPSR_EL1, and returns normally.

restore_context(context_t* c) takes a pointer to a saved context in x0, and never returns. It must:

1. Write the saved ELR_EL1, and SPSR_EL1 back into their system registers.
2. Restore fp, lr, and x0–x28 from the saved context.
3. Set sp to c + S_FRAME_SIZE or c + 272, popping the context from the stack.
4. eret, which sets pc from ELR_EL1 and PSTATE from SPSR_EL1 in a single step.

Part C: build an initial context, and start a kernel process with it

A process that has never run has no saved context—so the kernel has to fabricate one that looks exactly like a context saved from a process about to execute its first instruction. This is a lovely idea: to start a program, you construct a lie about its past and then resume it.

The initial context for a newly loaded process needs:

• Location: immediately prior (in address terms) to the top of the process’s stack, i.e. at stack_top - sizeof(context_t). Restoring it will therefore set sp to stack_top, which is exactly right for a program that has not pushed anything yet.
• All general-purpose registers: zero. A fresh program has no live values. Zero the whole frame first and then fill in what matters; this also means a stray read of an uninitialized register gives you a predictable 0 rather than junk.
• ELR_EL1: the program’s entry point, which is the ELF header’s e_entry plus the base address you loaded the process at. Recall that ELR_EL1 is where eret will jump to (normally a saved return address, but here the first instruction of the program).
• SPSR_EL1: the processor state the process should run with. For now: EL1 using SP_EL1 (EL1h), with all interrupts masked—you still have no interrupt handlers. We define this as a named constant, SPSR_PROC, in kernel/aarch64.h, composed from the SPSR_EL1h and SPSR_MASK_ALL constants in the same file. Use this constant for now; you will change it in Quest 4.

Check your work

make qemu should behave exactly as it did at the end of Quest 1: primecheck runs and prints primes. That is the point: the observable behavior is unchanged, but the mechanism underneath is completely different. Rather than calling your program as a function, your process is now running because your kernel built a context and restored it!

Verify that in gdb, because “I did nothing”, “it happens to work”, and “it actually works” can look identical here. Here’s a receipe for checking with GDB:

(gdb) break restore_context
(gdb) continue
(gdb) p/x $x0                 # the context pointer: should be stack_top - 272
(gdb) x/34gx $x0              # the stored context itself: mostly zeroes, then entry point, then SPSR
(gdb) # step to just past the `eret`, then:
(gdb) p/x $pc                 # should be the process's entry point
(gdb) p/x $sp                 # should be the top of the process's stack
(gdb) p/x $cpsr               # low nibble should be 0x5 (EL1h)

Quest 3: Cooperative concurrency

Files: kernel/memlayout.h, user/u_common.h, kernel/context.S, kernel/scheduling.c, kernel/scheduling.h, kernel/kernel.c.

Overview

Now you make your OS actually switch between kernel processes that exist in memory at the same time. In this quest you will expose a yield() function to user programs, implement it, write a round-robin scheduler, and watch three kernel processes take turns. You will also watch what happens when one of them refuses to take turns—which is the motivation for Quest 4.

Why are we doing this?

Cooperative concurrency is the simplest possible answer to “how does the kernel get the CPU back”. By the end of this quest you will have a working multitasking OS, akin to early versions of Mac OS or Windows.

What you need to do

Part A: expose yield to user programs

Part B: actual yielding and the scheduler

Now we’ll implement the actual scheduler. A scheduler consists of a policy, which will be the easy part here, and some mechanism, which is where the context switch you learned about in this project comes into play.

For the mechanism (“plumbing”) part, we will use the save_context and restore_context logic that you developed in Quest 2 to implement real yielding.

Look again at what restore_context needs: ELR_EL1 (where to resume) and SPSR_EL1 (what state to resume in). These registers are typically set by the hardware for you when an exception, interrupt, or system call happens. But on an ordinary function call, nobody does this for you: ELR_EL1 and SPSR_EL1 contain whatever they last contained, which is garbage.

The answer is for yield to do the hardware’s job by hand. Here is what an ARM64 CPU does when it takes an exception to EL1, and what your yield will do in imitation:

That is why yield needs a small assembly stub of its own, which we’ll call yield_entry. Once those first three steps have run, the situation is identical to an exception entry, and the rest of the code—save_context, the scheduler, restore_context—can be written once and used by both paths. In Quest 4, you will write the interrupt entry point and it will be the same stub with those first three steps deleted, because there the hardware really did do them.

Here is the shape of this assembly stub, which is often called a “trampoline”, since it bounces the process into the yield handler, handle_yield:

// void yield_entry(void)
// Called by a process as an ordinary function (through F_YIELD).
    .globl yield_entry
yield_entry:
    msr  DAIFSET, #2            // 1. mask IRQs: the kernel runs uninterruptibly
    msr  ELR_EL1, x30           // 2. resume address = our return address
    mov  x9, #SPSR_PROC         // 3. processor state to resume the process with
    msr  SPSR_EL1, x9           //    (uses x9 as a scratch register; see below)
    sub  sp, sp, #S_FRAME_SIZE  // 4. make room for the context on the stack
    stp  fp, lr, [sp]           // 5. save fp/lr now: `bl` is about to clobber lr
    bl   save_context           // 6. save everything else
    mov  x0, sp                 // 7. arg0 = pointer to the saved context
    bl   handle_yield           //    ...and into C, never to return
    b    .                      //    (should be unreachable)

This code will replace your no-op yield_entry placeholder from Part A.

To pull everything together, you’ll add a simple scheduling policy, round-robin scheduling, and set up the mechanism. While you can do this in a number of ways, we recommend using four pieces and putting them into kernel/scheduling.c (declared in kernel/scheduling.h):

• pick_next(), which implements the policy. Return the next RUNNABLE process in the table after current_process, wrapping around. If nothing is runnable, panic(): with no way to block and no idle process, that means something has gone wrong. (Your processes never terminate in this project, so this should never fire; a panic here will catch bugs elsewhere.)
• resume(struct proc* p), which puts process p on the CPU. Make it current_process, mark it RUNNING, and restore_context(p->context). This function never returns.
• scheduler(), which simply calls resume(pick_next()) and never returns. Keeping this separate from pick_next is what keeps your policy and your mechanism from getting tangled up. This will be helpful if you’re in CS 1690 and complete Quest 5.
• yield() (an internal kernel function of this name, distinct from yield in u_common.h), which marks current_process as RUNNABLE (it is not running any more, but it is still ready to run) and call scheduler(). This function also never returns.

Plus the entry point that ties them together:

• handle_yield(context_t* ctx), which is called from your yield_entry assembly code with a pointer to the just-saved context. Record that pointer in current_process->context, then call yield(). Like most of the other functions, this never returns because it switches to a different process.

Check your work

With two processes (hello as PID 0, counter as PID 1), the output is completely determined, and you should be able to predict it. hello prints, yields; counter prints, yields; hello resumes where it left off:

Process hello: before yield
Process counter: 0
Process hello: after yield
Process hello: before yield
Process counter: 1
Process hello: after yield
Process hello: before yield
Process counter: 2
...

Trace through your scheduler on paper and check that this is what you expect. If your output has the right lines in the wrong order, your scheduler works but your understanding of it is incorrect.

Then add primecheck back as PID 2 and run all three.

What you should see is that hello and counter each get one turn, and then everything stops except primecheck:

Process hello: before yield
Process counter: 0
Process primecheck: Found another 1000 primes; last one was 7919!
Process primecheck: Found another 1000 primes; last one was 17389!
Process primecheck: Found another 1000 primes; last one was 27449!
...forever...

The reason is that primecheck never calls yield(). It is not malicious, though: it is just a program doing a long computation (finding all primes), which is a completely reasonable thing for a program to do. (Of course, this sort of thing can be hard to distinguish by observation from a buggy or malicious program: e.g., Eve from CS 300 mining Bitcoin is also a “long computation”). But this long computation has completely crowded out the other two processes, and even your OS kernel no longer gets to run! Every other process is RUNNABLE, but never runs, and it will stay that way until the machine is switched off.

This is the flaw in cooperative concurrency, and no amount of cleverness in your scheduler can fix it: your scheduler is not running. You cannot schedule if you cannot get the CPU back. If you recall the Alice/Eve examples from CS 300, you’ll see a similarity here and might guess at the answer (timer interrupts). This is what the next quest is about.

Bonus Quests (Extra Credit)

Quest 4: Preemptive concurrency

Files: kernel/exceptions.S, kernel/exceptions.h, kernel/interrupts.c, kernel/interrupts.h, kernel/drivers/timer.c, kernel/drivers/timer.h, kernel/aarch64.h, kernel/kernel.c, kernel/printf.c.

Overview

We will now address the starvation problem with cooperative concurrency. To do so, you will make the CPU interrupt your processes on a schedule. This requires four new components:

1. An exception vector table, so that the CPU knows where to jump when anything exceptional happens, and a handler for synchronous exceptions including timer interrupts (which also gives you real error messages for kernel bugs).
2. A timer device driver, so that the hardware generates an interrupt at regular intervals.
3. Interrupt routing and dispatch, so that the timer’s interrupt actually reaches your CPU and your code figures out where it came from.
4. The connection to the scheduler: on a timer interrupt, preempt the running process.

Why are we doing this?

Preemption is the difference between an OS that depends on the goodwill of every program and an OS that is actually in charge. It is also the point at which you have to understand what the CPU does when it is interrupted, which is one of the genuinely essential pieces of knowledge in systems programming: it underlies system calls, page faults, device I/O, debuggers, profilers, and the reason your laptop doesn’t freeze when a program has a bug.

What you need to do: handling exceptions

In the first step, you will add support for your kernel to handle exceptions. This is a prerequisite for preemption, because the timer generates an interrupt, which is a kind of exception.

Part A: the exception vector table

.section .text                    // 1. put the table in the code segment
.globl exception_vector_table     // 2. make the exception vector table visible to C code
.balign 0x800                     // 3. align the table to a 2 KiB boundary, as hardware requires
exception_vector_table:           // 4. label that defines the actual table and its memory location
// Current EL, using SP_EL0 (unused in our OS)
    .balign 0x80                  // ensure 128-byte alignment for next entry
    b .                           // 0x000: synchronous
    .balign 0x80                  // ensure 128-byte alignment for next entry
    b .                           // 0x080: IRQ
    .balign 0x80                  // ensure 128-byte alignment for next entry
    b .                           // 0x100: FIQ
    .balign 0x80                  // ensure 128-byte alignment for next entry
    b .                           // 0x180: SError
// Current EL, using SP_ELx (x > 0)
// [... repeat as above for the other three cases ...]

In the next step, you will add support for timer interrupts. This requires understanding how the hardware timer device works, and how to handle the interrupt it generates.

What you need to do: taking timer interrupts

In order to handle timer interrupts, we need to first tell the hardware to generate them. This involves a device driver for the timer device, and some code to set up the interrupt controller to enable the interrupts and deliver them to your CPU core.

Part B: the timer driver

Part C: route and dispatch the interrupt

It’s not quite enough to have a timer that generates an interrupt: the interrupt has to be delivered to your CPU core, and your kernel has to figure out what happened and dispatch it. This is the final piece of the puzzle for preemption.

Interrupt delivery is handled by the interrupt controller, which is a hardware device responsible for routing and delivering interrupts to the CPU. Like many hardware devices, the interrupt controller is memory-mapped, so you can configure it via MMIO and reading/writing device registers.

You’re welcome to work out the details for yourself—they aren’t that complicated—but the interrupt controller is mostly plumbing in the context of this assignment, so we will give you the relevant code below if you want to use it. The ARM local peripherals documentation (see Appendix B) describes the relevant registers for the ARM CPU’s interrupt controller.

In particular, you will need:

• The ARM_LOCAL_PERIPHERALS_BASE address, which is 0x40000000. This is already defined for you in kernel/memlayout.h.
• The “Core 0 timers interrupt control” device register, and specifically the bit in it that enables the IRQ for the physical non-secure timer (the one CNTP_* controls).
• The “Core 0 interrupt source” register, which tells you which of core 0’s interrupt sources has triggered an interrupt.

Using these three memory-mapped locations, you should write a helper function to enable the interrupt controller and timer interrupts for core 0.

#define CORE0_TIMER_IRQ_CTRL (ARM_LOCAL_PERIPHERALS_BASE + 0x40)
#define CORE0_INTERRUPT_SOURCE (ARM_LOCAL_PERIPHERALS_BASE + 0x60)

void enable_interrupt_controller(void) {
    // Enable the ARM generic timer for core 0 by setting bit 1 of
    // the CORE0_TIMER_IRQ_CTRL register.
    mmio_write32(CORE0_TIMER_IRQ_CTRL, (0b1 << 1));
}

In addition to this, you need two more pieces:

1. A handler function that detects which interrupt occurred and calls the appropriate handler (in this case, the timer interrupt handler).
2. Code in your exception vector table that jumps to this handler when an interrupt occurs in EL1.

For the first, you’ll want to write a function with a signature handle_interrupt(context_t* trapframe), e.g., in kernel/interrupts.c. This function should read the interrupt source register to determine which interrupt occurred, and then dispatch to the appropriate handler. For the timer interrupt, it should call timer_interrupt(). If any other interrupt occurs, it should call panic() for now.

Part D: preempt

Everything is now in place, and connecting it is almost anticlimactic: a timer interrupt should cause the running process to be suspended and another process to run, which is precisely what yield() already does (except only if processes decide to do so voluntarily).

But there is one more thing to pay attention to that is easy to get wrong.

Recall step 4 of what the hardware does on an exception: it masks (disables) IRQs. That is essential—it keeps your handler from being interrupted again—but it means that after your first timer interrupt, interrupts are disabled. If nothing ever re-enables them, exactly one process gets preempted once and no timer interrupt ever happens again.

So: who unmasks interrupts? Follow the control flow. Your timer interrupt handler never “returns” in the ordinary sense; it ends by calling restore_context, whose last instruction is eret, which restores PSTATE from the saved SPSR_EL1 value in your saved context. So, the state a process resumes with is whatever is in its saved SPSR_EL1—and that comes from SPSR_PROC, the constant you used in Quest 2 with all interrupts masked.

Change that constant to leave interrupts unmasked (i.e., enabled), and every eret back into a process will re-enable interrupts as part of resuming it. Nothing else is needed. This gives rise to a rule about interrupt discipline in our OS at this point that is worth stating explicitly:

Part E: make printf atomic

Run your three processes and look carefully at the output. Sooner or later you will see something like this:

Process counter: 1Process primecheck: Found another 1000 primes; last one was 7919!
2

A timer interrupt arrived while the counter process was in the middle of printing a line. Its printf—which, remember, is your kernel’s printf, running on counter process’s stack—was suspended halfway through pushing characters into the UART, another process ran and printed its own line, and then counter resumed and finished.

The UART is a shared resource, and you now have preemption, which means two processes can be in the middle of using it at once. The fix is to make the part of printf that touches the UART a critical section: a region of code that must not be interrupted. You have exactly the tool for that from Part C.

Check your work

With all three processes running and preemption on, you should see hello and counter making progress via yield() and primecheck getting a share of the CPU without ever yielding:

Process hello: before yield
Process counter: 0
Process primecheck: Found another 1000 primes; last one was 7919!
Process hello: after yield
Process hello: before yield
Process counter: 1
Process primecheck: Found another 1000 primes; last one was 17389!
Process hello: after yield
...

The exact interleaving depends on your quantum and on how long primecheck takes between prints, so your output will not match ours line for line. What must be true is that (a) all three processes make progress forever, (b) primecheck is being interrupted, since it never yields, and (c) no line of output is spliced into the middle of another.

Some things worth checking deliberately:

1. Preemption really is happening, repeatedly. Add a counter to handle_timer_interrupt and print it every n^th interrupt. It should climb forever.
2. The quantum is what you think it is. Time 100 interrupts against a stopwatch, or read CNTPCT_EL0 in the handler and print the difference between consecutive interrupts.
3. Try a much shorter quantum (say 1 ms) and a much longer one (say 1 s), and watch what happens to the feel of the output. Does it match what you expect?

Congratulations—you have built a preemptively multitasking operating system. Three programs, none of which knows the others exist, sharing one CPU, with your kernel in charge 🎉! If you are in CS 1670, that completes the project (modulo hand-in). If you are in CS 1690/2670, there is still one quest to go.

Bonus Quests (Extra Credit)

Quest 5: A better scheduler (CS 1690/2670)

Files: kernel/scheduling.c, kernel/proc.h, plus a write-up.

Overview

Round-robin scheduling is very simple. In this quest you will research one scheduling algorithm that is more sophisticated, implement it, and argue for it.

Why are we doing this?

“Which process should run next?” is a design question, not a technical one, and the answer depends entirely on what you are trying to achieve. Round-robin’s crude equality is the right answer for some workloads and badly wrong for others. One way to really see that is to build an alternative and watch it behave differently on the same programs.

This is also a taste of what OS research and kernel engineering actually feel like: reading about a design, deciding what it is really optimizing for, mapping it onto the code you have, and then defending the result.

Note that “fairness” is not the only thing one might want, and different schedulers optimize for different quantities:

These conflict. Short quanta improve response time but waste more CPU on switching overhead. Always running the shortest job first minimizes average turnaround time but can starve long jobs forever. Prioritizing interactive programs makes interactive desktop computing feel responsive, but makes a background compilation job run slowly. There is no optimal scheduler, only schedulers that are good for particular goals—which is why real kernels have several, and why Linux’s default one has been replaced twice in the last twenty years.

Even your quantum length is a trade-off you will feel directly. If a context switch costs (say) 2 microseconds and your quantum is 100 milliseconds, you spend 0.002% of the CPU on switching. Shrink the quantum to 10 microseconds and you spend 20% of the CPU shuffling registers around.

What you need to do

Handing in & grading

You will submit your work via git, using our grading server, exactly as for Project 1.

Before you submit, make sure that:

• make clean && make qemu builds and runs without errors from a fresh checkout.
• Your code is formatted (make format) and free of debugging spew you did not intend to leave in—in particular, remove the test svc #0 from Quest 4 Part A and any tracing you added to your switch path.
• CS 1690/2670 students: your docs/SCHEDULER.md file describing your implementation for Quest 5 is in the repository.

Submitting your code (and checking on the grading server)

1. Log into the grading server with the password you received.
2. Connect your repository under the “Project 2: Processes” category, if you have not already, and click it to fetch your repository from GitHub.
3. Check your code works: use the buttons below the commit list to test your code in our grading environment.
4. Set your grading commit with the “Grade this commit” button. You can reassign it at any time before the 72 late hour cutoff.
5. Click the “Run submission checks” button to run a set of tests that tell you if there are any known problems with your handin. Passing this check doesn’t guarantee that everything works or is correct, but catches some common issues early.
6. After submitting your work, please sign up for a Whiteboard discussion.

Congratulations, you have made your OS multitask! 🎉

Grading breakdown

Your grade is based on:

• Functionality: We will run your code on the grading server and check that it works as expected (i.e., runs the three programs concurrently). This is worth 50% of your grade and impacts the “Projects” part of the course grade.
• Whiteboard Discussion: You will meet with a course staff member in a small group to discuss the concepts in this project for 45 minutes. The discussion is worth 50% of your grade and impacts the “Whiteboard Discussions” part of the course grade.
• If you are in CS 1690/2670 and complete Quest 5, your write-up of that quest will contribute 1/5 of your overall grade (i.e., the contributions of functionality and whiteboard discussion will be scaled to 40% of your grade each, and the write-up will be another 20%).

We will grade all components according to our honest grading scale.