DOC PREVIEW
Princeton COS 318 - Virtual Memory and Its Address Translations

This preview shows page 1-2-3-27-28-29 out of 29 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

COS 318: Operating SystemsVirtual Memory and Its Address Translations2Today’s Topics!Virtual Memory"Virtualization"Protection!Address Translation"Base and bound"Segmentation"Paging"Translation look-ahead buffer3The Big Picture!DRAM is fast, but relatively expensive"$25/GB"20-30ns latency"10-80GB’s/sec!Disk is inexpensive, but slow"$0.2-1/GB (100 less expensive)"5-10ms latency (200K-400K times slower)"40-80MB/sec per disk (1,000 times less)!Our goals"Run programs as efficiently as possible"Make the system as safe as possibleCPUMemoryDisk4Issues!Many processes"The more processes a system can handle, the better!Address space size"Many small processes whose total size may exceed memory"Even one process may exceed the physical memory size!Protection"A user process should not crash the system"A user process should not do bad things to other processes5Consider A Simple System!Only physical memory"Applications use physical memory directly!Run three processes"emacs, pine, gcc!What if "gcc has an address error?"emacs writes at x7050?"pine needs to expand?"emacs needs more memory than is on the machine?OSpineemacsgccFreex0000x2500x5000x7000x90006Protection Issue!Errors in one process should not affect others!For each process, check each load and store instruction to allow only legal memory referencesCPU CheckPhysicalmemoryaddresserrordatagcc7Expansion or Transparency Issue!A process should be able to run regardless of its physical location or the physical memory size!Give each process a large, static “fake” address space!As a process runs, relocate each load and store to its actual memoryCPU Check &relocatePhysicalmemoryaddressdatapine8Virtual Memory!Flexible"Processes can move in memory as they execute, partially in memory and partially on disk!Simple"Make applications very simple in terms of memory accesses!Efficient"20/80 rule: 20% of memory gets 80% of references"Keep the 20% in physical memory!Design issues"How is protection enforced?"How are processes relocated?"How is memory partitioned?9Address Mapping and Granularity!Must have some “mapping” mechanism"Virtual addresses map to DRAM physical addresses or disk addresses!Mapping must have some granularity"Granularity determines flexibility"Finer granularity requires more mapping information!Extremes"Any byte to any byte: mapping equals program size"Map whole segments: larger segments problematic10Generic Address Translation!Memory Management Unit (MMU) translates virtual address into physical address for each load and store!Software (privileged) controls the translation!CPU view"Virtual addresses!Each process has its own memory space [0, high]"Address space!Memory or I/O device view"Physical addressesCPUMMUPhysicalmemoryI/OdeviceVirtual addressPhysical address11Goals of Translation!Implicit translation for each memory reference!A hit should be very fast!Trigger an exception on a miss!Protected from user’s faultsRegistersL1MemoryDisk2-3x100-300x20M-30MxPagingL2-L310-20x12Base and Bound!Built in Cray-1!Each process has a pair (base, bound)!Protection"A process can only access physical memory in [base, base+bound]!On a context switch"Save/restore base, bound registers!Pros"Simple"Flat and no paging!Cons"Arithmetic expensive"Hard to share"Fragmentationvirtual addressbasebounderror+>physical address13Segmentation!Each process has a table of (seg, size)!Treats (seg, size) as a fine-grained (base, bound)!Protection"Each entry has(nil, read, write, exec)!On a context switch"Save/restore the table and a pointer to the table in kernel memory !Pros"Efficient"Easy to share!Cons"Complex management"Fragmentation within a segmentphysical address+segment offsetVirtual addressseg size...>error14Paging!Use a fixed size unit called page instead of segment!Use a page table to translate!Various bits in each entry!Context switch"Similar to the segmentation!What should be the page size?!Pros"Simple allocation"Easy to share!Cons"Big table"How to deal with holes?VPage # offsetVirtual address...>errorPPage#...PPage#......PPage # offsetPhysical addressPage tablepage table size15How Many PTEs Do We Need?!Assume 4KB page"Offset is low order 12 bits of VE for byte offset (0,4095)"Page IDis high-order 20 bits!Worst case for 32-bit address machine"220 maximum PTE’s"At least 4 bytes per PTE"220 PTEs per page table per process (> 4MB), but there might be 10K processes. They won’t fit in memory together!What about 64-bit address machine?"252 possible pages"252 * 8 bytes = 36 PBytes"A page table cannot fit in a disk"Let alone when each process has own page table16Multiple-Level Page TablesDirectory...pte.........dir table offsetVirtual addressWhat does this buy us?17Inverted Page Tables!Main idea"One PTE for each physical page frame"Optimization: Hash (Vpage, pid) to Ppage #!Pros"Small page table for large address space!Cons"Lookup is difficult "Overhead of managing hash chains, etcpid vpage offsetpid vpage0kn-1k offsetVirtual addressPhysical addressInverted page tableComparison18ConsiderationPagingSegmentationProgrammer aware of technique?NoYesHow many linear address spaces?1ManyTotal address space exceed physical memory?YesYesProcedures and data distinguished and protected separately?NoYesEasily accommodate tables whose size fluctuates?NoYesFacilitates sharing of procedures between users?NoYesWhy was technique invented?Large linear address space without more physical memoryTo break programs and data into logical independent address spaces and to aid sharing and protection19Segmentation with Paging (MULTICS, Intel Pentium)VPage # offsetVirtual address...>PPage#...PPage#......PPage # offsetPhysical addressPage tableseg size...Vseg #error20Virtual-To-Physical Lookups!Programs only know virtual addresses"Each program or process starts from 0 to high address!Each virtual address must be translated"May involve walking through the hierarchical page table"Since the page table stored in memory, a program memory access may requires several actual memory accesses!Solution"Cache “active” part of page table in a very fast memory21Translation Look-aside Buffer (TLB)offsetVirtual address...PPage#...PPage#...PPage#...PPage # offsetPhysical addressVPage #TLBHitMissRealpagetableVPage#VPage#VPage#22Bits in a TLB Entry!Common (necessary) bits"Virtual page number: match with the virtual address"Physical page number: translated address"Valid"Access bits: kernel and user (nil, read, write)!Optional (useful) bits"Process


View Full Document

Princeton COS 318 - Virtual Memory and Its Address Translations

Documents in this Course
Overview

Overview

25 pages

Deadlocks

Deadlocks

25 pages

lectute 2

lectute 2

28 pages

Lecturel

Lecturel

24 pages

Real mode

Real mode

49 pages

Lecture 2

Lecture 2

54 pages

lecture 5

lecture 5

27 pages

Load more
Download Virtual Memory and Its Address Translations
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 Its Address Translations 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 Its Address Translations 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?