15 213 Introduction to Computer Systems Memory Management II Dynamic Storage Allocation Oct 13 1998 Topics other placement policies cont buddy systems implementation issues sequential fits class15 ppt Basic allocator mechanisms Sequential fits best fit first fit or next fit placement various splitting and coalescing options splitting thresholds immediate or deferred coalescing Segregated free lists simple segregated storage segregated fits buddy systems class15 ppt 2 CS 213 F 98 Simple segregated storage Separate heap for different sized blocks No splitting To 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 time To free a block Usual constant time coalescing Tradeoffs fast but can fragment badly class15 ppt 3 CS 213 F 98 Segregated fits Array of free lists each one for some size class To 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 found To 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 help class15 ppt 4 CS 213 F 98 Buddy systems Special case of segregated fits all blocks are power of two sizes Basic 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 class15 ppt 5 CS 213 F 98 Buddy 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 2m buddy buddy buddy class15 ppt 6 CS 213 F 98 Buddy systems cont To free a block of size 2k buddy To free a block of size 2k if buddy free coalesce with buddy and return new block to free list To free a block of size 2k if buddy not free just return block to free list class15 ppt 7 CS 213 F 98 Buddy 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 x10000 Tradeoffs fast search and coalesce subject to internal fragmentation class15 ppt 8 CS 213 F 98 Internal fragmentation Internal 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 class15 ppt 9 CS 213 F 98 Steele mail fraud case March 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 class15 ppt 10 CS 213 F 98 Anatomy of a Computer keyboard memory temporary display programs and data disk buffer hard disk fixed class15 ppt diskette removeable 11 CS 213 F 98 How a DOS file is organized into clusters data slack clusters class15 ppt 12 CS 213 F 98 Internal fragmentation in DOS files Files allocated in fixed size logical sectors cluster abc data class15 ppt slack internal fragmentation 13 CS 213 F 98 How slack takes a picture of a disk when a file is copied 1 1 read source directory DE is directory entry DE1 DE2 DE3 DE4 disk buffer abc destination disk source disk class15 ppt 14 CS 213 F 98 How slack takes a picture of a disk when a file is copied 2 2 read file into disk buffer notice that old slack is not copied into disk buffer abc DE1 DE2 DE3 DE4 disk buffer abc destination disk source disk class15 ppt 15 CS 213 F 98 How slack takes a picture of a disk when a file is copied 3 3 write file to destination disk Notice that slack now contains a snapshot of the files on the source disk when the file was copied abc DE1 DE2 abc DE3 DE4 abc DE1 source disk class15 ppt disk buffer DE2 DE3 destination disk 16 CS 213 F 98 DE4 Federal diskette F1 is not a duplicate Cluster 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 Hid MSDOS SYS 37394 11 11 91 5 00 am 5419 CONFIG SYS 57 10 26 92 8 47 am 8998 Arc AUTOEXEC BAT 24 10 26 92 8 47 am 8997 Arc DOS 0 3 22 93 4 40 pm 19 Dir WININST 0 3 22 93 4 41 pm 597 Dir WINDOWS 0 3 22 93 4 43 pm 3042 Dir 47845 11 11 91 5 00 am 5429 0 3 22 93 4 50 pm 5570 9349 Diskedit 11 11 91 program 5 00 am Utilities 14 6 14 93 17 12 50 pm 5859 COMMAND COM SCAN WINA20 Source 386 Norton class15 ppt HARCHLRD REG 1492 R O Sys Hid Arc Dir ArcCS 213 F 98 Federal diskette F2 is not a duplicate Cluster 501 Sector 532 F2 CRIMALDI C498 501 Name Ext Size Date Time Cluster Arc R O Sys Hid Dir Vol WP51 0 3 23 93 12 05 pm 7242 Dir XTALK 0 3 23 93 12 13 pm 8910 Dir KATHY REL 2239 6 14 93 1 20 pm 5869 Arc FRECOVER DAT 101376 3 24 93 11 29 am 8951 Arc R O GO BAT 198 10 26 92 8 47 am 8966 Arc MENU BAT 947 10 26 92 8 47 am 8967 Arc SD INI 2497 10 26 92 8 47 am 8968 Arc XMENU EXE 5521 10 26 92 8 47 am 8969 Arc XMENU PIF 296 10 26 92 8 47 am 8971 Arc FRECOVER IDX 29 3 24 93 11 29 am 41442 Arc R …
View Full Document
Unlocking...