Operating Systems: Internals and Design Principles, 6/E William Stallings - Chapter 7: Memory Management

Chapter 7Memory ManagementOperating Systems:Internals and Design Principles, 6/EWilliam StallingsPatricia RoyManatee Community College, Venice, FL©2008, Prentice HallRoadmapBasic requirements of Memory ManagementMemory PartitioningBasic blocks of memory managementPagingSegmentationThe 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 a CPUThe OS must cleverly time the swapping to maximise the CPU’s efficiencyMemory ManagementMemory needs to be allocated to ensure a reasonable supply of ready processes to consume available processor timeMemory Management RequirementsRelocationProtectionSharingLogical organisationPhysical organisationRequirements: RelocationThe 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)Memory references must be translated to the actual physical memory addressMemory Management TermsTermDescriptionFrameFixed-length block of main memory.PageFixed-length block of data in secondary memory (e.g. on disk). SegmentVariable-length block of data that resides in secondary memory. Table 7.1 Memory Management TermsAddressingRequirements: ProtectionProcesses should not be able to reference memory locations in another process without permissionImpossible to check absolute addresses at compile timeMust be checked at run timeRequirements: SharingAllow several processes to access the same portion of memoryBetter to allow each process access to the same copy of the program rather than have their own separate copyRequirements: Logical OrganizationMemory is organized linearly (usually)Programs are written in modulesModules can be written and compiled independentlyDifferent degrees of protection given to modules (read-only, execute-only)Share modules among processesSegmentation helps hereRequirements: Physical OrganizationCannot leave the programmer with the responsibility to manage memoryMemory available for a program plus its data may be insufficientOverlaying allows various modules to be assigned the same region of memory but is time consuming to programProgrammer does not know how much space will be availablePartitioningAn 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 PartitioningEqual-size partitions (see fig 7.3a)Any process whose size is less than or equal to the partition size can be loaded into an available partitionThe operating system can swap a process out of a partitionIf none are in a ready or running stateFixed Partitioning ProblemsA program may not fit in a partition. The programmer must design the program with overlaysMain memory use is inefficient. Any program, no matter how small, occupies an entire partition.This is results in internal fragmentation.Solution – Unequal Size PartitionsLessens both problems but doesn’t solve completelyIn Fig 7.3b,Programs up to 16M can be accommodated without overlaySmaller programs can be placed in smaller partitions, reducing internal fragmentationPlacement AlgorithmEqual-sizePlacement is trivial (no options)Unequal-sizeCan assign each process to the smallest partition within which it will fitQueue for each partitionProcesses are assigned in such a way as to minimize wasted memory within a partitionFixed PartitioningRemaining Problems with Fixed PartitionsThe number of active processes is limited by the system I.E limited by the pre-determined number of partitionsA large number of very small process will not use the space efficientlyIn either fixed or variable length partition methodsDynamic PartitioningPartitions are of variable length and numberProcess is allocated exactly as much memory as requiredDynamic Partitioning ExampleExternal FragmentationMemory external to all processes is fragmentedCan resolve using compactionOS moves processes so that they are contiguousTime consuming and wastes CPU timeOS (8M)P1 (20M)P2(14M)P3(18M)Empty (56M)Empty (4M)P4(8M)Empty (6M)P2(14M)Empty (6M)Refer to Figure 7.4Dynamic PartitioningOperating system must decide which free block to allocate to a processBest-fit algorithmChooses the block that is closest in size to the requestWorst performer overallSince smallest block is found for process, the smallest amount of fragmentation is leftMemory compaction must be done more oftenDynamic PartitioningFirst-fit algorithmScans memory form the beginning and chooses the first available block that is large enoughFastestMay have many process loaded in the front end of memory that must be searched over when trying to find a free blockDynamic PartitioningNext-fitScans memory from the location of the last placementMore often allocate a block of memory at the end of memory where the largest block is foundThe largest block of memory is broken up into smaller blocksCompaction is required to obtain a large block at the end of memoryAllocationBuddy SystemEntire 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 smallest block greater than or equal to s is generatedExample of Buddy SystemTree Representation of Buddy SystemRelocationWhen program loaded into memory the actual (absolute) memory locations are determinedA 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 memory.RelativeAddress expressed as a location relative to some known point.Physical or AbsoluteThe absolute address or actual location in main memory.RelocationRegisters 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 inRegisters Used during ExecutionThe 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 not within bounds, an interrupt is generated to the operating systemPagingPartition memory into small equal fixed-size chunks and divide each process into the same size chunksThe chunks of a process are called pages The chunks of memory are called framesPagingOperating system maintains a page table for each processContains the frame location for each page in the processMemory address consist of a page number and offset within the pageProcesses and FramesA.0A.1A.2A.3B.0B.1B.2C.0C.1C.2C.3D.0D.1D.2D.3D.4Page TableSegmentationA program can be subdivided into segmentsSegments may vary in lengthThere is a maximum segment lengthAddressing consist of two partsa segment number and an offsetSegmentation is similar to dynamic partitioningLogical AddressesPagingSegmentation