1-概述

动态存储管理的基本问题是：系统如何按请求分配内存，如何回收内存再利用。提出请求的用户可能是系统的一个作业，也可能是程序中的一个变量。

空闲块

未曾分配的地址连续的内存区称为“空闲块”。

占用块

已分配给用户使用的地址连续的内存区称为“占用块”。

系统刚刚启动时，整个内存可看做一个大的“空闲块”，随着用户请求的进入，系统依次分配相应的内存。

在系统运行过程中，内存被分为两大部分：低地址区（若干占用块）和高地址区（空闲块）。

经过一段时间后，有的程序运行结束，释放掉它所占用的内存，使之变为空闲块，这就使整个内存中空闲块和占用块之间出现了相互交错的现象。如下图：

当系统进入到图中b），又有新的用户请求分配内存时，系统该如何处理呢？

方法一：系统继续从高地址区的空闲块进行分配，直到无法分配。当剩余的空闲块不能满足分配请求时，系统才去回收所有的不再使用的内存区，并重新组织内存，紧凑所有的空闲块为一个大的空闲块，以备在分配。

方法二：空闲链表。空闲链表中包含了所有空闲块的信息，一个节点对应一个空闲块。当用户请求分配时，系统所作的工作就是搜索空闲链表，按某种策略找到一个合适的空闲块进行分配，并删除对应的节点。当用户释放所占用的内存时，系统回收该内存，并将它插入到空闲链表中。

空闲链表

空闲链表三种结构形式：

（1）所有请求的内存大小相同。这是一种最简单的动态存储管理方式。

对此，系统通常的做法是：

a）系统启动时，将内存按大小均分成若干个块，并形成一个链表。

b）分配时，只需将链表中第一个节点分配给用户即可，无需扫描整个链表。

c）回收时，将空闲块插入到链表头即可。

（2）所有请求的内存大小有n种规格。可创建n个（1）情况中的链表，分配与回收与（1）类似，不同之处在于：当请求的链表为空时，需要在节点大的链表上进行分配，取一部分内存给用户，剩余部分作为一个新节点插入到相应的链表中。

（3）所有请求的内存大小是不同的，是不断发生变化的。这种情况下的分配与回收见下篇。

分配算法和回收

对于内存块大小不同的空闲链表，假如有一个大小为N的内存申请，如果空闲链表中大于N的内存只有一块，假如大小为M，就把M的一部分分配给用户，同时把剩余的M-N的部分作为一个节点插入到空闲链表中。

当大于N的内存有多块时，我们该如何分配呢？通常有以下三种方法：

（1）最先适配法。顾名思义，顺序扫描空闲链表，找到第一个大于等于N的空闲块，把其中的N分配给用户。因为链表不按内存的地址有序，也不按大小有序，所以回收内存块放到表头即可。

问题：运行一段时间后，链表中将会出现一些非常小的块，并在这些小块都在链表的前边。

（2）最优适配法。在空闲链表中找到一个不小于N并且最接近N的空闲块分配给用户。分配时需要整表扫描。如果链表按空闲块从小到大有序，分配时只需找到第一个大于N的空闲块，回收时需要插入到链表合适的位置上。

（3）最差适配法。将链表中不小于N且是链表中最大的空闲块的一部分分配给用户。链表可按空闲块从大到小的顺序排列，分配只需判断链表第一个空闲块即可，回收时需要插入到链表合适的位置上。

对于回收，我们考虑的不仅仅是归还节点，还要考虑空闲块的合并问题。这种把物理地址相邻的空闲块的合并以取得更大的空闲块的方法是需要的。空闲链表中的空闲块并不是按物理地址有序的，那又如何快速合并呢？下篇中将讨论一种方法：边界标识法

边界标识法

原文链接：http://blog.csdn.net/hbuxiaoshe/article/details/5994743

就空闲链表来说，要确定哪些空闲块是物理地址相邻的，确实不太容易，需要整表扫描。

边界标识法能够有效的判断空闲块的物理相邻内存块是否为空闲块。

所有的空闲块组成一个双向循环链表，链表中每一个节点的结构如下：

llink和rlink分别指向链表中的前驱后继节点。

size表明内存块的大小。

uplink指向本块的首地址，图中箭头，其作用下面讲述。

tag头和尾中各有一个，作为内存块边界的标识，0表空闲块，1表占用块。

分配时同样会在链表上产生很多非常小的空闲块，影响分配的效率，因此，可以定义一个全局的指针p，当不为空时分配，使其始终指向刚进行过分配的节点的后继节点。

回收时判断物理相邻的块是否为空闲块的方法：

假设当前回收块的物理地址为p（下面涉及到的左邻块和右邻块都是物理地址相邻的，在循环链表中也许不相邻），

左邻块：左邻块的尾的地址是p1=p-sizeof(尾)，左邻块是否为空闲块的判断则为p1->tag是否为0。当为空闲块时，只需将当前块合并到左邻块中即可，而左邻块的地址则需要由uplink来获得（原因是中间内存块的大小是不固定的，不能通过偏移来实现），即p1->uplink。修改左邻块的size和uplink即可。

右邻块：右邻块的首的地址为p2=p+sizeof(头)，右邻块是否为空闲块的判断则为p2->tag是否为0。当为空闲块时，与右邻块合并，修改p的llink、rlink和size，修改p2的uplink。

你可能会认为，既然链表中的块都是空闲块，干吗还要加上tag标识位呢？我的回答是，如果没有tag，当我们找到右邻块的地址时，没有办法判断右邻块是不是链表中的一个节点，也许它还在被用户使用着。那为什么要用两个tag呢？个人觉得，用一个也可以，但用两个更容易判断。