CSE 380 Computer Operating SystemsVirtual MemoryVirtual Memory Paging (1)PagingPaging (2)Virtual Memory in UnixPagingPage Table EntryPage Tables (1)Design IssuesMulti-Level PagingPaging in LinuxTranslation Lookaside Buffer (TLB)More on TLBInverted Page TablesHashed Page TablesSteps in PagingPage Fault HandlingPaging SummaryPage Replacement AlgorithmsReference StringForward and backward distancesPaging Replacement AlgorithmsOptimal Page Replacement AlgorithmFirst AttemptsQueue Based AlgorithmsSecond Chance Page ReplacementClock AlgorithmLeast Recently Used (LRU)How to implement LRU?Approximating LRU: AgingAging IllustrationAnalysis of Paging AlgorithmsEffect of replacement policyBelady’s AnomalyStack AlgorithmsSlide 38Locality of ReferenceLocalityWorking SetSlide 42Virtual Time and Working SetWSClock Replacement AlgorithmWSClock AlgorithmSlide 46Page Replacement in UnixUNIX and SwappingLocal Vs Global PolicyPFF (page Fault Frequency)Data structure on page faultsWhat’s a good page size ?Page SizeThm. (Optimal Page Size)Page size examplesSharing of PagesShared Pages with separate page tablesSegmentationSlide 60AdvantagesSegmentation with PagingMultics: Segmentation+ PagingMultics MemoryMultics details contPentiumPaging in Pentium1CSE 380Computer Operating SystemsInstructor: Insup LeeUniversity of PennsylvaniaFall 2003Lecture Note: Virtual Memory(revised version)2Virtual MemoryRecall: memory allocation with variable partitions requires mapping logical addresses to physical addresses Virtual memory achieves a complete separation of logical and physical address-spacesToday, typically a virtual address is 32 bits, this allows a process to have 4GB of virtual memoryPhysical memory is much smaller than this, and varies from machine to machineVirtual address spaces of different processes are distinctStructuring of virtual memoryPaging: Divide the address space into fixed-size pagesSegmentation: Divide the address space into variable-size segments (corresponding to logical units)3Virtual MemoryPaging (1)The position and function of the MMU4PagingPhysical memory is divided into chunks called page-frames (on Pentium, each page-frame is 4KB)Virtual memory is divided into chunks called pages; size of a page is equal to size of a page frameSo typically, 220 pages (a little over a million) in virtual memoryOS keeps track of mapping of pages to page-framesSome calculations:10-bit address : 1KB of memory; 1024 addresses20-bit address : 1MB of memory; about a million addresses30-bit address : 1 GB of memory; about a billion addresses5Paging (2)The relation betweenvirtual addressesand physical memory addres-ses given bypage table6Virtual Memory in Unix Process AVirtual spaceProcess BVirtual space7Paging A virtual address is considered as a pair (p,o)Low-order bits give an offset o within the pageHigh-order bits specify the page pE.g. If each page is 1KB and virtual address is 16 bits, then low-order 10 bits give the offset and high-order 6 bits give the page numberThe job of the Memory Management Unit (MMU) is to translate the page number p to a frame number fThe physical address is then (f,o), and this is what goes on the memory busFor every process, there is a page-table (basically, an array), and page-number p is used as an index into this array for the translation8Page Table Entry1. Validity bit: Set to 0 if the corresponding page is not in memory2. Frame numberNumber of bits required depends on size of physical memory3. Protection bits:Read, write, execute accesses4. Referenced bit is set to 1 by hardware when the page is accessed: used by page replacement policy5. Modified bit (dirty bit) set to 1 by hardware on write-access: used to avoid writing when swapped out9Page Tables (1)Internal operation of MMU with 16 4 KB pages10Design IssuesWhat is the “optimal” size of a page frame ?Typically 1KB – 4KB, but more on this laterHow to save space required to store the page tableWith 20-bit page address, there are over a million pages, so the page-table is an array with over million entriesSolns: Two-level page tables, TLBs (Translation Lookaside Beffers), Inverted page tablesWhat if the desired page is not currently in memory?This is called a page fault, and it traps to kernelPage daemon runs periodically to ensure that there is enough free memory so that a page can be loaded from disk upon a page faultPage replacement policy: how to free memory?11Multi-Level PagingKeeping a page-table with 220 entries in memory is not viableSolution: Make the page table hierarchicalPentium supports two-level pagingSuppose first 10-bits index into a top-level page-entry table T1 (1024 or 1K entries)Each entry in T1 points to another, second-level, page table with 1K entries (4 MB of memory since each page is 4KB)Next 10-bits of physical address index into the second-level page-table selected by the first 10-bitsTotal of 1K potential second-level tables, but many are likely to be unusedIf a process uses 16 MB virtual memory then it will have only 4 entries in top-level table (rest will be marked unused) and only 4 second-level tables12Paging in LinuxLinux uses three-level page tables13Translation Lookaside Buffer (TLB)Page-tables are in main memoryAccess to main memory is slow compared to clock cycle on CPU (10ns vs 1 ns)An instruction such as MOVE REG, ADDR has to decode ADDR and thus go through page tablesThis is way too slow !!Standard practice: Use TLB stored on CPU to map pages to page-framesTLB stores small number (say, 64) of page-table entries to avoid the usual page-table lookupTLB is associative memory and contains, basically, pairs of the form (page-no, page-frame)Special hardware compares incoming page-no in parallel with all entries in TLB to retrieve page-frameIf no match found in TLB, standard look-up invoked14More on TLBKey design issue: how to improve hit rate for TLB?Which pages should be in TLB: most recently accessedWho should update TLB?Modern architectures provide sophisticated hardware support to do thisAlternative: TLB miss generates a fault and invokes OS, which then decides how to use the TLB entries effectively.Page numberFrame numberModified bitProtection bits15Inverted Page TablesWhen virtual memory is much larger than physical memory, overhead of storing page-table is highFor example, in 64-bit machine