Question? Leave a message!

Modern Virtual Memory Systems

Modern Virtual Memory Systems
1 Modern Virtual Memory Systems Arvind Computer Science and Artificial Intelligence Laboratory M.I.T. Based on the material prepared by Arvind and Krste Asanovic 6.823 L102 Arvind Address Translation: putting it all together Virtual Address hardware Restart instruction hardware or software TLB software Lookup miss hit Protection Page Table Check Walk the page is denied permitted ∉ memory ∈ memory Page Fault Physical Protection Update TLB (OS loads page) Address Fault (to cache) SEGFAULT October 17, 2005 6.823 L103 Arvind Topics • Interrupts • Speeding up the common case: – TLB Cache organization • Speeding up page table walks • Modern Usage October 17, 2005 6.823 L104 Arvind Interrupts: altering the normal flow of control I HI i1 1 interrupt HI program I 2 i handler HI I n i+1 An external or internal event that needs to be processed by another (system) program. The event is usually unexpected or rare from program’s point of view. October 17, 2005 6.823 L105 Arvind Causes of Interrupts Interrupt: an event that requests the attention of the processor • Asynchronous: an external event – input/output device servicerequest – timer expiration – power disruptions, hardware failure • Synchronous: an internal event (a.k.a exceptions) – undefined opcode, privileged instruction – arithmetic overflow, FPU exception – misaligned memory access – virtual memory exceptions: page faults, TLB misses, protection violations – traps: system calls, e.g., jumps into kernel October 17, 2005 6.823 L106 Arvind Asynchronous Interrupts: invoking the interrupt handler • An I/O device requests attention by asserting one of the prioritized interrupt request lines • When the processor decides to process the interrupt – It stops the current program at instruction I, i completing all the instructions up to I i1 (precise interrupt) – It saves the PC of instruction I in a special i register (EPC) – It disables interrupts and transfers control to a designated interrupt handler running in the kernel mode October 17, 2005 6.823 L107 Arvind Interrupt Handler • Saves EPC before enabling interrupts to allow nested interrupts ⇒ – need an instruction to move EPC into GPRs – need a way to mask further interrupts at least until EPC can be saved • Needs to read a status register that indicates the cause of the interrupt • Uses a special indirect jump instruction RFE (returnfromexception) which – enables interrupts – restores the processor to the user mode – restores hardware status and control state October 17, 2005 6.823 L108 Arvind Synchronous Interrupts • A synchronous interrupt (exception) is caused by a particular instruction • In general, the instruction cannot be completed and needs to be restarted after the exception has been handled – requires undoing the effect of one or more partially executed instructions • In case of a trap (system call), the instruction is considered to have been completed – a special jump instruction involving a change to privileged kernel mode October 17, 2005 6.823 L109 Arvind Exception Handling 5Stage Pipeline Inst. Data Decode PC D E M W + Mem Mem PC address Illegal Data address Overflow Exception Opcode Exceptions Asynchronous Interrupts • How to handle multiple simultaneous exceptions in different pipeline stages • How and where to handle external asynchronous interrupts October 17, 2005 6.823 L1010 Arvind Exception Handling 5Stage Pipeline Commit Point Inst. Data Decode PC D E M W + Mem Mem Illegal Data address Overflow PC address Opcode Exceptions Exception Exc Exc Exc D E M PC PC PC Select D E M Asynchronous Kill F Kill D Kill E Kill Handler Interrupts Stage Stage Stage Writeback PC October 17, 2005 EPC Cause6.823 L1011 Arvind Exception Handling 5Stage Pipeline • Hold exception flags in pipeline until commit point (M stage) • Exceptions in earlier pipe stages override later exceptions for a given instruction • Inject external interrupts at commit point (override others) • If exception at commit: update Cause and EPC registers, kill all stages, inject handler PC into fetch stage October 17, 2005 6.823 L1012 Arvind Topics • Interrupts • Speeding up the common case: – TLB Cache organization • Speeding up page table walks • Modern Usage October 17, 2005 6.823 L1013 Arvind Address Translation in CPU Pipeline Inst Inst. Data Data Decode PC D E M W + TLB Cache TLB Cache TLB miss Page Fault TLB miss Page Fault Protection violation Protection violation • Software handlers need a restartable exception on page fault or protection violation • Handling a TLB miss needs a hardware or software mechanism to refill TLB • Need mechanisms to cope with the additional latency of a TLB: – slow down the clock – pipeline the TLB and cache access – virtual address caches – parallel TLB/cache access October 17, 2005 6.823 L1014 Arvind Virtual Address Caches PA VA Physical Primary CPU TLB Cache Memory Alternative: place the cache before the TLB VA Primary PA Virtual (StrongARM) CPU Memory TLB Cache • onestep process in case of a hit (+) • cache needs to be flushed on a context switch unless address space identifiers (ASIDs) included in tags () • aliasing problems due to the sharing of pages () October 17, 2005 6.823 L1015 Arvind Aliasing in VirtualAddress Caches Page Table Tag Data VA 1 VA 1st Copy of Data at PA 1 Data Pages PA VA 2nd Copy of Data at PA 2 VA 2 Virtual cache can have two copies of same physical data. Two virtual pages share Writes to one copy not visible one physical page to reads of other General Solution: Disallow aliases to coexist in cache Software (i.e., OS) solution for directmapped cache VAs of shared pages must agree in cache index bits; this ensures all VAs accessing same PA will conflict in direct mapped cache (early SPARCs) October 17, 2005 6.823 L1016 Arvind Concurrent Access to TLB Cache Virtual VA Index VPN L b Directmap Cache TLB k L 2 blocks b 2 byte block PA PPN Page Offset Tag = Physical Tag Data hit Index L is available without consulting the TLB ⇒ cache and TLB accesses can begin simultaneously Tag comparison is made after both accesses are completed Cases: L + b = k L + b k L + b k October 17, 2005 6.823 L1017 Arvind VirtualIndex PhysicalTag Caches: Associative Organization Virtual a 2 VA VPN a L = kb b Index Directmap Directmap TLB k L L 2 blocks 2 blocks Phy. PA Tag PPN Page Offset = = Tag a hit 2 Data a After the PPN is known, 2 physical tags are compared Is this scheme realistic October 17, 2005 6.823 L1018 Arvind Concurrent Access to TLB Large L1 The problem with L1 Page size Virtual Index L1 PA cache VA VPN a Page Offset b Directmap PPN Data VA a 1 TLB VA PPN Data 2 a PA PPN Page Offset b hit = Tag Can VA and VA both map to PA 1 2 October 17, 2005 6.823 L1019 Arvind A solution via Second Level Cache L1 Memory Instruction Cache Memory Unified L2 CPU Cache Memory L1 Data RF Memory Cache Usually a common L2 cache backs up both Instruction and Data L1 caches L2 is “inclusive” of both Instruction and Data caches October 17, 2005 6.823 L1020 Arvind AntiAliasing Using L2: MIPS R10000 L1 PA cache Virtual Index Directmap VPN a Page Offset b VA into L2 tag PPN Data VA a 1 TLB VA PPN Data 2 a PPN Page Offset b PA PPN hit = Tag • Suppose VA1 and VA2 both map to PA and VA1 is already in L1, L2 (VA1 ≠ VA2) PA a Data 1 • After VA2 is resolved to PA, a collision will be detected in L2. DirectMapped L2 • VA1 will be purged from L1 and L2, and VA2 will be loaded ⇒ no aliasing October 17, 2005 6.823 L1021 Arvind VirtuallyAddressed L1: AntiAliasing using L2 Virtual VA VPN Page Offset b Index Tag VA Data 1 TLB VA Data 2 PA PPN Page Offset b L1 VA Cache “Virtual Tag Tag” Physical Index Tag PA VA Data 1 Physicallyaddressed L2 can also be used to avoid aliases in virtually L2 PA Cache addressed L1 L2 “contains” L1 October 17, 2005 22 Fiveminute break to stretch your legs 6.823 L1023 Arvind Topics • Interrupts • Speeding up the common case: – TLB Cache organization • Speeding up page table walks • Modern Usage October 17, 2005 6.823 L1024 Arvind Page Fault Handler • When the referenced page is not in DRAM: – The missing page is located (or created) – It is brought in from disk, and page table is updated Another job may be run on the CPU while the first job waits for the requested page to be read from disk – If no free pages are left, a page is swapped out PseudoLRU replacement policy • Since it takes a long time to transfer a page (msecs), page faults are handled completely in software by the OS – Untranslated addressing mode is essential to allow kernel to access page tables October 17, 2005 6.823 L1025 Arvind Hierarchical Page Table Virtual Address 31 22 21 12 11 0 p1 p2 offset 10bit 10bit L1 index L2 index offset Root of the Current p2 Page Table p1 (Processor Level 1 Page Table Register) Level 2 Page Tables page in primary memory page in secondary memory PTE of a nonexistent page Data Pages October 17, 2005 A program that traverses the page table needs a “no translation” addressing mode.6.823 L1026 Arvind Swapping a Page of a Page Table A PTE in primary memory contains primary or secondary memory addresses A PTE in secondary memory contains only secondary memory addresses ⇒ a page of a PT can be swapped out only if none its PTE’s point to pages in the primary memory Why October 17, 2005 6.823 L1027 Arvind Atlas Revisited • One PAR for each physical page PAR’s • PAR’s contain the VPN’s of the pages resident in primary memory PPN VPN • Advantage: The size is proportional to the size of the primary memory • What is the disadvantage October 17, 2005 6.823 L1028 Arvind Hashed Page Table: Approximating Associative Addressing Virtual Address VPN d Page Table PA of PTE Offset PID hash + Base of Table VPN PID PPN • Hashed Page Table is typically 2 to 3 VPN PID DPN times larger than the number of PPN’s to reduce collision probability VPN PID • It can also contain DPN’s for some non­ resident pages (not common) • If a translation cannot be resolved in this table then the software consults a Primary data structure that has an entry for Memory every existing page October 17, 2005 6.823 L1029 Arvind Global System Address Space User map Global Physical System Level A map Memory Address Space Level B map User • Level A maps users’ address spaces into the global space providing privacy, protection, sharing etc. • Level B provides demandpaging for the large global system address space • Level A and Level B translations may be kept in separate TLB’s October 17, 2005 6.823 L1030 Arvind Hashed Page Table Walk: PowerPC Twolevel, Segmented Addressing Seg ID Page Offset 64bit user VA 0 35 51 63 hash S Hashed Segment Table PA of Seg Table + PA per process Global Seg ID Page Offset 80bit System VA 0 51 67 79 hash P Hashed Page Table PA of Page Table + PA systemwide 0 27 39 IBM numbers bits 40bit PA PPN Offset with MSB=0 October 17, 2005 6.823 L1031 Arvind Power PC: Hashed Page Table VPN d 80bit VA Page Table PA of Slot Offset VPN PPN hash + VPN Base of Table • Each hash table slot has 8 PTE's VPN,PPN that are searched sequentially • If the first hash slot fails, an alternate hash function is used to look in another slot All these steps are done in hardware • Hashed Table is typically 2 to 3 times larger Primary than the number of physical pages Memory • The full backup Page Table is a software data structure October 17, 2005 6.823 L1032 Arvind Virtual Memory Use Today 1 • Desktops/servers have full demandpaged virtual memory – Portability between machines with different memory sizes – Protection between multiple users or multiple tasks – Share small physical memory among active tasks – Simplifies implementation of some OS features • Vector supercomputers have translation and protection but not demandpaging (Crays: basebound, Japanese: pages) – Don’t waste expensive CPU time thrashing to disk (make jobs fit in memory) – Mostly run in batch mode (run set of jobs that fits in memory) – Difficult to implement restartable vector instructions October 17, 2005 6.823 L1033 Arvind Virtual Memory Use Today 2 • Most embedded processors and DSPs provide physical addressing only – Can’t afford area/speed/power budget for virtual memory support – Often there is no secondary storage to swap to – Programs custom written for particular memory configuration in product – Difficult to implement restartable instructions for exposed architectures Given the software demands of modern embedded devices (e.g., cell phones, PDAs) all this may change in the near future October 17, 2005 34 Thank you
Document Information
User Name:
User Type:
United States
Uploaded Date: