Hệ điều hành - Chapter 7: Memory management

Chapter 7Memory ManagementBasic requirements of Memory ManagementMemory PartitioningPagingSegmentationMemory ManagementThe principal operation of memory management is to bring processes into main memory for execution by the processor.A program must be loaded into main memory to be executed.Memory ManagementMemory needs to be allocated to ensure a reasonable supply of ready processes to consume available processor timeOtherwise, for much of the time all of the processes will be waiting for I/O and the processor will be idle.The need for memory managementMemory is cheap today, and getting cheaperBut applications are demanding more and more memory, there is never enough! Memory Management involves swapping blocks of data from secondary storage. Memory I/O is slow compared to CPUThe OS must cleverly time the swapping to maximise the CPU’s efficiencyMemory Management RequirementsRelocationProtectionSharingLogical organisationPhysical organisationRelocationThe programmer does not know where the program will be placed in memory when it is executed, it may be swapped to disk and return to main memory at a different location (relocated)But, OS knows because it is managing memory and is responsible for bringing this process into main memoryRelocation AddressingThe processor and OS must be able to translate the memory references found in the code of the program into actual physical memory addresses (to be discussed)ProtectionProcesses should not be able to reference memory locations in another process without permission.Impossible to check absolute addresses at compile time because the location of a program in main memory is unpredictable.Must be checked at run time by the processor.SharingAllow several processes to access the same portion of memoryBetter to allow each process executing the same program access to the same copy of the program rather than have their own separate copyProcesses that are cooperating on some task may need to share access to the same data structureLogical OrganizationMemory is organized linearly (usually)In contrast, programs are organized into modulesModules can be written and compiled independentlyDifferent degrees of protection can be given to different modules (read-only, execute-only)Modules can be shared among processesSegmentation helps herePhysical OrganizationCannot leave the programmer with the responsibility to manage memoryMemory available for a program plus its data may be insufficientProgrammer does not know how much space will be available or where the space will beThe task of moving information between different levels of memory should be a system responsibilityPartitioningAn early method of managing memoryPre-virtual memoryNot used much nowBut, it will clarify the later discussion of virtual memory if we look first at partitioningVirtual Memory has evolved from the partitioning methodsTypes of PartitioningFixed PartitioningDynamic PartitioningSimple PagingSimple SegmentationVirtual Memory PagingVirtual Memory SegmentationFixed PartitioningPartition memory into regions with fixed boundariesEqual-size partitionsAny process whose size is less than or equal to the partition size can be loaded into an available partitionFixed PartitioningProblemsA program may be too big to fit into a partitionMain memory use is inefficient. Any program, no matter how small, occupies an entire partition.This is results in internal fragmentation (wasted space internal to a partition).Fixed Partitioning Solution – Unequal Size PartitionsLessen both problemsBut doesn’t solve completelyLarger programs can be accommodated Smaller programs can be placed in smaller partitions, reducing internal fragmentationFixed Partitioning Placement AlgorithmEqual-sizePlacement is trivial: a process can be loaded into any available partitionUnequal-sizeCan assign each process to the smallest partition within which it will fitQueue for each partition Processes are assigned in such a way as to minimize wasted memory within a partitionIt is possible that a partition is unused even though some smaller process could have been assigned to itSelect the smallest available partition that will hold the processFixed Partitioning Placement AlgorithmThe number of active processes is limited by the system i.e., limited by the pre-determined number of partitionsPartition sizes are preset at system generation time, small jobs will not use space efficientlyFixed PartitioningRemaining ProblemsDynamic PartitioningDynamic partitioning can overcome some of the difficulties with fixed partitioningPartitions are of variable length and numberProcess is allocated exactly as much memory as requiredDynamic Partitioning ExampleExternal FragmentationMemory external to all processes is fragmented and memory utilization declinesCan resolve using compactionOS moves processes so that they are contiguous Time consuming and wastes CPU timeOS (8M)P1 (20M)P2(14M)P3(18M)Empty (56M)Empty (4M)P4(8M)Empty (6M)P2(14M)Empty (6M)Dynamic PartitioningOperating system must decide which free block to allocate to a processBest-fit algorithmChooses the block that is closest in size to the request Worst performer overallSince smallest block is found for a process, the fragment left behind is too small to satisfy other requestsMemory compaction must be done more oftenDynamic PartitioningFirst-fit algorithmScans memory from the beginning and chooses the first available block that is large enough Simplest and fastest May have many process loaded in the front end of memory such that small free partitions must be searched over on each subsequent passDynamic PartitioningNext-fitScans memory from the location of the last placement More often allocate a free block at the end of memory where the largest block is foundThe largest block of free memory is quickly broken up into smaller blocksCompaction is required more frequentlyDynamic Partitioning AllocationBuddy SystemA reasonable compromise to overcome the disadvantages of both the fixed and dynamic partitioning schemesEntire space available is treated as a single block of 2UIf a request of size s where 2U-1 < s  2Uentire block is allocatedOtherwise block is split into two equal buddiesProcess continues until the smallest block greater than or equal to s is generatedBuddy SystemExampleBuddy System Tree RepresentationA binary tree representation of the buddy allocation immediately after the Release B requestThe leaf nodes represent the current partitioning the memoryRelocationThe actual (absolute) memory locations are determined when program is loaded into memoryA process may occupy different partitions which means different absolute memory locations during executionSwappingCompactionAddressesLogicalReference to a memory location independent of the current assignment of data to memoryA relative address is expressed as a location relative to some known point (typically the program origin)Physical or AbsoluteThe absolute address or actual location in main memoryA translation must be made from a logical address to a physical address before memory access can be achievedRelocation Hardware Support 0. Initialize base and bounds registers when a process is assigned to the Running state1. Add the value in the base register to the relative address to produce an absolute address2. Compare the resulting address to the value in the bounds registerRelocation Registers Used during ExecutionBase registerStarting address for the processBounds registerEnding location of the processThese values are set when the process is loaded or when the process is swapped inThe value of the base register is added to a relative address to produce an absolute addressThe resulting address is compared with the value in the bounds registerIf the address is within bounds, instruction execution may proceedOtherwise, an interrupt indicating error is generated to OSRelocation Registers Used during ExecutionPagingPartition memory into small equal fixed-size chunks (frames) and divide each process into the same size chunks (pages)Pages of process could be assigned to available frames of memoryNo external fragmentation but little internal fragmentation consisting of only a fraction of the last page of a processPaging Processes and FramesA.0A.1A.2A.3B.0B.1B.2C.0C.1C.2C.3D.0D.1D.2D.3D.4OS finds free frames and loads the pages of Process A, B & CProcess B is suspended and is swapped out of main memoryAll of the processes in main memory are blocked, and OS brings in Process DPagingOperating system maintains a page table for each process which contains the frame location for each page in the processGiven a logical address (page number, offset), the processor uses the page table to produce a physical address Paging Page Tablepage numberframe numberPaging Logical AddressesUsing a page size that is a power of 2, a logical address (page no., offset) is identical to its relative addressExample16-bit address 210 =1024-byte page10-bit offset6-bit page numberA maximum of 26 =64 pagesPaging Logical to Physical Address Translation1. Extract the page no. 2. Use the page no. as an index into the process page table to find the frame number, k3. The physical address is constructed by appending the offset to kConsider an address of n+m bits, where the leftmost n bits are the page no. and the rightmost m bits are the offsetSegmentationA program can be subdivided into segmentsSegments may vary in lengthThere is a maximum segment lengthSegmentation is similar to dynamic partitioningBut, a program may occupy more than one partitionNo internal fragmentation but suffers from external fragmentation (as does dynamic partitioning)SegmentationA logical address consists of two partsa segment number and an offsetThere is a segment table for each process and a list of free blocks of main memory. Each segment table entry would have to givethe starting address in main memory of the corresponding segment. the length of the segment, to assure that invalid addresses are not used.Segmentation Logical AddressesThere is no simple relationship between a logical address (segment no., offset) and the physical addressExample16-bit address 12-bit offset4-bit segment numbermaximum segment size= 212=4096SegmentationLogical to Physical Address Translation1.Extract the segment no.2.Use the segment no. as an index into the process segment table to find the starting physical address of the segment3. If the offset  the length of the segment, the address is invalid4.The physical address is the sum of the starting physical address of the segment plus the offsetConsider an address of n + m bits, where the leftmost n bits are the segment no. and the rightmost m bits are the offset