1. malloc笔记
1.1 基础概念
1.dynamic memory allocators:应用程序运行期间申请的内存(malloc)。
2.堆:dynamic memory allocator管理的进程内存区域
3.types of allocator:隐式分配器(new and garbage collection)和显示分配器(malloc & free)
1.2 explicit allocator
1.malloc、free、realloc
2.16-byte (x86-64) alignment on 64-bit systems
3.内部碎片产生的原因:
- 维持堆所需的数据结构开销
- 对齐的需要
- 分配器实现的策略(比如,to return a big block to satisfy a small request)
4.外部碎片:Occurs when there is enough aggregate heap memory, but no single free block is large enough。(大块被划分成小块,虽然整个空闲内存能够放下程序,但是找不到单独的一块去存放)
5.keep track of free blocks:显式、隐式链表、Segregated free list(Different free lists for different size classes)、Blocks sorted by size(红黑树,长度为key)
1.2.1 隐式空闲链表
1.block structures
typedef struct block
{
word_t header;//包含1bit的是否分配、剩下的表示payload大小
unsigned char payload[0];
} block_t;
2.Header access
- Getting allocated bit from header
return header & 0x1;
- Getting size from header
return header & ~0xfL;
- Initializing header
block->header = size | alloc;
3.Traversing list
static block_t *find_next(block_t *block)
{
return (block_t *) ((unsigned char *) block
+ get_size(block));
}
- Finding a Free Block
- first fit
static block_t *find_fit(size_t asize)
{
block_t *block;
for (block = heap_start; block != heap_end;
block = find_next(block)) {
{
if (!(get_alloc(block))
&& (asize <= get_size(block)))
return block;
}
return NULL; // No fit found
}
- next fit
- best fit
5.Allocating in Free Block and Splitting Free Block
6.Freeing a Block and Coalescing and Bidirectional Coalescing
1.2.2 显式空闲链表
1.Unordered(插入时间复杂度O(1))
- LIFO (last-in-first-out) policy
- FIFO (first-in-first-out) policy
- Address-ordered policy(插入时间复杂度O(n))
1.2.3 Segregated List
1.按照不同的大小划分不同的List
2.To allocate a block of size n:
- Search appropriate free list for block of size m > n (i.e., first fit)
- If an appropriate block is found:
Split block and place fragment on appropriate list
If no block is found, try next larger class - Repeat until block is found
3.If no block is found:
- Request additional heap memory from OS (using sbrk())
- Allocate block of n bytes from this new memory
- Place remainder as a single free block in appropriate size class.
1.3 隐式内存管理(垃圾收集)
1.How does the memory manager know when memory can be freed?
- In general we cannot know what is going to be used in the future since it depends on conditionals
- But we can tell that certain blocks cannot be used if there are no pointers to them
2.Must make certain assumptions about pointers
- Memory manager can distinguish pointers from non-pointers
- All pointers point to the start of a block
- Cannot hide pointers (e.g., by coercing them to an int, and then back again):比如c语言,可以任意的使用指针,所以c语言不能够自动清理垃圾
3.采用有向图标记:堆中分配的block看成节点,边看成指针。利用dfs算法,可以标记现在或者未来依然会使用的堆中的block。
malloc实验
看了几个博客,用隐式链表的话能得个50分左右,采用显式空闲链表+LIFO或者显式空闲链表+地址排序能得个80分左右,采用Segregated List得分较高,有100分左右。