一种关于易失性内存的管理方法

本申请涉及计算机存储技术领域，尤其涉及一种关于易失性内存的管理方法。

在计算机系统里，存储资源可按持久性分为两类：易失性存储和持久性存储。易失性存储，如目前在主流设备中广泛使用的DDR，或者静态RAM，使用时必须一直加电。如果掉电，则存储的内容就丢失。持久性存储，如闪存(FLASH)，可擦可编程只读存储(EEPROM)，只读存储(ROM)，磁性存储(硬盘)，在掉电后依然可以保持存储信息不丢失。

存储管理涉及到分配和释放。在早期的编程语言中，存储的分配和释放都是由程序员管理。比如在C编程语言所提供的libc函数库中，可以使用malloc()函数分配内存，使用free()函数。但在很多现代面向对象的系统中都引入了垃圾回收，存储回收由系统自动处理，不需要程序员干预。

存储管理中最大的问题是内存碎片的问题。内存碎片问题是指计算机系统运行一段时间之后，经过若干次分配和释放，内存中产生了很多空闲的内存碎片。那么就可能在新的内存分配请求到来时，虽然总的空闲空间大于请求，但是因为不连续，导致新的内存分配请求失败。

首次适应(First-Fit)是内存分配算法中的一种，该算法以空闲链的首地址递增顺序组织起来，当提出分配需求时，遍历组织好的空白链，到第一个空间大于等于分配需求的空白分配块分配。若遍历一遍都未到满足需求的空白块，则分配失败。该算法倾向于优先利用低地址部分的空闲块，保留高地址部分的空闲块，则高地址部分就有可能留有大容量的内存块，为大需求的作业创造条件。但算法每次都是从低地址起，导致其低地址留下了许多无法使用的外部碎片，降低了后续查的效率。

存储管理有很多策略。针对不用的应用场景，可以有不同的方法使得存储管理最有效率。本申请提出一种新的关于易失性存储的管理方法，可以在首次适应(First-Fit)的基础上提供一种新的内存碎片压缩的方法，在某些应用场景，比如小需求的作业分配频繁、大需求的作业数量少的情况下可以提高存储管理效率。

为实现上述目的，本申请提供一种关于易失性内存的管理方法，基于系统和管理对象，所述系统包含易失性和持久性两种存储，所述易失性存储是一段地址连续的线性空间；所述管理对象的基础信息存储于持久性存储，实际数据存储于易失性存储；所述系统能遍历所述管理对象；其特征在于，所述方法包括：

初始化易失性存储空间，将所述易失性存储空间清零；制定分配策略和垃圾回收策略；

判断管理对象请求存储块的大小，当所述请求存储块的大小超过阈值，为大对象申请；否则，为小对象申请；

当可分配空间的大小满足所述请求存储块的大小时，按所述分配策略给所述大对象申请在可分配空间的尾侧或头侧分配内存，给所述小对象申请在可分配空间的另一侧分配内存；可分配空间总是位于整个存储空间的中部；

当可分配空间的大小不满足所述请求存储块的大小时，系统按照标记-清除算法遍历所有管理对象并标记活跃管理对象，对非活跃管理对象所占的数据域视为空闲空间按所述垃圾回收策略进行垃圾回收；

所述垃圾回收当所述分配策略在尾侧分配内存时，先对存储空间从尾至所述可分配空间尾部的区域，逐步向尾移动并链接活跃管理对象数据域，后对存储空间从头至所述可分配空间头部的区域，逐步向头移动并链接活跃管理对象数据域，以合并形成连续的空闲空间；当所述分配策略在头侧分配内存时，则先后顺序相反；

当所述垃圾回收策略为部分回收时，在所述连续的空闲空间满足请求存储块的大小时对所述连续的空闲空间进行分配内存并停止垃圾回收；当所述垃圾回收策略为全部回收时按照所述分配策略进行分配内存；

所述分配内存完成后在管理对象的基础信息中记录分配的数据域地址指针。

实际应用中，内存分配的各种技术已经相当成熟。只有针对特定场景的内存分配管理还有值得优化的余地。本申请是对简单分配(first-fit)算法的优化，小对象分配在可分配空间的一端，大对象分配在可分配空间另一端，可以减少内存碎片发生。另外，系统对内存垃圾进行回收的过程中，满足内存分配要求的时候，可以做部分回收，不需要进行全部回收，提高了内存分配的效率。

为了更简单说明本发明实施例的技术方案，下面将对实施例描述中所需要使用的附图作简单的介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本申请方法的流程示意图；

图2为本申请方法垃圾回收的流程示意图；

图3为本申请方法头部表垃圾回收的流程示意图；

图4为本申请方法尾部表垃圾回收的流程示意图。

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例，本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围

图1中，本发明提出的一种关于易失性内存的管理方法，基于系统和管理对象，系统包含易失性和持久性两种存储，易失性存储是一段地址连续的线性空间；管理对象的基础信息存储于持久性存储，实际数据存储于易失性存储；系统能遍历管理对象；方法步骤包括：

初始化易失性存储空间，将易失性存储空间清零；制定分配策略和垃圾回收策略；

判断管理对象请求存储块的大小，当请求存储块的大小超过阈值，为大对象申请；否则，为小对象申请；

当可分配空间的大小满足请求存储块的大小时，按分配策略给大对象申请在可分配空间的尾侧或头侧分配内存，给小对象申请在可分配空间的另一侧分配内存；可分配空间总是位于整个存储空间的中部；

当可分配空间的大小不满足请求存储块的大小时，系统按照标记-清除算法遍历所有管理对象并标记活跃管理对象，对非活跃管理对象所占的数据域视为空闲空间按垃圾回收策略进行垃圾回收；

执行垃圾回收：当分配策略在尾侧分配内存时，先对存储空间从尾至可分配空间尾部的区域，逐步向尾移动并链接活跃管理对象数据域，后对存储空间从头至可分配空间头部的区域，逐步向头移动并链接活跃管理对象数据域，以合并形成连续的空闲空间；当分配策略在头侧分配内存时，则先后顺序相反；

当垃圾回收策略为部分回收时，在连续的空闲空间满足请求存储块的大小时对连续的空闲空间进行分配内存并停止垃圾回收；当垃圾回收策略为全部回收时按照分配策略进行分配内存；

分配内存完成后在管理对象的基础信息中记录分配的数据域地址指针。

本发明提出的一种关于易失性内存的管理方法，还包括，在满足重置条件时，需要执行系统重置，对易失性存储空间进行分配重置；系统重置使系统遍历所有管理对象，对每一个活跃的管理对象，根据其类型和大小，使用分配策略重新分配该对象所需要的空间；

可选的，重置条件包括：接收到系统重置指令，系统内存管理模块分配内存达到预定次数，系统重新上电，系统切换到一个新的运行模式；

系统重置的前提为：经过若干次运行，系统已经创建了若干对象，这些对象的基础信息保留于持久性存储上，但对象的数据域里所保留的信息已经丢失，也不需要恢复。

在一个实施例中，管理对象的基础信息包含类型，大小、安全权限和数据域地址指针；数据域地址指针P，指向易失性存储。

在一个实施例中，请求存储块使用完毕后，按照特殊需求确定是否对请求存储块数据域清零；可选的，特殊需要为出于数据保密安全的需要。

在一个实施例中，易失性存储空间基地址表示为base，大小为size；可分配空间起始地址表示为head，结束地址为tail，可分配空间size＝tail-head。

在一个实施例中，初始化易失性存储空间表示为：令head＝base，tail＝base+size。

在一个实施例中，阈值sma110bjSize的大小根据系统要求和应用场合可以有不同的设定。

在一个实施例中，分配策略从可分配空间的两头进行分配，剩余可分配空间总是位于整个存储空间的中部；

可选的，分配策略可在分配请求时指定、由系统随机指定或由系统配置指定。

在一个实施例中，垃圾回收策略包括全部回收和部分回收，部分回收需要知道请求的空间大小len。

图2中，垃圾回收步骤包括：

系统按照标记-清除算法从根开始访问并标记所有活跃对象，生成头部表和尾部表，记录所有管理对象的数据域地址指针和大小，并按地址从低到高排序；然后再遍历一次整个内存区域，把所有没有标记活跃的对象进行回收处理。

其中，头部表：所有数据域指针小于head指针的对象的地址指针和大小；尾部表：所有数据域指针不小于tail指针的对象的地址指针和大小；

判断是全部回收还是部分回收；

执行垃圾回收过程，如果是全部回收，先处理头部表的垃圾回收，再进行尾部表的垃圾回收，在结束垃圾回收后按照分配策略进行分配内存；如果是部分回收，根据要分配的对象要处于头部还是尾部选择：如果从头部开始，先处理头部表的垃圾回收，如果不满足分配条件，再处理尾部表的垃圾回收；如果从尾部开始，先处理尾部表的垃圾回收，如果不满足分配条件，再处理头部表的垃圾回收。

图3中，头部表的垃圾回收就是从头至尾遍历头部表的过程，步骤如下：

将遍历到的处理对象设置为当前对象，检查其与后续对象的数据域之间是否有空闲空间，如果没有，则将后续对象设置为当前对象，继续遍历；

在部分回收时检查该空闲空间大小是否满足要求；如果满足，则从空闲空间进行内存分配并直接结束垃圾回收；在全部回收时跳过这一步；

移动后续对象的数据域，接续于当前对象的数据域尾部，同时改写后续对象的数据域指针指向新地址；将后续对象设置成为当前对象；

当前对象的数据域与head指针之间还有其它对象，继续第一步；当前对象的数据域与head指针之间没有其它对象，调整head指针为当前对象数据域尾部，如果是部分回收且[head，tail]所表示的可分配空间满足分配要求，则从可分配空间进行内存分配、调整head指针：head＝head+len并直接结束垃圾回收。

图4中，尾部表的垃圾回收就是从尾至头遍历尾部表的过程，步骤如下：

将遍历到的处理对象设置为当前对象，检查其与前序对象的数据域之间是否有空闲空间，如果没有，则将前序对象设置为当前对象，继续遍历；

在部分回收时检查该空闲空间大小是否满足要求；如果满足，则从空闲空间进行内存分配并直接结束垃圾回收；在全部回收时跳过这一步；

移动前序对象的数据域，接续于当前对象的数据域之前，同时改写前序对象的数据域指针指向新地址；将前序对象设置成为当前对象；

当前对象的数据域与tail指针之间还有其它对象，继续第一步；当前对象的数据域与tail指针之间没有其它对象，调整tail指针为当前对象数据域头部，如果是部分回收且[head，tail]所表示的可分配空间满足分配要求，则从可分配空间进行内存分配、调整tail指针：tail＝tail-len并直接结束垃圾回收。

需要说明的是，在此提供的方法不与任何特定计算机、虚拟装置或者其它设备固有相关。各种通用装置也可以与基于在此的示教一起使用。根据上面的描述，构造这类装置所要求的结构是显而易见的。此外，本发明也不针对任何特定的编程语言。应当明白，可以利用各种编程语言实现在此描述的本发明内容，并且上面对特定语言、系统功能模块的调用所做的描述仅仅是为了披露发明的最佳实施方式。

在此处所提供的说明书中，说明了大量的具体细节。然而，能够理解，本发明的实施例可以在没有这些具体细节的情况下完成实现。在一些示例中，并未详细示出公知的方法、结构和技术，以便不模糊对本说明书的理解。

显然，本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发明的精神和范围。这样，倘若对本发明的这些修改和变型属于本发明权利要去及其同等技术的范围之内，则本发明也意图包含这些改动和变型在内。