动态存储管理

Wu Jun 2020-03-23 10:52:20
01 数据结构与算法 > 数据结构

1 内存分配与回收策略

对内存的管理或对内存的分配测量通常有两种方法:

一般采用第 2 种方式。此时系统需要建立一张“可利用空闲表”,记录所有空闲块信息的表。表的形式有两种:目录表和链表。目录表中每一行代表一个空闲块,由三部分组成:初始地址、空闲块大小和使用情况;链表中每个结点代表一个空闲块,每个结点中需要记录空闲块的使用情况、大小和连接下一个空闲块的指针域。

2 可利用空间的分配方法

目录表在操作系统中详细介绍,这次仅讨论链表。

1)空间表结构

系统在不同的环境中运行,根据用户申请空间的不同,存储空闲块的可利用空间表有以下不同的结构:

  1. 如果每次用户请求的存储空间大小相同。对于此类系统中的内存来说,在用户运行初期就将整个内存存储块按照所需大小进行分割,然后通过链表链接。当用户申请空间时,从链表中摘除一个结点归其使用;用完后再链接到可利用空间表上。
  2. 每次如果用户申请的都是若干种大小规格的存储空间。针对这种情况可以建立若干个可利用空间表,每一个链表中的结点大小相同。当用户申请某一规格大小的存储空间时,就从对应的链表中摘除一个结点供其使用;用完后链接到相同规格大小的链表中。
  3. 用户申请的内存的大小不固定。所以造成系统分配的内存块的大小也不确定,回收时,链接到可利用空间表中每个结点的大小也各不一样。

2)查找方法

通常情况下系统中的可利用空间表是第 3 种情况。由于链表中各结点的大小不一,在用户申请内存空间时,就需要从可利用空间表中找出一个合适的结点,有三种查找的方法:

以上三种方法各有所长:

无论使用以上三种分配方式中的哪一种,最终内存空间都会成为一个一个特别小的内存空间,对于用户申请的空间的需求,单独拿出任何一个结点都不能够满足。为了更有效利用内存,要求回收时将相邻空闲块合并为尽可能大的结点。

3 存储紧缩

存储紧缩是另外一种动态内存管理的方法,使用这种方式在整个内存管理过程中,不管哪个时间段,所有未被占用的空间都是地址连续的存储区。这些地址连续的未被占用的存储区在编译程序中称为堆。

1)分配内存空间

在分配内存空间时,每次都从可利用空间中选择最低(或者最高)的地址进行分配。具体的实现办法为:设置一个指针(称为堆指针),每次用户申请存储空间时,都是堆的最低(或者最高)地址进行分配。假设当用户申请 N 个单位的存储空间时,堆指针向高地址(或者低地址)移动 N 个存储单位,这 N 个存储单位即为分配给用户使用的空闲块,空闲块的起始地址为堆指针移动之前所在的地址。

2)回收算法

存储紧缩有两种做法:

要实现存储紧缩,首先要对占用块进行“标志”。具体的实现过程是:

  1. 计算占用块的新地址。设立两个指针随巡查向前移动,分别用于指示占用块在紧缩之前和之后的原地址和新地址。因此,在每个占用块的第一个存储单位中,除了存储该占用块的大小和标志域之外,还需要新增一个新地址域,用于存储占用块在紧缩后应有的新地址,即建立一张新、旧地址的对照表。
  2. 修改用户的出事变量表,保证在进行存储紧缩后,用户还能找到自己的占用块。
  3. 检查每个占用块中存储的数据。如果有指向其它存储块的指针,则需作相应修改。
  4. 将所有占用块迁移到新地址去,即进行数据的传递。
  5. 最后,还要将堆指针赋以新的值。

存储紧缩较之无用单元收集更为复杂,是一个系统的操作,如果不是非不得已不建议使用。