Virtual Memory andAddress Translation1ReviewProgram addresses are virtual addresses.¾ Relative offset of program regions can not change during program execution. E.g., heap can not move further from code.gp¾ Virtual addresses == physical address inconvenient. Program location is compiled into the program.A single offset register allows the OS to place a process’ virtual address space anywhere in physical memory.¾ Virtual address space must be smaller than physical.¾ Program is swapped out of old location and swapped into new.Segmentation creates external fragmentation and requires large 2ggqgregions of contiguous physical memory.¾ We look to fixed sized units, memory pages, to solve the problem.Virtual MemoryConceptKey problem: How can one support programs that require more memory than is physically available?¾ How can we support programs that do not use all of their memory at once?2n-1Hide physical size of memory from users¾ Memory is a “large” virtual address space of 2n bytes ¾ Only portions of VAS are in physical memory at any one time (increase memory utilization).Issues¾ Placement strategies Where to place programs in physical memoryProgramP’sVA S3¾ Replacement strategies What to do when there exist more processes than can fit in memory¾ Load control strategies Determining how many processes can be in memory at one time0Realizing Virtual MemoryPagingPhysical memory partitioned into equal sized page frames¾ Page frames avoid external fragmentation.(fMAX-1,oMAX-1)gg(f,o)oPhysicalMemoryA memory address is a pair (f, o)f— frame number (fmaxframes)o— frame offset (omaxbytes/frames)Physical address = omax×f +o4(0,0)PA:fof1log2omaxlog2(fmax × omax)Physical Address SpecificationsFrame/Offset pair v. An absolute indexExample: A 16-bit address space with (omax=) 512 byte page frames¾ Addressing location (3, 6) = 1,542(3,6)1,542019PA:16(3,6)foPhysicalMemory11101000000000036101,5425(0,0)f1,5420QuestionsThe offset is the same in a virtual address and a physical address.¾AT¾A. True¾ B. FalseIf your level 1 data cache is equal to or smaller than 2number of page offsetbits then address translation is not necessary for a data cache tag check.¾ A. True¾BFalse6¾B. FalseRealizing Virtual MemoryPagingA process’s virtual address space is partitioned into equal sized pages¾page=page frame2n-1 =(pMAX-1,oMAX-1)¾page= page frame(p,o)oVirtualAddressSpaceA virtual address is a pair (p, o)p— page number (pmaxpages)o— page offset (omaxbytes/pages)Virtual address = omax×p +o7(0,0)popVA :1log2oMAXlog2(pmax×omax)PagingMapping virtual addresses to physical addressesPages map to framesPages are contiguous in a VAS... ¾ But pages are arbitrarily located ihil dVirtualin physical memory, and¾ Not all pages mapped at all timesVirtualAddressSpace(p2,o2)PhysicalMemory(f1,o1)8(p1,o1)(f2,o2)Frames and pagesOnly mapping virtual pages that are in use does what?¾A. Increases memory utilization.¾A. Increases memory utilization.¾ B. Increases performance for user applications.¾ C. Allows an OS to run more programs concurrently.¾ D. Gives the OS freedom to move virtual pages in the virtual address space.Address translation is¾ A. Frequent9¾ B. InfrequentChanging address mappings is¾ A. Frequent¾ B. InfrequentPagingVirtual address translationA page table maps virtual pages to physical frames(f,o)ProgramPCPUP’sVirtualAddressSpacePhysicalMemory120 910po116 910foVirtualAdd10Page Table(p,o)pPhysicalAddressesAddressesfVirtual Address Translation DetailsPage table structureContents:¾ Flags — dirty bit, resident bit, clock/reference bit¾ Frame number1 table per processPart of process’s state120 910po116 910foVirtualCPU111 0Page TablepPhysicalAddressesAddressesf0PTBR+Virtual Address Translation DetailsExampleA system with 16-bit addresses¾ 32 KB of physical memory¾ 1024 byte pages(4,1023)(4,0)CPUPhysicalMemory15po14910foPhysicalAddressesVirtualAddP’sVirtualAddressSpace(3,1023)(4,0)00109121 1 0 0 1 0 0Page TableAddresses0 0 0 0 0 0 0(0,0)10Virtual Address TranslationPerformance IssuesProblem — VM reference requires 2 memory references!¾ One access to get the page table entry¾ One access to get the dataPage table can be very large; a part of the page table can be on disk.¾ For a machine with 64-bit addresses and 1024 byte pages, what is the size of a page table?What to do?¾ Most computing problems are solved by some form of…13 Caching IndirectionVirtual Address Translation Using TLBs to Speedup Address TranslationCache recently accessed page-to-frame translations in a TLB¾ For TLB hit, physical page number obtained in 1 cycle¾ For TLB miss, translation is updated in TLB¾ Has high hit ratio (why?)f120 910po116 910foPhysicalAddressesVirtualAddressesCPUKeyValue?14Page TableTLBfKeyValueppfXDealing With Large Page Tables Multi-level pagingAdd additional levels of indirection to the page table by sub-dividing page number into k parts ¾ Create a “tree” of page tables¾ TLB still used, just not shownSecond-LevelPage Tables¾ The architecture determines the number of levels of page tablep2oVirtual Addressp3Page Tablesp1p215Third-LevelPage TablesFirst-LevelPage Tablep1p3Dealing With Large Page Tables Multi-level pagingExample: Two-level pagingCPUMemory120 1016p1o116 10foPhysicalAddressesVirtualAddressesCPUp2Memory16Second-LevelPage TableFirst-LevelPage Tablepage tablep2fp1PTBR++The Problem of Large Address SpacesWith large address spaces (64-bits) forward mapped page tables become cumbersome.¾ E.g. 5 levels of tables.gInstead of making tables proportional to size of virtual address space, make them proportional to the size of physical address space.¾ Virtual address space is growing faster than physical.Use one entry for each physical page with a hash table17Use one entry for each physical page with a hash table¾ Size of translation table occupies a very small fraction of physical memory¾ Size of translation table is independent of VM sizeVirtual Address TranslationUsing Page Registers (aka Inverted Page Tables)Each frame is associated with a register containing¾ Residence bit: whether or not the frame is occupied¾Occupier: page number of the page occupying frame¾Occupier: page number of the page occupying frame¾ Protection bitsPage registers: an example ¾ Physical memory size: 16 MB¾ Page size: 4096 bytes¾ Number of frames: 4096¾Space used for page registers (assuming 8 bytes/register): 3218¾Space used for page registers
View Full Document