Memory Management

Memory Management Goals

The OS must: - Allocate memory to processes as needed - Protect each process's memory from other processes - Provide abstraction (logical vs physical addresses) - Maximize utilization (minimize wasted space)

Address Binding

Program addresses get bound to physical memory addresses at one of three times:

Logical (virtual) address: generated by the CPU; what programs use. Physical address: what the memory hardware sees; managed by the OS + MMU.

Memory Management Unit (MMU): hardware chip that translates logical → physical at runtime using a relocation register: physical = logical + base.

Contiguous Memory Allocation

Each process occupies a single contiguous region.

Fixed Partitioning

Memory divided into fixed-size partitions. Each holds one process.

• Internal fragmentation: partition larger than process → wasted space inside
• Simple but inflexible; partition size constrains max process size

Dynamic Partitioning

Partitions created to exact process size.

• External fragmentation: free holes scattered; total free > request, but no single hole large enough
• Compaction: shuffle allocated blocks to merge holes — expensive

Free-List Allocation Strategies

Simulation studies: first fit and best fit generally beat worst fit in speed and utilization.

Segmentation

Process address space divided into logical segments (code, stack, heap, data), each with its own base and limit.

Segment table entry:

| Segment # | Base (physical) | Limit (length) | Valid | RWX |

Address translation:

Logical address = (segment, offset)
Physical = SegmentTable[segment].base + offset
if offset >= SegmentTable[segment].limit → SIGSEGV

Paging

Process address space divided into fixed-size pages; physical memory into same-size frames.

• Page size typically 4 KB (or 2 MB / 1 GB with huge pages)
• Eliminates external fragmentation; may have internal fragmentation (last page)

Address Translation

Logical address bits:  [  page number (p)  |  page offset (d)  ]
Physical address:      [  frame number (f) |       d            ]
f = PageTable[p]
physical = f × page_size + d

Example: 32-bit address space, 4 KB pages (12-bit offset) → 20-bit page number → up to 2²⁰ = 1 M pages.

Page Table Entry (PTE) Fields

TLB (Translation Lookaside Buffer)

Hardware cache for page table entries. Avoids full page table walk every access.

CPU issues address
  → check TLB
    HIT  → frame# from TLB (1 memory access total)
    MISS → walk page table (multiple memory accesses)
           → update TLB
           → access physical frame

Effective access time (EAT): EAT = α × (TLB hit time) + (1 − α) × (miss time) where α = TLB hit ratio.

Example: α=0.99, TLB=10ns, memory=100ns → EAT = 0.99×(10+100) + 0.01×(10+100+100) ≈ 111 ns

Multi-Level Page Tables

For 64-bit address spaces, flat page tables are impractical. Hierarchical structure:

x86-64: 4-level page table
VA bits: [9 PML4 | 9 PDP | 9 PD | 9 PT | 12 offset]
         CR3 → PML4 → PDPT → PD → PT → frame

Only present parts of the tree are allocated → sparse use of large address spaces.

Inverted Page Table

One entry per physical frame (not per virtual page). Used by IBM POWER, Itanium.

• Saves space: table size proportional to physical RAM, not virtual space
• Slower lookup: must search for (PID, page#) — use hash table to speed up

Fragmentation Summary

Slab Allocator (Kernel Memory)

Kernel objects (inodes, PCBs) reused frequently. Slab allocator pre-allocates slabs of same-size objects.

Cache (struct inode)
  └── Slab 1: [inode][inode][inode][inode]
  └── Slab 2: [inode][inode][free][free]

• Cache = collection of slabs for one object type
• Slab = one or more contiguous pages, divided into fixed-size objects
• Benefits: no fragmentation within a cache; fast alloc/free; avoids reinitialization