Swapping and FragmentationContentsBase Bounds RegistersSwappingSlide 5Slide 6Slide 7Slide 8Slide 9Slide 10Variable Partitions and FragmentationMemory Management with Bit MapsMemory Management with Linked ListsStorage Placement StrategiesSlide 15Slide 16CompactionMultiple Base RegistersStorage Management ProblemsSlide 20Quick QuestionAnswerHow Bad Is Fragmentation?Slide 24FragmentationSlide 26ReasonSlide 28Estimates of FragmentationUnused Memory Rule EstimateUnused MemorySlide 32Slide 33DiscussionSummary01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved1Swapping and FragmentationCS 241 Lecture 27T: Ch 4Roy Campbell01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved2ContentsSwappingStatic and Variable Partitions FragmentationStorage PlacementCompaction01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved3Base Bounds RegistersMemoryBounds Register Base RegisterCPUAddress< +MemoryAddress MALogicalAddress LAPhysical AddressPAFaultBase AddressLimit AddressMA+BABaseAddressBA01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved4SwappingMonitorDiskUserPartition01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved5SwappingMonitorDiskUser 1UserPartition01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved6SwappingMonitorUser 1DiskUser 1UserPartition01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved7SwappingMonitorUser 2User 1DiskUser 1UserPartition01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved8SwappingMonitorDiskUser 2User 2UserPartitionUser 101/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved9SwappingMonitorDiskUser 2User 2UserPartitionUser 101/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved10SwappingMonitorDiskUser 1User 2UserPartitionUser 101/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved11Variable Partitions and FragmentationMonitor Job 1 Job 2 Job 3 Job 4Free1Monitor Job 1 Job 3 Job 4Free2Monitor Job 1 Job 3 Job 4FreeJob 53Monitor Job 3 Job 4FreeJob 5 Job 64Monitor Job 3FreeJob 5 Job 6Job 7 Job 8501/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved12Memory Management with Bit MapsPart of memory with 5 processes, 3 holestick marks show allocation unitsshaded regions are freeCorresponding bit mapSame information as a list01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved13Memory Management with Linked ListsFour neighbor combinations for the terminating process X01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved14Storage Placement StrategiesBest fit. Worst Fit.First Fit.01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved15Storage Placement StrategiesBest fit. Use the hole whose size is equal to the need, or if none is equal, the whole that is larger but closest in size. First fit. Use the first available hole whose size is sufficient to meet the need.Worst fit. Use the largest available hole.01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved16Storage Placement StrategiesBest fit. Creates small holes that cant be used Worst Fit. Gets rid of large holes making it difficult to run large programs First Fit. Creates average size holes01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved17CompactionMonitor Job 3FreeJob 5 Job 6Job 7 Job 85Monitor Job 3FreeJob 5 Job 6Job 7 Job 86Monitor Job 3FreeJob 5 Job 6Job 7 Job 87Monitor Job 3FreeJob 5 Job 6Job 7 Job 88Monitor Job 3FreeJob 5 Job 6Job 7 Job 8901/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved18Multiple Base Registers•Break programs into smaller units because they will fit better•Use multiple base registers, one for each unit•Examples •Code/Data•Constants/variables01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved19Storage Management ProblemsFixed partitions suffer from internal fragmentationVariable partitions suffer from external fragmentationCompaction suffers from overhead01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved20Storage Management ProblemsPartitions must be less in size than real memoryOverlays are painful to program efficientlySwapping requires writing to disk sectors01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved21Quick QuestionAssuming average of 6 jobs in system with average memory size of 2 megabytes, what is the size of memory required for variable partitions?Q2) Answer = (integer)01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved22Answer1801/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved23How Bad Is Fragmentation?Statistical arguments - Random sizesFirst-fitGiven N allocated blocks0.5N blocks will be lost because of fragmentationI.e. 33% of memory may be unusable!!!Known as 50% RULE01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved24How Bad Is Fragmentation?Statistical arguments - Random sizesFirst-fitGiven N allocated blocks0.5N blocks will be lost because of fragmentationI.e. 33% of memory may be unusable!!!Known as 50% RULE01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved25Fragmentationconsider a system in equilibrium. the insertion rate is the same as the deletion rate.what can be said about memory usage?01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved26Fragmentation01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved27ReasonReplace thisReplace thisAnd Get One HoleAnd Get One Hole01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved28Fragmentation8 segments8 segments4 holes4 holes01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved29Estimates of Fragmentation50% rule if the system has an average of n segments and h holes, where n and h are large: i.e. there are approximately half as many holes as segments in memory 2nh 01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved30Unused Memory Rule Estimatef the fraction of memory occupied by holes. SS the average segment sizeand the average hole size be at least Sh . The ratio of hole size to segment sizeSsSesegm entsizholesizekh01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved31Unused Memory2kknkhkhSSnSShSShSnShShytotalmemorlesmemoryinhofShShShShh01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved32Estimates of Fragmentation using the 50% ruleit is impossible to use all of central memory, f > 0simulation indicates f can be made about 10%2kkf01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved3301/14/19 CS241 © 2005 Roy Campbell, All Rights
View Full Document