DOC PREVIEW
Princeton COS 318 - Virtual Memory & Address Translation

This preview shows page 1-2-17-18-19-35-36 out of 36 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 36 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 36 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 36 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 36 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 36 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 36 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 36 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 36 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Virtual Memory & Address TranslationMemory GedankenSome NumbersQuiz 1 AnswersQuiz 1 BreakdownGeneral Memory ProblemLots of VariantsHistory Versus PresentMany Programs, Small Total SizeSlide 10One Program, Lots of MemoryMany Programs, Lots of MemoryWhy Virtual Memory?How To TranslateTranslation OptionsTranslation OverviewGoals of TranslationBase and BoundSegmentationPagingHow Many PTEs Do We Need?Segmentation with PagingStretch Time: Getting A LineMultiple-Level Page TablesInverted Page TablesVirtual-To-Physical LookupsTranslation Look-aside Buffer (TLB)Bits in a TLB EntryHardware-Controlled TLBSoftware-Controlled TLBHardware vs. Software ControlledCache vs. TLBsCaches vs. TLBsIssuesConsistency IssuesIssues to PonderVirtual Memory &Address TranslationVivek PaiPrinceton UniversityOct 10, 2002 2Memory Gedanken•For a given system, estimate the following–# of processes–Amount of memory•Are all portions of a program likely to be used?•What fraction might be unused?•What does this imply about memory bookkeeping?Oct 10, 2002 3Some Numbers•Bubba: desktop machine–63 processes–128MB memory + 12MB swap used–About 2 MB per process•Oakley: CS shared machine–188 processes–2GB memory + 624MB swap–About 13 MB per process•Arizona: undergrad shared machine–818 processes–8GB memory, but only 2GB used–About 2MB per processOct 10, 2002 4Quiz 1 Answers•Microkernel – small privileged kernel with most kernel services running as user-space process•Speed? Lots of context switches, memory copying for communications•Memory layout:Oct 10, 2002 5Quiz 1 Breakdown•4.0 – 5•3.5 – 7•3.0 – 8•2.5 – 11•2.0 – 1•1.5 – 5•0.5 – 3Oct 10, 2002 6General Memory Problem•We have a limited (expensive) physical resource: main memory•We want to use it as efficiently as possible•We have an abundant, slower resource: diskOct 10, 2002 7Lots of Variants•Many programs, total size less than memory–Technically possible to pack them together–Will programs know about each other’s existence?•One program, using lots of memory–Can you only keep part of the program in memory?•Lots of programs, total size exceeds memory–What programs are in memory, and how to decide?Oct 10, 2002 8History Versus Present•History–Each variant had its own solution–Solutions have different hardware requirements–Some solutions software/programmer visible•Present – general-purpose microprocessors–One mechanism used for all of these cases•Present – less capable microprocessors–May still use “historical” approachesOct 10, 2002 9Many Programs, Small Total Size•Observation: we can pack them into memory•Requirements by segments–Text: maybe contiguous–Data: keep contiguous, “relocate” at start–Stack: assume contiguous, fixed size•Just set pointer at start, reserve space–Heap: no need to make it contiguousText 1Data 1Stack 1Data 2Text 2Stack 2Oct 10, 2002 10Many Programs, Small Total Size•Software approach–Just find appropriate space for data & code segments–Adjust any pointers to globals/functions in the code–Heap, stack “automatically” adjustable•Hardware approach–Pointer to data segment–All accesses to globals indirectedOct 10, 2002 11One Program, Lots of Memory•Observations: locality–Instructions in a function generally related–Stack accesses generally in current stack frame–Not all data used all the time•Goal: keep recently-used portions in memory–Explicit: programmer/compiler reserves, controls part of memory space – “overlays”–Note: limited resource may be address spaceDataStackTextActive HeapOtherHeap(s)Oct 10, 2002 12Many Programs, Lots of Memory•Software approach–Keep only subset of programs in memory–When loading a program, evict any programs that use the same memory regions–“Swap” programs in/out as needed•Hardware approach–Don’t permanently associate any address of any program to any part of physical memory•Note: doesn’t address problem of too few address bitsOct 10, 2002 13Why Virtual Memory?•Use secondary storage($)–Extend DRAM($$$) with reasonable performance•Protection–Programs do not step over each other–Communications require explicit IPC operations•Convenience–Flat address space–Programs have the same view of the worldOct 10, 2002 14How To Translate•Must have some “mapping” mechanism•Mapping must have some granularity–Granularity determines flexibility–Finer granularity requires more mapping info•Extremes:–Any byte to any byte: mapping equals program size–Map whole segments: larger segments problematicOct 10, 2002 15Translation Options•Granularity–Small # of big fixed/flexible regions – segments–Large # of fixed regions – pages•Visibility–Translation mechanism integral to instruction set – segments–Mechanism partly visible, external to processor – obsolete–Mechanism part of processor, visible to OS – pagesOct 10, 2002 16Translation Overview•Actual translation is in hardware (MMU)•Controlled in software•CPU view–what program sees, virtual memory•Memory view–physical memoryTranslation(MMU)CPUvirtual addressPhysicalmemoryphysical addressI/OdeviceOct 10, 2002 17Goals of Translation•Implicit translation for each memory reference•A hit should be very fast•Trigger an exception on a miss•Protected from user’s faultsRegistersCache(s)DRAMDisk10x100x10MxpagingOct 10, 2002 18Base and Bound•Built in Cray-1•A program can only access physical memory in [base, base+bound]•On a context switch: save/restore base, bound registers•Pros: Simple•Cons: fragmentation, hard to share, and difficult to use disksvirtual addressbasebounderror+>physical addressOct 10, 2002 19Segmentation•Have a table of (seg, size)•Protection: each entry has–(nil, read, write, exec)•On a context switch: save/restore the table or a pointer to the table in kernel memory •Pros: Efficient, easy to share•Cons: Complex management and fragmentation within a segmentphysical address+segment offsetVirtual addressseg size...>errorOct 10, 2002 20Paging•Use a page table to translate•Various bits in each entry•Context switch: similar to the segmentation scheme•What should be the page size?•Pros: simple allocation, easy to share•Cons: big table & cannot deal with holes easilyVPage # offsetVirtual address...>errorPPage#...PPage#......PPage # offsetPhysical addressPage tablepage table sizeOct 10, 2002 21How Many


View Full Document

Princeton COS 318 - Virtual Memory & Address Translation

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 & 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 & 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 & 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?