Operating Systems Notes

Booting

Stages of Booting

Booting proceeds in stages:

• Stage 0: CPU starts executing the ROM
• Stage 1: ROM loads the bootloader from persistent storage
• Stage 2: Bootloader loads the kernel ("image") into a fixed physical address

In stage 0, there is a fixed circuit that tells the CPU to jump to the first instruction of read-only memory (ROM). ROM can be both directly executed and mapped into RAM.

The stage 1 bootloader in ROM enables necessary devices (harddisk, SSD, RAM) and loads the stage 2 bootloader from persistent storage into RAM. This bootloader is generally fixed-size and OS-independent.

The stage 2 bootloader is usually a program that is stored in a fixed location on the storage device. (This helps the stage 1 bootloader find it.) The stage 2 bootloader is usually configurable by the programmer. It is generally written in assembly because C assumes that there is a stack, which does not exist yet.

The stage 2 bootloader is responsible for loading the kernel into a fixed address in RAM. It then jumps to the first instruction of the kernel code. The OS kernel sets up its own stack and memory segments.

I/O Devices

Device Drivers

An I/O device will expose some kind of interface that allows us to control the device. These interfaces are commonly called device registers. If we change the bits in a device register, this will physically pull the pin HIGH or LOW and change the state of the device. For example, if you want to send a character to the console, you can write the character to the device's data register.

Device drivers are pieces of software that understands how to interact with the device and its device registers. Device drivers typically run inside of the kernel because interacting with devices is a privileged operation.

PMIO and MMIO

Question: Now that the devices expose device drivers, how can the CPU actually modify these device drivers?

There are two primary means of communication:

1. In port-mapped I/O (PMIO), there are explicit I/O instructions, such as in <register>, <port> and out <register>, <port>
2. In memory-mapped I/O (MMIO), the hardware makes device registers available as if they were memory locations. When the OS issues a read or write to the address, the hardware routes it to the device.

With memory-mapped I/O, the physical address space now contains more than just RAM. On bare metal, the physical address space comprises of:

1. RAM regions used by running programs
2. Reserved regions wired directly to hardware devices (like console)¹

When the CPU attempts to access a memory address, there is a selector that either routes it to the connected device or to RAM.

Program Loaders

Programs are stored in an executable format on persistent storage. This executable format may contain:

• Machine code
• Global variables
• Entry point
• Relocation information

Different operating systems have different executable formats:

• Unix/Linux: ELF
• MacOS: Mach-O
• Windows: PE (Portable Executable)

To run a process, the OS needs to read the execuable from disk and run the program loader. The program loader's job is to parse the executable format and load the relevant segments into the memory region chosen for the sepcific process.

The loader must also ensure that all pointers contained in the executable point to the right places in memory. This may involve relocating sybols (functions and variables) whose memory addresses aren't known at compile time, but only at load time.

In early operating systems, this loading process was done eagerly, all at once before running the program. Modern operating systems perform this process lazily, loading pieces of code or data only as they are needed during program execution.

For more information about the ELF format, see CSCI 1655 notes.

Processes

Multiprogramming

Instead of running each process one by one (batch programming), we may want to run more than 1 program on the computer concurrently (multiprogramming).

Question: Why do we want multiprogramming?

Compared to the CPU, hardware devices are very slow. If we didn't have concurrency, the CPU might be idle for long periods of time while the program is waiting for I/O. Running several processes concurrently lets the OS multiplex a fast CPU across slow devices.

Question: What do we need for multiprogramming?

First, we need to be able to load multiple processes into memory. We also need a way to keep track of each of these processes through some kind of data structures. Finally, we also need a way to switch the CPU between different processes.

The Process Table

A process descriptor, also known as a process control block (PCB), is a data structure that stores information about a single process. It contains:

• The state of the process (UNUSED, USED, RUNNABLE, RUNNING)
• The process ID (PID), so that programs can refer to a process without having a pointer into kernel memory
• A pointer to the stack²
• A pointer to the context³

A process table is just an array of process descriptors. The kernel maintains a pointer to the descriptor of the current process running on the CPU.

The idle process is always runnable and yields immediately. It is necessary to run the idle process when there is nothing else to schedule.

Context-Switching

From the CPU's point of view, a running process is just defined by:

1. The general-purpose registers (x0-x30) which hold the program's live values, base pointer (in x29), and return address (in x30)
2. The stack pointer (sp) which points to the top of the stack
3. The program counter (pc) which contains the address of the next instruction to run
4. The processor state, which includes condition flags (N/Z/C/V) that a following conditional branch depends on, the current exception level, which stack pointer is in use, and which interrupts are masked

To change the process that the CPU is working on, we must save the running process's context and load another process's context. This is called a context switch.

The mechanism for a context switch usually involves a function to save_context and restore_context.

• save_context stores the context of the process on the process's stack, allowing the kernel to switch to a different process⁴
• restore_context finds the saved context on the process's stack (using the metadata in the process descriptor) and restores the registers

Concurrency

In order to do a context switch, the OS needs the ability to stop the CPU from running some process. However, the OS is itself a process that needs to run on the CPU.

There are two ways the OS can get the CPU back from a running process: (1) cooperative concurrency and (2) preemptive concurrency.

In cooperative concurrency⁵, the process gives it up voluntarily by calling into the kernel directly via yield(). yield should:

1. Save the process's context
2. Record where the context is in the process descriptor
3. Change the process's state
4. Decide which process to run next
5. Resume that process by restoring its context

The problem with cooperative concurrency is that it depends on the process being polite. To allow the kernel to forcibly take back the CPU, we need preemptive concurrency. The kernel takes the CPU back by arranging a hardware timer to interrupt the CPU periodically. When the timer fires, the CPU stops executing and jumps into the kernel, where it can schedule another process.

There are several components that are necessary for preemptive concurrency:

1. A timer device needs to periodically create interrupts
2. An interrupt controller needs to deliver the interrupt to the CPU
3. Once the CPU is interrupted, it should be configured by the hardware manufacturer to jump straight to the trap table
4. The trap table needs to be configured to jump to the asynchronous interrupt handler
5. The asynchronous interrupt handler needs to detect which interrupt occurred and call the appropriate handler (in this case, the timer interrupt handler)

Scheduling

The kernel needs to figure out which task to run next. The scheduler should be:

1. Fair - no task should starve
2. Fast - picking a task should be cheap
3. Responsive - interactive tasks need low latency
4. Scalable - work on hundreds of CPUs

Display

Preemption also allows the OS to respond to devices quickly. When a network packet arrives or when there is a disk read, the data is stored in a limited memory region.The OS needs to respond before that memory region is overwritten by other data.

To achieve this, peripheral devices make an interrupt request. This triggers the interrupt handler, which quickly takes the bytes out of the hardware FIO and puts them into a buffer in memory. Then it terminates and gives control back to the running process. Later, a process consumes the bytes in the buffer.

While processes are waiting for a device, they are in a BLOCKED state. Usually, there is a wait channel that allows the blocked process to be associated with some event, such as the address to some kernel data structure. The interrupt handler will wake up every process blocked on the same address by marking them as RUNNABLE for the scheduler.

Screen and Framebuffer

A screen is composed of pixels. Each pixel is composed of multiple bits which describe the alpha, red, green, and blue channels.

A framebuffer is a region of memory⁶ that the hardware continuously reads and then renders on the display.

User programs can read the FB_INFO_BASE to find the address of the framebuffer, and then they can write directly into this framebuffer to render things on the screen.

While the screen can be shared across multiple processes, the input keyboard has to go to some process. Most windowing systems handle this by setting a foreground process or window.

The compositor⁷ is responsible for copying the contents of the process' canvases into the framebuffer. This allows us to implement a tiling window manager and a floating tiling manager.

Tearing

If the compositor (CPU)⁸ and the GPU both access the framebuffer at the same time, we can get a race condition. This can result in screen glitches called tearing.

Double-Buffering

A race condition is defined as when two entities access the same memory location at the same time, and at least one operation is a write. To avoid a race condition, we can instead read and write from different framebuffers using a technique called double buffering.⁹

Damage-Tracking

Furthermore, we need to make sure that the compositor runs fast enough to update its framebuffer 30-60x a second. For example, we may want to do damage-tracking to check which process' canvases actually changed since our last read.¹⁰

Wait for Vsync

Recall that the process is writing to its canvas and the compositor is copying those contents to the framebuffer. It is possible for the process to be interrupted before it is finished writing to its canvas.

We thus need to make sure that the process itself and the compositor are synchronized. One solution to this is "wait for vertical sync," which tells the compositor to wait for the process to finish writing.¹¹

System Calls

Calling Convention

The Application Binary Interface (ABI) specifies the system calls exposed by the kernel for the userspace program.

Userspace programs can make a system call by invoking svc with the right system call number. Arguments should be passed in registers x0-x5 in order. A syscall can have at most six arguments. The return value will be returned in register x0.

On a system call, the hardware will:

1. Save the current pc and PSTATE
2. Set pc to a fixed location in the exception vector table
3. Switch to the kernel stack
4. Mask interrupts

Process Descriptors

In Unix, everything acts like a file with a file descriptor. To implement syscalls like read, write, fork and exec, it is necessary to also implement file descriptors.

Shell

The shell uses fork and execv to run multiple programs (and pipe them). The main idea is to fork the shell program, modify FD 0 and 1 so that the new program reads and writes to the right FDs, and then execv the program.

Virtual Memory

We want to prevent one process from reading or writing into the memory of another process.

Base and Bounds

One early memory protection mechanism was called base and bounds. In base and bounds, there is a BASE and BOUNDS register which holds the range of memory that the process can access. On each memory access, the CPU checks whether the memory falls within [BASE, BASE + BOUNDS].

One issue with this scheme is that it requires that the process is contiguous in memory. To grow a process, we may need to copy the entire process space to a new place in memory.

Segmentation

As we have more processes, the physical memory may quickly grow small holes of free space, leading to external fragmentation. One solution to this problem is to give each memory segment in a process (stack, heap, code and data) a separate BASE and BOUNDS register. This idea is called segmentation.¹²

Appendix

The appendix contains specific details about Raspberry Pi architecture, ARM64 architecture, and CSCI 1670 projects.

Raspberry Pi Architecture

The diagram below shows a simplified view of the Raspberry Pi architecture. Notice that ROM and UART are both on the system on chip (SoC).

Raspberry Pi Memory Layout

On the Raspberry Pi, the kernel must be at the fixed address 0x80000. The kernel stack can be placed at an address of your choosing.

ARM64 Architecture

ARM64 (also sometimes called "AArch64") is a computer architecture. Practically all mobile device and some laptops (such as Apple Silicon Macbooks) use ARM64 over x86-64 because its processors have significantly lower power consumption.

Compared to x86, ARM64 has many more registers used for specific tasks.

Additionally, ARM64 instructions are more specific than those in x86-65:

• ARM64 has special system registers which control the CPU. Only special mrs (read) and msr (write) instructions can read and write to system registers.
• x86-64 uses mov instructions to move data to and from registers. ARM64 requires you to use explicit lrd (load) and str (store) instructions to load and store from memory.
• x86-64 instructions can vary in length, while each ARM64 instruction is exactly 4 bytes.

ARM64 Exception Levels

ARM64 has several exception levels which control hardware access permissions.

• EL3 ("secure monitor")
• EL2 ("hypervisor")
• EL1 ("kernel")
• EL0 ("userspace")

The ARM architecture allows privileged exception levels (EL1, EL2, EL3) to use either their own dedicated stack pointer or the stack pointer of EL0 (user space). This is designated with the ELX_h (handler) or ELX_t (thread) suffixes:

• The handler suffix means that the processor should use the privileged SP_ELX. The OS typically uses EL1_h to execute code with stack pointer SP_EL1.
• The thread suffix means that the processor should use SP_EL0 (unprivileged). This is used in early boot or trap handlers.

The only way to move from a lower EL to a higher EL is to trigger a hardware exception, such as via supervisor calls (SVC), hypervisor calls (HVC), or secure monitor calls (SMC).

The only way to move from a higher EL to a lower EL is by running the instruction eret (exception return). eret is necessary for context-switching between the process and the kernel.

In an eret instruction, the following things happen atomically¹³:

• PSTATE is restored from SPSR_ELX
• pc is set from register ELR_ELX
• sp is set to the value in SP_ELX

ARM64 System Registers

In ARM64, many system registers have distinct instances per exception level. ELX is a placeholder for EL1, EL2, and EL3.

ARM64 Exception Handling

ARM64 has 4 different exception types:

1. Synchronous exception: caused by the instruction the CPU is executing (page fault, illegal instructinos, system calls)
2. Interrupt requests (IRQs): caused by something outside of the CPU
3. Fast interrupts (FIQs): high-priority interrupts
4. System errors (SErrors): casued by the hardware itself

When an interrupt occurs, the CPU will:

1. Finish the current instruction
2. Save pc into ELR_EL1¹⁵
3. Save PSTATE into SPSR_EL1¹⁶
4. Disable interrupts by setting DAIF in PSTATE
5. Switch to EL1 and select SP_EL1 as the stack pointer
6. Jump to VBAR_EL1 plus the offset for the exception type and origin

Note that the hardware does not save any general-purpose registers. For context switches, the handler inside of the exception vector table should save the context before using any of those registers. This is done with save_context.

ARM64 Context Switches

To implement yield(), we want to mimic everything the hardware does for us during an interrupt.

The yield_entry should:

1. Mask IRQs
2. Store the link register in ELR_ELX¹⁷
3. Store PSTATE in SPSR_ELX¹⁸
4. Make room for the context on the stack
5. Store fp and lr because bl will clobber lr
6. Save everything else with save_context
7. Move the return value from save_context, which is a pointer to the saved context, to sp
8. bl to handle_yield

The handle_yield function should then:

1. Record where the context is in the process descriptor
2. Change the process's state
3. Decide which process to run next by calling the scheduler
4. Resume that process by restoring its context¹⁹

yield_entry:
     msr DAIFSET, #2
     msr ELR_EL1, x30 
     mov x9, #SPSR_PROC
     msr SPSR_EL1, x9
     sub sp, sp, 272
     stp fp, lr, [sp]
     bl save_context
     mov x0, sp
     bl handle_yield
     b . // unreachable

The save_context code is shared by both cooperative and preemptive concurrency. It assumes that the caller has already:

• Subtracted from sp, making room for context
• Saved fp and lr
• Set ELR_EL1 and SPSR_EL1

save_context:
     // Store registers x0-x28 inside of this space
     stp x0, x1, [sp, #16]
     stp x2, x3, [sp, #32]
     stp x4, x5, [sp, #48]
     stp x6, x7, [sp, #64]
     stp x8, x9, [sp, #80]
     stp x10, x11, [sp, #96]
     stp x12, x13, [sp, #112]
     stp x14, x15, [sp, #128]
     stp x16, x17, [sp, #144]
     stp x18, x19, [sp, #160]
     stp x20, x21, [sp, #176]
     stp x22, x23, [sp, #192]
     stp x24, x25, [sp, #208]
     stp x26, x27, [sp, #224]

     mrs x0, SP_EL0
     mrs x1, ELR_EL1
     mrs x2, SPSR_EL1

     stp x28, x0, [sp, #240]
     stp x1, x2, [sp, #256]
     ret

Raspberry Pi Display Hardware

The Raspberry Pi is really a Broadcom VideoCore graphics processor that happens to have 4 ARM cores attached to it. This means that the display hardware belongs to the GPU, not to the CPU.

The CPU can request access to the display by sending a message through the mailbox. The CPU writes the address of a request buffer into one register; the GPU reads it, acts on it, writes results back into the buffer, and posts a reply.

[^]: The Mythical Man Month was written by Fred Books, who worked on the Multics project.

1. Note that this device MMIO region is fixed by the hardware, not by the operating system.

2. It's possible to store either the lowest address (base) or the highest address of the stack. If we store the base, we know where to free the memory later, but we'll have to initialize sp as stack_ptr + STACK_SIZE.

3. The context is also stored on the stack.

4. Note that save_context may differ depending on whether we are saving the context after a yield() syscall or handling an interrupt. If we are handling a yield(), we need to mimic everything that the hardware does for us during an interrupt.

5. For a concrete example of cooperative concurrency, see the section on ARM 64 Context Switches.

6. On the Raspberry Pi, this region of memory is given to the CPU by the GPU.

7. (missing definition)

8. In most modern computers, compositing can also happen in the GPU. But here we describe it as part of the operating system.

9. A mutex on the framebuffer is also possible, but that would be too slow.

10. It is possible to do damage-tracking on different levels of granularity, such as per-pixel, per-row, or per-canvas. Modern systems track damage as rectangles.

11. Double buffering again is also possible.

12. The term "segmentation fault" comes from trying to access a memory address that does not fall inside the process's segment.

13. There are several reasons why eret needs to be atomic. If we set the pc first, then the CPU will immediately start executing the process's code, and we'll never set PSTATE. If we set PSTATE first, then kernel code will execute with the process's PSTATE (with less privilege or with interrupts enabled).

14. Note that the bit positions in the daif register view, in the daifset selection, and in spsr_elx are all different.

15. Jumping into the vector table will change pc, which is why the hardware needs to save it first.

16. Disabling interrupts and switching exception levels will change PSTATE, which is why the hardware needs to save it first.

17. eret will restore pc with ELR_ELX. Thus, we should store the link register, which contains the return address of the callee of yield, in ELR_ELX.

18. Because we know what the processor state a process should resume it, it can just set it to a default #SPSR_PROC. Also, we can use x9 as a scratch register because under ARM64 calling convention, x9 to x15 are temporary registers that should be saved by the caller during a function call.

19. Note that handle_yield never returns, since it switches to running the next process. However, its stack frame is initialized on the yielding process's stack frame, after the saved context. This is okay because when the yielding process is scheduled again, it will pop the saved_context, resume at the original top of the stack, and clobber the old stack frame from handle_yield.