Memory Management

Learning outcomes:

  • Describe the memory hierarchy, and explain contiguous and noncontiguous allocation and fragmentation
  • Explain how virtual memory, paging, and page faults work
  • Apply page replacement strategies such as FIFO, LRU, and Optimal to a sequence of page requests, and compare their page faults
  • Explain thrashing, and describe how modern systems handle low memory and protect each process's memory

Would you like to download my PowerPoint to follow along?

  • Memory
    • Memory comes in tiers
      • Main memory (RAM): fast, but expensive and smaller
      • Secondary storage (SSDs and hard drives): cheap and large, but much slower
    • The OS has to manage RAM carefully, because there's never quite enough
    • RAM is volatile: it is cleared when the power goes off
  • Memory Hierarchy
    • From fastest and smallest to slowest and largest:
      • Registers: inside the processor. What's in your hands
      • Cache (L1, L2, L3): on the processor chip. Your desk
      • RAM: the bookshelf in your room
      • SSD or hard drive: the library across campus (Storage, I/O, and Backups week)
    • Keep what you use most close at hand. Recently used data is likely to be used again soon (temporal locality)
    • Apple silicon and many phones use unified memory: the processor and graphics share the same RAM
  • Memory Management Strategies
    • Fetch: when to bring data into RAM, only when asked for (demand) or ahead of time (anticipatory)
    • Placement: where in RAM to put it
    • Replacement: what to remove from RAM to make room
    • The same three questions come back for pages, below
  • Logical vs Physical Memory
    • Logical (virtual) memory: how a program sees memory, as one neat, continuous space
    • Physical memory: where the data really is in the RAM chips
    • The OS and hardware translate one into the other on every memory access
    • Like a building directory: you look up "Room 5", and it tells you which floor and door that really is
  • Contiguous vs. Noncontiguous Allocation
    • Contiguous: the whole program sits in one unbroken block
      • Simple, but a big enough block may not exist
    • Noncontiguous: the program is split into pieces placed wherever they fit
      • More overhead, but many more programs fit in memory at once
    • The same trade-off as file allocation in the File Systems week
  • Fixed Partitions
    • Memory is split into fixed-size blocks, and each process gets one
    • Internal fragmentation: a small process doesn't fill its block, so the rest is wasted
    • Base and limit registers stop a process from touching memory outside its block
    • Historical note: early systems loaded each program at a fixed address, so it could only run in one partition. Still worth knowing because it shows the problem virtual memory was invented to solve
  • Variable Partitions
    • Each process gets exactly as much memory as it needs, so no internal fragmentation
    • But as processes come and go, they leave holes
      • External fragmentation: enough free memory in total, but split into holes too small to use
    • Fixes:
      • Coalescing: join neighboring free holes into one
      • Compaction: move everything together to make one big free block. Works, but slow
  • Memory Placement Strategies
    • Where should a new process go?
      • First fit: the first hole big enough. Fast and simple
      • Best fit: the hole that leaves the least space over. Slower
      • Worst fit: the biggest hole, so the leftover space is still useful
    • Like parking: take the first open spot, the tightest spot, or the roomiest spot
  • Evolution of Memory Organizations
    • A chart in the PowerPoint shows how memory organization evolved: from single-user systems, to fixed and variable partitions, to virtual memory using paging, segmentation, or both
  • Virtual Memory
    • A process can run without all of it being in RAM at once
    • Each process gets its own private, continuous address space, and the OS decides where each piece really lives
      • Like every tenant thinking they have the whole building, while the landlord assigns the real rooms
    • Benefits:
      • Programs can be bigger than RAM
      • More programs can run at once
      • Programs can't see or change each other's memory
  • How Virtual Memory Works
    • Programs use virtual addresses. RAM uses physical addresses
    • The MMU (memory management unit), part of the processor, translates between them
    • The TLB (translation lookaside buffer) is a small cache of recent translations, so most lookups are instant
    • Memory is split into blocks called pages or segments, and only the ones being used need to be in RAM (Linux kernel documentation: Memory management concepts)
  • Paging
    • A page is a fixed-size block of a program's virtual memory, often 4 KB
    • A frame is a block of RAM the same size
    • Any page can go in any free frame, so there is no external fragmentation
    • Only the last page of a process may be partly empty (a little internal fragmentation)
    • A page table records which frame holds each page (Linux kernel documentation: Page tables)
  • Segmentation
    • A segment is a piece of a program that makes sense as a unit, such as its code, its data, or its stack
    • Segments are different sizes, and usually bigger than pages
    • Each segment needs one continuous block of RAM, so external fragmentation comes back
    • Modern systems mostly use paging, sometimes combined with segments
  • Page Faults
    • A page fault happens when a program uses a page that isn't in RAM right now
    • The OS pauses the program, loads the page from the drive, and then lets it continue
    • The drive is far slower than RAM, so lots of page faults make everything slow
    • That's why an app you haven't used in a while can take a moment to come back
    • Minor page faults, where the page is already in RAM but not yet mapped, are common and quick
  • When to Load Pages
    • Demand paging: load a page only when the program asks for it
      • Simple, and only loads what is needed, but the program builds up its pages one fault at a time
    • Anticipatory paging (prefetching): guess which pages will be needed and load them early
      • Faster when the guesses are right, wasteful when they are wrong
    • Modern systems mostly use demand paging, with some smart prefetching, such as reading ahead in a file
  • Page Replacement
    • When RAM is full and a page fault happens, one page has to go
    • If that page was changed, it must be written back to the drive first
    • The goal: pick a page that will not be needed again soon, so there are fewer page faults
    • Each strategy is a different guess about the future, with a different amount of overhead
  • First-In-First-Out (FIFO) Page Replacement
    • Throw out the page that has been in RAM the longest
    • Low overhead, but it may throw out a page that is still used all the time
    • Belady's anomaly: with FIFO, giving a process more frames can sometimes cause more page faults, not fewer
  • Least-Recently-Used (LRU) Page Replacement
    • Throw out the page that has gone the longest without being used
    • Uses temporal locality: recently used pages are likely to be used again
    • Usually better than FIFO, but tracking every use adds overhead
    • Can do badly when a program loops over more pages than will fit
  • Clock and Not-Used-Recently
    • Cheaper ways to get close to LRU
    • Second chance: check the oldest page. If it was used recently, clear its "used" bit and give it another turn
    • Clock: the same idea, with the pages arranged in a circle and a pointer moving around like a clock hand
    • Not used recently (NUR): use each page's "used" and "changed" bits to pick one quickly
  • Random and Least-Frequently-Used
    • Random: pick any page. Very low overhead, but it may throw out the page needed next
    • Least frequently used (LFU): throw out the page used the fewest times
      • But a page used heavily long ago can hang around, while newer pages get thrown out
  • Page Replacement, Worked Out
    • Pages requested, in order: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, with 3 frames of RAM
    • FIFO: 10 page faults
    • LRU: 9 page faults
    • Optimal (throw out the page that will not be needed for the longest time): 7 page faults. It needs to know the future, so it is only used to measure the others
  • Page Size
    • Small pages: less wasted space inside pages, and less memory needed for what a process is using
    • Large pages: fewer page table entries, each TLB entry covers more memory, and fewer drive reads
    • Many systems support both. Linux's huge pages can be 2 MB instead of 4 KB, which helps big databases and virtual machines (Linux kernel documentation: Transparent Hugepage Support)
  • Global vs. Local Page Replacement
    • Global: choose a page to replace from any process in the system
      • Global LRU (gLRU): replace the least recently used page in the whole system
      • SEQ: use LRU, but switch to most recently used when a process reads through pages in order, like streaming a big file
      • Simple, but one process can take memory from the others
    • Local: each process only replaces its own pages
      • Lets the OS give more memory to more important processes
  • Other Ideas You May See
    • Static vs dynamic frame allocation: a process gets a fixed number of frames, or a number that changes as it runs
    • Far page replacement: a near-perfect strategy on paper, but too complex to have been used in real systems
    • Voluntary page release: a program tells the OS it no longer needs a page, so the memory can be reused sooner
  • Thrashing
    • A process is thrashing when it spends more time swapping pages in and out than doing work
    • Like opening so many browser tabs that everything slows to a crawl and the drive light never stops
    • If the OS sees low CPU use and starts more processes, thrashing gets worse (the Week 3 feedback loop)
    • Fix: give each process enough frames for the pages it is actively using, or run fewer things at once
  • Running Low on Memory Today
  • See It Yourself
    • Windows: Task Manager, Performance, Memory. Shows in use, compressed, and committed memory
    • macOS: Activity Monitor, Memory. The Memory Pressure graph turns yellow, then red, as RAM runs low
    • Linux: free -h shows RAM and swap, and vmstat 1 shows swapping as it happens (Linux manual page: vmstat)
  • Memory Protection and Security
    • Each process's memory is kept separate, so one program can't read another's passwords or data
    • ASLR (address space layout randomization): programs are loaded at random addresses, so attackers cannot predict where things are (Microsoft: Threat mitigations in Windows (ASLR and DEP))
    • No-execute memory: data areas cannot be run as code (Windows calls this DEP)
    • Memory-safe languages like Rust prevent many memory bugs (Week 1)
    • More in Week 12, Security and Protection
  • Case Study: Linux Page Replacement
    • Historical note: for many years Linux used a clock-style approach with two lists. Still worth knowing because many textbooks and articles describe it
      • Active list: pages in use, with the most recently used near the front
      • Inactive list: pages not used lately. Only these get replaced
    • Newer kernels can use the multi-generational LRU, which sorts pages into several age groups and works better when memory is tight (Linux kernel documentation: Multi-Gen LRU)
  • Linux Page Replacement Diagram
    • Diagram: new pages go into the inactive list. Pages used while inactive move to the active list. Pages not used move from the active list back to the inactive list, and pages at the end of the inactive list are freed

Suggested Activities and Discussion Topics:

  • Activity: check how much memory your computer has, and how much is in use with your usual programs open. What happens when you open many more?
  • Activity: redo the page replacement example with 4 frames instead of 3, using FIFO and LRU. Then try FIFO on the requests 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 with 3 frames and then 4 frames. Did adding a frame help? You've just found Belady's anomaly
  • Activity: open browser tabs one at a time while watching memory. On Windows, use Task Manager, Performance, Memory. On a Mac, watch the Memory Pressure graph in Activity Monitor. On Linux, run vmstat 1. When does the system start compressing or swapping? Does anything slow down?
  • Activity: on a Linux system or virtual machine, run free -h and swapon --show. How much swap do you have? Is any of it in use? Is it a swap file, a swap partition, or zram?
  • Discussion: phones close background apps instead of swapping to storage. Why might phone makers choose that? What are the trade-offs for you as a user?

Would you like to see some more classes? Click here