动态内存分配

本文主要建设了什么是动态内存分配,动态内存分配原理及如何使用。动态内存分配,就是指在程序执行的过程中动态地分配或者回收存储空间的分配内存的方法。动态内存分配:内核堆、物理内存分配器。讨论了如何了解动态内存分配及内存的使用。在哪个方面该运用动态内存。
展开查看详情

1. Binghamton University Dynamic Memory Alloca/on Slides credit: Presenta/on based on slides by Dave O’halloran/CSAPP 1

2. Binghamton University Dynamic memory alloca/on ¢  Where is this important? §  Heap §  Kernel heap §  Physical memory allocator §  Problems are similar, but specific some/mes force different solu/ons 2

3. Binghamton University Dynamic Memory Alloca/on ¢  Programmers use Applica/on dynamic memory Dynamic Memory Allocator allocators (such as Heap malloc) to acquire VM at run /me. §  For data structures whose User stack size is only known at run/me. Top of heap ¢  Dynamic memory (brk ptr) Heap (via malloc) allocators manage an area of process virtual Unini/alized data (.bss) memory known as the Ini/alized data (.data) heap. Program text (.text) 0 3

4. Binghamton University Dynamic Memory Alloca/on ¢  Allocator maintains heap as collec/on of variable sized blocks, which are either allocated or free ¢  Types of allocators §  Explicit allocator: applica/on allocates and frees space §  E.g., malloc and free in C §  Implicit allocator: applica/on allocates, but does not free space §  E.g. garbage collec/on in Java, ML, and Lisp ¢  Will discuss explicit memory alloca/on 4

5. Binghamton University The malloc Package #include <stdlib.h> void *malloc(size_t size) §  Successful: §  Returns a pointer to a memory block of at least size bytes (typically) aligned to 8-byte boundary §  If size == 0, returns NULL §  Unsuccessful: returns NULL (0) and sets errno void free(void *p) §  Returns the block pointed at by p to pool of available memory §  p must come from a previous call to malloc or realloc Other func/ons §  calloc: Version of malloc that ini/alizes allocated block to zero. §  realloc: Changes the size of a previously allocated block. §  sbrk: Used internally by allocators to grow or shrink the heap 5

6. Binghamton University Alloca/on Example p1 = malloc(4) p2 = malloc(5) p3 = malloc(6) free(p2) p4 = malloc(2) 6

7. Binghamton University Constraints ¢  Applica/ons §  Can issue arbitrary sequence of malloc and free requests §  free request must be to a malloc’d block ¢  Allocators §  Can’t control number or size of allocated blocks §  Must respond immediately to malloc 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 sa/sfy all alignment requirements §  8 byte alignment for GNU malloc (libc malloc) on Linux boxes §  Can manipulate and modify only free memory §  Can’t move the allocated blocks once they are malloc’d §  i.e., compac/on is not allowed 7

8. Binghamton University Goals ¢  Given some sequence of malloc and free requests: §  R0, R1, ..., Rk, ... , Rn-1 ¢  Goals: maximize throughput and peak memory u/liza/on §  These goals are o\en conflic/ng ¢  Throughput: §  Number of completed requests per unit /me ¢  U/liza/on: §  Percentage of the heap that is u/lized §  Poor memory u/liza/on caused by fragmenta/on, or poor alloca/on policies 8

9. Binghamton University Implementa/on Issues ¢  How do we know how much memory to free given just a pointer? ¢  How do we keep track of the free blocks? ¢  What do we do with the extra space when alloca/ng a structure that is smaller than the free block it is placed in? ¢  How do we pick a block to use for alloca/on -- many might fit? ¢  How do we reinsert freed block? 9

10. Binghamton University Knowing How Much to Free ¢  Standard method §  Keep the length of a block in the word preceding the block. § This word is o\en called the header field or header §  Requires an extra word for every allocated block p0 p0 = malloc(4) 5 block size data free(p0) 10

11. Binghamton University Keeping Track of Free Blocks ¢  Method 1: Implicit list using length—links all blocks 5 4 6 2 ¢  Method 2: Explicit list among the free blocks using pointers 5 4 6 2 ¢  Method 3: Segregated free list §  Different free lists for different size classes ¢  Method 4: Blocks sorted by size §  Can use a balanced tree (e.g. Red-Black tree) with pointers within each free block, and the length used as a key 11

12. Binghamton University Method 1: Implicit List ¢  For each block we need both size and alloca/on status §  Could store this informa/on in two words: wasteful! ¢  Standard trick §  If blocks are aligned, some low-order address bits are always 0 §  Instead of storing an always-0 bit, use it as a allocated/free flag §  When reading size word, must mask out this bit 1 word Size a a = 1: Allocated block a = 0: Free block Format of allocated and Payload Size: block size free blocks Payload: applica/on data (allocated blocks only) Op/onal padding 12

13. Binghamton University Detailed Implicit Free List Example Unused Start of 8/0 16/1 32/0 16/1 0/1 heap Double-word Allocated blocks: shaded aligned Free blocks: unshaded Headers: labeled with size in bytes/allocated bit 13

14. Binghamton University Implicit List: Finding a Free Block ¢  First fit: §  Search list from beginning, choose first free block that fits: p = start; while ((p < end) && \\ not passed end ((*p & 1) || \\ already allocated (*p <= len))) \\ too small p = p + (*p & -2); \\ goto next block (word addressed) §  Can take linear /me in total number of blocks (allocated and free) §  In prac/ce it can cause “splinters” at beginning of list ¢  Next fit: §  Like first fit, but search list star/ng where previous search finished §  Should o\en be faster than first fit: avoids re-scanning unhelpful blocks §  Some research suggests that fragmenta/on is worse ¢  Best fit: §  Search the list, choose the best free block: fits, with fewest bytes le\ over §  Keeps fragments small—usually helps fragmenta/on §  Will typically run slower than first fit 14

15. Binghamton University Implicit List: Alloca/ng in Free Block ¢  Alloca/ng in a free block: spli?ng §  Since allocated space might be smaller than free space, we might want to split the block 4 4 6 2 p addblock(p, 4) 4 4 4 2 2 void addblock(ptr p, int len) { int newsize = ((len + 1) >> 1) << 1; // round up to even int oldsize = *p & -2; // mask out low bit *p = newsize | 1; // set new length if (newsize < oldsize) *(p+newsize) = oldsize - newsize; // set length in remaining } // part of block 15

16. Binghamton University Implicit List: Freeing a Block ¢  Simplest implementa/on: §  Need only clear the “allocated” flag void free_block(ptr p) { *p = *p & -2 } §  But can lead to “false fragmenta/on” 4 4 4 2 2 free(p) p 4 4 4 2 2 malloc(5) Oops! There is enough free space, but the allocator won’t be able to find it 16

17. Binghamton University Implicit List: Coalescing ¢  Join (coalesce) with next/previous blocks, if they are free §  Coalescing with next block 4 4 4 2 2 logically p free(p) gone 4 4 6 2 2 void free_block(ptr p) { *p = *p & -2; // clear allocated flag next = p + *p; // find next block if ((*next & 1) == 0) *p = *p + *next; // add to this block if } // not allocated §  But how do we coalesce with previous block? 17

18. Binghamton University Implicit List: Bidirec/onal Coalescing ¢  Boundary tags [Knuth73] §  Replicate size/allocated word at “boiom” (end) of free blocks §  Allows us to traverse the “list” backwards, but requires extra space §  Important and general technique! 4 4 4 4 6 6 4 4 Header Size a a = 1: Allocated block a = 0: Free block Format of Size: Total block size allocated and Payload and padding free blocks Payload: Applica/on data (allocated blocks only) Boundary tag Size a (footer) 18

19. Binghamton University Constant Time Coalescing Case 1 Case 2 Case 3 Case 4 Allocated Allocated Free Free Block being freed Allocated Free Allocated Free 19

20. Binghamton University Constant Time Coalescing (Case 1) m1 1 m1 1 m1 1 m1 1 n 1 n 0 n 1 n 0 m2 1 m2 1 m2 1 m2 1 20

21. Binghamton University Constant Time Coalescing (Case 2) m1 1 m1 1 m1 1 m1 1 n 1 n+m2 0 n 1 m2 0 m2 0 n+m2 0 21

22. Binghamton University Constant Time Coalescing (Case 3) m1 0 n+m1 0 m1 0 n 1 n 1 n+m1 0 m2 1 m2 1 m2 1 m2 1 22

23. Binghamton University Constant Time Coalescing (Case 4) m1 0 n+m1+m2 0 m1 0 n 1 n 1 m2 0 m2 0 n+m1+m2 0 23

24. Binghamton University Keeping Track of Free Blocks ¢  Method 1: Implicit free list using length—links all blocks 5 4 6 2 ¢  Method 2: Explicit free list among the free blocks using pointers 5 4 6 2 ¢  Method 3: Segregated free list §  Different free lists for different size classes ¢  Method 4: Blocks sorted by size §  Can use a balanced tree (e.g. Red-Black tree) with pointers within each free block, and the length used as a key 24

25. Binghamton University Explicit Free Lists Allocated (as before) Free Size a Size a Next Payload and Prev padding Size a Size a ¢  Maintain list(s) of free blocks, not all blocks §  The “next” free block could be anywhere §  So we need to store forward/back pointers, not just sizes §  S/ll need boundary tags for coalescing §  Luckily we track only free blocks, so we can use payload area 25

26. Binghamton University Explicit Free Lists ¢  Logically: A B C ¢  Physically: blocks can be in any order Forward (next) links A B 4 4 4 4 6 6 4 4 4 4 C Back (prev) links 26

27. Binghamton University Alloca/ng From Explicit Free Lists conceptual graphic Before AKer (with spli?ng) = malloc(…) 27

28. Binghamton University Freeing With Explicit Free Lists ¢  InserMon policy: Where in the free list do you put a newly freed block? §  LIFO (last-in-first-out) policy §  Insert freed block at the beginning of the free list §  Pro: simple and constant /me §  Con: studies suggest fragmenta/on is worse than address ordered §  Address-ordered policy §  Insert freed blocks so that free list blocks are always in address order: addr(prev) < addr(curr) < addr(next) §  Con: requires search §  Pro: studies suggest fragmenta/on is lower than LIFO 28

29. Binghamton University Freeing With a LIFO Policy (Case 1) conceptual graphic Before free( ) Root ¢  Insert the freed block at the root of the list AKer Root 29