嵌入式操作系统内核原理和开发（基于链表节点的内存分配算法）

您的位置：
门户
>> 文章精选
>> 软件开发专栏
>> 操作系统
>> 查看资讯

嵌入式操作系统内核原理和开发（基于链表节点的内存分配算法）

发表于：2012-6-27 10:06

作者：feixiaoxing 来源：51Testing软件测试网采编

操作系统

　　链接节点的内存分配方法，其实就是一种按需分配的内存分配方法。简单一点说，就是你需要多少内存，我就给你多少内存。当然，为了把分配的内存都连起来，我们还需要对分配节点进行管理记录。就比如下面这个数据结构，

typedef struct _MNG_NODE
{
struct _MNG_NODE* next;
unsigned int size;
}MNG_NODE;

　　其中，next节点记录了下面一个节点的位置，size表示了当前节点下方的内存大小。在内存初始化的时候，我们默认起始内存块就是一个大节点，其中前面8个字节就是上面的内容。此时，如果需要进行内存拆分，我们就可以把一个节点拆分成两个节点，就比如这样，

pNew = (MNG_NODE*)((char*)pOld + sizeof(MNG_NODE) + pOld->size - (sizeof(MNG_NODE) + size));

　　pNew代表了新生成的结点，pOld代表了原来的节点。为了不影响原来的节点，每次分配新节点的时候必须在内存的高端位置进行分配。这样也保证了原来节点结构和数据的连贯性。当然分配结束之后，只需要对节点的的size重新进行一下赋值就可以了。

pNew->size = size;
pOld->size -= sizeof(MNG_NODE) + size;

　　此时pOld节点会归还到pFreeList当中，而生成的pNew节点则插入到pAllocList当中。其中，pFreeList表示当前的空闲节点，pAllocList表示已分配节点。相比较而言，内存的释放就比较简单，只需要把节点找出来插入到pAllocList中即可。当然，此时如果能做一下前后节点的合并工作就更好了。

　　不过，上面描述的步骤只是就比较重要知识点讲解了一下。在真正设计代码的过程中还需要考虑到节点的查找、内存大小的判断、数据初始化、链表插入、测试用例编写等工作，步骤会稍微繁琐一下。下面我们就给出完整的代码示例。

/*************************************************
* malloc & free in link node algorithm
**************************************************/

#include <string.h>
#include <malloc.h>

/*************************************************
* struct definition
**************************************************/

typedef struct _MNG_NODE
{
struct _MNG_NODE* next;
unsigned int size;
}MNG_NODE;

/*************************************************
* global variable declaration
**************************************************/

#define MEM_BUFFER_LENGTH (0x1 << 24)

static void* pGlbData;
static MNG_NODE* pFreeList;
static MNG_NODE* pAllocList;

/*************************************************
* function: add node into headlist
**************************************************/

static void add_node_into_list_head(MNG_NODE* pNode, MNG_NODE** ppList)
{
pNode->next = *ppList;
*ppList = pNode;
}

/*************************************************
* function: find best fit node
**************************************************/

static MNG_NODE* find_best_fit_node(unsigned int size)
{
MNG_NODE* pCur = pFreeList;
MNG_NODE* pPre = pCur;

    while(pCur && pCur->size < (size + sizeof(MNG_NODE)))
    {
        pPre = pCur;
        pCur = pCur->next;
    }

if(NULL == pCur)
return NULL;

    if(pFreeList == pCur)
        pFreeList = pFreeList->next;
    else
        pPre->next = pCur->next;

return pCur;
}

/*************************************************
* function: implement memory allocation
**************************************************/

static void* _mem_malloc(unsigned int size)
{
MNG_NODE* pOld;
MNG_NODE* pNew;

    pOld = find_best_fit_node(size);
    if(NULL == pOld)
        return NULL;

    pNew = (MNG_NODE*)((char*)pOld + sizeof(MNG_NODE) + pOld->size - (sizeof(MNG_NODE) + size));
    pNew->size = size;
    pOld->size -= sizeof(MNG_NODE) + size;

add_node_into_list_head(pOld, &pFreeList);
add_node_into_list_head(pNew, &pAllocList);

return (void*)((char*)pNew + sizeof(MNG_NODE));
}

/*************************************************
* function: memory allocation
**************************************************/

void* mem_malloc(unsigned int size)
{
if(0 == size)
return NULL;

if(size > (MEM_BUFFER_LENGTH - sizeof(MNG_NODE)))
return NULL;

return _mem_malloc(size);
}

/*************************************************
* function: find previous node
**************************************************/

static MNG_NODE* find_previous_node(MNG_NODE* pNode)
{
    MNG_NODE* pFind = pAllocList;
    MNG_NODE* pPre = NULL;

    while(pFind && pFind != pNode)
    {
        pPre = pFind;
        pFind = pFind->next;
    }

if(NULL == pFind)
return NULL;

return pPre;
}

/*************************************************
* function: implement memory free
**************************************************/

static void _mem_free(MNG_NODE* pNode)
{
MNG_NODE* pPreNode;

    if(pNode == pAllocList)
    {
        pAllocList = pAllocList->next;
        add_node_into_list_head(pNode, &pFreeList);
        return;
    }

    pPreNode = find_previous_node(pNode);
    if(NULL == pPreNode)
        return;

    pPreNode->next = pNode->next;
    add_node_into_list_head(pNode, &pFreeList);
    return;
}

/*************************************************
* function: free memory function
**************************************************/

void mem_free(void* pData)
{
if(NULL == pData)
return;

if(pData < pGlbData || pData >= (void*)((char*)pGlbData + MEM_BUFFER_LENGTH))
return;

_mem_free(pData - sizeof(MNG_NODE));
}

/*************************************************
* function: get memory buffer
**************************************************/

void mem_init()
{
    pGlbData = (void*)malloc(MEM_BUFFER_LENGTH);
    if(NULL == pGlbData)
        return;

    memset(pGlbData, 0, MEM_BUFFER_LENGTH);
    pFreeList = (MNG_NODE*)pGlbData;
    pFreeList->size = MEM_BUFFER_LENGTH - sizeof(MNG_NODE);
    pAllocList = NULL;
}

/*************************************************
* function: free memory buffer
**************************************************/

void mem_exit()
{
if(NULL != pGlbData)
free(pGlbData);

pFreeList = NULL;
pAllocList = NULL;
}

/*************************************************
* function: file starts here
**************************************************/

int main(int argc, char* argv[])
{
    mem_init();
    mem_exit();
    return 1;
}

搜索风云榜

测试技术了解

2023测试行业调查报告

挣点稿费

AI与软件测试

文章资料精选