15-410, F’04- 1 -Virtual Memory #1Oct. 6, 2004Dave EckhardtDave EckhardtBruce MaggsBruce MaggsL15_VM115-410“...We are Computer Scientists!...”15-410, F’04- 2 -SynchronizationMid-term ExamMid-term ExamIn-class?Evening?“Mid-term week”: Wednesday 20th? Thursday 21st?“Project 3 week”: Wednesday 13th? Thursday 14th?You will soon receive coordination mail—act immediately!Reminder: Book reportReminder: Book reportPlease don't complain end-of-semester due date!Thinking about the futureThinking about the futureSummer internship with SCS Facilities?15-412, OS Practicum15-410, F’04- 3 -OutlineTextTextChapters 9, 10The Problem: logical vs. physicalThe Problem: logical vs. physicalContiguous memory mappingContiguous memory mappingFragmentationFragmentationPagingPagingType theoryA sparse map15-410, F’04- 4 -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 two programs?15-410, F’04- 5 -Every .o uses same address spacecodedatabsscodedatabss15-410, F’04- 6 -Linker Combines .o's, Changes Addressescodedatabsscodedatabss15-410, F’04- 7 -What about two programs?codedatabss000100000001020000010300stack FFFFF000codedatabss000100000001010000010300stack FFFFE00015-410, F’04- 8 -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, F’04- 9 -Reconciling Logical, PhysicalCould run programs at Could run programs at differentdifferent addresses addressesRequires using linker to “relocate one last time”Done by some old mainframe OSsSlow, complex, or bothPrograms could Programs could 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, F’04- 10 -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”process-id ⇒ fetch: (address ⇒ data)process-id ⇒ store: (address, data ⇒ . )What What reallyreally happens happensprocess-id ⇒ (virtual-address ⇒ physical-address)15-410, F’04- 11 -Simple Mapping FunctionsP1P1If V > 8191 ERRORElse P = 1000 + VP2P2If V > 16383 ERRORElse P = 9292 + VAddress space ===Address space ===Base addressLimitProcess 3Process 2Process 1OS Kernel016383919225575081911000919109990999VirtualPhysical15-410, F’04- 12 -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 user-visible registersAlso load process's base, limit registers15-410, F’04- 13 -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 around Very expensiveFragmentationFragmentationNew processes may not fit into unused memory “holes”Partial memory residencePartial memory residenceMust entire program be in memory at same time?15-410, F’04- 14 -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, F’04- 15 -Term: External FragmentationFree memory is small Free memory is small chunkschunksDoesn't fit large objectsDoesn't fit large objectsCan “disable” lots of Can “disable” lots of memorymemoryCan fixCan fixCostly “compaction” aka “Stop & copy”Process 4Process 1OS KernelProcess 215-410, F’04- 16 -Term: 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, F’04- 17 -SwappingMultiple user processesMultiple user processesSum of memory demands > system memoryGoal: Allow each process 100% of system memoryTake turnsTake turnsTemporarily evict process(es) to disk Not runnable Blocked on implicit I/O request (e.g., “swapread”)“Swap daemon” shuffles process in & outCan take seconds per process Modern analogue: laptop suspend-to-disk15-410, F’04- 18 -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, F’04- 19 -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, F’04- 20 -Problems Solved by 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- 21 -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- 22 -New Data StructureContiguous allocationContiguous allocationEach process described by
View Full Document
Unlocking...