内存分配方法.docx

内存分配方法
专利名称：内存分配方法
技术领域：
本发明涉及计算机科学技术领域，特别涉及一种内存分配方法。
背景技术：
随着计算机硬件制造技术的不断发展，市场上不仅出现了速度更快容量更大 的内存，越来越多的应用也依赖于操作系统对内部节点，以相邻两个内部节点为子节 点创建上一层内部节点，依次向上递归直到创建出一个根节点。由此看出，树中的每个 节点代表一段指定的内存区间，除叶子节点外每个节点均有两个子节点，分别代表此节 点的左子区间和右子区间，根节点代表被线段树所管理的整个内存区间。叶子节点为线 段树所管理内存的最细粒度，即固定内存块的大小，一般为256B 8KB。由于在实际 的实现中，线段树的每个节点本身需要耗费一定的空间来存储其所管理内存区域的统计 信息，因此若叶子节点的管理粒度细至每个Byte，则整个树的空间耗费会比其所管理的 内存区间还大，出于实际情况的考虑，同内存的分页机制相结合，每个叶子节点代表的 固定内存块为一个内存页大小，即4KB，是较为合适的管理粒度。如图2所示，示出了 一棵长为16 (16X4KB)的线段树，每个叶子节点对应的内存区域为4KB。以管理采用32 位地址的从0x00000000起始的长度为512M的内存为例。512M共有217个页，
每页对应 一个叶子节点，则需要217个叶子节点。每两个相邻的叶子节点作为一个管理两个页的内 部节点的孩子，而每两个管理两个页的内部节点作为管理四个页的内部节点的孩子，依 次向上递归直到根节点，可知共217-1个内部节点。每个节点记录如下信息，并在分配时进行初始化所述信息所述节点对应的内存区域的起始和终止端点start和end ；所述节点对应的内存区域内最大连续空闲内存的长度max—blank—length和其起始 位置 location ；所述节点对应的内存区域内由起始端点向右的最长连续空闲内存长度left—blank— length,由终止端点向左的最长连续空闲内存长度right—blank—length。在创建和初始化的同时分配线段树自己占用的内存，因为存储线段树的数据结 构本身需要占用一定的内存，这里默认线段树自身所占用的内存也是为自己所管理的， 故需事先分配。步骤S102，在内存分配和释放前，需要初始化线段树。其步骤为统计所述内存的长度，(遵循左闭右开的表示方式，包括已分配给线段树的内存 区域的长度)；根节点的start和end分别为所述内存的起始位置和终止位置，初始情况下默认整 个内存区域全部为空闲状态，max—blank—length为内存区域的长度，location等于start， left—blank—length 等于 right—blank—length 等于 max—blank—length ；自顶向下，根据每个节点的父节点信息及本身所在左子树或右子树，采用递归 方式初始化每个节点的 start、end、max—blank—length、location、left—blank—length和 right— blank—length，至叶子节点为止。
如图3所示，设有节点node其代表从[OxOOOOfTOO，0x00010000)这么一段内存， 其中黑色代表已经被分配，白色代表空闲。贝U:start = OxOOOOfTOO,end = 0x00010000