CS 105 Tour of the Black Holes of Computing Dynamic Memory Allocation I Topics Simple explicit allocators Data structures Mechanisms Policies Harsh Reality Memory Matters Memory is not unbounded It must be allocated and managed Many applications are memory dominated Memory referencing bugs especially pernicious Effects are distant in both time and space Memory performance is not uniform 2 Cache and virtual memory effects can greatly affect program performance Adapting program to characteristics of memory system can lead to major speed improvements CS 105 Dynamic Memory Allocation Application Dynamic Memory Allocator Heap Memory Explicit vs Implicit Memory Allocator Explicit application allocates and frees space E g malloc and free in C Semi implicit application allocates but does not free space E g garbage collection in Java Implicit allocation and freeing done under covers ML Lisp Python Perl Ruby Allocation 3 In all cases allocator provides abstraction of memory as set of blocks Doles out free memory blocks to application Done by run time system in user mode CS 105 Process Memory Image kernel virtual memory stack esp memory invisible to user code Memory mapped region for shared libraries Allocators request additional heap memory from the operating system using the sbrk function the brk ptr run time heap via malloc uninitialized data bss initialized data data program text text 4 0 CS 105 Malloc Package include stdlib h void malloc size t size If successful Returns a pointer to a memory block of at least size bytes typically aligned to 8 byte boundary If size 0 returns NULL If unsuccessful returns NULL 0 and sets errno void free void p Returns the block pointed to by p to pool of available memory p MUST come from a previous call to malloc or realloc NULL not a legal argument sigh void realloc void p size t size 5 Changes size of block p and returns pointer to new block Contents of new block unchanged up to min of old and new size CS 105 Malloc Example void foo int n int m int i p allocate a block of n ints if p int malloc n sizeof int NULL perror malloc exit 0 for i 0 i n i p i i add m bytes to end of p block if p int realloc p n m sizeof int NULL perror realloc exit 0 for i n i n m i p i i print new array for i 0 i n m i printf d n p i 6 free p return p to available memory pool CS 105 Assumptions Assumptions made in this lecture Memory is byte addressed Words are 4 bytes Pointer fits in a word 4 bytes All diagrams are word based Allocated block 4 words 16 bytes 7 Free block 3 words 12 bytes Free word Allocated word CS 105 Allocation Examples p1 malloc 16 p2 malloc 20 p3 malloc 24 free p2 p4 malloc 8 8 CS 105 Constraints Applications Can issue arbitrary sequence of allocation and free requests Free requests must correspond to an allocated block i e pointer must be correct Allocators Can t control number or size of allocated blocks Must respond immediately to all allocation requests i e can t reorder or buffer requests Must allocate blocks from free memory i e can only place allocated blocks in free memory Must align blocks so they satisfy all alignment requirements 8 byte alignment for GNU malloc libc malloc on Linux boxes Can only manipulate and modify free memory Can t move the allocated blocks once they are allocated i e compaction is not allowed 9 CS 105 Goals of Good malloc free Primary goals Good time performance for malloc and free Ideally should take constant time not always possible Should certainly not take time linear in number of blocks Good space utilization User allocated structures should be large fraction of the heap Want to minimize fragmentation to be defined later Some other goals Good locality properties Structures allocated close in time should be close in space Similar objects should be allocated close in space Robust Can check that free p1 is on a valid allocated object p1 don t free it twice or free some other ptr Can check that memory references are to allocated space 10 CS 105 Performance Goals Throughput Given some sequence of malloc and free requests R0 R1 Rk Rn 1 Want to maximize throughput minimize wasted space These goals often conflict Throughput Number of completed requests per unit time Example 5 000 malloc calls and 5 000 free calls in 10 seconds Throughput is 1 000 operations second 11 CS 105 Performance Goals Peak Memory Utilization Related to wasted space Given some sequence of malloc and free requests R0 R1 Rk Rn 1 Def Aggregate payload Pk malloc p results in a block with a payload of p bytes After request Rk has completed the aggregate payload Pk is the sum of currently allocated payloads excludes overhead Def Current heap size is denoted by Hk Assume that Hk is monotonically nondecreasing Def Peak memory utilization After k requests peak memory utilization is Uk maxi k Pi Hk 12 CS 105 Internal Fragmentation Poor memory utilization caused by fragmentation Comes in two forms internal and external fragmentation Internal fragmentation Also present in paging For any block internal fragmentation is the difference between the block size and the payload size block Internal fragmentation 13 payload Internal fragmentation Caused by overhead of maintaining heap data structures padding for alignment purposes or explicit policy decisions e g not to split a block Depends only on pattern of previous requests and thus easy to measure CS 105 External Fragmentation Occurs when there is enough aggregate heap memory but no single free block is large enough p1 malloc 16 p2 malloc 20 p3 malloc 24 free p2 p4 malloc 24 oops External fragmentation depends on pattern of future requests and thus is difficult to measure 14 CS 105 Implementation Issues How do we know how much memory to free when given just a pointer How do we track free blocks free list What do we do with extra space when allocating a structure smaller than the free block it is placed in How do we pick a block to use for allocation Many might fit How do we reinsert freed block in free list p0 free p0 15 p1 malloc 1 CS 105 Knowing How Much to Free Standard method Keep length of block in preceding word Often called header field or header Requires extra word for every allocated block p0 malloc 16 p0 20 free p0 16 Block size data CS 105 Keeping Track of Free Blocks Method 1 Implicit list using lengths links all blocks 20 16 24 8 Method 2 Explicit list among the free blocks using pointers within the free blocks 20 16 24 8 Method 3 Segregated free list Different free lists for different size classes
View Full Document
Unlocking...