DOC PREVIEW
U of I CS 241 - Swapping and Fragmentation

This preview shows page 1-2-16-17-18-34-35 out of 35 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 Reserved2ContentsSwappingStatic and Variable Partitions FragmentationStorage PlacementCompaction01/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 MapsPart of memory with 5 processes, 3 holestick marks show allocation unitsshaded regions are freeCorresponding bit mapSame 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 StrategiesBest fit. Worst Fit.First Fit.01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved15Storage Placement StrategiesBest 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 StrategiesBest 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 ProblemsFixed partitions suffer from internal fragmentationVariable partitions suffer from external fragmentationCompaction suffers from overhead01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved20Storage Management ProblemsPartitions must be less in size than real memoryOverlays are painful to program efficientlySwapping requires writing to disk sectors01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved21Quick QuestionAssuming 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 Reserved22Answer1801/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved23How Bad Is Fragmentation?Statistical arguments - Random sizesFirst-fitGiven N allocated blocks0.5N blocks will be lost because of fragmentationI.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 sizesFirst-fitGiven N allocated blocks0.5N blocks will be lost because of fragmentationI.e. 33% of memory may be unusable!!!Known as 50% RULE01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved25Fragmentationconsider 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 Fragmentation50% 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 Estimatef the fraction of memory occupied by holes. SS the average segment sizeand the average hole size be at least Sh . The ratio of hole size to segment sizeSsSesegm entsizholesizekh01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved31Unused Memory2kknkhkhSSnSShSShSnShShytotalmemorlesmemoryinhofShShShShh01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved32Estimates of Fragmentation using the 50% ruleit is impossible to use all of central memory, f > 0simulation indicates f can be made about 10%2kkf01/14/19 CS241 © 2005 Roy Campbell, All Rights Reserved3301/14/19 CS241 © 2005 Roy Campbell, All Rights


View Full Document

U of I CS 241 - Swapping and Fragmentation

Documents in this Course
Process

Process

28 pages

Files

Files

37 pages

File I/O

File I/O

52 pages

C Basics

C Basics

69 pages

Memory

Memory

23 pages

Threads

Threads

14 pages

Lecture

Lecture

55 pages

C Basics

C Basics

24 pages

Signals

Signals

27 pages

Memory

Memory

45 pages

Threads

Threads

47 pages

Threads

Threads

28 pages

LECTURE

LECTURE

45 pages

Threads

Threads

30 pages

Threads

Threads

55 pages

Files

Files

37 pages

SIGNALS

SIGNALS

22 pages

Files

Files

37 pages

Threads

Threads

14 pages

Threads

Threads

13 pages

Load more
Download Swapping and Fragmentation
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Swapping and Fragmentation and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Swapping and Fragmentation 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?