首页 > 系统相关 >嵌入式操作系统内核原理和开发(基于链表节点的内存分配算法)

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

时间:2022-11-23 11:36:48浏览次数:42  
标签:NODE NULL return 链表 嵌入式操作系统 内核 MNG 节点 size


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

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;
}





标签:NODE,NULL,return,链表,嵌入式操作系统,内核,MNG,节点,size
From: https://blog.51cto.com/feixiaoxing/5880699

相关文章

  • 嵌入式操作系统内核原理和开发(最快、最优、最差内存分配算法)
       前面我们说到了基于​​链表的内存分配​​算法。但是之前我们也说过,其实内存分配一般有三个原则,最快、最优和最差。最快比较好理解,就是寻找到合适的节点就立即分配......
  • 嵌入式操作系统内核原理和开发(信号量)
        之前因为工作的原因,操作系统这块一直没有继续写下去。一方面是自己没有这方面的经历,另外一方面就是操作系统比较复杂和琐碎,调试起来比较麻烦。目前在实际项目中,使......
  • 嵌入式操作系统内核原理和开发(互斥量)
       今天下午打开邮箱,打开rawos作者给我发的邮件,甚是惊喜。感谢他对我的支持,因为自己阅读过很多os的代码,包括ucos、rtthread、vxWorks、linux等等,所以阅读rawos对于我来......
  • 一步一步写算法(之链表排序)
       相比较线性表的排序而言,链表排序的内容稍微麻烦一点。一方面,你要考虑数据插入的步骤;另外一方面你也要对指针有所顾虑。要是有一步的内容错了,那么操作系统会马上给你......
  • 19.删除链表的倒数第N个节点 remove-nth-node-from-end-of-list
    问题描述19.删除链表的倒数第N个节点解题思路首先设置一个虚拟头节点pre,pre->next=head;双指针法,考虑使用两个指针fast,slow,一快一慢,fast指针先前进n个位置,然后fast和......
  • python 用这样子将链表置None了, 为什么没有成功?
    res=ListNode(1)res.next=ListNode(2)#res1->2方式1打印12,这里是为什么?res1=res.nextres1=None方式2打印1res.next=Nonewhileres:pr......
  • 奇偶链表问题
    奇偶链表问题作者:Grey原文地址:博客园:奇偶链表问题CSDN:奇偶链表问题题目描述给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节......
  • 嵌入式学习-链表
    链表是一种数据结构,它相对于数组来说十分灵活,它存放着一个数据和指向下一个数据的地址(指针)。链表和数组的区别在于,数组是连续的,而链表可以是不连续的。  输出结果:......
  • #yyds干货盘点# LeetCode 腾讯精选练习 50 题:删除链表中的节点
    题目:有一个单链表的 head,我们想删除它其中的一个节点 node。给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。链表的所有值都是唯一的,并且保证给定......
  • 【链表2】链表中倒数第k个结点
    :题目描述输入一个链表,输出该链表中倒数第k个结点。有很多种方法,要么用集合,要么用双指针的方法。方法一:集合(这里的每次移除的数要特别注意)/*p......