Lecture 11:Lecture 11:PagingPagingCSE 120: Principles of Operating SystemsAlex C. SnoerenHW 3 due 11/10CSE 120 – Lecture 112Lecture OverviewLecture OverviewToday 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 filesCSE 120 – Lecture 113Managing Page TablesManaging Page Tables Last lecture we computed the size of the page tablefor 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 addressspace 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 tablesCSE 120 – Lecture 114Two-Level Page TablesTwo-Level Page Tables Last time, virtual addresses (VAs) had two parts◆ Page number (which mapped to frame) and an offset Now VAs have three parts:◆ Master page number, secondary page number, and offset Master page table maps VAs to secondary page table◆ We’d like a manageable master page size Secondary table maps page number to physical page◆ Determines which physical frame the address resides in Offset indicates which byte in physical page◆ Final system page/frame size is still the same, so offset lengthstays the sameCSE 120 – Lecture 115Virtual AddressPhysical AddressTwo-Level Page TablesTwo-Level Page TablesPage tableMaster page number SecondaryMaster Page TablePage frame OffsetPhysical MemoryOffsetPage frameSecondary Page TableCSE 120 – Lecture 116Virtual AddressPhysical AddressAnAn Example w/4-byteExample w/4-byte PTEsPTEsPage tableMaster page number SecondaryMaster Page TablePage frame OffsetPhysical MemoryOffsetPage frameSecondary Page Table4K pages = 12-bit offset; 1 master page = 4K/4 = 1K entries = 10bitsSecondary page table size = 32 - 12 - 10 = 10 bits = 1K entries * 4 = 4K10 bits1Kentries12 bits12 bits10 bits1KentriesCSE 120 – Lecture 117Where Do Page Tables Live?Where Do Page Tables Live? 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 wellpage the entire OS address space, too◆ Need to wire special code and data (fault, interrupt handlers)CSE 120 – Lecture 118Efficient TranslationsEfficient Translations Our original page table scheme already doubled thecost 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 costabout the same as fetching from memory?◆ Cache translations in hardware◆ Translation Lookaside Buffer (TLB)◆ TLB managed by Memory Management Unit (MMU)CSE 120 – Lecture 119TLBsTLBs Translation Lookaside Buffers◆ Translate virtual page #s into PTEs (not physical addresses)◆ 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 importantCSE 120 – Lecture 1110Loading Loading TLBsTLBs Most address translations are handled using the TLB◆ >99% of translations, but there are misses (TLB miss)… Who places translations into the TLB (loads the TLB)?◆ 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)◆ Hardware (Memory Management Unit)» Must know where page tables are in main memory» OS maintains tables, HW accesses them directly» Tables have to be in HW-defined format (inflexible)CSE 120 – Lecture 1111Managing Managing TLBsTLBs OS ensures that TLB and page tables are consistent◆ When it changes the protection bits of a PTE, it needs toinvalidate 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 beloaded, 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)CSE 120 – Lecture 1112Paged Virtual MemoryPaged Virtual Memory We’ve mentioned before that pages can be movedbetween memory and disk◆ This process is called demand paging OS uses main memory as a page cache of all the dataallocated by processes in the system◆ Initially, pages are allocated from memory◆ When memory fills up, allocating a page in memory requiressome other page to be evicted from memory» Why physical memory pages are called “frames”◆ Evicted pages go to disk (where? the swap file/partition)◆ The movement of pages between memory and disk is doneby the OS, and is transparent to the applicationCSE 120 – Lecture 1113Page FaultsPage Faults What happens when a process accesses a page thathas been evicted?1. When it evicts a page, the OS sets the PTE as invalid andstores the location of the page in the swap file in the PTE2. When a process accesses the page, the invalid PTE willcause 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 PTE to point to it6. Restarts process But where does it put it? Has to evict something else◆ OS usually keeps a pool of free pages around so thatallocations do not always cause evictionsCSE
View Full Document
Unlocking...