Khoa học máy tính - Chapter 11: Memory management

Chapter 11Memory ManagementCopyright © 20081Operating Systems, by Dhananjay Dhamdhere*IntroductionManaging the Memory HierarchyStatic and Dynamic Memory AllocationExecution of ProgramsMemory Allocation to a ProcessHeap ManagementContiguous Memory Allocation2Operating Systems, by Dhananjay Dhamdhere*Introduction (continued)Noncontiguous Memory AllocationPagingSegmentationSegmentation with PagingKernel Memory AllocationUsing Idle RAM Effectively3Operating Systems, by Dhananjay Dhamdhere*Managing the Memory Hierarchy4Operating Systems, by Dhananjay Dhamdhere*Static and Dynamic Memory AllocationMemory allocation is an aspect of a more general action in software operation known as bindingStatic allocation performed by compiler, linker, or loaderSizes of data structures must be known a prioriDynamic allocation provides flexibilityMemory allocation actions constitute an overhead during operation5Operating Systems, by Dhananjay Dhamdhere*Execution of ProgramsA has to be transformed before it can be executedMany of these transformations perform memory bindingsAccordingly, an address is called compiled address, linked address, etc6Operating Systems, by Dhananjay Dhamdhere*A Simple Assembly LanguageFormat of an assembly language statement:[Label] ,First operand is always a GPRAREG, BREG, CREG or DREGSecond operand is a GPR or a symbolic name that corresponds to a memory byteOpcodes are self-explanatoryADD, MULT, MOVER, MOVEM, BCFor simplicity, assume that addresses and constants are in decimal, and instructions occupy 4 bytes7Operating Systems, by Dhananjay Dhamdhere*RelocationInstructions using memory addresses are address-sensitiveRelocation is needed if program is to execute correctly in some other memory area: involves changing addresses8Operating Systems, by Dhananjay Dhamdhere*Relocation (continued)Relocation may be performed in two ways:Static (before program is executed)Dynamic (during program execution)Alternative 1: suspend execution and relocateAlternative 2: use a relocation register9Operating Systems, by Dhananjay Dhamdhere*LinkingAssembler puts information about ENTRY and EXTRN statements in an object module for linker’s useCalled entry points and external referencesLinking: binding external reference to correct addressLinker links modules to form an executable programLoader loads program in memory for executionStatic linking produces binaries with no unresolved external referencesDynamic linking enables sharing of a single copy of a module and dynamic updating of library modulesE.g., Dynamically linked libraries (DLLs)10Operating Systems, by Dhananjay Dhamdhere*Program Forms Employed in Operating Systems11Operating Systems, by Dhananjay Dhamdhere*Self-Relocating ProgramsA self-relocating program:Knows its own translated origin and translated addresses of its address-sensitive instructionsContains relocating logicStart address of the relocating logic is specified as the execution start address of the programStarts off by calling a dummy functionReturn address provides its own execution-time addressNow performs its own relocation using this addressPasses control to first instruction to begin its own execution12Operating Systems, by Dhananjay Dhamdhere*Reentrant ProgramsCan be executed concurrently by many usersCode accesses its data structures through the GPR13Operating Systems, by Dhananjay Dhamdhere*Stacks and HeapsStack: LIFO allocations/deallocations (push and pop)Memory is allocated when a function, procedure or block is entered and is deallocated when it is exited14Operating Systems, by Dhananjay Dhamdhere*Stacks and Heaps (continued)A heap permits random allocation/deallocationUsed for program-controlled dynamic data (PCD data)15Operating Systems, by Dhananjay Dhamdhere*Memory Allocation to a ProcessStacks and HeapsThe Memory Allocation ModelMemory Protection16Operating Systems, by Dhananjay Dhamdhere*The Memory Allocation Model17Operating Systems, by Dhananjay Dhamdhere*Memory ProtectionMemory protection uses base and size registerMemory protection violation interrupt is raised if an address used in a program lies outside their rangeOn processing interrupt, kernel aborts erring processBase/size registers constitute the memory protection information (MPI) field of PSWKernel loads appropriate values while scheduling a processLoading and saving are privileged instructionsWhen a relocation register is used, this register and the size register constitute MPI field of PSW18Operating Systems, by Dhananjay Dhamdhere*Heap ManagementReuse of MemoryMaintaining a Free ListPerforming Fresh Allocations by Using a Free ListMemory FragmentationMerging of Free Memory AreasBuddy System and Power-of-2 AllocatorsComparing Memory AllocatorsHeap Management in Windows19Operating Systems, by Dhananjay Dhamdhere*Reuse of Memory20Operating Systems, by Dhananjay Dhamdhere*Maintaining a Free ListFor each memory area in free list, kernel maintains:Size of the memory areaPointers used for forming the listKernel stores this information it in the first few bytes of a free memory area itself21Operating Systems, by Dhananjay Dhamdhere*Performing Fresh Allocations by Using a Free ListThree techniques can be used:First-fit technique: uses first large-enough areaBest-fit technique: uses smallest large-enough areaNext-fit technique: uses next large-enough area22Operating Systems, by Dhananjay Dhamdhere*Memory Fragmentation Fragmentation leads to poor memory utilization23Operating Systems, by Dhananjay Dhamdhere*Merging of Free Memory AreasExternal fragmentation can be countered by merging free areas of memoryTwo generic techniques:Boundary tagsMemory compaction24Operating Systems, by Dhananjay Dhamdhere*Merging of Free Memory Areas (continued)A tag is a status descriptor for a memory areaWhen an area of memory becomes free, kernel checks the boundary tags of its neighboring areas If a neighbor is free, it is merged with newly freed area25Operating Systems, by Dhananjay Dhamdhere*Merging of Free Memory Areas (continued)The 50-percent rule holds when merging is performed26Operating Systems, by Dhananjay Dhamdhere*Merging of Free Memory Areas (continued)Memory compaction is achieved by “packing” all allocated areas toward one end of the memoryPossible only if a relocation register is provided27Operating Systems, by Dhananjay Dhamdhere*Buddy System and Power-of-2 AllocatorsThese allocators perform allocation of memory in blocks of a few standard sizesLeads to internal fragmentationEnables the allocator to maintain separate free lists for blocks of different block sizesAvoids expensive searches in a free listLeads to fast allocation and deallocationBuddy system allocator performs restricted mergingPower-of-2 allocator does not perform merging28Operating Systems, by Dhananjay Dhamdhere*Buddy System Allocator29Operating Systems, by Dhananjay Dhamdhere*Power-of-2 AllocatorSizes of memory blocks are powers of 2Separate free lists are maintained for blocks of different sizesEach block contains a header elementContains address of free list to which it should be added when it becomes freeAn entire block is allocated to a requestNo splitting of blocks takes placeNo effort is made to coalesce adjoining blocksWhen released, a block is returned to its free list30Operating Systems, by Dhananjay Dhamdhere*Comparing Memory AllocatorsCompared on the basis of speed of allocation and efficient use of memoryBuddy and power-of-2 allocators are faster than first-fit, best-fit, and next-fit allocatorsPower-of-2 allocator is faster than buddy allocatorTo compare memory usage efficiency:First-fit, best-fit, or next-fit allocators do not incur internal fragmentationBuddy allocator achieved 95% efficiency in simulation31Operating Systems, by Dhananjay Dhamdhere*Heap Management in WindowsHeap management aims at low allocation overhead and low fragmentationBy default, uses free list and best-fit allocation policyNot adequate: (1) when process makes heavy use of heap, and (2) in a multiprocessor environmentAlternative: use the low-fragmentation heap (LFH)Maintains many free lists; each for areas of a specific sizeNeither splitting, nor merging is performedAnalogous to power-of-2 allocatorOS monitors requests and adjusts sizes to fine-tune performance32Operating Systems, by Dhananjay Dhamdhere*Contiguous Memory AllocationIn contiguous memory allocation each process is allocated a single contiguous area in memoryFaces the problem of memory fragmentationApply techniques of memory compaction and reuseCompaction requires a relocation registerLack of this register is also a problem for swapping33Operating Systems, by Dhananjay Dhamdhere*Noncontiguous Memory AllocationPortions of a process address space are distributed among different memory areasReduces external fragmentation34Operating Systems, by Dhananjay Dhamdhere*Logical Addresses, Physical Addresses, and Address TranslationLogical address: address of an instruction or data byte as used in a processViewed as a pair (compi, bytei)Physical address: address in memory where an instruction or data byte exists35Operating Systems, by Dhananjay Dhamdhere*Approaches to Noncontiguous Memory AllocationTwo approaches:PagingProcess consists of fixed-size components called pagesEliminates external fragmentationThe page size is defined by hardwareSegmentationProgrammer identifies logical entities in a program; each is called a segmentFacilitates sharing of code, data, and program modules between processesHybrid approach: segmentation with pagingAvoids external fragmentation36Operating Systems, by Dhananjay Dhamdhere*37Operating Systems, by Dhananjay Dhamdhere*Memory ProtectionMemory areas allocated to a program have to be protected against interference from other programsMMU performs this through a bounds checkWhile performing address translation for a logical address (compi, bytei), MMU checks if compi actually exists in program and whether bytei exists in compiProtection violation interrupt raised if check failsBounds check can be simplified in pagingbytei cannot exceed size of a page38Operating Systems, by Dhananjay Dhamdhere*PagingIn the logical view, the address space of a process consists of a linear arrangement of pagesEach page has s bytes in it, where s is a power of 2 The value of s is specified in the architecture of the computer systemProcesses use numeric logical addresses39Paging (continued)Memory is divided into areas called page framesA page frame is the same size as a pageOperating Systems, by Dhananjay Dhamdhere*40Operating Systems, by Dhananjay Dhamdhere*Paging (continued)Notation used to describe address translation:s Size of a pagell Length of a logical address (i.e., number of bits in it)lp Length of a physical addressnb Number of bits used to represent the byte number in a logical addressnp Number of bits used to represent the page number in a logical addressnf Number of bits used to represent frame number in a physical addressThe size of a page, s, is a power of 2nb is chosen such that s = 2nb logical address start address of frame qi effective physical address41Operating Systems, by Dhananjay Dhamdhere*Example: Address Translation in Paging32-bit logical addressesPage size of 4 KB12 bits are adequate to address the bytes in a page212 = 4KBFor a memory size of 256 MB, lp = 28If page 130 exists in page frame 48,pi = 130, and qi = 48If bi = 600, the logical and physical addresses are:42Operating Systems, by Dhananjay Dhamdhere*SegmentationA segment is a logical entity in a programE.g., a function, a data structure, or an objectEach logical address used in Q has the form (si, bi) si and bi are the ids of a segment and a byte within a segment43Operating Systems, by Dhananjay Dhamdhere*Segmentation with PagingEach segment in a program is paged separately Integral number of pages allocated to each segmentSimplifies memory allocation and speeds it upAvoids external fragmentation44Operating Systems, by Dhananjay Dhamdhere*Kernel Memory AllocationKernel creates and destroys data structures at a high rate during its operationMostly control blocksE.g., PCB, ECB, IOCB, FCBSizes of control blocks known in OS design stageHelps make memory allocation simple and efficientModern OSs use noncontiguous memory allocation with pagingMcKusick–Karels allocatorLazy buddy allocatorSlab allocator45Operating Systems, by Dhananjay Dhamdhere*Kernel Memory Allocation (continued)McKusick–Karels and lazy buddy allocators allocate memory areas that are powers of 2 in size within a pageStart address of each allocated memory area of size 2n is a multiple of 2nBoundary alignment on a power of 2Leads to a cache performance problemSome parts of the cache face a lot of contention leading to poor cache performance of kernel codeSlab allocator uses an interesting technique to avoid this cache performance problem46Operating Systems, by Dhananjay Dhamdhere*Kernel Memory Allocation (continued)Slab allocator was first used in Solaris 2.4Has been used in Linux since version 2.2A slab consists of many slots; each can hold an objectColoring areas are chosen such that objects in different slabs of pool have different alignments with respect to the closest multiples of a power of 2Map into different areas of a set-associative cache47Operating Systems, by Dhananjay Dhamdhere*Using Idle RAM EffectivelyMemory is idle when applications are not activeHow can idle memory be exploited by OS?Run utilities during idle periods of a computerE.g., antivirus software Can have a negative impact on performance by displacing applications from memoryWindows Vista uses techniques that use idle RAM to enhance system performanceSuperFetch: preloads frequently used applications in idle RAMReadyboost: uses USB drive as a cache between disk and RAM48Operating Systems, by Dhananjay Dhamdhere*SummaryCompiler assumes a specific memory area to be available to program and generates object moduleLinker performs relocation of a program, and performs linking to connect the program with library functionsSelf-relocating programs perform their own relocationCPU has a relocation register to facilitate relocationMemory allocation can be: static or dynamicBoth combined in programs through stack and heap49Operating Systems, by Dhananjay Dhamdhere*SummaryAllocation/deallocation of memory can lead to fragmentation: internal or externalFirst-fit, next-fit and best-fit strategies try to reduce fragmentationbuddy systems and power-of-2 allocators eliminate external fragmentationNoncontiguous allocation reduces external fragmentationRequires use of the memory management unit (MMU) of CPUKernel creates and destroys data structures at high rateUses special techniques to make memory reuse fast and efficient 50