CS 241 Section Week #10(11/12/09)Outline• Virtual Memory– Why Virtual Memory– Virtual Memory Addressing– TLB (Translation Lookaside Buffer)– Multilevel Page Table– Inverted Page Table• ProblemsVirtual MemoryWhy Virtual Memory?• Use main memory as a Cache for the Disk– Address space of a process can exceed physical memory size– Sum of address spaces of multiple processes can exceed physical memoryWhy Virtual Memory?• Use main memory as a Cache for the Disk– Address space of a process can exceed physical memory size– Sum of address spaces of multiple processes can exceed physical memory• Simplify Memory Management– Multiple processes resident in main memory.• Each process with its own address space– Only “active” code and data is actually in memoryWhy Virtual Memory?• Use main memory as a Cache for the Disk– Address space of a process can exceed physical memory size– Sum of address spaces of multiple processes can exceed physical memory• Simplify Memory Management– Multiple processes resident in main memory.• Each process with its own address space– Only “active” code and data is actually in memory• Provide Protection– One process can’t interfere with another.• because they operate in different address spaces.– User process cannot access privileged information• different sections of address spaces have different permissions.Principle of Locality• Program and data references within a process tend to clusterPrinciple of Locality• Program and data references within a process tend to cluster• Only a few pieces of a process will be needed over a short period of time (active data or code)Principle of Locality• Program and data references within a process tend to cluster• Only a few pieces of a process will be needed over a short period of time (active data or code)• Possible to make intelligent guesses about which pieces will be needed in the futurePrinciple of Locality• Program and data references within a process tend to cluster• Only a few pieces of a process will be needed over a short period of time (active data or code)• Possible to make intelligent guesses about which pieces will be needed in the future• This suggests that virtual memory may work efficientlyVM Address Translation• Parameters– P = 2p= page size (bytes). – N = 2n= Virtual address limit– M = 2m= Physical address limitvirtual page number page offsetvirtual addressphysical page number page offsetphysical address0p–1address translationpm–1n–1 0p–1pPage offset bits don’t change as a result of translationPage Table• Keeps track of what pages are in memoryPage Table• Keeps track of what pages are in memory• Provides a mapping from virtual address to physical addressHandling a Page Fault• Page fault– Look for an empty page in RAM• May need to write a page to disk and free itHandling a Page Fault• Page fault– Look for an empty page in RAM• May need to write a page to disk and free it– Load the faulted page into that empty pageHandling a Page Fault• Page fault– Look for an empty page in RAM• May need to write a page to disk and free it– Load the faulted page into that empty page– Modify the page tableAddressing• 64MB RAM (2^26)Addressing• 64MB RAM (2^26)• 2^32 (4GB) total memoryVirtual Address (32 bits)Addressing• 64MB RAM (2^26)• 2^32 (4GB) total virtual memory• 4KB page size (2^12)Virtual Address (32 bits)Addressing• 64MB RAM (2^26)• 2^32 (4GB) total memory• 4KB page size (2^12)• So we need 2^12 for the offset, we can use the remainder bits for the pageVirtual Page number (20 bits) Page offset (12 bits)Virtual Address (32 bits)Addressing• 64MB RAM (2^26)• 2^32 (4GB) total memory• 4KB page size (2^12)• So we need 2^12 for the offset, we can use the remainder bits for the page– 20 bits, we have 2^20 pages (1M pages)Virtual Page number (20 bits) Page offset (12 bits)Virtual Address (32 bits)Address Conversion• That 20bit page address can be optimized in a variety of ways– Translation Look‐aside BufferTranslation Lookaside Buffer (TLB)• Each virtual memory reference can cause two physical memory accesses– One to fetch the page table– One to fetch the dataTranslation Lookaside Buffer (TLB)• Each virtual memory reference can cause two physical memory accesses– One to fetch the page table– One to fetch the data• To overcome this problem a high‐speed cache is set up for page table entriesTranslation Lookaside Buffer (TLB)• Each virtual memory reference can cause two physical memory accesses– One to fetch the page table– One to fetch the data• To overcome this problem a high‐speed cache is set up for page table entries• Contains page table entries that have been most recently used (a cache for page table)Translation Lookaside Buffer (TLB)Effective Access Time– Effective Access time (EAT)• m –memory cycle, α‐ hit ratio, ε‐ TLB lookup time• Eat = (m + ε)α + (2m + ε)(1 –α) = 2m + ε–mαAddress Conversion• That 20bit page address can be optimized in a variety of ways– Translation Look‐aside Buffer– Multilevel Page TableMultilevel Page Tables• Given:– 4KB (212) page size– 32‐bit address space– 4‐byte PTE Multilevel Page Tables• Given:– 4KB (212) page size– 32‐bit address space– 4‐byte PTE • Problem:– Would need a 4 MB page table!• 220 *4 bytesMultilevel Page Tables• Given:– 4KB (212) page size– 32‐bit address space– 4‐byte PTE • Problem:– Would need a 4 MB page table!• 220 *4 bytes• Common solution– multi‐level page tables– e.g., 2‐level table (P6)• Level 1 table: 1024 entries, each of which points to a Level 2 page table.• Level 2 table: 1024 entries, each of which points to a pageSummary: Multi‐level Page Tables•Instead of one large table, keep a tree of tables–Top‐level table stores pointers to lower level page tables•First n bits of the page number == index of the top‐level page table•Second n bits == index of the 2nd‐level page table•Etc.Example: Two‐level Page Table• 32‐bit address space (4GB)Example: Two‐level Page Table• 32‐bit address space (4GB)• 12‐bit page offset (4kB pages)Example: Two‐level Page Table• 32‐bit address space (4GB)• 12‐bit page offset (4kB pages)• 20‐bit page address– First 10 bits index the top‐level page table– Second 10 bits index the 2nd‐level page table– 10
View Full Document
Unlocking...