COMP 3000 Operating Systems
Memory Management (part 1)
Lianying Zhao
Virtual Memory vs. Physical Memory
• We have discussed the abstraction of address space
• Each process sees its own memory, with addresses starting from 0
• This is the application’s view
• Memory allocation was also from the application’s perspective
• There are heap, stack, and other sections; malloc() manages in-app memory; mmap() can
map outside resources into such memory • What about the kernel’s view?
• The kernel provides such abstraction with physical memory
• So, there is mapping between virtual memory and physical memory • Each virtual address needs to be translated into a physical address
• Who does the translation?
COMP 3000 (Winter 2021) 2
Revisiting Memory Allocation Mechanisms
• Segmentation
• The old way of organizing memory, coarse-grained
• Segments with a 16-bit offset
• Today, the idea is still reflected in segment descriptors, not for memory allocation but for describing characteristics of memory regions
• Paging
• Physical memory is divided into pages of a fixed size • Physicalpagesaka.pageframes
• Pages are managed (and addressed) with page tables • Page tables are hierarchical (4/5 levels for x64)
• Addressable units and allocation granularity • Addressable in bytes but allocated in pages
COMP 3000 (Winter 2021) 3
Facts about Memory Management
• No contiguousness guarantee with physical memory, due to allocation/deallocation
• Memory is allocated in pages and disk storage is allocated in blocks
• Comparing managing memory and managing disk space?
• Disk blocks→abstracted to→files
• Memory pages→abstracted to→address space (virtual memory) • Both create an illusion of contiguous space
• But virtual memory can be (way) larger than physical memory
• Size of virtual memory is determined by the “width” (size) of the addresses/pointers, while size of physical memory is determined by cost/power/space/etc. constraints
COMP 3000 (Winter 2021) 4
Who does the Virtual-physical Translation?
• Performance matters again
• Imagine such translations happen at each access of a single byte
• So, again hardware does it.
• Memory management unit (MMU), usually as part of the CPU
• With the help from the OS
• Translation is at the granularity of page
COMP 3000 (Winter 2021) 5
Multi-level Paging
• If we used a “flat” linear mapping, for a 64-bit system: • 252 entries (for a page size of 4KB, i.e., 12bits)
• Sparse array/tree
• Not all addresses are necessarily allocated. Accessing unallocated memory
will lead to “segmentation fault”
• Unallocated pages do not need to have entries in the page table
• Multiple levels can also ensure entries for a level to fit into one page COMP 3000 (Winter 2021) 6
Page Tables
• The physical address of the “root” table is stored in a hardware location, i.e., a register.
• On x86, this is CR3
• Page table entries (PTEs)
• After levels of indexing, PTEs point to actual page frames
• Page tables are per-process (actually per address space) • The kernel has its own page tables
• This means CR3 is part of the execution context
COMP 3000 (Winter 2021) 7
What is in a Page Table Entry?
• A page number (pointing to a target page), and
• Metadata about the target page • Valid/invalid (aka present/absent)
• Dirty bit (aka modified bit)
• RW, i.e., whether read-only
• User (or kernel)
• Page Size Exception (PSE), large or regular? • No-execute (NX)
• Etc.
• Note that this is also a mechanism for security • The kernel is not running, most of the time
Like “RWX” for memory pages!
COMP 3000 (Winter 2021)
8
Discussion on Page Sizes
• Having too small pages leads to too big page tables
• Remember this will be multiplied by the number of processes
• Bigger page sizes lead to more internal fragmentation
• While not having fixed page sizes may lead to external fragmentation
• A best-practice default is 4KB (212)
• Multi-level Page Tables (current): how does it solve the problem?
• Compare to how file “holes” are implemented in file systems
• A page of PTEs are all unallocated, that page does not need to be allocated either, equivalent to pointed to by a null pointer
COMP 3000 (Winter 2021) 9
Page Table Organization
• The number of levels determines how much physical space can be covered • Although x86-64 supports only 52 bits physical address size
• 4-level page tables -> 248 = 256TB
• 5-level page tables -> 258 = 128PB
• The OS determines the number of levels and how they are supported
• The upper limits are may vary with implementations (at least not 264 which is 16EB)
• Linux:CONFIG_X86_5LEVEL=y
COMP 3000 (Winter 2021) 10