CS 152 Computer Architecture andEngineering Lecture 11 - Virtual Memory and CachesKrste AsanovicElectrical Engineering and Computer SciencesUniversity of California at Berkeleyhttp://www.eecs.berkeley.ed u/~krstehttp://inst.eecs.berkeley.e du/~cs1523/5/2009 CS152-Spring!092Today is a review of last two lectures• Translation/Protection/Virtual Memory• This is complex material - often takes several passesbefore the concepts sink in• Try to take a different path through concepts today3/5/2009 CS152-Spring!093VM features track historical uses:• Bare machine, only physical addresses– One program owned entire machine• Batch-style multiprogramming– Several programs sharing CPU while waiting for I/O– Base & bound: translation and protection between programs (not virtualmemory)– Problem with external fragmentation (holes in memory), needed occasionalmemory defragmentation as new jobs arrived• Time sharing– More interactive programs, waiting for user. Also, more jobs/second.– Motivated move to fixed-size page translation and protection, no externalfragmentation (but now internal fragmentation, wasted bytes in page)– Motivated adoption of virtual memory to allow more jobs to share limitedphysical memory resources while holding working set in memory• Virtual Machine Monitors– Run multiple operating systems on one machine– Idea from 1970s IBM mainframes, now common on laptops» e.g., run Windows XP on top of Mac OS X– Hardware support for two levels of translation/protection» Guest OS virtual -> Guest OS physical -> Host machine physical3/5/2009 CS152-Spring!094Bare Machine• In a bare machine, the only kind of address is aphysical addressPCInst.CacheDDecodeE MDataCacheW+Main Memory (DRAM)Memory ControllerPhysicalAddressPhysicalAddressPhysicalAddressPhysicalAddressPhysical Address3/5/2009 CS152-Spring!095Base and Bound SchemeLogical address is what user software sees. Translated tophysical address by adding base register.PhysicalAddressPhysicalAddressLoad XProgramAddressSpaceMain MemorydatasegmentData BoundRegisterMem. AddressRegisterData BaseRegister!+BoundsViolation?Program BoundRegisterProgramCounterProgram BaseRegister!+BoundsViolation?programsegmentLogicalAddressLogicalAddress3/5/2009 CS152-Spring!096Base and Bound MachinePCInst.CacheDDecodeE MDataCacheW+Main Memory (DRAM)Memory ControllerPhysicalAddressPhysicalAddressPhysicalAddressPhysical AddressData BoundRegisterData BaseRegister!+[ Can fold addition of base register into (base+offset) calculationusing a carry-save adder (sum three numbers with only a fewgate delays more than adding two numbers) ]LogicalAddressBoundsViolation?PhysicalAddressProg. BoundRegisterProgram BaseRegister!+LogicalAddressBoundsViolation?3/5/2009 CS152-Spring!097Memory Fragmentation As users come and go, the storage is “fragmented”. Therefore, at some stage programs have to be moved around to compact the storage. OSSpace16K24K24K32K24Kuser 1user 2user 3OSSpace16K24K16K32K24Kuser 1user 2user 3user 5user 48KUsers 4 & 5 arriveUsers 2 & 5leaveOSSpace16K24K16K32K24Kuser 1user 48Kuser 3free3/5/2009 CS152-Spring!098• Processor generated address can be interpreted as a pair<page number, offset>• A page table contains the physical address of the base ofeach pagePaged Memory SystemsPage tables make it possible to store thepages of a program non-contiguously.01230123Address Spaceof User-1Page Table of User-11023page number offset3/5/2009 CS152-Spring!099Private Address Space per User• Each user has a page table• Page table contains an entry for each user pageVA1User 1Page Table VA1User 2Page Table VA1User 3Page Table PhysicalMemoryfreeOSpages3/5/2009 CS152-Spring!0910Linear Page TableVPNOffsetVirtual addressPT Base RegisterVPNData wordData PagesOffsetPPNPPNDPNPPNPPNPPNPage TableDPNPPNDPNDPNDPNPPN• Page Table Entry (PTE)contains:– A bit to indicate if a page exists– PPN (physical page number) fora memory-resident page– DPN (disk page number) for apage on the disk– Status bits for protection andusage• OS sets the Page TableBase Register wheneveractive user processchanges3/5/2009 CS152-Spring!0911Page Tables in Physical MemoryVA1User 1PT User 1 PT User 2 VA1User 23/5/2009 CS152-Spring!0912Size of Linear Page TableWith 32-bit addresses, 4-KB pages & 4-byte PTEs:" 220 PTEs, i.e, 4 MB page table per user" 4 GB of swap needed to back up full virtual address spaceLarger pages?• Internal fragmentation (Not all memory in a page is used)• Larger page fault penalty (more time to read from disk)What about 64-bit virtual address space???• Even 1MB pages would require 244 8-byte PTEs (35 TB!) What is the “saving grace” ?sparsity of virtual address usage3/5/2009 CS152-Spring!0913Hierarchical (Two-Level) Page TableLevel 1 Page TableLevel 2Page Tables Data Pagespage in primary memory page in secondary memoryRoot of the CurrentPage Tablep1offsetp2Virtual Address(ProcessorRegister)PTE of a nonexistent pagep1 p2 offset0111221223110-bitL1 index10-bit L2 index3/5/2009 CS152-Spring!0914Two-Level Page Tables in PhysicalMemoryVA1User 1User1/VA1User2/VA1Level 1 PTUser 1Level 1 PTUser 2VA1User 2Level 2 PTUser 2VirtualAddressSpacesPhysicalMemory3/5/2009 CS152-Spring!0915Address Translation & Protection• Every instruction and data access needs address translation and protection checksA good VM design needs to be fast (~ one cycle) andspace efficientPhysical AddressVirtual AddressAddressTranslationVirtual Page No. (VPN) offsetPhysical Page No. (PPN) offsetProtectionCheckException?Kernel/User ModeRead/Write3/5/2009 CS152-Spring!0916Translation Lookaside BuffersAddress translation is very expensive!In a two-level page table, each referencebecomes several memory accessesSolution: Cache translations in TLBTLB hit " Single Cycle Translation TLB miss " Page Table Walk to refillVPN offsetV R W D tag PPNphysical addressPPN offsetvirtual addresshit?(VPN = virtual page number)(PPN = physical page number)3/5/2009 CS152-Spring!0917Handling a TLB MissSoftware (MIPS, Alpha)TLB miss causes an exception and the operating systemwalks the page tables and reloads TLB. A privileged“untranslated” addressing mode used for walkHardware (SPARC v8, x86, PowerPC)A memory management unit (MMU) walks the pagetables and reloads the TLBIf a missing (data or PT) page is encountered during theTLB reloading, MMU gives up and signals an exceptionfor the original instruction3/5/2009 CS152-Spring!0918Demand-Paged
View Full Document
Unlocking...