1Virtual Memory andVirtual Memory andDemand PagingDemand PagingVirtual Memory IllustratedVirtual Memory Illustratedtextdataidatawdataheadersymboltable, etc.programsectionstextdataBSSuser stackargs/envkerneldataprocesssegmentsphysicalpage framesvirtualmemory(big)physicalmemory(small)executablefilebackingstoragevirtual-to-physicaltranslationspageout/evictionpage fetch2Virtual Address TranslationVirtual Address TranslationVPN offset29 013Example: typical 32-bitarchitecture with 8KB pages.addresstranslationVirtual address translation maps avirtual page number (VPN) to aphysical page frame number (PFN):the rest is easy.PFNoffset+00virtual addressphysical address{Deliver exception toOS if translation is notvalid and accessible inrequested mode.Role of MMU Hardware and OSRole of MMU Hardware and OSVM address translation must be very cheap (on average).• Every instruction includes one or two memory references.(including the reference to the instruction itself)VM translation is supported in hardware by a MemoryManagement Unit or MMU.• The addressing model is defined by the CPU architecture.• The MMU itself is an integral part of the CPU.The role of the OS is to install the virtual-physical mappingand intervene if the MMU reports that it cannot completethe translation.3The Translation Lookaside Buffer (TLB)The Translation Lookaside Buffer (TLB)An on-chip hardware translation buffer (TBorTLB)cachesrecently used virtual-physical translations (ptes).Alpha 21164: 48-entry fully associative TLB.A CPU pipeline stage probes the TLB to complete over 99%of address translations in a single cycle.Like other memory system caches, replacement of TLBentries is simple and controlled by hardware.e.g., Not Last UsedIf a translation misses in the TLB, the entry must be fetchedby accessing the page table(s) in memory.cost: 10-200 cyclesAViewoftheMMUandtheTLBAViewoftheMMUandtheTLBControlMemoryTLBCPUMMU4Completing a VM ReferenceCompleting a VM Referenceraiseexceptionprobepage tableloadTLBprobeTLBaccessphysicalmemoryaccessvalid?pagefault?signalprocessallocateframepage ondisk?fetchfrom diskzero-fillloadTLBstarthereMMUOSThe OS Directs the MMUThe OS Directs the MMUThe OS controls the operation of the MMU to select:(1) the subset of possible virtual addresses that are valid foreach process (the process virtual address space);(2) the physical translations for those virtual addresses;(3) the modes of permissible access to those virtual addresses;read/write/execute(4) the specific set of translations in effect at any instant.need rapid context switch from one address space to anotherMMU completes a reference only if the OS “says it’s OK”.MMU raises an exception if the reference is “not OK”.5Alpha Page Tables (Forward Mapped)Alpha Page Tables (Forward Mapped)2110POL3L2L1base+10 10 13++PFNseg 0/1three-level page table(forward-mapped)sparse 64-bit address space(43 bits in 21064 and 21164)offset at each level isdetermined by specific bits in VAA Page Table Entry (PTE)A Page Table Entry (PTE)PFNvalid bit: OS uses this bit to tell theMMU if the translation is valid.write-enable: OS touches this to enable ordisable write access for this mapping.reference bit: MMU sets this when areference is made through the mapping.dirty bit: MMU sets this when a store iscompleted to the page (page is modified).This is (roughly) what a MIPS/Nachospage table entry (pte) looks like.6Paged Virtual MemoryPaged Virtual MemoryLike the file system, the paging system manages physicalmemory as a page cache over a larger virtual store.• Pages not resident in memory can be zero-filled or foundsomewhere on secondary storage.• MMU and TLB handle references to resident pages.• A reference to a non-resident page causes the MMU to raisea page fault exception to the OS kernel.Page fault handler validates access and services the fault.Returns by restarting the faulting instruction.• Page faults are (mostly) transparent to the interrupted code.Care and Feeding ofCare and Feeding ofTLBsTLBsThe OS kernel carries out its memory management functionsby issuing privileged operations on the MMU.Choice 1: OS maintains page tables examined by the MMU.• MMU loads TLB autonomously on each TLB miss• page table format is defined by the architecture• OS loads page table bases and lengths into privilegedmemory management registers on each context switch.Choice 2: OS controls the TLB directly.• MMU raises exception if the needed pte is not in the TLB.• Exception handler loads the missing pte by reading datastructures in memory (software-loaded TLB).7Where Pages Come FromWhere Pages Come FromtextdataBSSuser stackargs/envkerneldatafile volumewithexecutable programsFetches for clean textor data are typicallyfill-from-file.Modified (dirty)pages are pushed tobacking store (swap)on eviction.Paged-out pages arefetched from backingstore when needed.Initial references to userstack and BSS are satisfiedby zero-fill on demand.Demand Paging and Page FaultsDemand Paging and Page FaultsOS may leave some virtual-physical translations unspecified.mark the pte for a virtual page as invalidIf an unmapped page is referenced, the machine passes controlto the kernel exception handler (page fault).passes faulting virtual address and attempted access modeHandler initializes a page frame, updates pte, and restarts.If a disk access is required, the OS may switch to another processafter initiating the I/O.PagefaultsaredeliveredatIPL0,justlikeasystemcalltrap.Fault handler executes in context of faulted process, blocks on asemaphore or condition variable awaiting I/O completion.8Issues for Paged Memory ManagementIssues for Paged Memory ManagementThe OS tries to minimize page fault costs incurred by allprocesses, balancing fairness, system throughput, etc.(1) fetch policy: When are pages brought into memory?prepaging: reduce page faults by bring pages in before neededclustering: reduce seeks on backing storage(2) replacement policy: How and when does the system selectvictim pages to be evicted/discarded from memory?(3) backing storage policy:Where does the system store evicted pages?When is the backing storage allocated?When does the system write modified pages to backing store?Where Pages Come FromWhere Pages Come FromtextdataBSSuser stackargs/envkerneldatafile volumewithexecutable programsFetches for clean textor data are typicallyfill-from-file.Modified (dirty)pages are pushed tobacking store (swap)on eviction.Paged-out pages arefetched from backingstore when