Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 4715-410, S’04- 1 -Virtual Memory #2Mar. 1, 2004Dave EckhardtDave EckhardtBruce MaggsBruce MaggsL19_VM215-410“...The only way to win is not to play...”15-410, S’04- 1 -SynchronizationCheckpoint 1Checkpoint 1Wednesday 23:59Final Exam list postedFinal Exam list postedYou must notify us of conflicts in a timely fashion15-410, S’04- 1 -Last TimeMapping problem: logical vs. physical addressesMapping problem: logical vs. physical addressesContiguous memory mapping (base, limit)Contiguous memory mapping (base, limit)Swapping – taking turns in memorySwapping – taking turns in memoryPagingPagingArray mapping page numbers to frame numbersObservation: typical table is sparsely occupiedResponse: some sparse data structure (e.g., 2-level array)TLB – cache of virtual TLB – cache of virtual physical mappings physical mappingsSoftware-loaded TLBSoftware-loaded TLB15-410, S’04- 1 -SwappingMultiple user processesMultiple user processesSum of memory demands > system memoryGoal: Allow each process 100% of system memoryTake turnsTake turnsTemporarily evict process(es) to disk“Swap daemon” shuffles process in & outCan take seconds per processCreates external fragmentation problem15-410, S’04- 1 -External Fragmentation (“Holes”)Process 3Process 4Process 1OS KernelProcess 2Process 3Process 4Process 1OS KernelProcess 215-410, S’04- 1 -Benefits of PagingProcess growth problemProcess growth problemAny process can use any free frame for any purposeFragmentation compaction problemFragmentation compaction problemProcess doesn't need to be contiguousLong delay to swap a whole processLong delay to swap a whole processSwap part of the process instead!15-410, S’04- 1 -Partial ResidenceP0 code 0OS Kernel[free]P0 data 0P1 data 0P1 stack 0P0 stack 0P1 data 1[free]P0 code 0P0 code 1P0 data 0P0 stack 0P1 code 0P1 data 0P1 data 1P1 stack 015-410, S’04- 1 -Page Table Entry (PTE) flagsProtection bits – set by OSProtection bits – set by OSRead/write/executeValid/Present bit – set by OSValid/Present bit – set by OSFrame pointer is valid, no need to faultDirty bitDirty bitHardware sets 01 when data stored into pageOS sets 10 when page has been written to diskReference bitReference bitHardware sets 01 on any data access to pageOS uses for page eviction (below)15-410, S’04- 1 -OutlinePartial memory residence (demand paging) in actionPartial memory residence (demand paging) in actionThe task of the page fault handlerThe task of the page fault handlerBig speed hacksBig speed hacksSharing memory regions & filesSharing memory regions & filesPage replacement policiesPage replacement policies15-410, S’04- 1 -Partial Memory ResidenceError-handling code not used by every runError-handling code not used by every runNo need for it to occupy memory for entire duration...Tables may be allocated larger than usedTables may be allocated larger than usedplayer players[MAX_PLAYERS];Can run Can run veryvery large programs large programsMuch larger than physical memoryAs long as “active” footprint fits in RAMSwapping can't do thisPrograms can launch fasterPrograms can launch fasterNeedn't load whole program before running15-410, S’04- 1 -Demand PagingUse RAM frames as a cache for the set of all pagesUse RAM frames as a cache for the set of all pagesPage tables indicate which pages are residentPage tables indicate which pages are residentNon-resident pages have “present=0” in page table entryMemory access referring to page generates page faultHardware invokes page fault exception handler15-410, S’04- 1 -Page fault - Why?Address is invalid/illegal – deliver Address is invalid/illegal – deliver software exceptionsoftware exceptionUnix – SIGSEGVMach – deliver message to thread's exception port15-410 – kill threadProcess is growing stack – give it a new frameProcess is growing stack – give it a new frame““Cache misses” - fetch from diskCache misses” - fetch from diskWhere?15-410, S’04- 1 -Satisfying Page FaultscodedatabssstackFilesystemPaging SpaceFree-frame pool15-410, S’04- 1 -Page fault story - 1Process issues memory referenceProcess issues memory referenceTLB: miss (right?)PT: “not present”TrapTrap to OS kernel! to OS kernel!Dump trap frameTransfer via “page fault” interrupt descriptorRun trap handler15-410, S’04- 1 -Page fault story – 2Classify fault address: legal/illegalClassify fault address: legal/illegalCode/rodata region of executable?Code/rodata region of executable?Determine which sector of executable fileLaunch read() into a blank framePreviously resident, paged outPreviously resident, paged out“somewhere on the paging partition”Queue disk read into a blank frameFirst use of bss/stack pageFirst use of bss/stack pageAllocate a zero frame, insert into PT15-410, S’04- 1 -Page fault story – 3Put process to sleep (for most cases)Put process to sleep (for most cases)Switch to running anotherHandle I/O-complete interruptHandle I/O-complete interruptFill in PTE (present = 1)Mark process runnableRestore registers, switch page tableRestore registers, switch page tableFaulting instruction re-started transparentlySingle instruction may fault more than once!15-410, S’04- 1 -Memory Regions vs. Page TablesWhat's a poor page fault handler to do?What's a poor page fault handler to do?Kill process?Copy page, mark read-write?Fetch page from file? Which? Where?Page Table not a good data structurePage Table not a good data structureFormat defined by hardwarePer-page nature is repetitiveNot enough bits to encode OS metadataDisk sector address can be > 32 bits15-410, S’04- 1 -Dual-view Memory ModelLogicalLogicalProcess memory is a list of regions“Holes” between regions are illegal addressesPer-region methodsfault(), evict(), unmap()PhysicalPhysicalProcess memory is a list of pagesFaults delegated to per-region methodsMany “invalid” pages can be made validBut sometimes a region
View Full Document