CPSC 410/611 : Operating SystemsMemory Management: Paging / Segmentation 1Memory Management• Address binding– Linking, loading– Logical vs. physical address space• Fragmentation• Paging• Segmentation•Reading: Silberschatz (8th ed.), Chapter 8Memory Management• Observations:– Process needs at least CPU and memory to run.– CPU context switching is relatively cheap.– Swapping memory in/out from/to disk is expensive.• Need to subdivide memory to accommodate multiple processes!• How do we manage this memory?CPSC 410/611 : Operating SystemsMemory Management: Paging / Segmentation 2Requirements for Memory Management• Relocation– We do not know a priori where memory of process will reside.• Protection– No uncontrolled references to memory locations of otherprocesses.– Memory references must be checked at run-time.• Sharing– Data portions and program text portions.• Logical organization– Take advantage of semantics of use.– Data portions (read/write) vs. program text portions (readonly).• Memory hierarchy– RAM vs. secondary storage– SwappingS1O1LtempLphysS2S3O2O3Preparing a Program for Execution• compiler: translates symbolic instructions, operands, and addressesinto numerical values.• linker: resolves external references; i.e. operands or branchaddresses referring to data or instructions within some othermodule• loader: brings program into main memory.compilerlinkerloaderSi : Source ProgramOi: Object ModuleLtemp: Load ModuleLphys: Memory Imagedynamicallyloaded systemlibrarysystem libraryCPSC 410/611 : Operating SystemsMemory Management: Paging / Segmentation 3Address Binding• Compile-time binding:• Load-time binding (static relocation):• Execution-time binding (dynamic relocation):branch AA: ...branch 150assembler100150branch AA: ...branch 50assembler0050branch 150linker100150other modulebranch 1150loader11001150other moduleother progrmsA: ...branch AA: ...branch 50assembler0050branch 150linker100150other modulebranch 150loader11001150other moduleother progrmsMMU1150Dynamic Loading, Dynamic Linking• Dynamic Loading:– load routine into memory only when it is needed– routines kept on disk in relocatable format• Load-time Linking:– postpone linking until load time.• Dynamic Linking:– postpone linking until execution time.– Problem: Need help from OS!call xstubx: load routinelink x to location of routineCPSC 410/611 : Operating SystemsMemory Management: Paging / Segmentation 4Logical vs. Physical Address Space• Logical address: address as seen by the process (i.e. as seen by the CPU).• Physical address: address as seen by the memory.• Example:branch AA: ...branch 50assembler0050branch 150linker100150branch 1150loader11001150A: ...logical = physicalbranch AA: ...branch 50assembler0050branch 150linker100150branch 150loader11001150MMU1150physicallogicalexecution time:load time:Logical vs. Physical Memory Spacephysicaladdressspace of processPiprocess base sizeP1 28 1000P2 1028 3000P3 5034 250CPU< +OSrelocationregisterlimitregisteraddressing error!logical addressspace of processPiMemory Management Unitpartition tablePhysical Memory• Logical address: address as seen by the process (i.e. as seen by the CPU).• Physical address: address as seen by the memory.CPSC 410/611 : Operating SystemsMemory Management: Paging / Segmentation 5Swappingwaitingrunningstartwaiting_swready_swreadyjobs are in memoryjobs are on diskOSswap_outswap_inswapping store memoryFragmentationOS8MB2MBInternal Fragmentation4MB 8MB 12MB?!External FragmentationP4?P1P1P2P1P2P3P1P3CPSC 410/611 : Operating SystemsMemory Management: Paging / Segmentation 6Paging• Contiguous allocation causes (external) fragmentation.• Solution: Partition memory blocks into smaller subblocks (pages)and allow them to be allocated non-contiguously.Memory Management Unitlogical memoryphysical memorysimple relocationMemory Management Unitlogical memoryphysical memorypagingBasic Operations in Paging HardwareMemory Management UnitCPUphysicalmemoryp d f dfppage tabledExample: PDP-11 (16-bit address, 8kB pages)CPSC 410/611 : Operating SystemsMemory Management: Paging / Segmentation 7Internal Fragmentation in Paging• Example:logical memory13300Bpage size 4kBphysical memory• Last frame allocated may not be completely full.• Average internal fragmentation per block is typically half frame size.• Large frames vs. small frames:• Large frames cause more fragmentation.• Small frames cause more overhead (page table size, disk I/O)4084 byteswasted!Implementation of Page Table• Page table involved in every access to memory. Speed veryimportant.• Page table in registers?– Example: 1MB logical address space, 2kB page size; needs apage table with 512 entries!• Page table in memory?– Only keep a page table base register that points to locationof page table.– Each access to memory would require two accesses tomemory!• Cache portions of page table in registers?– Use translation lookaside buffers (TLBs): typically a fewdozens entries.– Hit ratio: Percentage of time an entry is found.Hit ratio must be high in order to minimize overhead.CPSC 410/611 : Operating SystemsMemory Management: Paging / Segmentation 8Hierarchical (Multilevel) Paging• Problem: Page tables can become very large! (e.g. 32-bit address space?)• Solution: Page the page table itself! (e.g. page directory vs. page table)• Two-level paging:– Example: 32 bit logical address, page size 4kB• Three-level paging (SPARC), four-level paging (68030), ...• AMD64 (48-bit virtual addresses) has 4 levels.• Even deeper for 64 bit address spaces (5 to 6 levels)f dfpage table (10)offset(12)page directory (10)page table base registerVariations: Inverted Page Tablen…3210page noprocess idpage noproc id offsetoffset3• Array of page numbers indexed by frame number.– page lookup: search for matching frame entry• Size scales with physical memory.• Single table for system (not per process)• Used in early virt. memory systems, such as theAtlas computer.• Not practical today. (Why?)CPSC 410/611 : Operating SystemsMemory Management: Paging / Segmentation 9Variations: Hashed Page Table• Used by many 64bit architectures:– IBM POWER– HP PA-RISC– Itanium• Scales with physical memory• One table for whole system• Difficult to share memory betweenprocessespage number offsethash functionproc id page no chainSoftware-loaded TLBs: Paging - MIPS