Blog OS: Writing an Operating System in Rust

In Rust's asynchronous model, futures do not progress unless they are polled. This necessitates two key components:

Executors

An Executor is a global component responsible for polling all active futures in the system until they complete. Instead of manually polling futures in a loop, you can use an executor to spawn futures as independent tasks. When a future returns Poll::Pending, the executor can switch to another future, allowing multiple asynchronous operations to progress concurrently.

Wakers

To avoid the inefficiency of constantly re-polling futures that are not ready, executors use the Waker API.

• During each poll call, a Waker is passed to the future inside a Context object.
• The Waker is created by the executor.
• An asynchronous task (like a disk driver) can use this Waker to signal the executor when the task is ready to make progress again.
• The executor will not call poll on a future again until it receives a notification via the Waker.

CPU exceptions occur when the processor encounters an error during instruction execution, such as division by zero or invalid memory access. When an exception occurs, the processor stops current execution and immediately calls a specific exception handler function defined in the Interrupt Descriptor Table (IDT).

Common x86 exceptions include:

• Page Fault: Occurs during illegal memory access (e.g., reading from an unmapped page or writing to a read-only page).
• Invalid Opcode: Occurs when the current instruction is invalid (e.g., using unsupported SSE instructions on an older CPU).
• General Protection Fault: A broad category of access violations, such as attempting to execute privileged instructions in user mode.
• Double Fault: Occurs if a second exception happens while the processor is attempting to call the handler for the first exception, or if no handler is registered.
• Triple Fault: Occurs if an exception happens while attempting to call the Double Fault handler. Most processors respond to a triple fault by resetting the system.

CPU exceptions occur when an instruction encounters an error, such as accessing invalid memory or dividing by zero. When an exception occurs, the CPU interrupts its current task and immediately calls a specific handler function based on the exception type.

Key exception types include:

• Page Fault: Occurs during illegal memory accesses (e.g., reading unmapped memory or writing to read-only memory).
• Invalid Opcode: Occurs when the current instruction is invalid or unsupported by the CPU.
• General Protection Fault: A broad category for access violations, such as executing privileged instructions in user mode.
• Double Fault: Occurs if a second exception happens while the CPU is attempting to call the handler for the first exception.
• Triple Fault: A fatal error occurring if an exception happens while handling a Double Fault. This typically causes the processor to reset the system.

When designing or choosing an allocator, consider these two common variations of the fixed-size block approach:

Slab Allocator

• Concept: Uses block sizes that correspond directly to specific kernel types.
• Benefit: Eliminates memory waste for those types as they fit perfectly into blocks. It can also be used to implement an object pool pattern.
• Usage: Often combined with other allocators to reduce waste.

Buddy Allocator

• Concept: Uses a binary tree data structure with block sizes that are powers of two.
• Mechanism: When a block is needed, a larger block is split into two 'buddies'. When a block is freed, the allocator checks if its buddy is also free; if so, they are merged back into a larger block.
• Benefit: Reduces external fragmentation by allowing small freed blocks to be recombined for larger allocations.
• Trade-off: Can lead to significant internal fragmentation because it only supports power-of-two sizes.

Segmentation was originally designed to increase addressable memory. In x86, it uses segment registers to provide a displacement that is added to a memory address.

Key Terms

• Segment Registers: Specific registers used for different types of access: CS (code), SS (stack), DS (data), ES (extra), and FS/GS (general purpose).
• Protected Mode: A mode where segment descriptors contain an index to a Descriptor Table (Global or Local), which includes the segment's base address, size, and access permissions.
• Virtual Memory: An abstraction that translates virtual addresses (before translation) into physical addresses (after translation).

Limitations: External Fragmentation

Segmentation suffers from external fragmentation. Because it requires large, contiguous blocks of physical memory, the system may have enough total free memory to run a program, but if that memory is split into small, non-contiguous gaps, the program cannot be loaded without a costly defragmentation process (moving memory contents to create contiguous space).

An exception is a signal from the CPU that the current instruction encountered an error. When an exception occurs, the CPU interrupts its current work and jumps to a specific handler function defined in the Interrupt Descriptor Table (IDT).

Common exception types include:

• Invalid Opcode: Occurs when the CPU encounters an instruction it doesn't recognize or isn't enabled (e.g., using SSE instructions without SSE enabled).
• Page Fault: Occurs during illegal memory accesses, such as reading from an unmapped page or writing to a read-only page.
• Double Fault: Occurs if a second exception happens while the CPU is attempting to call the handler for the first exception. This also happens if no handler is registered for an exception.
• Triple Fault: A fatal error occurring if an exception happens while trying to call the double fault handler. This typically causes the CPU to reset and reboot the system.

Multitasking allows multiple tasks to appear as if they are running simultaneously by switching execution between them. There are two primary models:

Non-cooperative Multitasking

• Mechanism: The OS controls task switching by using hardware interrupts (e.g., timer interrupts or I/O interrupts). When an interrupt occurs, the CPU jumps to an interrupt handler, allowing the OS to regain control and switch tasks.
• State Management: Requires a context switch. The OS must save the entire state of the task (CPU registers, program counter, stack pointer) to a dedicated stack for that task (often called a thread).
• Pros/Cons: Provides guaranteed CPU fairness and control over untrusted user code, but has higher memory overhead because each task requires its own stack.

Cooperative Multitasking

• Mechanism: Tasks voluntarily relinquish control of the CPU, typically via a yield operation. This is common in language-level implementations like coroutines and async/await.
• State Management: Instead of saving the entire CPU state, tasks only save the specific state needed to resume (e.g., local variables). In Rust, async/await transforms tasks into state machines where necessary variables are stored in an automatically generated struct.
• Pros/Cons: Highly efficient and allows many tasks to share a single call stack, significantly reducing memory consumption compared to threads.