alloc malloc calloc realloc区别

malloc、calloc、realloc的区别

概述

<1>alloca是向栈申请内存,因此无需释放.

<2>malloc分配的内存是位于堆中的,并且没有初始化内存的内容,因此基本上malloc之后,调用函数memset来初始化这部分的内存空间.

<3>calloc则将初始化这部分的内存,设置为0.

<4>realloc则对malloc申请的内存进行大小的调整.

<5>申请的内存最终需要通过函数free来释放

malloc分配器的实现原理（csapp）

约束：

处理任意请求队列；立即响应请求；只是用堆；==对齐块==；不修改已分配的块。

目标

• 最大化吞吐率：每个单位时间内完成的请求数目。
• 最大化内存利用率：当前已分配的块的有效载荷之和/当前堆的大小，造成利用低的原因是（内部碎片和外部碎片）

内存块的结构：

内存块的大致结构：每个块由meta区和数据区组成，meta区记录数据块的元信息（数据区大小、空闲标志位、指针等等），数据区是真实分配的内存区域，并且数据区的第一个字节地址即为malloc返回的地址。

1.空闲块的组织（如何记录空闲块）

• 隐式空闲链表：通过头部中的大小字段隐含地连接，分配器遍历所有的块的过程中也遍历着这些空闲块（简单，但是操作的开销大）
• 显示空闲链表：块的排序策略（LIFO，将最先释放的块放到链表头部；按地址顺序），缺点是空闲块要更大。
• 分离式空闲链表：维护多个空闲链表，每个链表的块大小是大致相等的

（伙伴系统）：每个块大小为2^k维护一个分离空闲链表。用bitmap维护。

2.放置（如何选择合适的空闲块放置新分配的块）

• 首次适配：从头开始搜索空闲链表选择第一个合适的块。（缺点：链表首部留下小碎片）
• 下一次适配：每一次搜索从上一次结束的地方开始，遍历找到第一个合适的块。（缺点：存储器利用率没有首次适应高）
• 最佳适配：检查每个空闲块找到适合所需大小的最小空闲块。（缺点：需要全部搜索）

3.分割（如何处理放置后块中的剩余部分）

分配整个空闲块会导致内部碎片。将空闲分割区分割成已分配快和新的空闲块。找不到合适的空闲块会合并物理上相邻的空闲块。若还是找不到合适的块，分配器调用sbrk向内核请求额堆存储器 并将存储器转化为大的空闲块，将它插入空闲链表总并将请求放置块中。

4.合并（如何处理一个被释放的块）

空闲块太小不足以使用的现象叫假碎片。可以通过合并相邻块来解决。合并有==立即合并和推迟合并==。

自己的简单实现

GNU malloc（分离适配的方式实现的）

brk 与 sbrk

int brk(void *end_data_segment);
void *sbrk(ptrdiff_t increment);

• brk（堆的当前最后地址），就是动态内存分配当前的终止地址
• brk sets the end of the data segment to the value specified by end_data_segment, when that value is reasonable, the system does have enough memory and the process does not exceed its max data size (see setrlimit(2)).
• sbrk increments the program's data space by increment bytes. sbrk isn't a system call, it is just a C library wrapper. Calling sbrk with an increment of 0 can be used to find the current location of the program break.