1.内存管理
1.1内存分为三部分
（1）栈区：
存放局部变量。函数调用结束，栈上相应内容被销毁。
（2）堆区：
由malloc或者new分配的内存。由free或者delete决定生命周期，如果没有释放，会一直存在，直到程序结束。
（3）数据区：
存放全局变量、静态变量。
（4）补充栈区和堆区的区别：
①管理方式：堆区的空间需要程序员自己利用malloc函数申请，调用free函数释放的。而栈区的空间是程序进行分配与释放管理的。
②增长方式：堆区的增长方式是通过低地址向高地址进行扩展的，是不连续的内存区域。而栈区是由高地址向低地址进行扩展的，是连续的内存区域。
③空间大小：堆区的空间大小比较大。但是栈区的空间大小比较小。
④内存碎片：堆区产生的内存碎片比较多，因为如果申请的空间小与系统分配出来的大小，那么系统会将剩余的空间依旧放入空闲链表中。但是栈区是不会存在内存碎片的问题，因为栈区的特点是先进后出。
⑤分配效率：堆区空间的分配是需要调用相关的函数，所以效率比较低。但是栈区是通过专门的寄存器存放栈的地址，压栈出栈由专门的指令执行，效率比较高。
⑥分配方式：堆区只能动态分配并且手动释放。但是栈区可以动态分配也可以静态分配，静态分配是由编译器完成，动态分配是通过调用alloc函数在栈上申请空间。
⑦分配后系统相应：操作系统为堆区维护了一个空闲链表，当用户向堆区申请空间，操作系统就会遍历空闲链表寻找第一个大小可用的空间结点，然后将这片空间的结点从空闲链表中删除，并将结点返回给程序使用。如果空闲链表中没有大小可用的空间，就会调用系统的功能去增加程序数据段的内存空间，然后将可用大小的内存返回。但是对于栈区而言，如果剩余空间大于需要申请的空间，系统就会为程序提供内存，否则报告异常提示栈溢出。
1.2内存操作经常出现的五大问题
（1）没有为指针分配合法的内存
（2）为指针分配的内存大小不够
（3）分配内存但未初始化
（4）指针访问的内存越界
（5）内存泄漏
2.动态内存分配
动态内存分配器维护着一个进程的虚拟内存——堆。分配器将堆视为一组大小不同的块的集合来维护。每个块就是一个连续的虚拟内存片，要么是已经分配的，要么是空闲的。分配器有两种基本的风格：
显示分配器：要求显示地释放任何已经分配的块。例如：C语言里面的malloc函数分配一个块，使用解释之后调用free函数释放一个块。
隐式分配器：要求分配器检测一个已分配块何时不再被程序所使用，就释放这个块。例如垃圾收集器。
那么，问题来了，为什么要使用动态内存分配呢？
原因是当我们在程序设计的时候，需要申请一个数组的大小，但是这个数组的大小我们提前并不知道多大，只有在运行的时候我们才可以根据某个变量来动态的分配数组的空间，如果提前设定好数组的大小为某个值，就会出现数组空间浪费或者数组空间不足的情况，所以动态的分配可以在不修改源码的情况下做到恰到好处。
2.1分配器的要求和目标
（1）要求：
处理任意请求序列
不修改已经分配的块
只在堆区进行分配
遵守内存对齐的原则
立即响应
（2）目标：
最大化吞吐率
最大化内存利用率
2.2分配器的实现问题
由于分配器从不重复使用任何块，内存利用率极差，所以需要考虑到：
①空闲块组织：如何组织空闲块？
②放置：怎样选择一个合适的空闲块来放置一个新分配的块？
③分割：将一个新分配的块放置到某个空闲块之后，如何处理这个空闲块中的剩余部分？
④合并：如何处理被释放的块？
2.3简单分配器的设计与实现——隐式空闲链表
（1）隐式空闲链表的概念：
所谓的隐式空闲链表就是通过空闲块头部的大小字段隐式的连接起来。
（2）隐式空闲链表的优点：
简单。
（3）隐式空闲链表的缺点：
任何操作的开销，如防止分配块，就需要遍历整个空闲链表，寻找空闲块，所以搜索的时间是与堆中已分配块和空闲块的总数呈线性关系。
2.3.1隐式空闲链表的初始化：
（1）使用边界的堆块格式：
使用边界标记（所谓的边界标记就是每一个块的脚部），使得块无论是判断当前块的下一个块是否空闲还是当前块的上一个块是否空闲，都能够在O(1)的时间复杂度下进行判断。
（2）隐式空闲链表的形式：
如下图：
第一个字是一个八个字节边界的不使用的填充字。
序言块是一个八个字节的已分配块，由一个头部和一个脚部组成，在初始化的时候创建，并且用不释放。
序言块后面是多个由malloc或者free调用创建的普通块。
堆总是以一个特殊的结尾块结束，其中的0/1表示：大小为0，已分配的块(用1表示)。
（3）初始化空闲链表代码：
#include <stdio.h>
#include <malloc.h>
#define MAX_HEAP (1<<12)//模拟虚拟内存的大小
//静态空闲链表的初始化部分
static char* mem_heap;//指向堆的第一个字节
static char* mem_brk;//指向堆的最后一字节加1
static char* mem_max_addr;//指向最大合法堆加1
char *heap_listp=NULL; //序言块与结尾块之间靠序言块那一侧的指针
char *next_listp=NULL; //下一次适配的全局变量
void mem_init(void)
{
mem_heap = (char*)malloc(MAX_HEAP);
mem_brk = (char*)mem_heap;
mem_max_addr = (char*)mem_heap + MAX_HEAP;
}
void* mem_sbrk(int incr)
{
char* old_brk = mem_brk;
if ((incr<0)||(mem_brk+incr)>mem_max_addr)
{
return (void*)-1;
}
//通过模拟内核的brk指针增加incr来扩展和搜索堆
mem_brk += incr;
return (void*)old_brk;
}
（4）分析图：
mem_init()函数代码分析图：
mem_sbrk（）函数代码分析图：
2.3.2操作空闲链表的基本常数和宏：
//操作空闲链表的基本常数和宏
#define WSIZE 4//单字4字节对齐
#define DSIZE 8//双字8字节对齐
#define CHUNKSIZE (1<<8)//扩展堆的总字节数
#define MAX(x,y) ((x)>(y)?(x):(y))//求最大值
#define PACK(size,alloc) ((size)|(alloc))//将头部的大小和分配位通过“|”加起来返回一个值
#define GET(p) (*(unsigned int *)p)//读取参数p所指向的值
#define PUT(p,val) (*(unsigned int*)(p)=(val))//将参数p所指向的值修改为val
#define GET_SIZE(p) (GET(p)&~0x7)//0x70是块头部的最后三位，取反之后就可以得到块头部的大小位，从而计算块的大小
#define GET_ALLOC(p) (GET(p)&0x1)//计算块的分配位是已经分配还是未分配
#define HEAD(p) ((char *)(p)-WSIZE)//将P指针移动到这个块的头部
#define TAIL(p) ((char *)(p)+GET_SIZE(HEAD)-DSIZE)//将p指针移动到这个块的尾部
#define NEXT_BLKP(p) ((char*)(p)+GET_SIZE(((char*)(p)-WSIZE)))//指向下一个块
#define PRE_BLKP(p) ((char*)(p)-GET_SIZE(((char*)(p)-DSIZE)))//指向上一个块
2.3.3创建初始化空闲链表：
mm_init函数从内存系统得到4个字，并将它们初始化，创建一个空的空闲链表。
然后调用extend_heap函数将堆扩展CHUNKSIZE字节，并且创建初始空闲块。
需要明确的是：
extend_heap()函数的调用情况有两种：
第一种情况是在堆被初始化的时候使用。
第二种情况是当堆里面没有合适的匹配块的时候，像系统申请额外的堆空间。
（1）代码：
//创建初始化空闲链表
int mm_init(void)
{
//将heap_listp从虚拟内存中申请4*WSIZE个字节，如果失败返回-1,如果成功继续执行后面的操作
heap_listp = (char*)mem_sbrk(4 * WSIZE);
if (heap_listp == (void*)-1) //证明虚拟内存不够
{
return -1;
}
//初始化填充字部分
PUT(heap_listp, 0);
//初始化序言块——一共八字节，包括头部和脚部
PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1));//头部
PUT(heap_listp + (2 * WSIZE),PACK(DSIZE, 1));//脚部
//初始化结尾块——其中0表示大小，1表示占位
PUT(heap_listp + (3 * WSIZE), PACK(0, 1));
//将heap_listp移动到头部的后面
heap_listp += (2 * WSIZE);
//如果扩展堆失败返回-1
if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
{
return -1;
}
return 0;
}
//用一个新的空闲块扩展堆
static void* extend_heap(size_t words)
{
char* bp;
size_t size;
//该块的大小是双字的整数倍
size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
if ((long)(bp = (char*)mem_sbrk(size)) == -1)
{
return NULL;
}
PUT(HEAD(bp), PACK(size, 0));
PUT(TAIL(bp), PACK(size, 0));
PUT(HEAD(NEXT_BLKP(bp)), PACK(0, 1));//更新结尾块
return coalesce(bp);
}
（2）代码分析图：
mm_init()函数：
extend_heap()函数：
2.3.4放置已分配的块：
（1）放置策略：
①首次适配：从头开始搜索空闲链表，当发现能够满足申请的空闲块时，就使用。
优点：趋向于将大的空闲块保存在链表的后面。
缺点：空闲链表前面的内存碎片比较多，增加了对较大空闲块的搜索时间。
②下一次适配：之前使用了某一个空闲块，那么下一次适配就是从之前分配的那个空闲块的下一个地方开始寻找满足申请的空闲块。
优点：这种方法比首次适配用起来运行会快一些。
③最佳适配：从头到尾遍历空闲链表，然后寻找最合适的空闲块用来满足申请。
优点：能够找到最合适的空闲块，减少空闲链表的内存碎片，提高内存利用率。
缺点：需要对空闲链表进行彻底搜索，时间复杂度比较高。
（2）分割空闲块：
分配器会将选择的这个空闲块分为两部分，一部分是变为分配块，然后让剩余的那部分变为新的空闲块，从而减少内部碎片。
（3）获取额外的堆内存：
①合并内存中物理相邻的空闲块，从而组成一个大的空闲块以供使用
②调用sbrk()函数向内核请求额外的堆内存，分配器将额外的堆内存转化为一个大的空闲块，将这个块插入空闲链表中，然后将被请求的块放置在这个新的空闲块中。
（4）代码：
//查找空闲块并返回指向空闲块的指针——采用首次适配搜索
static char* find_fit(size_t asize)
{
char* i;
for (i = heap_listp; GET_SIZE(HEAD(i))>0; NEXT_BLKP(i))
{
if (!GET_ALLOC(HEAD(i)) && (asize <= GET_SIZE(HEAD(i))))
{
return i;
}
}
return NULL;
}
//放置已分配的块
static void place(char* bp, size_t asize)
{
//获取的空闲分配块中不需要使用的部分，也就是剩余的
size_t size = GET_SIZE(HEAD(bp)) - asize;
//如果分割之后剩余的块>=2*DSIZE（这里之所以要以2*DSIZE为判断条件，是因为头部尾部占DSIZE个字，剩余一个DSIZE供下一次使用），就进分割
if (size >= (2 * DSIZE))
{
PUT(HEAD(bp), PACK(asize, 1));//设置头部
PUT(TAIL(bp), PACK(asize, 1));//设置脚部
PUT(HEAD(NEXT_BLKP(bp)), PACK(size, 0));
PUT(TAIL(NEXT_BLKP(bp)), PACK(size, 0));
}
//否则的话就没有分割的意义，因为即使分割了，下一次即使是很小的请求也无法使用，都是碎片,所以索性不分割
else
{
PUT(HEAD(bp), PACK(GET_SIZE(HEAD(bp)), 1));//设置头部
PUT(TAIL(bp), PACK(GET_SIZE(HEAD(bp)), 1));//设置脚部
}
}
//分配块
void* mm_malloc(size_t size)
{
size_t asize;
size_t extendsize;
char* bp;
//如果是无效请求直接返回
if (size == 0)
{
return NULL;
}
if (size <= DSIZE)
{
//如果请求小与或者等于8字节，由于头部和脚部一共8字节+size，然后向上扩展尾8的倍数
asize = 2 * DSIZE;
}
else
{
//申请的字节数扩展尾8的倍数，需要加上（DSIZE-1）的原因，举个例子：
/*
如果size=5,加上头部和脚部：5+8=13
如果直接用13/8=1，然后再×8得到的结果为8，这明显是不满足申请要求的
所以需要加上DSIZE-1，——》8*((5+8+7)/8)=16
*/
asize = DSIZE * ((size + DSIZE + (DSIZE - 1)) / DSIZE);
}
//从空闲链表查找合适的空闲块并放置
if ((bp =(char*) find_fit(asize)) != NULL)
{
place(bp, asize);
return bp;
}
//如果从空闲链表中没有找到合适的空闲块，就需要在虚拟内存中进行扩展
extendsize = MAX(asize, CHUNKSIZE);
bp = (char*)extend_heap(extendsize / WSIZE);
//表示虚拟内存中也没足够的空间，所以直接返回NULL
if (bp == NULL)
{
return NULL;
}
place(bp, asize);
return bp;
}
（5）代码函数分析图：
find_fit()函数和place()函数分析图：
mm_malloc()函数分析图：
2.3.5空闲链表的释放与合并：
（1）合并空闲块：
当分配器释放一个已分配块时，可能有其他空闲块与当前释放的这个块相邻，为了能够减少内存碎片，分配器会将这种情况下的空闲块进行合并。合并的策略有两种:一种是立即合并，这种方式说白了就是释放当前块之后，立即检测与它相邻的块是否空闲，如果空闲，立即合并，这种方式有一个弊端：如果释放之后合并，然后又会申请之前释放的那么大一个空间，那么分配器又要分割，用完又要合并，这样反复执行就会显得合并空闲块多此一举。另外一种合并的策略是推迟合并，也就是等到某个稍晚的时候再合并空闲块。
那么如何检测释放的当前块的相邻块是否是空闲呢？
堆块的格式有头部和脚部，脚部是头部的一个副本，分配器可以通过检查下一个块的头部判断是否已分配，通过检查上一个块的脚部判断是否已分配。
（2）代码:
//合并空闲块
void my_free(void* bp)
{
size_t size = GET_SIZE(HEAD(bp));
PUT(HEAD(bp), PACK(size, 0));
PUT(TAIL(bp), PACK(size, 0));
coalesce(bp);
}
static void* coalesce(void* bp)
{
size_t prev_alloc = GET_ALLOC(TAIL(PRE_BLKP(bp)));
size_t next_alloc = GET_ALLOC(HEAD(NEXT_BLKP(bp)));
size_t size = GET_SIZE(HEAD(bp));
//第一种情况：前后块都不空闲
if (prev_alloc && next_alloc)
{
return bp;
}
//第二种情况：前面的块不空闲，但是后面的块空闲
else if (prev_alloc && !next_alloc)
{
size += GET_SIZE(HEAD(NEXT_BLKP(bp)));
PUT(HEAD(bp), PACK(size, 0));
PUT(TAIL(bp), PACK(size, 0));
}
//第三种情况：前面的块空闲，后面的块不空闲
else if (!prev_alloc && next_alloc)
{
size += GET_SIZE(TAIL(PRE_BLKP(bp)));
PUT(HEAD(PRE_BLKP(bp)), PACK(size, 0));
PUT(TAIL(bp), PACK(size, 0));
bp = PRE_BLKP(bp);
}
//第四种情况：前面的块空闲，后面的块也空闲
else
{
size += GET_SIZE(TAIL(NEXT_BLKP(bp))) + GET_SIZE(HEAD(PRE_BLKP(bp)));
PUT(HEAD(PRE_BLKP(bp)), PACK(size, 0));
PUT(TAIL(NEXT_BLKP(bp)), PACK(size, 0));
bp = PRE_BLKP(bp);
}
return bp;
}
（3）代码函数分析图：
coalesce（）函数：
2.4显示空闲链表
2.4.1基本概念
与隐式空闲链表相比，显示空闲链表就是把空闲内存块单独拿出来组成一个链表。
2.4.2显示空闲链表的优点：
可以使得首次适配方法的时间复杂度降低，从块总数（n）的线性时间减少到空闲块数量的线性时间（m）,O(m)<O(n)，其中m<n。
但是释放一个块的时间取决于选择的空闲链表中块的排序策略，如果使用后进先出的顺序维护表，这种情况释放一个块在常数时间内完成。
合并块的时间复杂度是O(1) 。
