Partitions and PagingCS241 AdministrativeKey conceptsMemory Management with Bit MapsMemory Management with Linked ListsAllocation schemesStorage Placement StrategiesSlide 8Slide 9Solve Fragmentation w. CompactionOr… use Multiple Base RegistersStorage Management ProblemsSlide 13How Bad Is Fragmentation?DiscussionPagingBenefits of Virtual MemoryPaging RequestSlide 19Slide 20Slide 21Slide 22Slide 23Page Mapping HardwareSlide 25Paging IssuesSlide 27Slide 28Slide 29Paging - Caching the Page TablePaging Implementation IssuesSlide 32Slide 33Slide 34CS 241 Spring 2007System Programming 01/14/19 CS241 © 2007 LA, RHC and YZ, All Rights Reserved1Partitions and PagingCS 241 Lecture 29Stallings: Ch 7[317-322],Ch 8[333-352] Lawrence Angrave2CS241 AdministrativeRead Stallings Chapter 7 about Memory Management Regular Quiz 9 this week on Memory ManagementDiscussion Sessions this week (on Memory Management – needed for LMP2)LMP2 is on (Deadline April 16, but Part I has deadline April 9) – start early3Key conceptsFragmentation Issues of Fixed PartitioningDynamic PartitioningMemory Management Data StructuresStorage Placement StrategiesCompactionFragmentation IssuesPaging ConceptPage/FramesPage Table4Memory Management with Bit MapsPart of memory with 5 processes, 3 holestick marks show allocation unitsshaded regions are freeCorresponding bit mapLink list5Memory Management with Linked ListsFour neighbor combinations for the terminating process X6Allocation schemesBitmap and link listWhich one occupies more space?Depending on the individual memory allocation scenario. In most cases, bitmap usually occupies more space.Which one is faster reclaim freed space?On average, bitmap is faster because it just needs to set the corresponding bitsWhich one is faster to find a free hole?On average, a link list is faster because we can link all free holes together7Storage Placement StrategiesAt a memory allocation request, which free hole to use?Best fit. Worst Fit.First Fit.8Storage Placement StrategiesBest fitUse the hole whose size is equal to the need, or if none is equal, the whole that is larger but closest in size. Rational?First fitUse the first available hole whose size is sufficient to meet the needRational?Worst fitUse the largest available holeRational?9Storage Placement StrategiesEvery placement strategy has its own problemBest fitCreates small holes that cant be used Worst FitGets rid of large holes making it difficult to run large programs First FitCreates average size holes10Solve Fragmentation w. CompactionMonitor Job3FreeJob5 Job6Job7 Job85Monitor Job3FreeJob5 Job6Job7 Job86Monitor Job3FreeJob5 Job6Job7 Job87Monitor Job3FreeJob5 Job6Job7 Job88Monitor Job3FreeJob5 Job6Job7 Job8911Or… use Multiple Base RegistersBreak programs into smaller units because they will fit betterUse multiple base registers, one for each unitExamples Code/DataConstants/variables12Storage Management ProblemsFixed partitions suffer frominternal fragmentationVariable partitions suffer fromexternal fragmentationCompaction suffers from overhead13Storage Management ProblemsPartitions must be less in size than real memoryOverlays are painful to program efficientlySwapping requires writing to disk sectors14How Bad Is Fragmentation?Statistical arguments - Random sizesFirst-fitGiven N allocated blocks0.5N blocks will be lost because of fragmentationKnown as 50% RULE15DiscussionWhat schemes could be used to overcome fragmentation?What does the use of secondary storage for swap space imply about memory organization?16PagingProvide user with virtual memory that is as big as user needsStore virtual memory on diskCache parts of virtual memory being used in real memoryLoad and store cached virtual memory without user program intervention17Benefits of Virtual MemoryUse secondary storage($)Extend DRAM($$$) with reasonable performanceProtectionPrograms do not step over each otherConvenienceFlat address spacePrograms have the same view of the worldLoad and store cached virtual memory without user program intervention Reduce fragmentation: make cacheable units all the same size (page)Remove memory deadlock possibilities:permit pre-emption of real memory18Paging Request3 1234DiskCacheVirtualMemoryStoredonDisk1 2 3 4 5 6 7 81 2 3 41234PageTableVM FrameRealMemoryRequestAddresswithinVirtualMemoryPage319Paging3 11 234DiskCacheVirtualMemoryStoredonDisk1 2 3 4 5 6 781 2 3 41234PageTableVM FrameRealMemoryRequestAddresswithinVirtualMemoryPage120Paging3 116234DiskCacheVirtualMemoryStoredonDisk1 2 3 4 5 6 7 81 2 3 41234PageTableVM FrameRealMemoryRequestAddresswithinVirtualMemoryPage621Paging3 116234DiskCacheVirtualMemoryStoredonDisk1 2 3 4 5 6 7 81 2 3 41234PageTableVM FrameRealMemoryRequestAddresswithinVirtualMemoryPage2222Paging3 116234DiskCacheVirtualMemoryStoredonDisk1 2 3 4 5 6 7 81 2 3 41234PageTableVM FrameRealMemoryStoreVirtualMemoryPage1todisk2RequestAddresswithinVirtualMemory823Paging3 16234DiskCacheVirtualMemoryStoredonDisk1 2 3 4 5 6 7 81 2 3 41234PageTableVMFrameRealMemory2LoadVirtualMemoryPage8tocache8824Page Mapping HardwareContents(P,D)Contents(F,D)P DF DP->F0101101PageTableVirtualMemoryPhysicalMemoryVirtualAddress(P,D)PhysicalAddress(F,D)PFDDP25Page Mapping HardwareContents(4006)Contents(5006)004 006005 0064->50101101PageTableVirtualMemoryPhysicalMemoryVirtualAddress(004006)PhysicalAddress(F,D)0040050060064Pagesize1000NumberofPossibleVirtualPages1000NumberofPageFrames826Paging Issuessize of page is 2n , usually 512, 1k, 2k, 4k, or 8kE.g. 32 bit VM address may have 220 (1 meg) pages with 4k (212 ) bytes per pageRational?27Paging Issues220 (1 meg) 32 bit page entries take 222 bytes (4 meg)page frames must map into real memory28Paging IssuesQuestionPhysical memory size: 32 MB (2^25 ) Page size 4K bytesHow many pages? 2^13Page Table base register must be changed for context switchWhy?Different page tableNO external fragmentationInternal fragmentation on last page ONLY29DiscussionHow
View Full Document