COMP 3000 Operating Systems
Memory Management (part 2)
Lianying Zhao
Page Table “Walk”
• Page Global Directory (PGD) • P4D (Page Directory Level 4) • Page Upper Directory (PUD) • Page Middle Directory (PMD) • Page Table Entry (PTE)
• Offset into a page frame
COMP 3000 (Winter 2021) 2
Page Table “Walk” (CONT’d)
COMP 3000 (Winter 2021)
3
Source: www.chegg.com
Translation Lookaside Buffer (TLB)
• Where are page tables stored? Just in regular memory
• Thus page walk overhead will be non-trivial
• TLB is just another name for page table cache • Can be considered part of the MMU
• TLB stores recently used PTEs
• As with other caches, you cannot see/manipulate the TLB (the CPU
manages it transparently), at least on x86
COMP 3000 (Winter 2021) 4
More Facts about Kernel/User Memory
• Kernel space ≠ physical memory
• The kernel also benefits from virtual memory, but has the capability
to work with physical addresses
• Canonical addresses
• Only the least significant 48 bits of a virtual address would actually be used
• Bits 48 – 63 must be copies of bit 47 (similar to sign extension) • Thus dividing the whole space into two
• Kernel takes the higher half and user space takes the lower
COMP 3000 (Winter 2021) 5
Calculating Addressable Virtual Memory
• We are still interested in knowing the theoretical virtual limit, despite OS-specific implementations
• All entries for a level fit into one page
• Each added level increases the limit by a factor of 512
COMP 3000 (Winter 2021) 6
Page Cache
• Recall: when discussing the block layer
• “The write() system call usually doesn’t immediately write to the block device”,
hence the need for the sync command
• Page cache is where it ends up, and returns to the caller
• By nature, it’s disk cache
• But generalized due to memory mapping, and almost everything is a file
• Candidates include:
• Data of regular files
• Dentries
• Other data from the block layer (devices)
• It is relevant because most content of an address space is loaded from disk • A page becomes “dirty” if it’s different from its disk copy (updated)
COMP 3000 (Winter 2021) 7
When You Do Need More Memory
• This is not a corner case
• Very often, if not most of the time, you have more applications open than
what your physical memory allows for
• Two options in general
• Getting more space somewhere
• Sparing some space by “sacrificing” existing applications
COMP 3000 (Winter 2021) 8
Swapping or Paging (broader sense)
• The idea is to use the disk space to simulate memory
• Swapping tends to emphasize the per-application granularity • Paging tends to emphasize the per-page granularity
• Swap space
• Usually a dedicated partition, of the type “swap” • Compare with: pagefile.sys in Windows
• Various policies may exist
• Usually to swap out pages that have not been recently used (aging)
COMP 3000 (Winter 2021) 9
Page Fault
• Fault in its original sense: something wrong, e.g., “out of bounds” • Segmentation fault
• Hence considered an exception*
• Nevertheless, “page faults” here are kind of expected • Actually, page-not-present faults
• A requested page is found to be on disk
• Indicated by the present/absent bit in PTEs
• Page fault handler
• An exception handler
• Part of the OS (note that otherwise the OS is not running) • Whose job is to fetch the requested page from disk
Why not hardware this time?
COMP 3000 (Winter 2021) 10
Which Page Should Be Paged Out?
• Aging – Timestamps will be ideal • But too expensive
• Least Recently Used (LRU) and the “clock algorithm”
• One more bit in the PTE: Accessed
• The OS “sweeps” all PTEs to set Accessed to 0, at a known interval
• When the page is next accessed, its corresponding Accessed is set to 1
• At the next interval, the OS knows those still with a 0 are at least an interval old and can be a candidate
COMP 3000 (Winter 2021) 11
Gluing Up Everything
COMP 3000 (Winter 2021)
12
Source: thetopsites.net
Thrashing
• Does that mean we can use swap space or page file to support as many apps as we like?
• Oversubscribed memory –> too frequent page faults
COMP 3000 (Winter 2021) 13
Out-of-memory (OOM) Killer
• Actually OOM has been with Linux for decades
• Triggered when the system is critically low on memory • For example, to cope with thrashing
• OOM is just a mechanism. It can have a variety of policies
• See: Android/iOS
• With a different philosophy
• Used as a regular mechanism to maintain proper memory utilization
COMP 3000 (Winter 2021) 14
Android’s Low Memory Killer
• Define a set of thresholds for different types of apps
• Usually transparent to the user and even apps
COMP 3000 (Winter 2021) 15
COMP 3000 (Winter 2021) 16