CS61C L36 VM II (1) Garcia, Fall 2004 © U CBLecturer PSOE Dan Garciawww.cs.berkeley.edu/~ddgarciainst.eecs.berkeley.edu/~cs61cCS61C : Machine StructuresLecture 36 VM II2004-11-22#4 Bears crush Stanford⇒In the 9th-longest rivalry in the US, we get the most dominant win (41-6) since 1930!JJ Arrington ran for 169yds, a school record for asingle-season and is now the only RB in the US tohave run for 100yds in every game this season.We now must best Southern Miss on Dec 4…calbears.collegesports.com/sports/m-footbl/recaps/112004aac.htmlCS61C L36 VM II (2) Garcia, Fall 2004 © U CBReview…• Cache design choices:• size of cache: speed v. capacity• direct-mapped v. associative• for N-way set assoc: choice of N• block replacement policy• 2nd level cache?• Write through v. write back?• Use performance model to pickbetween choices, depending onprograms, technology, budget, ...• Virtual Memory• Predates caches; each process thinks ithas all the memory to itself; protection!CS61C L36 VM II (3) Garcia, Fall 2004 © U CBVirtual to Physical Addr. Translation• Each program operates in its own virtualaddress space; ~only program running• Each is protected from the other• OS can decide where each goes inmemory• Hardware (HW) provides virtual ⇒physical mappingvirtualaddress(inst. fetchload, store)Programoperates inits virtualaddressspaceHWmappingphysicaladdress(inst. fetchload, store)Physicalmemory(incl. caches)CS61C L36 VM II (4) Garcia, Fall 2004 © U CBAnalogy• Book title like virtual address• Library of Congress call number likephysical address• Card catalogue like page table,mapping from book title to call #• On card for book, in local library vs.in another branch like valid bitindicating in main memory vs. on disk• On card, available for 2-hour in libraryuse (vs. 2-week checkout) like accessrightsCS61C L36 VM II (5) Garcia, Fall 2004 © U CBSimple Example: Base and Bound Reg0∞OSUser AUser BUser C$base $base+$bound • Want discontinuousmapping• Process size >> mem• Addition not enough!⇒ use Indirection!Enough space for User D,but discontinuous (“fragmentation problem”) CS61C L36 VM II (6) Garcia, Fall 2004 © U CBMapping Virtual Memory to Physical Memory 0Physical Memory∞Virtual MemoryCodeStaticHeapStack64 MB• Divide into equal sizedchunks (about 4 KB - 8 KB)0• Any chunk of VirtualMemory assigned to anychuck of Physical Memory(“page”)CS61C L36 VM II (7) Garcia, Fall 2004 © U CBPaging Organization (assume 1 KB pages)AddrTransMAPPage is unit of mappingPage also unit oftransfer from diskto physical memorypage 01K1K1K0102431744Virtual MemoryVirtualAddresspage 1page 311K2048page 2...... ...page 0010247168PhysicalAddressPhysicalMemory1K1K1Kpage 1page 7...... ...CS61C L36 VM II (8) Garcia, Fall 2004 © U CBVirtual Memory Mapping Function• Cannot have simple function topredict arbitrary mapping• Use table lookup of mappings• Use table lookup (“Page Table”) formappings: Page number is index• Virtual Memory Mapping Function• Physical Offset = Virtual Offset• Physical Page Number= PageTable[Virtual Page Number](P.P.N. also called “Page Frame”)Page Number OffsetCS61C L36 VM II (9) Garcia, Fall 2004 © U CBAddress Mapping: Page TableVirtual Address:page no. offsetPage TableBase RegPage Table located in physical memoryindexintopagetable+PhysicalMemoryAddressPage TableVal-idAccessRightsPhysicalPageAddress.VA.R.P. P. A.......CS61C L36 VM II (10) Garcia, Fall 2004 © U CBPage Table• A page table is an operating systemstructure which contains the mappingof virtual addresses to physicallocations• There are several different ways, all up tothe operating system, to keep this dataaround• Each process running in the operatingsystem has its own page table• “State” of process is PC, all registers, pluspage table• OS changes page tables by changingcontents of Page Table Base RegisterCS61C L36 VM II (11) Garcia, Fall 2004 © U CBRequirements revisited• Remember the motivation for VM:• Sharing memory with protection• Different physical pages can beallocated to different processes (sharing)• A process can only touch pages in itsown page table (protection)• Separate address spaces• Since programs work only with virtualaddresses, different programs can havedifferent data/code at the same address!• What about the memory hierarchy?CS61C L36 VM II (12) Garcia, Fall 2004 © U CBPage Table Entry (PTE) Format• Contains either Physical Page Numberor indication not in Main Memory• OS maps to disk if Not Valid (V = 0)• If valid, also check if have permissionto use page: Access Rights (A.R.)may be Read Only, Read/Write,Executable...Page TableVal-idAccessRightsPhysicalPageNumberVA.R.P. P. N.VA.R.P. P.N....P.T.E.CS61C L36 VM II (13) Garcia, Fall 2004 © U CBPaging/Virtual Memory Multiple ProcessesUser B: Virtual Memory∞CodeStaticHeapStack0CodeStaticHeapStackA PageTableB PageTableUser A: Virtual Memory∞00Physical Memory64 MBCS61C L36 VM II (14) Garcia, Fall 2004 © U CBComparing the 2 levels of hierarchy Cache Version Virtual Memory vers. Block or Line Page Miss Page Fault Block Size: 32-64B Page Size: 4K-8KB Placement: Fully AssociativeDirect Mapped,N-way Set Associative Replacement: Least Recently UsedLRU or Random (LRU) Write Thru or Back Write BackCS61C L36 VM II (15) Garcia, Fall 2004 © U CBNotes on Page Table• Solves Fragmentation problem: all chunkssame size, so all holes can be used• OS must reserve “Swap Space” on disk foreach process• To grow a process, ask Operating System• If unused pages, OS uses them first• If not, OS swaps some old pages to disk• (Least Recently Used to pick pages to swap)• Each process has own Page Table• Will add details, but Page Table is essence ofVirtual MemoryCS61C L36 VM II (16) Garcia, Fall 2004 © U CBAdministrivia?CS61C L36 VM II (17) Garcia, Fall 2004 © U CBVirtual Memory Problem #1• Map every address ⇒ 1 indirection viaPage Table in memory per virtualaddress ⇒ 1 virtual memory accesses =2 physical memory accesses ⇒ SLOW!• Observation: since locality in pages ofdata, there must be locality in virtualaddress translations of those pages• Since small is fast, why not use a smallcache of virtual to physical addresstranslations to make translation fast?• For historical reasons, cache is called aTranslation Lookaside Buffer, or TLBCS61C L36 VM II (18) Garcia, Fall 2004 © U CBTranslation Look-Aside Buffers (TLBs)•TLBs usually
View Full Document
Unlocking...