CSE 451

Operating Systems

L18 - Demand Paging, Page Replacement

​

​

​

Slides by: Tom Anderson

Rohan Kadekodi

Demand Paging (Before)

Page B

Demand Paging

1. TLB miss
2. Page table walk
3. Page fault (page invalid in page table)
4. Trap to kernel
5. Locate page on disk
6. Allocate page frame
• Evict page if needed
7. Initiate disk block read into page frame

8. Disk interrupt when DMA complete
9. Mark page as valid
10. Resume process at faulting

instruction

11. TLB miss
12. Page table walk to fetch translation
13. Execute instruction

Demand Paging (After)

Locating a Page on Disk

• When a page is non-resident, how do we know where to find it on disk?
• Option: Reuse page table entry
• If resident, page frame
• If non-resident, disk sector
• Option: Use file system
• Code pages: executable image (read-only)
• Data/Heap/Stack: file per-memory region, file offset = f(virtual offset)

Allocating a Page Frame

• Select old page to evict
• Find all page table entries that refer to old page
• If page frame is shared (hint: use a coremap)
• Set each page table entry to invalid
• Remove any TLB entries (on any core)
• Careful! Not: first remove TLB entries then set page table entry to invalid
• Write changes on page back to disk, if necessary
• Careful! Not: write changes to disk then set page table entry to invalid

PA

PA

VA

VA’

VA -> PA

PgTable (Proc 1)

PgTable (Proc 2)

TLB

Has page been modified/recently used?

• Every hardware page table entry has some bookkeeping
• Has page been modified? (x86 “D” bit)
• Set by hardware on store instruction
• In both TLB and (after a memory fence) corresponding page table entry
• Has page been recently accessed? (x86 “A” bit)
• Set by hardware on in page table entry on every TLB miss
• The hardware page table A and D bit can be reset by the OS kernel
• Reset D bit, mark page as read-only, flush change to disk, mark page as R/W
• Periodically reset U bit to track whether page is recently used

Tracking page modifications (Before)

Tracking page modifications (After)

Modified/Use Bits are (often) Virtual

• Most machines keep modified/use bits in the page table entry
• Not the core map – why?
• Physical page is
• Modified if any page table entry that points to it is modified
• Recently used if any page table entry that points to it is recently used
• Superpages
• One page table entry per superpage
• Access/modified bit applies to entire superpage

=> May need to copy some unmodified bytes back to disk

Use Bits are Fuzzy

• Page-modified bit must be ground truth
• What happens if we evict a modified page without writing the changes

back to disk?

• Page-use bit can be approximate
• What happens if we evict a page that is currently being used?
• “Evict any page not used for a while” is nearly as good as “evict the

single page not used for the longest”

Emulating a Modified Bit

• Some processor architectures do not keep a modified bit per page
• Extra bookkeeping and complexity
• Kernel can emulate a modified bit:
• Set all clean pages as read-only
• On first write to page, trap into kernel
• Kernel set modified bit in core map
• Kernel set page table entry as read-write
• Resume execution
• Kernel needs to keep track
• Current page table permission (e.g., read-only)
• True page table permission (e.g., writeable, clean)

Emulating a Recently Used Bit

• Some processor architectures do not keep a recently used bit per page
• Extra bookkeeping and complexity
• Kernel can emulate a recently used bit:
• Set all pages as invalid
• On first read or write, trap into kernel
• Kernel set recently used bit in core map
• Kernel mark page table entry as read or read/write
• Resume execution
• Kernel needs to keep track
• Current page table permission (e.g., invalid)
• True page table permission (e.g., read-only, writeable)

Models for Application File I/O

• Explicit read/write system calls
• Data copied to user process using system call
• Application operates on data
• Data copied back to kernel using system call
• Memory-mapped files
• Open file as a memory region
• Program uses load/store instructions, implicitly operating on the file
• Page fault if portion of file is not yet in memory
• Kernel brings missing blocks into memory, restarts process

Advantages to Memory-mapped Files

• Programming simplicity, esp for large files
• Operate directly on file, instead of copy in/copy out
• Zero-copy I/O
• Data brought from disk directly into page frame
• Pipelining
• Process can start working before all the pages are populated
• Interprocess communication
• Shared memory segment vs. temporary file

Implementing Memory-Mapped Files

• Memory mapped file is just a memory region
• Per-region access control (read-only, read-write)
• File pages brought in on demand
• Using page fault handler
• Modifications written back to disk on eviction, file close
• Using per-page modified bit
• Transactional (atomic, durable) updates to memory mapped file requires more mechanism

From Memory-Mapped Files to Demand-Paged Virtual Memory

• Every process segment backed by a file on disk
• Code segment -> code portion of executable
• Data, heap, stack segments -> temp files
• Shared libraries -> code file and temp data file
• Memory-mapped files -> memory-mapped files
• When process ends, delete temp files
• Unified memory management across file buffer and process memory

Cache Replacement Policy

• On a cache miss, how do we choose which entry to replace?
• Assuming the new entry is more likely to be used in the near future
• In direct mapped caches, not an issue!

​

• Policy goal: reduce cache misses
• Improve expected case performance
• Also: reduce likelihood of very poor performance

A Simple Policy

• Random?
• Replace a random entry

​

• FIFO?
• Replace the entry that has been in the cache the longest time
• What could go wrong?

FIFO in Action

Worst case for FIFO is if program strides through memory that is larger

than the cache

MIN, LRU, LFU

• MIN (optimal for page faults)
• Replace the cache entry that will not be used for the longest time into the future
• Optimality proof: if evict an entry used sooner, that will trigger an earlier cache

miss

• Least Recently Used (LRU)
• Replace the cache entry that has not been used for the longest time in the past
• Approximation of MIN
• Least Frequently Used (LFU)
• Replace the cache entry used the least often (recently)
• Better than LRU when usage pattern is based on popularity, not history

LRU/MIN for Sequential Scan

Belady’s Anomaly

Question

• How accurately do we need to track the least recently/least frequently used page?
• If miss cost is low, any approximation will do
• Hardware caches
• If miss cost is high but number of pages is large, any not recently used

page will do

• Main memory paging with small pages
• If miss cost is high and number of pages is small, need to be precise
• Main memory paging with superpages

Clock Algorithm: Estimating LRU

• Hardware sets use bit
• Periodically, kernel sweeps through all physical page frames
• If page is unused (by any process), reclaim
• After flushing changes to disk
• If page is used, mark as unused
• Downside: modern servers can have 100M+ physical page frames

Second Chance List

• Periodically sweep through all page frames

if (page is dirty) {

flush to disk, mark page as clean, unused

} else if (page is used) { mark page as unused

} else {

mark as invalid; put at end of “second chance” list

if page is referenced, pull off “second chance” list, mark

page as valid

}

• If need page, pull off front of second chance list

Recap

• MIN is optimal
• replace the page or cache entry that will be used farthest into the future
• LRU is an approximation of MIN
• For programs that exhibit spatial and temporal locality
• Clock/Second Chance is an approximation of LRU
• Bin pages into sets of “not recently used”