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)

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

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 process's stack
• A pointer to its 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.

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) or instruction pointer 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. These functions are usually written in assembly because we need to directly modify registers.

There are two obvious places where we can store the context:

1. Inside the process descriptor. This means that the stack pointer needs to be saved and restored explicitly. It does not generalize well to interrupts.
2. On the process's own stack. Just before saving, subtract the size of a context from the stack pointer to make room, and then write the registers into that space. The process descriptor stores only a pointer to it.

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. In cooperative concurrency, the process gives it up voluntarily by calling into the kernel directly (via yield()). yield() should mimic the behavior of the hardware during an interrupt.

The problem with cooperative concurrency is that it depends on the process being polite. To get 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)

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 achive 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 struction. The interrupt handler will wake up every process blocked on the same address by marking them as RUNNABLE for the scheduler.

A framebuffer is a region of memory that the hardware continuously reads and then renders on the display. 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.

Appendix

This appendix contains specific details about the projects in CSCI 1670 and about ARM64 architecture.

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 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:

• The processor state is resotred from SPSR_ELX
• The program counter is set from register ELR_ELX
• The stack pointer 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.

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.