1&6(&6(3ULQFLSOHVRI2SHUDWLQJ3ULQFLSOHVRI2SHUDWLQJ6\VWHPV6\VWHPV)DOO)DOOLecture 9: PagingLecture 9: PagingGeoffrey M. VoelkerGeoffrey M. VoelkerOctober 31, 2001 CSE 120 – Lecture 9 – Paging 2/HFWXUH2YHUYLHZ/HFWXUH2YHUYLHZToday we’ll cover more paging mechanisms:● Optimizations◆ Managing page tables (space)◆ Efficient translations (TLBs) (time)◆ Demand paged virtual memory (space)● Recap address translation● Advanced Functionality◆ Sharing memory◆ Copy on Write◆ Mapped files2October 31, 2001 CSE 120 – Lecture 9 – Paging 30DQDJLQJ3DJH7DEOHV0DQDJLQJ3DJH7DEOHV● Last lecture we computed the size of the page table for a 32-bit address space w/ 4K pages to be 4MB◆ This is far far too much overhead for each process● How can we reduce this overhead?◆ Observation: Only need to map the portion of the address space actually being used (tiny fraction of entire addr space)● How do we only map what is being used?◆ Can dynamically extend page table…◆ Does not work if addr space is sparce (internal fragmentation)● Use another level of indirection: two-level page tablesOctober 31, 2001 CSE 120 – Lecture 9 – Paging 47ZR7ZR/HYHO3DJH7DEOHV/HYHO3DJH7DEOHV● Two-level page tables◆ Virtual addresses (VAs) have three parts:» Master page number, secondary page number, and offset◆ Master page table maps VAs to secondary page table◆ Secondary page table maps page number to physical page◆ Offset indicates where in physical page address is located● Example◆ 4K pages, 4 bytes/PTE◆ How many bits in offset? 4K = 12 bits◆ Want master page table in one page: 4K/4 bytes = 1K entries◆ Hence, 1K secondary page tables. How many bits?◆ Master (1K) = 10, offset = 12, inner = 32 – 10 – 12 = 20 bits3October 31, 2001 CSE 120 – Lecture 9 – Paging 57ZR7ZR/HYHO3DJH7DEOHV/HYHO3DJH7DEOHVPage tableMaster page number SecondaryVirtual AddressMaster Page TablePage frame OffsetPhysical AddressPhysical MemoryOffsetPage frameSecondary Page TableOctober 31, 2001 CSE 120 – Lecture 9 – Paging 6$GGUHVVLQJ3DJH7DEOHV$GGUHVVLQJ3DJH7DEOHVWhere do we store page tables (which address space)?● Physical memory◆ Easy to address, no translation required◆ But, allocated page tables consume memory for lifetime of VAS● Virtual memory (OS virtual address space)◆ Cold (unused) page table pages can be paged out to disk◆ But, addressing page tables requires translation◆ How do we stop recursion?◆ Do not page the outer page table (called wiring)● If we’re going to page the page tables, might as well page the entire OS address space, too◆ Need to wire special code and data (fault, interrupt handlers)4October 31, 2001 CSE 120 – Lecture 9 – Paging 7(IILFLHQW7UDQVODWLRQV(IILFLHQW7UDQVODWLRQV● Our original page table scheme already doubled the cost of doing memory lookups◆ One lookup into the page table, another to fetch the data● Now two-level page tables triple the cost!◆ Two lookups into the page tables, a third to fetch the data◆ And this assumes the page table is in memory● How can we use paging but also have lookups cost about the same as fetching from memory?◆ Cache translations in hardware◆ Translation Lookaside Buffer (TLB)◆ TLB managed by Memory Management Unit (MMU)October 31, 2001 CSE 120 – Lecture 9 – Paging 87/%V7/%V● Translation Lookaside Buffers◆ Translate virtual page #s into PTEs (not physical addrs)◆ Can be done in a single machine cycle● TLBs implemented in hardware◆ Fully associative cache (all entries looked up in parallel)◆ Cache tags are virtual page numbers◆ Cache values are PTEs (entries from page tables)◆ With PTE + offset, can directly calculate physical address● TLBs exploit locality◆ Processes only use a handful of pages at a time» 16-48 entries/pages (64-192K)» Only need those pages to be “mapped”◆ Hit rates are therefore very important5October 31, 2001 CSE 120 – Lecture 9 – Paging 90DQDJLQJ0DQDJLQJ7/%V7/%V● Address translations for most instructions are handled using the TLB◆ >99% of translations, but there are misses (TLB miss)…● Who places translations into the TLB (loads the TLB)?◆ Hardware (Memory Management Unit)» Knows where page tables are in main memory» OS maintains tables, HW accesses them directly» Tables have to be in HW-defined format (inflexible)◆ Software loaded TLB (OS)» TLB faults to the OS, OS finds appropriate PTE, loads it in TLB» Must be fast (but still 20-200 cycles)» CPU ISA has instructions for manipulating TLB» Tables can be in any format convenient for OS (flexible)October 31, 2001 CSE 120 – Lecture 9 – Paging 100DQDJLQJ0DQDJLQJ7/%V7/%V● OS ensures that TLB and page tables are consistent◆ When it changes the protection bits of a PTE, it needs to invalidate the PTE if it is in the TLB● Reload TLB on a process context switch◆ Invalidate all entries◆ Why? What is one way to fix it?● When the TLB misses and a new PTE has to be loaded, a cached PTE must be evicted◆ Choosing PTE to evict is called the TLB replacement policy◆ Implemented in hardware, often simple (e.g., Last-Not-Used)6October 31, 2001 CSE 120 – Lecture 9 – Paging 113DJHG9LUWXDO0HPRU\3DJHG9LUWXDO0HPRU\● We’ve mentioned before that pages can be moved between memory and disk◆ This process is called demand paging● OS uses main memory as a page cache of all the data allocated by processes in the system◆ Initially, pages are allocated from memory◆ When memory fills up, allocating a page in memory requires some other page to be evicted from memory» Why physical memory pages are called “frames”◆ Evicted pages go to disk (where? the swap file)◆ The movement of pages between memory and disk is done by the OS, and is transparent to the applicationOctober 31, 2001 CSE 120 – Lecture 9 – Paging 123DJH)DXOWV3DJH)DXOWV● What happens when a process accesses a page that has been evicted?1. When it evicts a page, the OS sets the PTE as invalid and stores the location of the page in the swap file in the PTE2. When a process accesses the page, the invalid PTE will cause a trap (page fault)3. The trap will run the OS page fault handler4. Handler uses the invalid PTE to locate page in swap file5. Reads page into a physical frame, updates
View Full Document
Unlocking...