无限大的快速记忆体

1、Chap. 7.4: Virtual MemoryCS61C L35 VM I (2)Garcia UCBReview: CachesCache design choices:size of cache: speed v. capacitydirect-mapped v. associativefor N-way set assoc: choice of Nblock replacement policy2nd level cache?Write through v. write back?Use performance model to pick between choices, depen

2、ding on programs, technology, budget, .CS61C L35 VM I (3)Garcia UCBAnother View of the Memory HierarchyRegsL2 CacheMemoryDiskTapeInstr. , OperandsBlocksPagesFilesUpper LevelLower LevelFasterLargerCacheBlocksThus farNext:VirtualMemoryRecall: illusion of memorynProgrammers view about memorynUnlimited

3、amount of fast memorynHow to create the above illusion?無限大的快速記憶體Scene: libraryBook shelfdeskbooksVirtual memory 虛擬記憶體nCreate an illusion of unlimited memorynMotivation nA collection of programs running at once on a machinenTotal memory required by all programs the amount of main memory availablenAll

4、ow a single user program to exceed the size of primary memorynSoftware solution: programmers divided programs into pieces, called overlays多個程式同時執行，大於主記憶體單一程式大於主記憶體Process nThe state of a program is called a processnState of a program:nProgram counter (PC), registers, page table,nTo allow another pro

5、gram to use the CPU, we must save this statenContext switchingnOS (operating system) changes from running process P1 to running process P2行程CS61C L35 VM I (7)Garcia UCBSimple Example: Base and Bound Reg0 OSUser AUser BUser C$base $base+$bound Want discontinuous mappingProcess size memAddition not en

6、ough!= What to do?Enough space for User D,but discontinuous (“fragmentation problem”) Virtual memory systemnMain memory as a cache for the secondary storage (disk)MemoryCPUMemorySizeCost ($/bit)SpeedSmallestBiggestHighestLowestFastestSlowestMemorycacheDiskCache for diskHow to mapto disk?More about V

7、irtual MemorynCalled “Virtual Memory”nAlso allows OS to share memory, protect programs from each othernToday, more important for protection vs. just another level of memory hierarchynEach process thinks it has all the memory to itselfnHistorically, it predates cachesCS61C L35 VM I (10)Garcia UCBMapp

8、ing Virtual Memory to Physical Memory 0Physical Memory Virtual MemoryCodeStaticHeapStack64 MBDivide into equal sizedchunks (about 4 KB - 8 KB)0Any chunk of Virtual Memory assigned to any chuck of Physical Memory (“page”)CS61C L35 VM I (11)Garcia UCBPaging Organization (assume 1 KB pages)AddrTransMAP

9、Page is unit of mappingpage 01K1K1K0102431744Virtual MemoryVirtualAddresspage 1page 311K2048page 2.page 0010247168PhysicalAddressPhysicalMemory1K1K1Kpage 1page 7.VM address translation (1)3 2 1 011 10 9 815 14 13 1231 30 29 28 27Page offsetVirtual page numberVirtual address3 2 1 011 10 9 815 14 13 1

10、229 28 27Page offsetPhysical page numberPhysical addressTranslationPage size=212VirtualaddressPhysicaladdressAddress space=232=4GBAddress space=230=1GBHow to translate virtual addresses ? Ans: Direct mapped, set-associative, full-associative?VM address translation (2)Page offsetVirtual page numberVi

11、rtual addressPage offsetPhysical page numberPhysical addressPhysical page numberValidIf 0 then page is notpresent in memoryPage table registerPage table20121831 30 29 28 27 15 14 13 12 11 10 9 8 3 2 1 029 28 2715 14 13 12 11 10 9 8 3 2 1 0Each programhas its ownpage table220Address translation: Full

12、-associativeCS61C L35 VM I (14)Garcia UCBPaging/Virtual Memory Multiple ProcessesUser B: Virtual Memory CodeStaticHeapStack0CodeStaticHeapStackA PageTableB PageTableUser A: Virtual Memory 00Physical Memory64 MBPage fault (cache miss)Physical memoryDisk storageValid111101101101Page tableVirtual pagen

13、umberPhysical page ordisk addressVirtualPage numberKey issues in VMnPage fault penalty takes millions of cyclesnPages should be large enough to amortize the high access timen32-64KBnReduce the page fault rate: full-associative placementnUse clever algorithm to replace pages while page faults occurnL

14、RU (least recently used) ?nUse write-back instead of write-throughMake the address translation fasternMotivation: page tables are stored in main memoryLoad/storevirtual addressPage tablePhysical addressIn memoryMain memorydata2 memoryaccesses !Use a cacheto store page tableTranslation-lookaside buff

15、er (TLB) V alid111101101101Page tableP hysical pageaddressValidTLB111101TagVirtual pagenum berPhysical pageor disk addressPhysical m em oryDisk storageTLBTLBmissCS61C L35 VM I (19)Garcia UCBVM, TLB, and cacheTLBs usually small, typically 128 - 256 entries Like any other cache, the TLB can be direct

16、mapped, set associative, or fully associative ProcessorVACachemisshitdataTLBLookupPAhitmissMainMemoryTrans-lationOn TLB miss, get page table entry from main memoryVM, TLB, and cachesValidTagDataPage offsetPage offsetVirtual page numberVirtual addressPhysical page num berValid1220201614Cache index32C

17、acheDataCache hit2ByteoffsetDirtyTagTLB hitPhysical page num berPhysical address tagTLBPhysical address31 30 29 15 14 13 12 11 10 9 8 3 2 1 0 31 30 12 11 1 0 Virtual addressTLBcacheProtection with Virtual memorynVM allows the sharing of a single main memory by multiple processesnOS place the page ta

18、bles in the address space of OSnIndependent virtual pages map to disjoint physical pagenUser process can not change the page table mappingCS61C L35 VM I (22)Garcia UCBComparing the 2 levels of hierarchy Cache VersionVirtual Memory vers. Block or LinePage MissPage Fault Block Size: 32-64BPage Size: 4

19、K-8KB Placement:Fully AssociativeDirect Mapped, N-way Set Associative Replacement: Least Recently UsedLRU or Random(LRU) Write Thru or BackWrite BackCS61C L36 VM II (23)Garcia UCBReview: 4 Qs for any Memory Hierarchy Q1: Where can a block be placed? One place (direct mapped) A few places (set associ

20、ative) Any place (fully associative) Q2: How is a block found? Indexing (as in a direct-mapped cache) Limited search (as in a set-associative cache) Full search (as in a fully associative cache) Separate lookup table (as in a page table) Q3: Which block is replaced on a miss? Least recently used (LR

21、U) Random Q4: How are writes handled? Write through (Level never inconsistent w/lower) Write back (Could be “dirty”, must have dirty bit) CS61C L36 VM II (24)Garcia UCB Block 12 placed in 8 block cache:Fully associativeDirect mapped2-way set associative- Set Associative Mapping = Block # Mod # of Se

22、ts0 1 2 3 4 5 6 7Blockno.Fully associative:block 12 can go anywhere0 1 2 3 4 5 6 7Blockno.Direct mapped:block 12 can go only into block 4 (12 mod 8)0 1 2 3 4 5 6 7Blockno.Set associative:block 12 can go anywhere in set 0 (12 mod 4)Set0Set1Set2Set3Q1: Where block placed in upper level?CS61C L36 VM II

23、 (25)Garcia UCB Direct indexing (using index and block offset), tag compares, or combination Increasing associativity shrinks index, expands tagBlockoffsetBlock AddressTagIndexQ2: How is a block found in upper level?Set SelectData SelectCS61C L36 VM II (26)Garcia UCBEasy for Direct MappedSet Associative or Fully Associative: Random LRU (Least Recently Used)Miss RatesAssociativity:2-way 4-way 8-waySizeLRU Ran LRU Ran LRU Ran16 KB5.2% 5.7% 4.7% 5.3% 4.4%5.0%64 KB1.9% 2.0% 1.5% 1