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 49Slide 50Slide 51Slide 52Slide 5315-410, S’04- 1 -Virtual Memory #1Feb. 23, 2004Dave EckhardtDave EckhardtBruce MaggsBruce MaggsL17_VM115-410“...The only way to win is not to play...”15-410, S’04- 1 -SynchronizationMid-termMid-termWednesday, 19:00, 7500 WeanDoes not cover today's lectureFinal Exam list postedFinal Exam list postedYou must notify us of conflicts in a timely fashionSummer internship with SCS Facilities?Summer internship with SCS Facilities?15-410, S’04- 1 -OutlineThe Problem: logical vs. physicalThe Problem: logical vs. physicalContiguous memory mappingContiguous memory mappingFragmentationFragmentationPagingPagingType theorySeveral mapping functionsTLBTLB15-410, S’04- 1 -Logical vs. PhysicalIt's all about address spacesIt's all about address spacesGenerally a complex issueIPv4 IPv6 is mainly about address space exhaustionReviewReviewCombining .o's changes addressesBut what about But what about twotwo programs? programs?15-410, S’04- 1 -Every .o uses same address spacecodedatabsscodedatabss15-410, S’04- 1 -Combining .o's Changes Addressescodedatabsscodedatabss15-410, S’04- 1 -What about two programs?codedatabss000100000001020000010300stack FFFFF000codedatabss000100000001010000010300stack FFFFE00015-410, S’04- 1 -Logical vs. Physical AddressesLogical addressLogical addressEach program has its own address spacefetch: address datastore: address, data . As envisioned by programmer, compiler, linkerPhysical addressPhysical addressWhere your program ends up in memoryThey can't all be loaded at 0x10000!15-410, S’04- 1 -Reconciling Logical, PhysicalOk, load programs at Ok, load programs at differentdifferent addresses addressesRequires using linker to “relocate one last time”Done by some old mainframe OSsSlow, complex, or bothPrograms can Programs can take turnstake turns in memory in memoryRequires swapping programs out to diskVery slowWe are computer scientists!We are computer scientists!Insert a level of indirectionWell, get the ECE folks to do it for us15-410, S’04- 1 -Type TheoryPhysical memory behaviorPhysical memory behaviorfetch: address datastore: address, data . Process thinks of memory as...Process thinks of memory as...fetch: address datastore: address, data . Goal: each process has “its own memory”Goal: each process has “its own memory”fetch: process-id (address data)store: process-id (address, data . )What What reallyreally happens happensprocess-id (virtual-address physical-address)15-410, S’04- 1 -Simple Mapping FunctionsP1P1If V > 8191 ERRORElse P = 1000 + VP2P2If V > 16383 ERRORElse P = 9292 + VAddress space ===Address space ===Base addressLimitProcess 3Process 2Process 1OS Kernel016383929225675081911000929115-410, S’04- 1 -Contiguous Memory MappingProcessor contains two Processor contains two control registerscontrol registersMemory baseMemory limitEach memory access checksEach memory access checksIf V < limit P = base + V;Else ERROR /* what do we call this error? */Context switchContext switchSave/load registersLoad process's base, limit registers15-410, S’04- 1 -Problems with Contiguous AllocationHow do we How do we growgrow a process? a process?Must increase “limit” valueCannot expand into another process's memory!Must move entire address spaces aroundVery expensiveFragmentationFragmentationNew processes may not fit into unused memory “holes”Partial memory residencePartial memory residenceMust entire program be in memory at same time?15-410, S’04- 1 -Can We Run Process 4?Process exit creates Process exit creates “holes”“holes”New processes may be New processes may be too largetoo largeMay require moving entire May require moving entire address spacesaddress spacesProcess 3Process 4OS KernelProcess 115-410, S’04- 1 -External FragmentationFree memory in small Free memory in small chunkschunksDoesn't fit large objectsDoesn't fit large objectsCan disable lots of Can disable lots of memorymemoryCan fixCan fixCostly “compaction”Process 4Process 1OS KernelProcess 215-410, S’04- 1 -Internal FragmentationAllocators often round upAllocators often round up8K boundary (some power of 2!)Some memory is wasted Some memory is wasted insideinside each segment each segmentCan't fix via compactionCan't fix via compactionEffects often non-fatalEffects often non-fatalProcess 3Process 4Process 1OS Kernel081921100929215-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 diskNot runnableBlocked on implicit I/O request (e.g., “swapread”)“Swap daemon” shuffles process in & outCan take seconds per processModern analogue: laptop suspend-to-disk15-410, S’04- 1 -Contiguous Allocation PagingSolve multiple problemsSolve multiple problemsProcess growth problemFragmentation compaction problemLong delay to swap a whole processDivide memory more finelyDivide memory more finelyPage = small region of virtual memory (4K)Frame = small region of physical memory[I will get this wrong, feel free to correct me]Key idea!!!Key idea!!!Any page can map to (occupy) any frame15-410, S’04- 1 -Per-process Page MappingP0 code 0OS KernelP1 code 0P0 data 0P1 data 0P1 stack 0P0 stack 0P1 data 1P0 code 1P0 code 0P0 code 1P0 data 0P0 stack 0P1 code 0P1 data 0P1 data 1P1 stack 015-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
View Full Document