Slide 1Basic Memory Management Concepts Address spacesSlide 3Basic Concepts Address generationProgram RelocationBasic Concepts (Cont’d.) Address TranslationSlide 7Evaluating Dynamic Allocation Techniques The fragmentation problemSimple Memory Management Schemes Dynamic allocation of partitionsFirst Fit AllocationRationale & ImplementationBest Fit AllocationSlide 13Worst Fit AllocationSlide 15Allocation strategiesDynamic Allocation of Partitions Eliminating FragmentationMemory Management Sharing Between ProcessesMultiple Name Spaces Example — Protection/Fault isolation & sharingSupporting Multiple Name Spaces SegmentationImplementing Segmentation Base + Limit register schemeMemory Management Basics Are We Done?1Memory Management Basics2ProgramPBasic Memory Management ConceptsAddress spacesPhysical address space — The address space supported by the hardwareStarting at address 0, going to address MAXsysLogical/virtual address space — A process’s view of its own memoryStarting at address 0, going to address MAXprog0MAXsys0MAXprogMOV r0, @0xfffa620eBut where do addresses come from?3Which is bigger, physical or virtual address space?A. Physical address spaceB. Virtual address spaceC. It depends on the system.4Basic ConceptsAddress generationThe compilation pipelineprog P : : foo() : :end Pprog P : : foo() : :end PP: :push ...inc SP, xjmp _foo :foo: ...P: :push ...inc SP, xjmp _foo :foo: ... :push ...inc SP, 4jmp 75 : ... :push ...inc SP, 4jmp 75 : ...07511001175LibraryRoutines1000175LibraryRoutinesLibraryRoutines0100Compilation Assembly Linking Loading : : :jmp 1175 : ... : : :jmp 175 : ... : : :jmp 175 : ...5Program RelocationProgram issues virtual addressesMachine has physical addresses.If virtual == physical, then how can we have multiple programs resident concurrently?Instead, relocate virtual addresses to physical at run time.While we are relocating, also bounds check addresses for safety.I can relocate that program (safely) in two registers…6Basic Concepts (Cont’d.)Address Translation0MAXsysProgramProgramP’slogicaladdressspaceProgramP’slogicaladdressspace0MAXprog10001500CPUCPU++10001000BaseRegisterLogicalAddresses≤≤500500LimitRegisterMEMORYEXCEPTIONPhysicalAddressesyesnoInstructionsP’sphysicaladdre ssspace7With base and bounds registers, the OS needs a hole in physical memory at least as big as the process.A. TrueB. False8Evaluating Dynamic Allocation TechniquesThe fragmentation problemExternal fragmentationUnused memory between units of allocationE.g, two fixed tables for 2, but a party of 4Internal fragmentationUnused memory within a unit of allocationE.g., a party of 3 ata table for 40MAXProgramR’s PASProgramQ’sPASExecution StackExecution StackProgram Code(“text”)Program Code(“text”)DataDataExecution StackExecution Stack9Simple Memory Management SchemesDynamic allocation of partitionsSimple approach:Allocate a partition when a process is admitted into the systemAllocate a contiguous memory partition to the process0MAXProgramP2ProgramP3ProgramP1P5ProgramP4OS keeps track of...Full-blocksEmpty-blocks (“holes”)Allocation strategiesFirst-fitBest-fitWorst-fit10First Fit Allocation To allocate n bytes, use the first available free block such that the block size is larger than n. 500 bytes1K bytes2K bytesTo allocate 400 bytes,we use the 1st free blockavailable2K bytes500 bytes11Rationale & ImplementationSimplicity of implementationRequires:Free block list sorted by addressAllocation requires a search for a suitable partitionDe-allocation requires a check to see if the freed partition could be merged with adjacent free partitions (if any)AdvantagesSimpleTends to produce larger free blocks toward the end of the address spaceDisadvantagesSlow allocationExternal fragmentation12Best Fit Allocation To allocate n bytes, use the smallest available free block such that the block size is larger than n. 500 bytes1K bytes2K bytesTo allocate 400 bytes,we use the 3rd free blockavailable (smallest)1K bytes2K bytes13Rationale & ImplementationTo avoid fragmenting big free blocksTo minimize the size of external fragments producedRequires:Free block list sorted by sizeAllocation requires search for a suitable partitionDe-allocation requires search + merge with adjacent free partitions, if anyAdvantagesWorks well when most allocations are of small sizeRelatively simpleDisadvantagesExternal fragmentationSlow de-allocationTends to produce many useless tiny fragments (not really great)Doug Lea’s malloc “In most ways this malloc is a best-fit allocator”14Worst Fit Allocation To allocate n bytes, use the largest available free block such that the block size is larger than n. 500 bytes1K bytes2K bytesTo allocate 400 bytes,we use the 2nd free blockavailable (largest)1K bytes15Rationale & ImplementationTo avoid having too many tiny fragmentsRequires:Free block list sorted by sizeAllocation is fast (get the largest partition)De-allocation requires merge with adjacent free partitions, if any, and then adjusting the free block listAdvantagesWorks best if allocations are of medium sizesDisadvantagesSlow de-allocationExternal fragmentationTends to break large free blocks such that large partitions cannot be allocated16Allocation strategiesFirst fit, best fit and worst fit all suffer from external fragmentation.A. TrueB. False17Dynamic Allocation of PartitionsEliminating FragmentationCompactionRelocate programs to coalesce holes0MAXProgramP2ProgramP3ProgramP1ProgramP4SuspendedSuspendedsuspendedqueuereadyqueuesemaphore/condition queuesWaitingWaitingRunningRunningReadyReady? Swapping Preempt processes & reclaim their memory1802n-1ProgramP’sVASMemory ManagementSharing Between ProcessesSchemes so far have considered only a single address space per processA single name space per processNo sharing Program P’sVASProgramDataProgramTextHeapRun-Time StackHow can one share code and data between programs without paging?19Multiple Name SpacesExample — Protection/Fault isolation & sharing02n-102n1-10002n2-12n3-12n4-102n6-1Libraries2n5-10ProgramDataProgramTextHeapRun-Time StackProgramTextProgramDataRun-Time StackHeapUser Code20Supporting Multiple Name SpacesSegmentationNew concept: A segment — a memory “object”A virtual address spaceA process now addresses objects —a pair (s, addr)s — segment