Virtual Memory and Address TranslationReview: the Program and the Process VASReview: Virtual AddressingWhat’s in an Object File or Executable?Role of MMU Hardware and OSThe OS Directs the MMUThe Translation Lookaside Buffer (TLB)Care and Feeding of TLBsA Simple Page TablePage Tables (2)Alpha Page Tables (Forward Mapped)A Page Table Entry (PTE)Page Tables (3)Virtual Address TranslationWhat You Should KnowBackgroundMemory Management 101Memory and MultiprogrammingBase and Bound RegistersBase and Bound: Pros and ConsVariable PartitioningFixed PartitioningCompleting a VM ReferenceDemand Paging and Page FaultsWhere Pages Come FromFaultsOptions for Handling a Fault (1)Options for Handling a Fault (2)Issues for Paged Memory ManagementVirtual Memory and Address TranslationVirtual Memory and Address TranslationReview: the Program and the Process VASReview: the Program and the Process VAS textdataidatawdataheadersymboltablerelocationrecordsprogramtextdataBSSuser stackargs/envkerneldataprocess VASsectionssegmentsBSS“Block Started by Symbol”(uninitialized global data)e.g., heap and sbuf go here.Args/env strings copied in by kernel when the process is created. Process text segment is initialized directly from program text section.Process data segment(s) are initialized from idata and wdata sections. Process stack and BSS (e.g., heap) segment(s) are zero-filled. Process BSS segment may be expanded at runtime with a system call (e.g., Unix sbrk) called by the heap manager routines.Text and idata segments may be write-protected.Review: Virtual AddressingReview: Virtual AddressingtextdataBSSuser stackargs/envkerneldatavirtualmemory(big)physicalmemory(small)virtual-to-physical translationsUser processes address memory through virtual addresses.The kernel and the machine collude to translate virtual addresses to physical addresses.The kernel controls the virtual-physical translations in effect for each space.The machine does not allow a user process to access memory unless the kernel “says it’s OK”.The specific mechanisms for memory management and address translation are machine-dependent.What’s in an Object File or Executable?What’s in an Object File or Executable?int j = 327;char* s = “hello\n”;char sbuf[512];int p() { int k = 0; j = write(1, s, 6); return(j);} textdataidatawdataheadersymboltablerelocationrecordsUsed by linker; may be removed after final link step and strip.Header “magic number”indicates type of image.Section table an arrayof (offset, len, startVA)program sectionsprogram instructionspimmutable data (constants)“hello\n”writable global/static dataj, sj, s ,p,sbufRole 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 Memory Management 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 mapping and intervene if the MMU reports that it cannot complete the translation.The 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 for each 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”.The Translation Lookaside Buffer (TLB)The Translation Lookaside Buffer (TLB)An on-chip hardware translation buffer (TB or TLB) caches recently 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 TLB entries is simple and controlled by hardware.e.g., Not Last UsedIf a translation misses in the TLB, the entry must be fetched by accessing the page table(s) in memory.cost: 10-500 cyclesCare and Feeding of TLBsCare and Feeding of TLBsThe OS kernel carries out its memory management functions by 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 privileged memory 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 data structures in memory (software-loaded TLB).A Simple Page TableA Simple Page TablePFN 0PFN 1PFN ipage #ioffsetuser virtual addressPFN i+offset process page table physical memorypage framesIn this example, each VPN j maps to PFN j, but in practice any physical frame may be used for any virtual page.Each process/VAS has its own page table. Virtual addresses are translated relative to the current page table.The page tables are themselves stored in memory; a protected register holds a pointer to the current page table.Page Tables (2)Page Tables (2)32 bit address with 2 page table fieldsTwo-level page tablesSecond-level page tablesTop-level page table[from Tanenbaum]Alpha 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 the MMU if the translation is valid.write-enable: OS touches this to enable or disable write access for this mapping.reference bit: MMU sets this when a reference is made through the mapping.dirty bit: MMU sets this when a store is completed to the page (page is modified).This is (roughly) what a MIPS/Nachos page table entry (pte) looks like.Page Tables (3)Page Tables (3)Typical page table entry [from Tanenbaum]Virtual Address TranslationVirtual Address TranslationVPN offset29013Example: typical 32-bitarchitecture with 8KB pages.addresstranslationVirtual address translation maps a