Memory Management#

The OS must multiplex physical memory among many processes while giving each the illusion of a large, private, contiguous address space. Memory management handles allocation, protection, and efficient use of RAM.

Address Spaces#

Every process operates in its own virtual address space — a logical view of memory that the hardware translates to physical addresses.

Paging#

Paging divides memory into fixed-size blocks, eliminating external fragmentation:

Address Translation#

Virtual address (32-bit, 4KB pages):
┌──────────────────────┬────────────────┐
│   Page number (20)   │ Offset (12)    │
└──────────────────────┴────────────────┘
          │                    │
          ▼                    │
    ┌───────────┐              │
    │ Page Table │              │
    │  entry[p] │──▶ frame #   │
    └───────────┘       │      │
                        ▼      ▼
                  ┌─────────────────┐
                  │ Physical address │
                  │ = frame × 4096  │
                  │   + offset      │
                  └─────────────────┘

Page Table Entry (PTE)#

Each entry contains:

Translation Lookaside Buffer (TLB)#

The page table lives in memory — every memory access would require two accesses (one for the page table, one for the data). The TLB is a fast hardware cache of recent translations.

CPU generates virtual address
         │
         ▼
    ┌─────────┐
    │   TLB   │──── HIT ──▶ Physical address (fast: ~1 cycle)
    └─────────┘
         │
        MISS
         │
         ▼
    ┌───────────┐
    │ Page Table │──▶ Physical address (slow: ~100 cycles)
    │ (in RAM)  │    + update TLB
    └───────────┘

TLB Characteristics#

TLB and Context Switches#

On a context switch, the TLB must be invalidated (different process = different page table). Solutions:

• Flush entire TLB — simple but expensive (cold TLB after switch)
• Address Space Identifiers (ASID) — tag TLB entries with process ID, no flush needed

Page Faults#

A page fault occurs when a process accesses a page not currently in physical memory:

1. CPU generates address → MMU checks page table → Present bit = 0
2. MMU raises page fault exception
3. OS page fault handler:
   a. Is the access valid? (segfault if not)
   b. Find a free frame (or evict one via replacement algorithm)
   c. Read page from disk (swap or file) into frame
   d. Update page table entry (set present bit, frame number)
   e. Restart the faulting instruction
4. Process continues as if nothing happened

Types of Page Faults#

Demand Paging#

Load pages only when accessed — not at program start:

Program starts → minimal pages loaded (just code entry point)
         │
         ▼ (access unmapped page)
    Page fault → load page from disk → continue
         │
         ▼ (access another unmapped page)
    Page fault → load page from disk → continue
         ...

Advantages:

• Faster program startup
• Less memory wasted on unused code/data
• Processes can be larger than physical memory

Cost: Each first access to a page incurs a page fault (expensive). Amortized over time as the working set loads.

Page Replacement Algorithms#

When physical memory is full and a page fault occurs, the OS must evict a page. The choice of victim page determines performance.

FIFO (First-In, First-Out)#

Evict the oldest page in memory.

Reference string: 7 0 1 2 0 3 0 4 2 3 (3 frames)

Step:  7  0  1  2  0  3  0  4  2  3
      [7][ ][ ]
      [7][0][ ]
      [7][0][1]
      [2][0][1] ← evict 7
      [2][0][1] ← hit
      [2][3][1] ← evict 0
      [0][3][1] ← evict 2
      [0][4][1] ← evict 3
      [0][4][2] ← evict 1
      [3][4][2] ← evict 0

Page faults: 9 (out of 10 references — poor)

Problem: Bélády’s anomaly — increasing frames can increase faults with FIFO.

LRU (Least Recently Used)#

Evict the page that hasn’t been used for the longest time.

Reference string: 7 0 1 2 0 3 0 4 2 3 (3 frames)

Page faults: 7 (better than FIFO)

Optimal in practice (close to theoretical minimum), but expensive to implement perfectly:

• Counter-based: timestamp every access → find minimum
• Stack-based: maintain access order stack

Clock Algorithm (Second Chance)#

Approximation of LRU using only the reference bit:

         ┌───┐
    ┌───▶│ 0 │──── reference bit = 0? EVICT
    │    └───┘
    │      │ reference bit = 1? Clear it, move on
    │      ▼
    │    ┌───┐
    │    │ 1 │ ← hand pointer moves clockwise
    │    └───┘
    │      │
    │      ▼
    │    ┌───┐
    └────│ 1 │
         └───┘

Algorithm:

1. Point hand at current position
2. If reference bit = 0 → evict this page
3. If reference bit = 1 → clear bit, advance hand, go to step 2

Low overhead, good approximation of LRU. Used in most real operating systems.

Comparison#

Thrashing#

Thrashing occurs when a process spends more time handling page faults than executing:

CPU utilization
      │
  100%│       ╱╲
      │      ╱  ╲
      │     ╱    ╲
      │    ╱      ╲ ← thrashing begins
      │   ╱        ╲
      │  ╱          ╲
      │ ╱            ╲
      │╱              ╲
      └────────────────────▶ Degree of multiprogramming

Cause: Too many processes competing for too few frames — each evicts pages the others need.

Symptoms: Disk is busy, CPU is idle, system unresponsive.

Working Set Model#

The working set W(t, Δ) is the set of pages referenced in the last Δ time units:

If Σ working_set_sizes > total_frames → thrashing will occur

Strategy:

1. Monitor each process’s working set
2. Allocate enough frames to hold the working set
3. If total demand exceeds memory, suspend a process (reduce multiprogramming)

Approximating the Working Set#

• Use reference bits sampled at intervals
• Maintain a “recent reference” window
• Linux uses the page aging mechanism (multiple reference bit levels)

Memory-Mapped Files#

Instead of read()/write() system calls, map a file directly into the address space:

void *addr = mmap(NULL, file_size, PROT_READ | PROT_WRITE,
                  MAP_SHARED, fd, 0);

// Now access file contents directly via pointer:
char first_byte = ((char *)addr)[0];

Common uses: Shared libraries (.so files), database files, IPC via shared memory.

Key Takeaways#

• Paging eliminates external fragmentation by using fixed-size pages and frames
• The TLB is critical for performance — without it, every memory access would double in cost
• Demand paging defers loading until necessary, enabling processes larger than RAM
• LRU is the gold standard for page replacement; the clock algorithm approximates it cheaply
• Thrashing is catastrophic — the working set model prevents it by matching memory allocation to actual need
• Memory-mapped files unify the file and memory abstractions for efficient I/O