Transcript Virtual Memory - RCS Lab Main Page

Virtual Memory
Motivation
• Motivations
– Some programs (or their data sets) are
very large
– It’s much easier to write these programs
assuming everything fits in main memory
• A small main memory requires shuffling data
with secondary storage
– But a big main memory is expensive
• Cost-cutting solution: Virtual Memory
– Use a small main memory and big cheap
secondary storage (e.g. hard disk)
– Let the program think the main memory is
big – trick it by shuffling data
transparently between main and
secondary
– Implemented by special hardware and the
operating system
Addresses and Address Spaces
• Phyical vs. virtual
– Program sees virtual memory space and
generate virtual addresses
– Memory chips provide physical memory
space and respond to physical addresses
– Special hardware translates virtual
addresses into physical addresses with
page-size granularity
• Pages and page frames
– Virtual memory space is divided into
numbered virtual pages
– Physical memory is divided into
numbered page frames
– Virtual memory translation maps virtual
pages (in virtual memory space) into page
frames (in physical memory)
• Address format.
– E.g. 32 bit address, 4 kB page
– offset within page: log2(4096)=12 bits
– page number: 32 – 12 = 20 bits. 220 pages
Implementation
• OS moves pages in and out of memory
– Paging in reads it in from disk
– Paging out writes it to disk
• A mapped virtual page has been allocated a page frame
number
• Page table holds mapping information, in page table
entries (PTE)
– Page’s owner (e.g. process ID)
– Virtual page number
– Page location in memory (page frame number) or on disk
(location within swap file)
– Valid?
– Reference – recently accessed?
– Modified – recently written?
– page protection – read-only, read-write, etc.
Demand Paging - Initialization
• OS loads part of program by paging in the
pages it thinks are needed
– E.g. beginning of the program instructions, start
of stack
• OS initializes page table
– Set valid bit and initialize page frame number
for mapped pages (paged in)
– Clear valid bit and initialize swap file offset for
unmapped pages (not yet paged in)
• OS starts program running
Demand Paging – Operation
• As program runs, each virtual memory reference
(instruction load, data load or store) is translated to
physical address using page table
• Search for page table entry with same page as the
virtual memory reference
• Is page mapped to a page frame? (i.e. is there a
PTE with the virtual page number and valid == 1?)
– Yes? Create a physical address by replacing the virtual
page number with the (physical) page frame number
– No? A page fault occurs. OS Page fault handler runs
Demand Paging – Page Fault Handler
• Save state of processor (registers, flags, program counter)
• Check range of valid addresses for process. If this is not a
valid memory address, terminate process
• Else is valid address, so…
– Find a free page frame (e.g. from a list of free frames) to use
– Look in PTE to find where in swap file (on disk) that page is
located
– Perform disk operation to load that page into the free page frame
– Update PTE
• Valid = 1 (in memory)
• Update page frame number with new one
– Restart instruction which caused page fault
TLB - Accelerating Page Table Search
• Have to examine page table for each memory access –
very slow in software
• Could cache the most recent PTE…
• Could cache several recent PTEs… in a Translation
lookaside buffer (TLB)
– Input: virtual page number
– Output: hit/miss, physical page frame number and protection
information
• If TLB misses, then we need to
– Find the virtual page number in the full (memory-resident) page
table – page table walking
– Update an entry in the TLB so we don’t miss on the next access
to the same page
Accelerating TLB Misses
• Modern processors have massive address spaces
– 32 bit address space with 4 kB-long pages has 220 = 1,048,576
pages (and hence potentially that many PTEs)
– Too large to put every PTE into the TLB
• Searching (walking) the page table in software on TLB
misses is really slow
• Page table optimizations:
– Forward-mapped (hierarchical) page table
– Inverse-mapped (inverted) page table