5.4.3 核心内存池的管理

在Hello China当前的实现中，核心内存池又进一步分成了两部分：

（1）4KB区域，以4KB为单位进行分配和回收的区域，这部分内存池一般供驱动程序使用，用来当做设备的数据缓冲区；

（2）任意尺寸区域，以任意尺寸进行分配（在当前的实现中，最小的分配单位是16字节），供操作系统核心和驱动程序使用。操作系统在运行过程中创建的核心对象，比如核心线程对象、同步对象等，都从该区域内分配内存。

对于任意尺寸的内存区域，采用空闲链表的方式来进行管理。空闲链表算法简单描述如下：

（1）系统维护一个空闲链表，连接所有的空闲内存块。开始时，整个核心内存区域作为一个空闲块连接到空闲链表中；

（2）每当有一个内存分配申请到达时，内存管理函数遍历空闲链表，寻找一块空闲内存，该内存的大小大于（或等于）请求的内存；

（3）如果不能找到，则返回空指针（NULL）；

（4）如果找到，判断寻找到的内存的大小，如果跟请求的内存大小一致，或比请求的内存大少许（比如16字节），那么内存管理函数就把整个内存块返回给用户，然后把该空闲块从内存中删除；

（5）如果找到的内存比用户请求的内存大许多（比如大于16字节），那么内存管理函数把该空闲块分成两块，一块仍然作为空闲块插入空闲链表中，另外一块返回用户。

对于内存回收算法，如下。

① 回收函数（KMemAlloc）把释放的内存插入空闲链表；

② 在插入的同时，回收函数判断跟该空闲块相邻的下一块是否可以跟当前块合并（合并成更大的块）；

③ 如果可以合并（地址连续），那么回收函数将合并两块空闲内存块，然后作为一块更大的内存块重新插入空闲链表；

④ 如果不能合并，则简单返回。

错误！

为了维护空闲块，必须为每块空闲块分配一个控制结构，然后由这个控制结构指定特定的空闲内存块。分配和回收时，需要对空闲块的控制结构进行修改，因此，必须有一种方法能够快速地定位控制结构。

为了解决这个问题，我们把空闲块的控制结构放在空闲块的前端，这样给定一个内存地址就可以很容易地索引到其控制块，比如假设给定的内存地址为lpStartAddr，空闲内存控制结构为__FREE_BLOCK_CONTROL_BLOCK，那么对应该空闲块的控制结构可以这样获取：

__FREE_BLOCK_CONTROL_BLOCK＊  lpControlBlock=
    (__FREE_BLOCK_CONTROL_BLOCK＊)((DWORD)lpStartAddr-
    sizeof(__FREE_BLOCK_CONTROL_BLOCK));

这在内存释放（KMemFree）的时候特别有用。

在Hello China当前版本的实现中，空闲链表算法使用的是初次适应算法，即把第一次发现的空闲块分配给用户，而不管这个内存块是否太大。这样往往会造成内存碎片，即随着分配次数的增加，内存中零碎的内存片数量逐渐增多，到了一定的程度，整个内存中全部是零碎的内存片，如果此时用户请求一块大的内存，往往会以失败告终。但这些缺点仅仅是理论上的，实验表明，首次适应算法能很好地满足实际需求。实际上，很多操作系统的内存分配算法就是使用这种方式实现的，运行效果也十分理想。对于空闲锂表算法参考图5-17。

图5-17 Hello China的空闲链表算法

对于4KB区域，采用位图算法进行管理，即把整个4KB区域以4KB为单位进行划分，对于每个单位，有一个比特与之对应，若该比特的值为1，则说明该比特对应的内存区域（4KB）已经分配，若为0，则说明该区域尚未分配。如图5-18所示。

图5-18 Hello China的位图算法示意

位图实际上是一个静态定义的全局数组，操作系统初始化时，会对位图数据进行适当的初始化。内存分配时，分配函数会根据请求的大小，检索整个位图以找到空闲的能够满足请求的内存块。若找到符合条件的内存区域，则设置该区域对应的位图，并把首地址返回给申请程序，否则返回NULL。内存释放时，则清除相应的位图标志。

对于核心内存的申请和释放，统一由下列两个函数来完成：

KMemAlloc：

该函数完成核心内存的分配，原型如下：

LPVOID KMemAlloc(DWORD dwSize,DWORD dwAllocType);

其中，dwAllocType参数指明了要从4KB区域申请，还是从任何尺寸区域申请。若该参数为KMEM_SIZE_TYPE_4K，则KmemAlloc从4KB区域内分配内存；若该参数为KMEM_SIZE_TYPE_ANY，则从任意尺寸区域内分配内存。

KmemFree：

该函数完成核心内存的释放，原型如下：

VOID KmemFree(LPVOID lpAddr,DWORD dwAllocType,DWORD dwSize);

其中，lpAddr参数指出了要释放的核心内存的首地址，dwAllocType参数指明了内存的位置（与KmemAlloc一样）。4KB区域内的内存块释放时，需要指定尺寸，即最后一个参数dwSize。

上一章目录下一章