1 内存分配与回收策略
- 分配结构：需要登记内存使用情况，供分配程序使用的表格与链表。
- 放置策略：
对内存的管理或对内存的分配测量通常有两种方法：
- 系统从高地址的空闲块分配空间，直到分配无法进行，系统才会去回收之前的空闲块，重新组织继续分配；
- 当用户运行一结束，系统马上将其所占空间进行回收。当有新的用户请求分配内存时，系统遍历所有的空闲块，从中找出一个合适的空闲块分配给用户。
一般采用第 2 种方式。此时系统需要建立一张“可利用空闲表”，记录所有空闲块信息的表。表的形式有两种：目录表和链表。目录表中每一行代表一个空闲块，由三部分组成：初始地址、空闲块大小和使用情况；链表中每个结点代表一个空闲块，每个结点中需要记录空闲块的使用情况、大小和连接下一个空闲块的指针域。
2 可利用空间的分配方法
目录表在操作系统中详细介绍，这次仅讨论链表。
1）空间表结构
系统在不同的环境中运行，根据用户申请空间的不同，存储空闲块的可利用空间表有以下不同的结构：
- 如果每次用户请求的存储空间大小相同。对于此类系统中的内存来说，在用户运行初期就将整个内存存储块按照所需大小进行分割，然后通过链表链接。当用户申请空间时，从链表中摘除一个结点归其使用；用完后再链接到可利用空间表上。
- 每次如果用户申请的都是若干种大小规格的存储空间。针对这种情况可以建立若干个可利用空间表，每一个链表中的结点大小相同。当用户申请某一规格大小的存储空间时，就从对应的链表中摘除一个结点供其使用；用完后链接到相同规格大小的链表中。
- 用户申请的内存的大小不固定。所以造成系统分配的内存块的大小也不确定，回收时，链接到可利用空间表中每个结点的大小也各不一样。
2）查找方法
通常情况下系统中的可利用空间表是第 3 种情况。由于链表中各结点的大小不一，在用户申请内存空间时，就需要从可利用空间表中找出一个合适的结点，有三种查找的方法：
- 首次拟合法：在可利用空间表中从头开始依次遍历，将找到的第一个内存不小于用户申请空间的结点分配给用户，剩余空间仍留在链表中；回收时只要将释放的空闲块插入在链表的表头即可。
- 最佳拟合法：和首次拟合法不同，最佳拟合法是选择一块内存空间不小于用户申请空间，但是却最接近的一个结点分配给用户。为了实现这个方法，首先要将链表中的各个结点按照存储空间的大小进行从小到大排序，由此，在遍历的过程中只需要找到第一块大于用户申请空间的结点即可进行分配；用户运行完成后，需要将空闲块根据其自身的大小插入到链表的相应位置。
- 最差拟合法：和最佳拟合法正好相反，该方法是在不小于用户申请空间的所有结点中，筛选出存储空间最大的结点，从该结点的内存空间中提取出相应的空间给用户使用。为了实现这一方法，可以在开始前先将可利用空间表中的结点按照存储空间大小从大到小进行排序，第一个结点自然就是最大的结点。回收空间时，同样将释放的空闲块插入到相应的位置上。
以上三种方法各有所长：
- 最佳拟合法由于每次分配相差不大的结点给用户使用，所以会生成很多存储空间特别小的结点，以至于根本无法使用，使用过程中，链表中的结点存储大小发生两极分化，大的很大，小的很小。该方法适用于申请内存大小范围较广的系统
- 最差拟合法，由于每次都是从存储空间最大的结点中分配给用户空间，所以链表中的结点大小不会起伏太大。依次适用于申请分配内存空间较窄的系统。
- 首次拟合法每次都是随机分配。在不清楚用户申请空间大小的情况下，使用该方法分配空间。
- 同时，三种方法中，最佳拟合法相比于其它两种方式，无论是分配过程还是回收过程，都需要遍历链表，所有最费时间。
无论使用以上三种分配方式中的哪一种，最终内存空间都会成为一个一个特别小的内存空间，对于用户申请的空间的需求，单独拿出任何一个结点都不能够满足。为了更有效利用内存，要求回收时将相邻空闲块合并为尽可能大的结点。
3 存储紧缩
存储紧缩是另外一种动态内存管理的方法，使用这种方式在整个内存管理过程中，不管哪个时间段，所有未被占用的空间都是地址连续的存储区。这些地址连续的未被占用的存储区在编译程序中称为堆。
1）分配内存空间
在分配内存空间时，每次都从可利用空间中选择最低（或者最高）的地址进行分配。具体的实现办法为：设置一个指针（称为堆指针），每次用户申请存储空间时，都是堆的最低（或者最高）地址进行分配。假设当用户申请 N 个单位的存储空间时，堆指针向高地址（或者低地址）移动 N 个存储单位，这 N 个存储单位即为分配给用户使用的空闲块，空闲块的起始地址为堆指针移动之前所在的地址。
2）回收算法
存储紧缩有两种做法：
- 一旦用户释放所占空间就立即进行回收紧缩；
- 在程序执行过程中不立即回收用户释放的存储块，而是等到可利用空间不够分配或者堆指针指向了可利用存储区的最高地址时才进行存储紧缩。
要实现存储紧缩，首先要对占用块进行“标志”。具体的实现过程是：
- 计算占用块的新地址。设立两个指针随巡查向前移动，分别用于指示占用块在紧缩之前和之后的原地址和新地址。因此，在每个占用块的第一个存储单位中，除了存储该占用块的大小和标志域之外，还需要新增一个新地址域，用于存储占用块在紧缩后应有的新地址，即建立一张新、旧地址的对照表。
- 修改用户的出事变量表，保证在进行存储紧缩后，用户还能找到自己的占用块。
- 检查每个占用块中存储的数据。如果有指向其它存储块的指针，则需作相应修改。
- 将所有占用块迁移到新地址去，即进行数据的传递。
- 最后，还要将堆指针赋以新的值。
存储紧缩较之无用单元收集更为复杂，是一个系统的操作，如果不是非不得已不建议使用。