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 47Slide 48Slide 4915-410, F’04- 1 -Virtual Memory #2Oct. 8, 2004Dave EckhardtDave EckhardtBruce MaggsBruce MaggsL16_VM215-410“...The cow and Zaphod...”15-410, F’04- 1 -SynchronizationProject 2 due tonightProject 2 due tonightPlease check “make html_doc” and “make print” are okPlease put your files in mygroup/p2not mygroup/p2/p2not mygroup/p2/our_project_2not mygroup/p2/p2_tar_fileUse the late-day request page to request late days (if)Don't mail us files15-410, F’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)15-410, F’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, F’04- 1 -External Fragmentation (“Holes”)Process 3Process 4Process 1OS KernelProcess 2Process 3Process 4Process 1OS KernelProcess 215-410, F’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, F’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, F’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, F’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, F’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];Computer can run Computer 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, F’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 pagesSome pages are fast to access (in a RAM frame)Some pages are slow to access (in a disk “frame”)Page tables indicate which pages are “resident”Page tables indicate which pages are “resident”Non-resident pages have “present=0” in page table entryMemory access referring to page generates page faultHardware invokes page-fault exception handler15-410, F’04- 1 -Page fault – Reasons, ResponsesAddress 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 on disk, exactly?15-410, F’04- 1 -Satisfying Page FaultscodedatabssstackFilesystemPaging SpaceFree-frame pool15-410, F’04- 1 -Page fault story - 1Process issues memory referenceProcess issues memory referenceTLB: missPT: “not present”TrapTrap to OS kernel! to OS kernel!Processor dumps trap frameTransfers via “page fault” interrupt descriptor table entryRuns trap handler15-410, F’04- 1 -Page fault story – 2Classify fault addressClassify fault addressIllegal address deliver an ouch, else...Code/rodata region of executable?Code/rodata region of executable?Determine which sector of executable fileLaunch read() from file into an unused framePreviously resident r/w data, paged outPreviously resident r/w data, paged out“somewhere on the paging partition”Queue disk read into an unused frameFirst use of bss/stack pageFirst use of bss/stack pageAllocate a frame full of zeroes, insert into PT15-410, F’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, F’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, F’04- 1 -Dual-view Memory ModelLogicalLogicalProcess memory is a list of
View Full Document