Memory 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 sizeclasses)• 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 theaddress of its buddy• e.g., block of size 32 with address xxx...x00000 has buddyxxx...x10000Tradeoffs:• fast search and coalesce• subject to internal fragmentationCS 213 F’98– 9 –class15.pptInternal fragmentationInternal fragmentation is wasted space inside allocatedblocks:• 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 forensictechniques in the context of disk blocks• contents of “slack” at the end of the last sector of a file containdirectory 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 firmSteele & Hoffman, after watching the movie "The Firm",copies school board billing records from firm's laptopsonto some diskettes, then resigns.July 29, 1993• McCalister hands over 4 diskettes to postal instpectors asevidence of systematic overbilling of school systems byCharlie Steele, managing partner of Steele & Hoffman.September, 1996• I'm asked by defense to determine if the 4 diskettes are theoriginals 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 3years 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 organizedinto 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 5:00 am 2 R/O Sys HidMSDOS SYS 37394 11-11-91 5:00 am 5419 R/O Sys HidCONFIG SYS 57 10-26-92 8:47 am 8998 ArcAUTOEXEC BAT 24 10-26-92 8:47 am 8997 ArcDOS 0 3-22-93 4:40 pm 19 DirWININST 0 3-22-93 4:41 pm 597 DirWINDOWS 0 3-22-93 4:43 pm 3042 DirCOMMAND COM 47845 11-11-91 5:00 am 5429 ArcSCAN 0 3-22-93 4:50 pm 5570 DirWINA20 386 9349 11-11-91 5:00 am 14HARCHLRD REG 1492 6-14-93 12:50 pm 5859 ArcASP 0 3-23-93 11:59 am 6242 DirDO 0 3-23-93 12:01 pm 6295 DirGOLF 0 3-23-93 12:01 pm 6361 DirLOTUS 0 5-07-93 4:32 pm 5341
View Full Document