Memory Management

Goals

  • Abstract physical memory into a logical address space per process
  • Protect processes from each other
  • Allow efficient sharing of physical memory
  • Enable processes larger than physical memory (virtual memory)

Address Binding

Program addresses can be bound to physical memory at different stages:

Stage When Example
Compile time Address known at compile time MS-DOS .COM files, hardcoded addresses
Load time Relocatable code bound when loaded Static linking with relocation
Execution time Bound at runtime, can move Modern OSes with virtual memory

Logical vs Physical Address

  • Logical address (virtual address): Address generated by CPU. What the program sees. Starts from 0.
  • Physical address: Actual address in RAM hardware.

The Memory Management Unit (MMU) translates logical → physical at runtime.

Contiguous Memory Allocation

Each process gets a single contiguous block of memory.

Fixed Partitioning

Memory divided into fixed-size partitions. One process per partition.

  • Simple but wasteful: internal fragmentation (unused space inside a partition)

Variable Partitioning

Partitions sized to fit processes exactly.

  • External fragmentation: Free space exists but is scattered in small non-contiguous holes

Allocation strategies:

  • First fit: Allocate first hole that’s big enough. Fast.
  • Best fit: Allocate smallest hole that fits. Minimizes wasted space but leaves many tiny holes.
  • Worst fit: Allocate largest hole. Leaves larger leftover chunks (sometimes more useful).

Compaction: Move processes to eliminate fragmentation. Expensive. Requires runtime binding.

50% rule: With first fit, ~½ of memory is wasted on average to fragmentation (empirical).

Segmentation

Process memory divided into logical segments (code, stack, heap, data). Each segment has a base and limit.

Segment table: Maps segment number → (base, limit).

Logical address = (segment number, offset) Physical address = base[segment_number] + offset (if offset < limit)

  • Supports protection (read-only code segment, no-execute stack)
  • Supports sharing (multiple processes can share a code segment)
  • Still suffers from external fragmentation

Paging

Physical memory divided into fixed-size frames. Logical memory divided into same-size pages.

  • Eliminates external fragmentation (any free frame can be used)
  • Internal fragmentation: last page of a process may not be fully used (average waste = ½ page)

Page table: Maps page number → frame number.

Logical address = (page number p, offset d) Physical address = frame_base[p] + d

Frame size is typically 4KB (4096 bytes). Offset uses log2(frame_size) bits.

Translation Lookaside Buffer (TLB)

Page table lookups require a memory access (slow). TLB is a fast hardware cache of recent page table entries.

TLB hit:  logical → TLB → physical  (1 memory access)
TLB miss: logical → page table → physical  (2 memory accesses)

Effective Access Time (EAT):

EAT = hit_rate × (TLB_time + memory_time)
    + miss_rate × (TLB_time + 2 × memory_time)

TLB hit rates are typically >99%, making EAT nearly equal to one memory access.

TLB flushing: On context switch, TLB must be flushed (or use ASIDs, Address Space Identifiers, to tag entries by process).

Multi-Level Page Tables

For 64-bit address spaces, a flat page table would be huge (e.g., 2^52 entries × 8 bytes = 32TB per process).

Solution: Hierarchical page table. Only allocate page table pages that are actually needed.

Two-level paging (32-bit):

logical address: [p1 (10 bits)][p2 (10 bits)][offset (12 bits)]
p1 → outer page table → page of page table
p2 → entry in inner page table → frame number

x86-64 uses 4-level paging (PGD → PUD → PMD → PTE → offset).

Inverted Page Table

One global page table, indexed by frame number rather than virtual page number. Reduces memory overhead but makes lookup slower (search by PID + virtual page). Used in some architectures (PowerPC, IA-64).

Shared Pages

Multiple processes can map the same physical frame (read-only code sharing, shared libraries).

Requirements: Shared page must appear at the same virtual address in all processes (for code with absolute addresses), or use position-independent code (PIC).

Memory Protection

Each page table entry contains protection bits:

  • Read/write/execute permissions
  • Valid/invalid bit (is this page in logical address space?)
  • Dirty bit (has page been written?)
  • Reference/accessed bit (has page been read/written recently?)

Invalid access → hardware raises a protection fault (segmentation fault in user space).

Swapping

When physical memory is full, the OS can swap entire processes to disk (backing store).

  • Swap out: Move process from RAM to disk
  • Swap in: Move process from disk back to RAM

Modern systems use page-level swapping (demand paging) rather than whole-process swapping.

Fragmentation Summary

Type Cause Solution
Internal Fixed allocation, wasted space inside allocation Smaller allocation units (pages)
External Variable allocation, scattered free space Compaction, paging, segmentation