Memory Management

Wikipedia · Memory management · CC BY-SA 4.0

The OS gives each process the illusion of a private, contiguous address space. Behind the scenes, paging maps virtual addresses to scattered physical frames. The page table is the translation dictionary. The TLB is the cache that makes it fast.

Address spaces

Each process sees virtual addresses starting from 0. The hardware (MMU) translates these to physical addresses at runtime. No process can see another's memory unless the OS explicitly shares a region.

Base and limit registers

The simplest scheme: the base register holds the starting physical address, the limit register holds the size. Every access is checked: if the virtual address exceeds the limit, trap. Simple, but no sharing and external fragmentation.

Segmentation

Divide memory into logical segments (code, stack, heap). Each segment has its own base and limit. The address is (segment, offset). Problem: variable-size segments cause external fragmentation.

Paging

Divide virtual memory into fixed-size pages and physical memory into same-size frames. The page table maps page numbers to frame numbers. No external fragmentation. Internal fragmentation is at most one page per process.

Scheme

; Page table: translate virtual address to physical address
; page-size = 4096 bytes (2^12)

(define page-size 4096)

; Page table: maps page number to frame number
(define page-table '((0 . 5) (1 . 2) (2 . 7) (3 . 0) (4 . 3)))

(define (translate virtual-addr)
  (let* ((page-num (quotient virtual-addr page-size))
         (offset (modulo virtual-addr page-size))
         (frame (cdr (assoc page-num page-table)))
         (physical (+ (* frame page-size) offset)))
    (display "Virtual: ") (display virtual-addr)
    (display " -> Page ") (display page-num)
    (display ", Offset ") (display offset)
    (display " -> Frame ") (display frame)
    (display " -> Physical: ") (display physical)
    (newline)))

(translate 0)       ; page 0, offset 0 -> frame 5
(translate 8192)    ; page 2, offset 0 -> frame 7
(translate 13000)   ; page 3, offset 808 -> frame 0

Translation Lookaside Buffer (TLB)

Every memory access requires a page table lookup, which is itself a memory access. The TLB is a small, fast hardware cache of recent page-to-frame mappings. TLB hit: one memory access. TLB miss: two (or more, with multi-level page tables).

Neighbors

⚙ Algorithms Ch.5 — hash tables and address translation: memory management uses page tables as hash maps from virtual to physical addresses
🔢 Discrete Math Ch.1 — set theory: memory allocation partitions the address space into disjoint segments
🪄 SICP Ch.6 — environment frames and memory: the OS heap and stack are the runtime realization of lexical environments

Foundations (Wikipedia)

← Deadlock by june.kim Virtual Memory →