基本概念 Link to 基本概念

使用动态内存分配在运行时请求虚拟内存.用于在运行时才确定大小的数据结构. 动态内存分配管理虚拟内存中的堆. 分配器将堆维护为连续的变大小的块的集合,块能被分配或释放. 分配器的类型:

• 显式分配器:显式分配,显式释放 例如C语言的malloc和free
• 隐式分配器:显式分配,系统隐式释放 例如JAVA,python的垃圾回收机制

动态内存分配函数包 Link to 动态内存分配函数包

malloc, free, calloc, realloc, sbrk

• void *malloc(size_t size): 成功:返回指向至少size字节(x86-64为16字节边界对齐)的块的指针;如果size=0,返回NULL 失败返回空指针并设置errno.
• void free(void *p): p必须是之前动态内存分配的指针
• calloc: 初始化为0
• realloc:改变之前分配的块的大小
• sbrk: 在分配器内部用于增长或缩小堆

约束 Link to 约束

• 程序
  • 任意使用分配/释放函数
  • 释放的必须是动态分配的指针
• 分配器
  • 不能控制分配的块的大小
  • 请求分配必须立即响应,不能积攒
  • 只能从空余空间分配
  • 满足对齐原则
  • 不能移动分配的块

性能目标 Link to 性能目标

由于分配器有诸多限制和约束,评估它的性能就很重要. 对于给定的一系列malloc和free请求: $R_{0},R_{1},\dots,R_{k},\dots,R_{n-1}$

1. 吞吐量 提高单位时间处理分配释放请求的次数

2. 峰值内存利用率

   • 定义:有效载荷$P_{k}$
     • malloc(p)导致有效载荷p字节
     • $R_{k}$请求后,有效载荷$P_{k}=\sum p_{i}$
   • 定义:当前堆大小$H_{k}$
     • 假设堆不减小
   • 定义:峰值内存利用率
     • $U_{k}=\frac{max_{i\leq k}P_{i}}{H_{k}}$

   分配器的目标就是在整个请求序列中使$U_{n-1}$最大化. 完美的内存利用率是1.但实际上由于对齐原则,不可避免地产生碎片

碎片(Fragmentation) Link to 碎片(Fragmentation)

低内存利用率是由碎片导致的. 有两种碎片类型:

1. 内部碎片
2. 外部碎片

内部碎片 Link to 内部碎片

如果有效载荷小于块大小,称为内部碎片 原因:

• 分配器需要维护一种堆的数据结构
• 对齐原则:块中的填充
• 策略决定:返回大块来确保小块请求的安全

取决于语句自身,容易评估.

外部碎片 Link to 外部碎片

有足够多的堆内存,但没有一个块是足够大的.

取决于前后请求,难以评估.

追踪空块 Link to 追踪空块

1. [[#隐式空闲块列表|隐式空闲块列表]](implicit list) 用长度连接所有块.
2. [[动态内存分配(进阶概念)#显式空闲块列表|显式空闲块列表]](explicit list) 在用指针指示空闲块
3. [[动态内存分配(进阶概念)#隔离空闲块列表|隔离空闲块列表]](segregated free list) 多种空闲列表,每个包含特定大小或特定大小范围的块
4. 按大小排列的块 使用平衡树将块按照大小来排序.

隐式空闲块列表 Link to 隐式空闲块列表

由于块按字长对齐,字长通常低位有几个0,利用这些0来存储是否分配的信息. 在块中加上一个头部,指示块的大小/是否分配等信息. 块的头部占有1字长,而载荷是double-word内存对齐的,所以头部没有double-word aligned.上图有效载荷是8字节对齐的,字长是4字节. 结束块是1个0字节的有效块.

寻找空闲块的算法 Link to 寻找空闲块的算法

1. first fit: 从列表开始处寻找,选择第一个合适的块:

   C

   Copy to clipboard

   1
   2
   3

   p = start;
   while((p < end) && ((*p & 1) || (*p <= len)))  // 加上头部大小
   	p = p + (*p & -2);  // go to next block
   

2. next fit: 从上次搜索结束的地方开始搜索 虽然避免了一些重复搜索,但是导致更严重的碎片化

3. best fit: 搜寻堆中所有块,找到最佳适配的块 需要更多的时间,但提升了内存利用率

在空闲块中分配 Link to 在空闲块中分配

通过上面的某种方式,已经找到了一个适配的块.接下来是对它进行修改以达到分配的目的. 在空闲块中分配:分割 分配的大小可能小于空闲的大小,所以需要分割

1
2
3
4
5
6
7

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

释放块 Link to 释放块

1
2
3

void free_block(ptr p){
	*p = *p & -2;
}

这会导致越来越多的碎片,所以需要合并空闲块

合并块 Link to 合并块

现有的头部设计只能合并后面的空闲块,无法判断前一个块是空闲. 所以在块的设计中,加上边界标记boundary tag,形成类似双向链表模拟的数组:

合并的时间复杂度是常数:

缺点也明显:增加了内部碎片. 如何优化? 实际上只有空闲块需要脚标.然后,利用字长低位的另一个0来标志之前一个块是否是空闲状态. 具体来说,就是在释放一块,并且合并后面的空闲块后,整个空闲块设置脚标,并将下一个分配块设置前一个块是空闲的标记. 当以后释放块时,就可以直到前一个块是空闲的,然后退一个字长访问其脚标,得到这个空闲块的大小,向前合并.

分配器策略 Link to 分配器策略

• 放置策略 first fit, next fit, best fit会造成吞吐量和碎片程度的差异,顾此失彼
• 分割策略 空闲块大于分配需要的大小就一定要分割吗?如果不分割,可能提升搜寻的效率,但会造成内部碎片的增加.
• 合并策略 在调用free时立即合并;还是推迟合并,在下一次用malloc扫描列表时再合并?

隐式空闲列表是这中间最简单的数据结构,然而已经有如此多需要考量的细节了.

总结 Link to 总结

非常简单的设计,但分配时与堆的大小呈线性相关关系. 不用于malloc和free函数,因为效率太低了. 通过这种数据结构的学习,我们熟悉了一系列基本概念和块的设计.