跳到主要内容

dynomic_memory_manage

动态存储的基本问题：系统如何应用户请求分配内存，回收用户不再需要的内存。

结构中每个数据元素都只有一定的内存位置，在程序执行过程中，数据元素的出去是通过对应的存储单元来进行的。高级语言使用变量进行描述，但不会涉及具体的存储分配。。低级语言则需要对存储进行管理，将给数据分配好对应的内存地址。

在单用户系统中，整个内存分为操作系统占用部分和用户可使用部分，用户可以直接使用用户可使用部分；而多用户系统中，用户可使用部分被多个用户共享，所以只能是操作系统接管其管理。

不管什么动态管理系统，在刚开始时，这个内存区是一个"空闲块（堆）"，随着用户进入系统，先后提出存储请求，系统依次分配。在早期，用户可使用部分的存储区中，低地址为包含若干占用块，高地址为一个空闲块。一段时间后，因为内存回收，整个内存就占用块和空闲块交替出现。

我们要讨论的就是动态存储管理的策略。

可利用空间表及分配方法​

为了记录每个内存的使用情况，我们会创建一张记录内存使用情况的表，这里我们用链表。当用户请求内存时，系统从可用的空间表中删除一个节点分配之，用户释放内存时在讲它插入到空间表中。有以下几种策略：

类型请求释放优点缺点
所有的请求分配的存储量大小一样将第一个节点分配给用户将空闲块插入到表头--
给请求分配的存储大小分几个种类将大于等于用户请求的节点分配给用户，剩余的再插入小的节点中同上可能需要对小内存块进行重新组织
大小就不固定用户请求多少就给多少，具体策略见下面将其标识为未使用--

其中，大小不固定分配策略：最初，整个链表就一个节点，标识为未使用。随着内存的请求和释放，链表中有许多节点，标识分别为使用和未使用，当一个分配n的请求过来，系统处理的策略有：

类型描述
首次拟合法分配从表头开始一直找到第一个不小于n的内存未使用块
最佳拟合法分配最接近n的内存未使用块
最差拟合法不小于n的最大的内存未使用块，可以在回收时排序，分配时直接给第一个

边界标识法​

将所有的空闲块链接在一个双重循环链表结构的可利用空间表中。分配可用最佳|首次拟合进行。特点在于回收：每个内存块的头部和底部两个边界都设有标识标识该块是否为空，用户释放内存时，尽量将所有地址连续的空闲存储区组合成一个尽可能大的空闲块。

我们来看一下一个结点的数据结构：

字段含义内存开始位置长度
llink指向前驱结点的指针x1 = 相对位置 + 0a1
uplink指向本结点头部x2 = x1 + a1a2
tag块标识x3 = x2 + a2a3
size被分配内存大小x4 = x3 + a3a4
space内存本身x5 = x4 + a4a4
tag块标识x6 = x5 + a4a5
rlink指向后继结点的指针x7 = x6 + a5-

分配算法​

双向循环链表，只需从表头指针所指结点起找到最佳|首次拟合的空闲块就可进行分配，为了提高效率，有：

  • 给定一个适当常量e，当 e < 空闲块大小 - 请求大小，将空闲块一次性分配出去；
  • 头结点在每次分配后往后移动一位，避免小空闲块集中。

回收算法​

目的是讲空闲块的数量最小化，空间最大化。释放m块时时最少释放m，若左边的块l为空闲块，则两者合并；右边r同理，最终释放一个空闲块的最大产生空闲块大小为 l + m + r。

伙伴系统​

空闲块和占用块的大小都是$2^n$大小。

分配算法​

每个块大小都对应一张子表。请求n大小的内存块：

  • 从对应的子表中随机分配一个，若子表为空
  • 依次从更大的子表中随机查找到m，将m依次对开直到大小为n，将其分配，剩余的分别加入到对应的子表中。

回收算法​

其实是归并策略。只合并伙伴块。

伙伴：由同一大块裂变出来的两个块互为伙伴。

当块n进行回收时，n去查找，若存在n的伙伴块，合并为m，m再去查找，循环进行。

存储收缩​

在动态存储管理过程中，任意时刻可利用空间都地址连续（堆）。

分配算法​

在程序最初时设置一个指针p指向堆头|尾。当用户请求n大小内存时，p移动n，将移动之前的p值给用户。

回收算法​

实现需要对占用块进行标识，然后进行：

  • 计算占用块的新地址
  • 修改用户的初始变量表，时用户的程序还能正常运行
  • 检查每个占用块中存储的数据，若指向其他地方，需要进行相应修改
  • 复制数据

无用单元收集​

无用单元：用户不再使用而系统没有回收的结构和变量。 悬挂结点：若 p = malloc(size); q = p; free(p); 这时，q为悬挂结点。调用q结果不得而知。

程序通常用广义表进行存储，具体算法我们暂不讨论。