15-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- 2 -SynchronizationCheckpoint 1Checkpoint 1Wednesday 23:59Final Exam list postedFinal Exam list postedYou must notify us of conflicts in a timely fashion15-410, S’04- 3 -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- 4 -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- 5 -External Fragmentation (“Holes”)Process 3Process 4Process 1OS KernelProcess 2Process 3Process 4Process 1OS KernelProcess 215-410, S’04- 6 -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- 7 -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- 8 -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 0⇒1 when data stored into pageOS sets 1⇒0 when page has been written to diskReference bitReference bitHardware sets 0⇒1 on any data access to pageOS uses for page eviction (below)15-410, S’04- 9 -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- 10 -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- 11 -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- 12 -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 disk“Cache misses” - fetch from diskWhere?15-410, S’04- 13 -Satisfying Page FaultscodedatabssstackFilesystemPaging SpaceFree-frame pool15-410, S’04- 14 -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- 15 -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- 16 -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- 17 -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 structure Format defined by hardware Per-page nature is repetitive Not enough bits to encode OS metadataDisk sector address can be > 32 bits15-410, S’04- 18 -Dual-view Memory ModelLogicalLogical Process memory is a list of regions “ Holes” between regions are illegal addresses Per-region methodsfault(), evict(), unmap()PhysicalPhysical Process memory is a list of pages Faults delegated to per-region methods Many “ invalid” pages can be made validBut sometimes a region fault handler returns “ error”»Handle as with “ hole” case above15-410, S’04- 19 -Page-fault story (for real)Examine fault addressExamine fault addressLook up: address Look up: address ⇒⇒ region regionregion->fault(addr, access_mode)region->fault(addr, access_mode) Quickly fix up problem Or put process to sleep, run scheduler15-410, S’04- 20 -Demand
View Full Document
Unlocking...