UT CS 372 - Virtual Memory and Address Translation

Unformatted text preview:

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

UT CS 372 - Virtual Memory and Address Translation

Documents in this Course
MapReduce

MapReduce

17 pages

Processes

Processes

19 pages

MapReduce

MapReduce

17 pages

Load more
Download Virtual Memory and Address Translation
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Virtual Memory and Address Translation and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Virtual Memory and Address Translation 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?