Systems Programming: Memory, I/O, and Concurrency
Virtual Memory and Memory Management
Virtual Memory (VM): The virtual address space is divided into fixed-size pages (standard 4KB); physical memory serves as a cache for these pages. A page table (which is per process) maps virtual pages to physical pages or marks them as invalid/unmapped.
Address Translation and Page Faults
Address Translation: The Virtual Address (VA) is composed of [VPN | VPO]. The Memory Management Unit (MMU) looks up the Virtual Page Number (VPN) in the page table to get a Page Table Entry (PTE). If valid, it resolves to the Physical Page Number (PPN), resulting in the Physical Address [PPN | VPO].
Page Fault: Occurs when a PTE valid bit is 0. This triggers the OS fault handler, which picks a victim physical page (evicting or writing if dirty), loads the needed page, updates the PTE, and restarts the instruction.
Translation Lookaside Buffer (TLB): A small, fast, fully associative cache inside the MMU that holds VPN to PPN mappings. It avoids page walks, though a TLB miss still requires a page walk.
Multi-Level Page Tables and Protection
Multi-level Page Tables: Instead of one large table (which is impossible even for 64-bit systems), a hierarchy is used. Lower-level pages only get allocated when in use, allowing for large chunks of virtual memory to remain unmapped.
VM as Protection: VM simplifies linking and loading because processes use the same virtual addresses regardless of physical location (e.g., code starts at the same address). It simplifies sharing by mapping the same physical page to multiple different virtual addresses. Dynamic malloc allows the heap to request contiguous virtual pages without needing contiguous physical memory. It provides protection because each page can hold protection bits (e.g., kernel bits for kernel pages).
Dynamic Memory Allocation
Dynamic Memory Allocators: These manage the heap of the Virtual Address Space (VAS), which grows with sbrk or mmap for large allocations. The goal is to maximize throughput and minimize memory utilization/fragmentation.
- Implicit Allocators: Reclaiming is managed (e.g., Java).
- Explicit Allocators: Freeing is managed by the program (e.g., C).
Tracking Blocks:
- Implicit Free List: Walks free/allocated blocks using the block size; requires walking the entire heap.
- Explicit Free List: Free blocks store pointers; traverse pointers to find free blocks.
- Segregated Free List: Free blocks are stored in multiple lists according to size.
Placement Policies: First fit, next fit, and best fit (listed in order of speed; reverse order for memory utilization). Splitting occurs when allocating a block; the block is split if the remainder is large enough for the minimum block size. Coalescing merges adjacent free blocks to reduce fragmentation (immediate vs. deferred). Boundary tags (footers duplicating headers) allow for backward coalescing.
Fragmentation: Internal fragmentation occurs when an allocated block is larger than requested. External fragmentation occurs when total memory is sufficient but not contiguous.
Garbage Collection and Common C Bugs
Garbage Collection (GC): Used by implicit allocators (e.g., mark and sweep). It treats registers and the stack as roots, traverses all reachable objects, and frees anything unmarked. GC in C must be conservative because it cannot always distinguish a pointer from a bit pattern, which may retain garbage.
Common C Bugs: Dereferencing bad or NULL pointers, reading uninitialized memory (do not assume a default zero heap), buffer overflows (off-by-one or fully unbound like strcpy), using memory after it has been freed, memory leaks, double frees, and failing to dereference a pointer.
System Level I/O and File Descriptors
File Descriptors: Small, non-negative integers that index into the process’s descriptor table. Standard values are 0 (stdin), 1 (stdout), and 2 (stderr). Every open file, socket, or pipe has one.
Kernel Data Structures
- Descriptor Table: Per-process array of pointers into the open file table.
- Open File Table: System-wide table; one entry per open instance. It contains the current file position, reference count, and a pointer to the v-node table.
- V-node Table: System-wide table; one entry per distinct file on disk. It contains file type, size, and pointers to data blocks.
Two separate open() calls on the same file get separate entries in the open file table. fork() duplicates the descriptor table, but points to the same file table entry, sharing the file position. dup2(oldfd, newfd) makes the newfd entry point to the same open file table entry as oldfd, commonly used to redirect stdout.
Short Counts and Buffered I/O
Short Counts: read and write can transfer fewer bytes than requested, which is not an error. This happens on EOF, when reading from slow devices/sockets, or when interrupted by a signal. Code should loop until n bytes are transferred or EOF/error occurs; the RIO package handles this.
Buffered vs. Unbuffered I/O: The RIO package buffers I/O, which is good for binary data. Do not mix buffered and unbuffered calls on the same file descriptor.
Standard I/O on Sockets: Sockets are full-duplex byte streams with no natural EOF. Standard I/O buffer assumptions make it unsafe for sockets; use RIO instead. Metadata can be retrieved via stat/fstat to check file types (e.g., S_ISREG, S_ISDIR), size, and permissions.
Network Programming and Sockets
Client-Server Model: The client sends a request, and the server receives, processes, and responds. Both are processes, not machines. One server can handle many clients via queues or concurrency.
IP Addressing: IPv4 uses 32-bit dot notation. Network byte order is always Big Endian. Use htons/htonl (host to network) and ntohs/ntohl (network to host). Use getaddrinfo for protocol-independent domain name resolution.
Socket Interface and Flow
Sockets: An endpoint for communication identified by an (IP address, port) pair. A socket descriptor is a special file descriptor; read, write, and close work, but you cannot seek.
- Server Flow:
getaddrinfo→socket→bind(associate with local port) →listen(mark to accept requests) →accept(block until a client requests, returns a new descriptor for communication). - Client Flow:
getaddrinfo→socket→connect.
HTTP Basics
An HTTP request consists of a request line (METHOD URI VERSION, e.g., GET /index.html HTTP/1.1), headers, and an optional body, terminated by a blank CRLF line. A response consists of a status line (VERSION CODE PHRASE, e.g., HTTP/1.1 200 OK), headers, and a body. Static content is read directly from disk.
Concurrent Programming Strategies
Three Main Strategies
- Process-based (fork): Each worker is an isolated process. This is the safest approach but has the highest overhead for creation and context switching. Sharing data requires IPC (pipes/sockets).
- Thread-based: Threads exist within one process. They have lower overhead and easy data sharing, but explicit synchronization is required.
- I/O Multiplexing (select/poll): A single process/thread monitors descriptors. It avoids threading and provides control but lacks real parallelism and uses a complex event-style loop.
Threads and Lifecycle
Threads: Share the same code, heap, and global/static data, but have their own stack, thread ID, registers, PC, and condition codes. Stacks are only logically private; threads can potentially corrupt each other’s stacks. A thread ends upon returning, calling pthread_exit, being canceled, or process termination.
Joinable vs. Detached: Joinable thread resources are not reclaimed until pthread_join is called. Detached thread resources are reclaimed automatically upon termination and cannot be joined.
Synchronization and Semaphores
Race Condition: The outcome depends on the specific order of events between threads. This is fixed with mutexes or semaphores. Progress Graphs help reason about correctness by modeling execution on an n-dimensional grid where unsafe regions are protected by P and V operations.
Semaphores: Non-negative integers with atomic P (wait) and V (post) operations. A Mutex is a binary semaphore initialized to 1 (P=lock, V=unlock). Counting semaphores (N > 1) track available resources like buffer slots.
Synchronization Patterns: The producer-consumer (bounded buffer) requires a mutex to protect state and two counting semaphores: slots (initialized to capacity) and items (initialized to 0).
Thread Safety and Deadlock
Thread Safety Violations: Failing to protect shared variables, relying on state across invocations (e.g., static seeds in rand), returning pointers to shared state, or calling thread-unsafe functions. Reentrant functions are a subset of thread-safe functions that touch no shared state and are safe for signal handlers.
Deadlock: Occurs when two or more threads are waiting for locks held by each other. This is common when acquiring mutexes in different orders. The solution is to enforce a strict lock acquisition order.