COSC240 • Operating Systems

Week 9: Memory Management & Virtual Memory

Following the mid-trimester break, we bridge the chasm between raw physical hardware addressing and isolated virtual memory abstractions. We analyze Address Relocation, Dynamic Partitioning, Paging Architectures, Hardware TLB Caching, and Page Replacement Algorithms.

📚 What You Will Learn

The evolution from bare-metal monoprogramming to dynamic hardware relocation via Base and Limit registers.
Contiguous allocation algorithms (First-Fit, Best-Fit, Worst-Fit) and buddy-system power-of-two coalescing.
Internal vs. external memory fragmentation, Knuth's 50% rule, and compaction overheads.
Hardware page tables, virtual address decomposition ($p, d$), and MMU translation mechanics.
Hardware acceleration via Translation Lookaside Buffers (TLBs) and Effective Memory Access Time (EMAT).
Page replacement algorithms: FIFO, Optimal (Belady), LRU, Clock, Aging, and Working Set (WSClock).

✅ What You Should Do

Read Tanenbaum & Bos Chapter 3 (Memory Management) and OSTEP Chapters 13–23.
Work through Modules 01 to 04 sequentially, tracing address translation formulas.
Engage with the Page Replacement Deep-Dives (Clock, Aging, Working Set).
Complete Theory Tutorial 07/09 (Multi-Level Page Table Footprints & EMAT).
Complete Practical Tutorial 07/09 (Simulating Free List Allocation Policies in C).
Prepare for Quiz 4 (covering Virtual Memory, Paging, and Address Translation).

📂 Foundational Memory Virtualization Modules

Module 01

Physical Address Spaces & Monoprogramming

Trace the evolution from early bare-metal execution to dynamic hardware relocation using Base and Limit registers, swapping, and memory overlays.

Monoprogramming Base & Limit Address Relocation Fragmentation

Launch Module 01 →

Module 02

Dynamic Partitioning & Free Space Management

Analyze contiguous memory allocation policies (First-Fit, Best-Fit, Worst-Fit), bitmap tracking vs. free linked lists, and power-of-two buddy allocators.

Dynamic Partitioning Free Lists Buddy Allocator Compaction

Launch Module 02 →

Module 03

Virtual Memory & Paging Architectures

Examine the Memory Management Unit (MMU), virtual address split ($p, d$), Page Table Entries (PTE flags), and 64-bit multi-level hierarchical page tables.

Virtual Memory MMU Translation Page Tables PTE Flags

Launch Module 03 →

Module 04

TLB Acceleration & Inverted Page Tables

Study hardware TLB caching, associative address matching, hardware vs. software walks, EMAT calculations, and inverted page tables with hash anchors.

TLB Cache EMAT Formula Inverted Page Tables Hardware Walk

Launch Module 04 →

⚙ Page Replacement & Thrashing Subsystems

Algorithm 07

Clock Page Replacement

The circular first-in, first-out buffer using hardware referenced bits to approximate Least Recently Used (LRU) eviction with minimal software overhead.

Clock Pointer Reference Bit Second-Chance

Explore Clock Algorithm →

Algorithm 08

Aging Algorithm in Software

Simulating true LRU eviction through shift registers updated at timer clock ticks, tracking recent page reference recency.

Aging Registers Shift Vectors LRU Approximation

Explore Aging Algorithm →

Algorithm 09 & 10

Working Set & WSClock

Peter Denning's working set principle: calculating page sets referenced in virtual time window $\tau$ to prevent thrashing and maintain multiprogramming equilibrium.

Working Set W(t, τ) WSClock Thrashing Control

Explore WSClock →

Policy 11