复盘动态内存管理机制

对于内存两大问题

• 向系统提出的申请空间的请求，系统如何分配内存？
• 在完成使用之前申请的内存空间后，系统又如何回收？

占用块和空闲块

对于计算机的内存来说，对已经分配使用的内存区称为“占用块”，还未分配出去的内存区统称为“空闲块”或者“可利用空间块”

堆

对于初始状态下的内存来说，整个空间都是一个空闲块（在编译程序中称为“堆”）。但是随着不同的用户不断地提出存储请求，系统依次分配

系统的内存管理

整个内存区就会分割成两个大部分：低地址区域会产生很多占用块；高地址区域还是空闲块

但是当某些用户运行结束，所占用的内存区域就变成了空闲块

这样就形成了空闲快和占用块交错的情况，系统对于后续的内存分配就有了两种分配方式

1. 系统继续将高内存地址分配给新的内存申请

2. 当用户运行结束，系统将其内存空间进行回收，当有新的用户请求分配内存时，系统遍历所有的空闲块，从中找出一个合适的空闲块分配给用户

分配存储空间的方式

1. 首次拟合法：在可利用空间表中从头开始依次遍历，将找到的第一个内存不小于用户申请空间的结点分配给用户，剩余空间仍留在链表中；回收时只要将释放的空闲块插入在链表的表头即可。

2. 最佳拟合法：和首次拟合法不同，最佳拟合法是选择一块内存空间不小于用户申请空间，但是却最接近的一个结点分配给用户。为了实现这个方法，首先要将链表中的各个结点按照存储空间的大小进行从小到大排序，由此，在遍历的过程中只需要找到第一块大于用户申请空间的结点即可进行分配；用户运行完成后，需要将空闲块根据其自身的大小插入到链表的相应位置。

3. 最差拟合法：和最佳拟合法正好相反，该方法是在不小于用户申请空间的所有结点中，筛选出存储空间最大的结点，从该结点的内存空间中提取出相应的空间给用户使用。为了实现这一方法，可以在开始前先将可利用空间表中的结点按照存储空间大小从大到小进行排序，第一个结点自然就是最大的结点。回收空间时，同样将释放的空闲块插入到相应的位置上。

以上三种方法中，最佳拟合法无论是分配过程还是回收过程，都需要遍历链表，所以效率最低