DOC PREVIEW
U of I CS 232 - A Real Problem

This preview shows page 1-2-21-22 out of 22 pages.

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

Unformatted text preview:

November 10, 2007 1A Real Problem What if you wanted to run a program that needs more memory than youhave?November 10, 2007 ©2003 Craig Zilles 2Virtual Memory (and Indirection) Finally, we get to Virtual Memory!— We’ll talk about the motivations for virtual memory— We’ll talk about how it is implemented— Lastly, we’ll talk about how to make virtual memory fast: TranslationLookaside Buffers (TLBs). Starting Friday, we’ll turn our attention to peripheral devices and I/O.November 10, 2007 Virtual Memory 3A Real Problem What if you wanted to run a program that needs more memory than youhave?— You could store the whole program on disk, and use memory as acache for the data on disk. This is one feature of virtual memory.— Before virtual memory, programmers had to manually manageloading “overlays” (chunks of instructions & data) off disk beforethey were used. This is an incredibly tedious, not to mention error-prone, process.November 10, 2007 Virtual Memory 4More Real Problems Running multiple programs at the same time brings up more problems.1. Even if each program fits in memory, running 10 programs might not.2. Multiple programs may want to store something at the same address.3. How do we protect one program’s data from being read or written byanother program?November 10, 2007 Virtual Memory 5More Real Problems Running multiple programs at the same time brings up more problems.1. Even if each program fits in memory, running 10 programs might not.– This is really the same problem as on the previous slide.2. Multiple programs may want to store something at the same address.– I.e., what if both Program A and B want to use address 0x10000000as the base of their stack?– It is impractical (if not impossible) to compile every pair of programsthat could get executed together to use distinct sets of addresses.3. How do we protect one program’s data from being read or written byanother program?November 10, 2007 Virtual Memory 6Indirection “Any problem in CS can be solved by adding a level of indirection” Without Indirection With IndirectionNameThingNameThingThingNovember 10, 2007 Virtual Memory 7Indirection Indirection: Indirection is the ability to reference something using aname, reference, or container instead the value itself. A flexiblemapping between a name and a thing allows changing the thing withoutnotifying holders of the name. Without Indirection With Indirection Examples:Pointers, Domain Name Service (DNS) name->IP address, phone system(e.g., cell phone number portability), snail mail (e.g., mail forwarding),911 (routed to local office), DHCP, color maps, call centers that routecalls to available operators, etc.NameThingNameThingThingNovember 10, 2007 Virtual Memory 8Virtual Memory We translate “virtual addresses” used by the program to “physicaladdresses” that represent places in the machine’s “physical” memory.— The word “translate” denotes a level of indirectionVirtual AddressPhysicalMemoryDiskA virtual address can bemapped to either physicalmemory or disk.November 10, 2007 Virtual Memory 9Virtual Memory Because different processes will have different mappings from virtual tophysical addresses, two programs can freely use the same virtualaddress. By allocating distinct regions of physical memory to A and B, they areprevented from reading/writing each others data.Virtual AddressPhysicalMemoryDiskVirtual AddressProgram AProgram BNovember 10, 2007 Virtual Memory 10Caching revisited Once the translation infrastructure is in place, the problem boils down tocaching.— We want the size of disk, but the performance of memory. The design of virtual memory systems is really motivated by the high costof accessing disk.— While memory latency is ~100 times that of cache, disk latency is~100,000 times that of memory.• i.e., the miss penalty is a real whopper. Hence, we try to minimize the miss rate:— VM “pages” are much larger than cache blocks. Why?— A fully associative policy is used.• With approximate LRU Should a write-through or write-back policy be used?November 10, 2007 Virtual Memory 11Finding the right page If it is fully associative, how do we find the right page without scanningall of memory?November 10, 2007 Virtual Memory 12Finding the right page If it is fully associative, how do we find the right page without scanningall of memory?— Use an index, just like you would for a book. Our index happens to be called the page table:— Each process has a separate page table• A “page table register” points to the current process’s page table— The page table is indexed with the virtual page number (VPN)• The VPN is all of the bits that aren’t part of the page offset.— Each entry contains a valid bit, and a physical page number (PPN)• The PPN is concatenated with the page offset to get the physicaladdress— No tag is needed because the index is the full VPN.November 10, 2007 Virtual Memory 13Page Table picturePage offsetVirtual page numberVirtual addressPage offsetPhysical page numberPhysical addressPhysical page numberValidIf 0 then page is notpresent in memoryPage table registerPage table20 121831 30 29 28 27 15 14 13 12 11 10 9 8 3 2 1 029 28 27 15 14 13 12 11 10 9 8 3 2 1 0November 10, 2007 Virtual Memory 14How big is the page table? From the previous slide:— Virtual page number is 20 bits.— Physical page number is 18 bits + valid bit -> round up to 32 bits. How about for a 64b architecture?November 10, 2007 Virtual Memory 15Dealing with large page tables Multi-level page tables— “Any problem in CS can be solved by adding a level of indirection”or two… Since most processes don’t use the whole address space, you don’tallocate the tables that aren’t needed— Also, the 2nd and 3rd level page tables can be “paged” to disk.VPN1 VPN2 VPN3 offsetPage TableBase PointerPPNPPN offset1st2nd3rdA 3-level page tableApril 28, 2003 Cache writes and examples 16November 10, 2007 Virtual Memory 17Waitaminute! We’ve just replaced every memory access MEM[addr] with:MEM[MEM[MEM[MEM[PTBR + VPN1<<2] + VPN2<<2] + VPN3<<2] + offset]— i.e., 4 memory accesses And we haven’t talked about the bad case yet (i.e., page faults)…“Any problem in CS can be solved by adding a level of indirection”— except too many levels of indirection… How do we deal with too many


View Full Document

U of I CS 232 - A Real Problem

Documents in this Course
Goal

Goal

2 pages

Exam 1

Exam 1

5 pages

Exam 1

Exam 1

6 pages

Exam 2

Exam 2

6 pages

Exam 1

Exam 1

5 pages

Load more
Download A Real Problem
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 A Real Problem 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 A Real Problem 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?