Memory Management II: Dynamic Storage Allocation Oct 13, 1998Basic allocator mechanismsSimple segregated storageSegregated fitsBuddy systemsBuddy systems (cont)Slide 7Slide 8Internal fragmentationSteele mail fraud caseAnatomy of a ComputerHow a DOS file is organized into clustersInternal fragmentation in DOS filesHow slack takes a picture of a disk when a file is copied (1)How slack takes a picture of a disk when a file is copied (2)How slack takes a picture of a disk when a file is copied (3)Federal diskette F1 is not a duplicateFederal diskette F2 is not a duplicateFederal diskette F3 is not a duplicateFiles on the federal diskettes came from the hard diskThe federal diskettes were produced in the afternoon of July 29, 1993Implementation Issues (cont)Implementation issues (cont)General coalescingImplementation issuesConstant time coalescing (1)Constant time coalescing (2)Constant time coalescing (3)Constant time coalescing (4)Slide 30Food for thoughtFor more informationMemory Management II:Dynamic Storage AllocationOct 13, 1998Topics•other placement policies (cont)•buddy systems•implementation issues (sequential fits)class15.ppt15-213Introduction to Computer SystemsCS 213 F’98– 2 –class15.pptBasic allocator mechanismsSequential fits•best fit, first fit, or next fit placement•various splitting and coalescing options–splitting thresholds–immediate or deferred coalescingSegregated free lists•simple segregated storage•segregated fits–buddy systemsCS 213 F’98– 3 –class15.pptSimple segregated storageSeparate heap for different sized blocksNo splittingTo allocate a block of size n:•if free list for size n is not empty,–allocate first block on list•if free list is empty, –get a new page –create new free list–allocate first block on list•constant timeTo free a block:•Usual constant-time coalescingTradeoffs:•fast, but can fragment badlyCS 213 F’98– 4 –class15.pptSegregated fitsArray of free lists, each one for some size classTo allocate a block of size n:•search appropriate free list for block of size m > n•if an appropriate block is found:–split block and place fragment on appropriate list (optional)•if no block is found, try next larger class•repeat until block is foundTo free a block:•coalesce and place on appropriate list (optional)Tradeoffs•faster search than sequential fits (i.e., log time for power of two size classes)•controls fragmentation of simple segregated storage•coalescing can increase search times–deferred coalescing can helpCS 213 F’98– 5 –class15.pptBuddy systemsSpecial case of segregated fits.•all blocks are power of two sizesBasic idea:•Heap is 2m words•Maintain separate free lists of each size 2k, 0 <= k <= m.•Requested block sizes are rounded up to nearest power of 2.•Originally, one free block of size 2m.CS 213 F’98– 6 –class15.pptBuddy systems (cont)To allocate a block of size 2k:•Find first available block of size 2j s.t. k <= j <= m.•if j == k then done.•otherwise recursively split block until j == k.2mbuddybuddybuddyCS 213 F’98– 7 –class15.pptBuddy systems (cont)To free a block of size 2k:buddyTo free a block of size 2k:•if buddy free, coalesce with buddy and return new block to free listTo free a block of size 2k:•if buddy not free, just return block to free listCS 213 F’98– 8 –class15.pptBuddy systems (cont)Key fact about buddy systems:•given the address and size of a block, it is easy to compute the address of its buddy•e.g., block of size 32 with address xxx...x00000 has buddy xxx...x10000Tradeoffs:•fast search and coalesce•subject to internal fragmentationCS 213 F’98– 9 –class15.pptInternal fragmentationInternal fragmentation is wasted space inside allocated blocks:•minimum block size larger than requested amount–e.g., due to minimum free block size, free list overhead•policy decision not to split blocks–e.g., buddy system –Much easier to define and measure than external fragmentation.Source of interesting computer science forensic techniques in the context of disk blocks•contents of “slack” at the end of the last sector of a file contain directory entries.•provide a snapshop of the system that copied the file.CS 213 F’98– 10 –class15.pptSteele mail fraud caseMarch 6, 1993 (Pittsburgh, PA)•Phil McCalister, disgruntled associate at Pgh law firm Steele & Hoffman, after watching the movie "The Firm", copies school board billing records from firm's laptops onto some diskettes, then resigns.July 29, 1993•McCalister hands over 4 diskettes to postal instpectors as evidence of systematic overbilling of school systems by Charlie Steele, managing partner of Steele & Hoffman.September, 1996•I'm asked by defense to determine if the 4 diskettes are the originals from March 6, 1993 (they weren't).December, 1996•Despite brilliant testimony by the computer expert witness, Charlie Steele convicted of mail fraud and sentenced to 3 years in federal pen and $80,000 fine.CS 213 F’98– 11 –class15.pptAnatomy of a Computermemory(temporary)disk bufferprogramsanddatakeyboard displayhard disk (fixed) diskette (removeable)CS 213 F’98– 12 –class15.pptHow a DOS file is organized into clustersclustersdataslackCS 213 F’98– 13 –class15.pptInternal fragmentation in DOS filesFiles allocated in fixed size logical sectorsclusterabcdata slack (internal fragmentation)CS 213 F’98– 14 –class15.pptHow slack takes a picture of a disk when a file is copied (1)abcsource diskdestination diskdisk buffer1. read source directory ("DE" is directory entry)DE1 DE2 DE3 DE4CS 213 F’98– 15 –class15.pptHow slack takes a picture of a disk when a file is copied (2)abcsource diskdestination diskdisk buffer2. read file into disk buffer (notice that old slack is not copied into disk buffer!)DE1 DE2 DE3 DE4abcCS 213 F’98– 16 –class15.pptHow slack takes a picture of a disk when a file is copied (3)abcsource disk destination diskdisk buffer3. write file to destination disk. Notice that slack now contains a snapshot of the files on the source disk when the file was copied.DE1 DE2 DE3 DE4abcDE1 DE2 DE3 DE4abcCS 213 F’98– 17 –class15.pptFederal diskette F1 is not a duplicateCluster 1,789, Sector 1,820 [F1:1991-$.IN C1638-1789]Name .Ext Size Date Time Cluster Arc R/O Sys Hid Dir Vol----------------------------------------------------------------------------- ... YS 33430 11-11-91
View Full Document