預(yù)習(xí)老師課件2018版l18

1、航空航天大學(xué)計算機(jī)學(xué)院內(nèi)容主要取材：CS61C的24講和CS152的8講虛擬器(VM, Virtual Memory)頁表(Page Tables)TLB(Translation Lookaside Buffer)VM性能VM總結(jié)提綱RegsMemoryDiskTInstr OperandsL2 CacheBlocksPagesFilesUpper LevelFasterLargerLower LevelL1 CacheBlocksMemory HierarchyVirtual MemoryCaches7/30/2012Summer 2012 - Lecture #243Virtual Mem

2、oryprotect them from each other Each process thinks it has all the memory to itselfNext level in the memory hierarchyProvides illusion of very large main memoryWorking set of “pages” residing in main memory (subset of all pages residing on disk)Main goal:Avoid reaching all the way back to disk as mu

3、ch as possibleAdditional goals:共享與 Let OS share memory among many programs and保護(hù)視圖7/30/2012Summer 2012 - Lecture #246Virtual to Physical Address TranslationEach program operates in its own virtual address space and thinks its the only program runningEach is protected from the otherOS can decide wher

4、e each goes in memoryHardware gives virtual physical mapProgram operates in its virtual address spaceVirtual Address (VA)(inst. fetchload, store)HWmapPhysicalAddress (PA)(inst. fetchload, store)Physical memory (including caches)虛實轉(zhuǎn)換virtual address虛擬地址 physical address物理地址7/30/2012Summer 2012 - Lectu

5、re #247航空航天大學(xué)計算機(jī)學(xué)院內(nèi)容主要取材：CS61C的24講虛擬器頁表(Page Tables)TLB(Translation Lookaside Buffer)VM性能VM總結(jié)提綱0$baseUser CUser BUser AOS$base+$boundWant:Discontinuous mapProcess size memNeed to use indirectionEnough space for User D, but discontinuous (“fragmentation problem”)Attempt: Base and Bound Reg7/30/2012Su

6、mmer 2012 - Lecture #2411fragmentation/碎片Divide into equal sizedchunks (about 4 KiB - 8 KiB)Any chunk of Virtual Memory can beassigned to any chunk of PhysicalMemory (“page”)7/30/20120HeapStaticPhysical Memory64 MBMapVM to PMVirtual Memory0Summer 2012 - Lecture #2412頁/頁面PaginganizationAddrTrans MAPV

7、irtual Address 0 x000000 x010000 x02000.0 x1F000Virtual Memorypage 31page0page1page24 Ki4 Ki4 Ki.4 KiPhysical AddressPhysical Memorypage 1page 70 x00000 x1000.0 x7000page 04 Ki4 Ki.4 KiHere assume page size is 4 KiBPage is both unit of mapand unit of transfer between disk and physical memory7/30/201

8、2Summer 2012 - Lecture #2413Virtual Memory MapFunctionHow large is main memory?Disk?Dont know!Designed to be interchangeable componentsNeed a system that works regardless of sizesUse lookup table (page table) to deal with arbitrary mapIndex lookup table by # of pages in VM (not all entries will be u

9、sed/valid)Size of PM will affect size of stored translation頁表7/30/2012Summer 2012 - Lecture #2414Address MapPages are aligned in memory Border address of each page has same lowest bitsowest Page size is same in VM and PM, so deno O = log2(page size/B) bits as page offsetUse remaining upper address b

10、its in mapls you which page you want (similar to Tag)Page OffsetVirtual Page #Page OffsetPhysical Page #Same SizeNot necessarilythe same size地址7/30/2012Summer 2012 - Lecture #2415Address Map: Page TablePage Table functionality:ing request is Virtual Address (VA), want Physical Address (PA)Physical O

11、ffset = Virtual Offset(aligned)So just swap Virtual Page Number () for Physical PageNumber (PPN)/Virtual Page #Physical Page #Page OffsetImplementation?Useas index into PTStore PPN and management bits (Valid, Access Rights)Does NOT store actual data (the data sits in PM)虛頁號；PPN物理頁號Page Table LayoutV

12、irtual Address:offsetPage Table1) Indexinto PT usingVARPPN2) Check Valid and AccessRights bits. . .+3) Combine PPN and offsetPhysical Address4) Use PAto accessmemory7/30/2012Summer 2012 - Lecture #2417Page Table Entry Format7/30/2012Summer 2012 - Lecture #2418Contains either PPN or indication not in

13、 main memoryValid = Valid page table entry1 virtual page is in physical memory0 OS needs to fetch page from diskAccess Rights checked on every access to see if allowed (provides protection)Read Only:Can read, but not write pageRead/Write:Read or write data on pageExecutable:Can fetch instructions fr

14、om pagePage Tables (1/2)of virtualA page table (PT) contains the map addresses to physical addressesPage tables located in main memory Why?Too large to fit in registers (220 entries for 4 KiB pages)Faster to access than disk and can be shared by multiple processorsThe OS maintains the PTsEach proces

15、s has its own page table“State” of a process is PC, all registers, and PT OS stores address of the PT of the current process in the Page Table Base Registercontext上下文7/30/2012Summer 2012 - Lecture #2419Page Tables (2/2)Solves fragmentation problem: all pages are the same size, so can utilize all ava

16、ilable slotsOS must reserve “swap space” on disk for each processRunning programs requires hard drive space!To grow a process, ask Operating SystemIf unused pages in PM, OS uses themIf not, OS swaps some old pages (LRU) to disk7/30/2012Summer 2012 - Lecture #2420Paging/Virtual Memory Multiple Proces

17、sesStackStaticCode0CodeStaticPage Table BUser A:User B:Virtual MemoryVirtual MemoryPage Table A0Physical Memory64 MB07/30/2012Summer 2012 - Lecture #2421Review: Paging TerminologyPrograms use virtual addresses (VAs)Space of all virtual addresses called virtual memory (VM)Divided into pages indexed b

18、y virtual page number ()Main memory indexed by physical addresses (PAs)Space of all physical addresses called physical memory (PM)Divided into pages indexed by physical page number (PPN)7/30/2012Summer 2012 - Lecture #2422Question:How many bits wide are the following fields?16 KiB pages40-bit virtua

19、l addresses64 GiB physical memoryPPN26262422202223航空航天大學(xué)計算機(jī)學(xué)院內(nèi)容主要取材：CS61C的24講虛擬器頁表(Page Tables)TLB(Translation Lookaside Buffer)VM性能VM總結(jié)提綱VA1User 1 Virtual Address SpaceUser 2 VirtualAddress SpacePT User 1PT User 2VA27/30/2012Summer 2012 - Lecture #2425Retrieving Data from Memory1)Access pagetable f

20、or address translationPhysical Memory2)Access correct physical addressRequires two accesses of physical memory!Virtual Memory Problem2 physical memory accesses per data access= SLOW!Since locality in pages of data, there must be locality in the translations of those pagesBuild a separate cache for t

21、he Page TableFor historical reasons, cache is called a Translation Lookaside Buffer (TLB)Notice that what is stored in the TLB is NOT data, but the PPN maptranslations7/30/2012Summer 2012 - Lecture #2426TLBs vs. CachesTLBs usually small, typically 16 512 entriesTLB access time comparable to cache (

22、main memory)TLBs can have associativity Usually fully/highly associativeD$ / I$MemoryAddressData atmemory addressAccess next cache level / main memoryOn miss:TLBPPNAccess Page Table in main memoryOn miss:7/30/2012Summer 2012 - Lecture #2427Where Are TLBs Located?Which should we check: Cache or TLB?C

23、an cache hold requested data if corresponding page is not in physical memory?NoWith TLB, does cache receive VA or PA?CacheVAPAhitdata hitmissCPUMain MemoryTLBmissPage TableNotice that it is now the TLB that does translation, not the Page Table!7/30/2012Summer 2012 - Lecture #2428Assumes page tables

24、held in untranslated physical memoryFebruary 16, 2012CS152, Spring 201229Based Virtual-Memory Machine(Hardware Table Walk)PCInst.TLBInst. CacheDDecodeEMData CacheW+DataTLBMain Memory (DRAM)Memory ControllerPhysicalAddressPhysical AddressPhysical AddressPhysical AddressPage-Table BaseRegisterPage Fau

25、lt?Protection violation?Virtual AddressPhysical AddressPage Fault?Protection violation?Virtual AddressHardware PageTable WalkerMiss?Miss?Address Translation Using TLBTLB TagTLB IndexPage OffsetTLB TagPPN(used justlike in acache). . .TLBPPNPage OffsetTagIndexOffsetVirtual AddressPhysical AddressTagBl

26、ock Data. . .Data CachePA split two different ways!7/30/2012Summer 2012 - Lecture #2430Note:TIO for VA & PA unrelatedValid and Access Rights:Same usage as previously discussed for page tablesDirty:Basically always use write-back, so indicates whether or not to write page to disk when replacedRef:Use

27、d to implement LRUSet when page is accessed, cleared periodically by OSIf Ref = 1, then page was referenced recentlyTLB Tag:mod (# TLB entries)Typical TLB Entry FormatValidDirtyRefAccess RightsTLB TagPPNXX7/30/2012Summer 2012 - Lecture #2431Question:How many bits wide are the following?16 KiB pages4

28、0-bit virtual addresses64 GiB physical memory2-way set associative TLB with 512 entriesTLB Tag12TLB Index 14TLB Entry 3832ValidDirtyRefAccess RightsTLB TagPPNXXCheck TLB (input: , output: PPN)TLB Hit: Fetch translation, return PPNTLB Miss: Check page table (in memory)Page Table Hit: Lo age table ent

29、ry into TLBPage Table Miss (Page Fault): Fetch page from disk to memory, update corresponding page table entry, then load entry into TLBCheck cache (input: PPN, output: data)Cache Hit:Return data value to processorCache Miss:Fetch data value from memory, store it in cache, return it to processor7/30

30、/2012Summer 2012 - Lecture #2433Fetching Data on a Memory ReadPage FaultsLoad the page off the disk into a free page of memory Switch to some other process while we waitInterrupt thrown when page loaded and the process page table is updated When we switch back to the task, the desired data will be i

31、n memoryIf memory full, replace page (LRU), writing back ifnecessary, and update both page tables Continuous swapbetween disk and memory called “thrashing”7/30/201234Summer 2012 - Lecture #24thrashing/顛簸加載頁面更新頁表頁面替換Performance Metrics7/30/2012Summer 2012 - Lecture #2435VM performance also uses Hit/M

32、iss Rates and Miss PenaltiesTLB Miss Rate:Fraction of TLB accesses that result in a TLB MissPage Table Miss Rate:Fraction of PT accesses that result in a page faultCaching performance definitions remain the sameSomewhat independent, as TLB will always pass PA to cache regardless of TLB hit or missDa

33、ta Fetch Scenarios7/30/2012Summer 2012 - Lecture #2436Are the following scenarios for a single data access possible?TLB Miss, Page FaultTLB Hit, Page Table HitTLB Miss, Cache HitPage Table Hit, Cache MissPage Fault, Cache HitYes No Yes Yes NoQuestion:A program tries to load a word at X that causes a

34、 TLB miss but not a page fault.Are the following statements TRUE or FALSE?The page table does not contain a valid mapfor the virtual page corresponding to the address XThe word that the program is trying to load is present in physical memoryFTTF12FF37Updating ScenariosUsing V = valid, D = dirty, R =

35、 ref to mean that field is set to the shown value for any entry in either PT or TLBWhich of the following scenarios for a single data access are possible?Read, D = 1Write, R = 1Read, V = 0Write, D = 07/30/2012No Yes Yes NoSummer 2012 - Lecture #2438Question:Assume the page table entry in question is

36、 present in the TLB and we are using a uniprocessor system.Are the following statements TRUE or FALSE?The valid bit for that page must be the same in the PT and TLBThe dirty bit for that page must be the same in the PT and TLBTF12FFFT39航空航天大學(xué)計算機(jī)學(xué)院內(nèi)容主要取材：CS61C的24講虛擬器頁表(Page Tables)TLB(Translation Loo

37、kaside Buffer)VM性能VM總結(jié)提綱VM Performance7/30/2012Summer 2012 - Lecture #2441Virtual Memory is the level of the memory hierarchy that sits below main memoryTLB comes before cache, but affects transfer of data from disk to main memoryPreviously we assumed main memory was lowest level, now we just have t

38、o account for disk accessesSame CPI, AMAT equations apply, but now treat main memory like a mid-level cacheCPUcacheprimarymemorysecondarymemoryCachingcache entrycache block (32 bytes) cache miss rate (1% to 20%) cache hit (1 cycle)cache miss (100 cycles)Demand pagingpage framepage (4Ki bytes)page mi

39、ss rate (0.001%) page hit (100 cycles) page miss (5M cycles)primarymemory7/30/2012Summer 2012 - Lecture #2442CPUTypical Performance StatsImpact of Paging on AMAT (1/2)7/30/2012Summer 2012 - Lecture #2443Memory Parameters:L1 cache hit = 1 clock cycles, hit 95% of accessesL2 cache hit = 10 clock cycle

40、s, hit 60% of L1 missesDRAM = 200 clock cycles (100 nanoseconds)Disk = 20,000,000 clock cycles (10 milliseconds)Average Memory Access Time (no paging):1 + 5%10 + 5%40%200 = 5.5 clock cyclesAverage Memory Access Time (with paging):5.5 (AMAT with no paging) + ?Impact of Paging on AMAT (2/2)7/30/2012Su

41、mmer 2012 - Lecture #2444Average Memory Access Time (with paging) =5.5 + 5%40% (1-HRMem)20,000,000AMAT ifHRMem = 99%?5.5 + 0.020.0120,000,000 = 4005.5(728x slower)1 in 20,000 memory accesses goes to disk: 10 sec program takes 2 hours!AMAT ifHRMem = 99.9%?5.5 + 0.020.00120,000,000 = 405.5AMAT if HRMe

42、m = 99.9999%5.5 + 0.020.00000120,000,000 = 5.9Impact of TLBs on PerformanceEach TLB miss to Page Table L1 Cache missTLB Reach: Amount of virtual address space that can be simultaneously mapped by TLB:TLB typically has 128 entries of page size 4-8 KiB128 4 KiB = 512 KiB = just 0.5 MiBWhat can you do

43、to have better performance? Multi-level TLBs Variable page size (segments) Special situationally-used “superpages”Conceptually same as multi-level cachesNot coveredhere7/30/2012Summer 2012 - Lecture #2445航空航天大學(xué)計算機(jī)學(xué)院內(nèi)容主要取材：CS61C的24講虛擬器頁表(Page Tables)TLB(Translation Lookaside Buffer)VM性能VM總結(jié)提綱Virtual

44、Memory MotivationMemory as cache for disk (reduce disk accesses) Disk is so slow it significantly affects performance Pagingizes memory usage with large, evenly-sized pages that can go anywhereAllows processor to run multiple processes simultaneouslyGives each process illusion of its own (large) VME

45、ach process uses standard set of VAsAccess rights provide protection7/30/2012Summer 2012 - Lecture #2447Paging SummaryPaging requires address translationCan run programs larger than main memoryHides variable machine configurations (RAM/HD)Solves fragmentation problems stored in page tables inAddress map memoryAdditional memory access mitigated with TLBCheck TLB, then Page Table (if necessary), then Cache7/3