参考链接: melloc堆区的动态内存分配(该部分对应CSAPP第九章)

空闲块管理

堆被分成许多不同的blocks,只有记录空闲块位置才能进行空间分配

分配器原则

  • 处理任意请求序列
  • 立即响应请求
  • 只使用heap
  • 对齐块
  • 不修改已分配块

    隐式空闲链表

    | 块格式 | image.png | | :—-: | :—-: | | 链表 | image.png | | 说明 | “隐式”指空闲块是通过头部的大小字段隐含的连接起来,分配器访问空闲块必须经过已分配块,因此:隐式空闲链表任何操作开销都和和(空闲块+分配块)的大小成线性关系 |

显式空闲链表

块格式 image.png
显式空闲链表即构造了”双向链表”,空闲块中标记了前后空闲块地址,链表结构和隐式基本一致
说明 显式空闲链表任何操作开销都只和空闲块的大小成线性关系

放置策略⭐

当需要把数据放入free block时,需要考虑选择哪一块,即放置策略(placement policy)

最先适配(First Fit)

从链表head开始,选择最先满足需求的块

  • 优点:把较大空闲块留在了链表后

  • 缺点:容易在链表起始处产生碎片,使得速度速度降低

    下次适配(Next FIt)

    和FF类似,但每次从上次结束处开始搜索

  • 优点:比FF速度快

  • 缺点:空间利用率低

    最佳适配(Best Fit)

    从链表head开始,选择满足且最接近需求大小的块

  • 优点:空间利用率高于FF和NF

  • 缺点:需要彻底对heap进行搜索

    最坏适配(Worst Fit)

    从链表head开始,选择满足且最大的块

    分离适配(Segregated Fit)

    分离适配下分配器维护着空闲链表数组,每条链表维护大小不同的块

  • 优先进行first fit

    • 适配后,对当前块分割,提高利用率
    • 未适配,则考虑合并**(coalesce)空闲块,如果依旧不满足,则请求额外**空间,从数组中更大一级的链表中适配 | image.png | 分离适配:
      32位机中,向heap请求3个word(12bytes),最先适配到32字节的空闲块,分割成两个16字节的块 | | —- | —- |

垃圾收集器

定义:垃圾收集器是一种动态内存分配器,自动释放程序不再需要的分配块,即垃圾
思想:

  • 垃圾收集器把内存视为可达图,图中可分为root node和heap node,堆节点都位于堆中的已分配块,而根节点都不在堆中,需要无论何时都可达,可以是寄存器,栈中变量,全局变量等.p->q表示p中某个位置指向q中某处,此时q可达,而不可达节点即为垃圾,表示程序不会再去访问它
  • 垃圾收集器需要维护一张可达图,回收不可达节点,返回块给空闲链表

image.png
实际:

  • Java等对指针使用严格的语言可精确维护可达图,进行垃圾回收

  • C/C++等对指针使用更灵活的语言无法精确维护(Ch6选择第2题),保险起见,只能认为某些”垃圾”也是可达的—保守垃圾收集器

    常用算法⭐

    参考链接: 常见GC算法介绍
    Reference counting-引用计数算法
    思路:给每个对象一个引用计数器,每当对象被引用,counter就会加1；当引用失效时，counter的值就会减1.任何时刻计数器的值为0的对象就是不再被使用的,可被清除
    优点:

  • 回收空间随时进行,回收时不会引发中断挂起程序

  • 简单高效,可利用全部heap空间

缺点:

  • counter增加任务繁重
  • 实现复杂
  • 循环结构无法回收:即两个对象相互引用,计数永远是1,因此被JVM放弃

Mark and Sweep-标记清除算法
思路:分为标记和清除两阶段.

  • 标记:从根结点出发遍历对象,对访问过的对象打上标记,表示该对象可达
  • 清除:标记完成后对那些没有标记的对象进行回收(不可达对象)

缺点:

  • 效率低:两阶段效率都不高
  • 堆空间碎片化:算法结束后会产生大量不连续的堆空间碎片
  • 周期性中断:用于回收空间


Copying-复制算法
思路:将内存空间按容量分成两块,当一块内存用完的时候,就将还存活着的对象复制到另外一块上,然后把已经使用过的一块一次性全部清除.这样使得每次都是对半块内存进行内存回收,分配时就不存在内存碎片等复杂情况,只要移动堆顶的指针,按顺序分配内存即可,通常简单高效
优点:**

  • 分配时只要移动堆顶的指针即可,通常更高效

缺点:

  • 堆使用效率低下
  • 周期性中断:用于回收空间

小结

算法\特点 利用所有heap空间 发生周期性中断 处理循环结构
标记清除 ❌ ✌ ✌
引用计数 ✌ ❌ ❌
复制 ❌ ✌ ✌

内存相关Bug

间接引用坏指针
某些指针指向内存空洞或只读区域,无意中引用/写入会产生后果
如下代码,如果写成错误形式,scanf把val的值视为内存地址写入数据,结果难料

  1. //正确
  2. scanf("%d",&val);
  3. //错误
  4. scanf("%d",val);

未初始化指针
函数中未初始化的指针值是未定义(0xcccccccc),实测如下:
image.png
⭐读取未初始化的存储器
bss存储器位置总是被加载器初始化为0，但堆存储器不是这样,此时可以:

  • 显式的初始化新得到区域为0
  • 使用void calloc()代替void malloc(),malloc()不初始化分配的内存,calloc()初始化已分配的内存为0

栈溢出
栈大小优先,如果不检查串的大小就写入栈中的目标缓冲区可能会有缓冲区溢出错误
内存泄漏
未free()heap上申请的空间
⭐错误的引用指针,而非对象

  1. long a[10];  
  2. ptr = a + 5;  
  3. *ptr++ = x; //实际效果a[5]=x; ptr=ptr+1

一元运算符++和*优先级相同,则从右向左结合,即(ptr++),则指针值+1,同时后缀++的特性表示先使用当前值进行下一步计算,即a[5] = x,然后再进行ptr++(极易错写为a[6]=x)
*⭐重复free()

  1. #include <stdio.h> 
  2. #include <malloc.h>
  3. void main(void) {
  4.     int* p = (int*)malloc(100);
  5.     int* q = p;
  6.     free(p);
  7. }

实际上free(p)和free(q)结果一样,因为二者保存的地址是相同的(再次说明free及其依赖malloc时的地址),free后二者指向相同的被freed heap空间
image.png

  • 当重复free(q)时,会报关于无效heap指针的错误

image.png

选择题知识点

  1. 当C中变量被声明为static是①变量被静态分配空间②变量只对当前文件内函数可见(无论全局,局部),static声明不代表变量值不经常改变
  2. 静态变量都会自动初始化为0,见bss区
  3. ⭐关于结构体free():当free()一个使用malloc()动态分配空间创建的结构对象时,只会释放结构指针指向的堆空间,当结构体内也还有指针时,该内部指针指向空间不会被释放,可见free()释放struct结构体,尤其对于结构体中含有char* ptr时应当注意
  4. 避免重复free()的办法:为没一块设置free flag,free()前检查标记
  5. 垃圾收集器回收无法通过解引用指针访问的空间
  6. 提高内存池性能的方法是”一次性free()池中所有block”
  7. 垃圾回收器的”引用计数”: 指向当前block的指针个数
  8. 对于常用数据类型,为了提高malloc()/free()效率,可以维护一条对应数据类型大小的空闲块链表
  9. 内部碎片:被分配出去（能明确指出属于哪个进程）却不能被利用的内存空间,比如被malloc后却从未free的空间;

外部碎片:没有被分配出去（不属于任何进程),但由于太小无法分配给新进程的内存空闲区域,比如标记清除后的块

  1. 关于分配器的说法,错误的为B,分离空闲链表优先FF

A. 最理想情况,带标记边界的合并使用常数时间
B. 分离空闲链表优先BF
C. 负载必须和边界对齐
D. 显式空闲链表更快