Virtual to physical address translationVirtual memory with paging Page table per process Page table entry includes  present bit frame number modify bit flags for protection and sharing. Page tables can be huge an entry per page of the process large processes -- larger than main memory Page table itself is placed in virtual memory2Program execution For a program to execute, the following must be present in main memory the relevant portion of the page table  the starting instructions of the process  the relevant data of the process  The page table descriptor is usually in a processor register Has a pointer to the page table3General address translation4CPUMMUcachevirtual addressPhysicaladdressdataGlobal memoryMemory management unit Translates Virtual Addresses page tables translation lookaside buffer (TLB) Page tables One for kernel addresses one or more for user space processes Page Table Entry (PTE) for user space processes Typically 32 bits  page frame, protection, valid, modified, referenced5Address translation  Virtual address:  A logical address Virtual page number + offset Finds PTE for virtual page number Extract frame number and adds offset Fail (MMU raises an exception - page fault): bounds error - outside address range validation error - non-resident page protection error - not permitted access6Address translation example712 bits20 bitsvirtual page numberoffset in pagecurrent page table register(Process) Page Tableaddframe numberMRcontrol bitsDRAMFramesX offsetFrame XPTEVirtual addressReal addressTwo-level page table8Example with two-level page tableConsider a process as described here: Logical address space is 4-GB (232 bytes) Size of a page is 4KB (212bytes) There are ___ pages in the process.  This implies we need ____ page table entries in the process page table. If each page table entry occupies 4-bytes, then we need a ______ byte large page table The page table will occupy __________ pages. Root table will consist of ____ entries  one for each page that holds part of the process page table Root table will occupy 212bytes  4KB of space will be kept in main memory permanently A page access could require two disk accesses9Example with two-level page tableConsider a process as described here: Logical address space is 4-GB (232) Size of a page is 4KB (212bytes) There are 220pages in the process. (232/212) This implies we need 220page table entries in the process page table, one entry per page. If each page table entry occupies 4-bytes, then we need a 222byte (4MB) large page table. The page table will occupy 222/212i.e. 210pages. Root table will consist of 210entries  one for each page that holds a part of the process page table Root table will occupy 212bytes  4KB of space will be kept in main memory permanently A page access could require two disk accesses1011Always in main memoryBrought into main memory as neededInverted page table The page table can get very large  An inverted page table is another solution An inverted page table has an entry for every frame in main memory and hence is of a fixed size This is why it is called an inverted page table A hash function is used to map the page number (and process number) to the frame number A PTE has  a page number, process id, valid bit, modify bit, chain pointer12Inverted page table13matches Page # and PIDOffsetFrame #OffsetV M PID,Page #Virtual Address Physical AddressPage FrameProgramPaging HardwareMemoryInvertedPage TablePage #<PID, Page #>SearchFrame #Inverted page table with hashing14matches Page # and PIDOffsetFrame #OffsetV M PID,Page #Virtual Address Physical AddressPage FrameProgramPaging HardwareMemoryInvertedPage TablePage #<PID, Page #>SearchHashHash TableSynonym ChainHashing techniques15(b) Chained rehashingHashing function: X mod 8Memory management concerns Problem:  Page tables require at least 2 memory access per instruction  One to fetch the page table entry One to fetch the data Solution: Translation Lookaside Buffer (TLB) A high-speed HW associative cache set up for page table entries  Cache the address translations themselves 16TLB details Associative cache of address translations Entries may contain a tag identifying the process as well as the virtual address.  Why is this important? MMU typically manages the TLB17More TLB details Contains page table entries that have been most recently used Functions same way as a memory cache Given a virtual address, processor examines the TLB If present (TLB hit), the frame number is retrieved and the real address is formed  No memory access If not found (TLB miss), page number is used to index the process page table Memory access TLB updated to include new PTE18Address translation with TLB19VirtualaddressMMUPage tablesphysicaladdresscacheCPUTLBPage Table PtrPage TableAssociative cache20Direct page lookup Associative page lookupTypical TLB use21TLB use with memory cache22Access time example with TLB In tlb = 10ns (TLB) + 100ns (data) not in TLB: 10ns (TLB) + 100 (PT) + 100ns (data) Average access time = 110ns (.90) + (1-.90) * 210ns = 120ns23Typical TLB parameters24Block Size 4 to 8 bytes (1 page entry)Hit Time 2.5 to 5 nsec (1 clock cycle)Miss Penalty 50 to 150 nsecTLB Size 32 bytes to 8 KBDesired Hit Rate 98% to 99.9%HW/SW decisions: page size Smaller page size less amount of internal fragmentation more pages required per process More pages per process  means larger page tables Larger page tables  means large portion of page tables in virtual memory Secondary memory is designed to efficiently transfer large blocks of data so a large page size is better25Page size Smaller page size means large number of pages will be found in main memory As time goes on during execution the pages in memory will all contain portions of the process most recent references  Low page faults Increased page size causes  pages to contain locations further from any recent reference  page faults to rise26Page size (2)27Page fault rate28Page size revisited Multiple page sizes are supported by many architectures Multiple page sizes provide the flexibility needed to effectively use a TLB Large pages can be used for program instructions Small pages can be used for threads