11CSE 380Computer Operating SystemsInstructor: Insup LeeUniversity of PennsylvaniaFall 2003Lecture Note: Virtual Memory(revised version)2Virtual Memory Recall: memory allocation with variable partitions requiresmapping logical addresses to physical addresses Virtual memory achieves a complete separation of logical andphysical address-spaces Today, typically a virtual address is 32 bits, this allows aprocess to have 4GB of virtual memory Physical memory is much smaller than this, and varies frommachine 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-sizesegments (corresponding to logical units)3Virtual MemoryPaging (1)The position and function of the MMU4Paging Physical memory is divided into chunks called page-frames (onPentium, each page-frame is 4KB) Virtual memory is divided into chunks called pages; size of apage 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 addresses25Paging (2)The relation betweenvirtual addressesand physicalmemory addres-ses given bypage table6Virtual Memory in UnixProcess 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, thenlow-order 10 bits give the offset and high-order 6 bits givethe page number The job of the Memory Management Unit (MMU) is totranslate the page number p to a frame number f The physical address is then (f,o), and this is what goes on thememory bus For every process, there is a page-table (basically, an array),and page-number p is used as an index into this array forthe translation8Page Table Entry1. Validity bit: Set to 0 if the corresponding page is not inmemory2. 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 isaccessed: used by page replacement policy5. Modified bit (dirty bit) set to 1 by hardware on write-access:used to avoid writing when swapped out39Page 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 thepage-table is an array with over million entries Solns: Two-level page tables, TLBs (Translation LookasideBeffers), 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 enoughfree memory so that a page can be loaded from disk upon apage 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 1Kentries) Each entry in T1 points to another, second-level, page table with 1Kentries (4 MB of memory since each page is 4KB) Next 10-bits of physical address index into the second-level page-tableselected 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 intop-level table (rest will be marked unused) and only 4 second-level tables12Paging in LinuxLinux uses three-level page tables413Translation Lookaside Buffer (TLB) Page-tables are in main memory Access to main memory is slow compared to clock cycle onCPU (10ns vs 1 ns) An instruction such as MOVE REG, ADDR has to decodeADDR and thus go through page tables This is way too slow !! Standard practice: Use TLB stored on CPU to map pagesto page-frames TLB stores small number (say, 64) of page-table entries toavoid the usual page-table lookup TLB is associative memory and contains, basically, pairs ofthe form (page-no, page-frame) Special hardware compares incoming page-no in parallelwith 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 supportto 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 physicalmemory, overhead of storing page-table is high For example, in 64-bit machine with 4KB per page and256 MB memory, there are 64K page-frames but 252pages ! Solution: Inverted page tables that store entries of theform (page-frame, process-id, page-no) At most 64K entries required! Given a page p of process x, how to find thecorresponding page frame? Linear search is too slow, so use hashing Note: issues like hash-collisions must be handled Used in some IBM and HP workstations; will be usedmore with 64-bit machines16Hashed Page TablesPage numberOffsetHashPage#Frame #Hash tableNumber of entries: Number of page framesPIDPID517Steps in Paging Today’s typical systems use TLBs and multi-level paging Paging requires special hardware support Overview of steps1. Input to MMU: virtual address = (page p, offset o)2. Check if there is a frame f with (p,f) in TLB3. If so, physical address is (f,o)4. If not, lookup page-table in main memory ( a couple ofaccesses due to multi-level paging)5. If page is present, compute physical address6. If not, trap to kernel to process page-fault7. Update TLB/page-table entries (e.g. Modified bit)18Page Fault Handling Hardware traps to kernel on page fault CPU registers of current process are saved OS determines which