首页 > 系统相关 >嵌入式操作系统内核原理和开发（最快、最优、最差内存分配算法）

嵌入式操作系统内核原理和开发（最快、最优、最差内存分配算法）

时间：2022-11-23 11:36:35浏览次数：41  
标签：NODE NULL 内存 pFind pCur 嵌入式操作系统 内核 size MNG


    前面我们说到了基于​​链表的内存分配​​算法。但是之前我们也说过，其实内存分配一般有三个原则，最快、最优和最差。最快比较好理解，就是寻找到合适的节点就立即分配内存，我们在前面一篇博客采用的就是这个方法。最优呢，就是寻找可以满足当前内存分配的最小节点，这样不会有很大的浪费，但是有可能会产生碎片节点。最后一种就是最差分配算法，说是最差效果未必最差。因为在大的内存分配的时候至少不会很快产生内存碎片，对整个系统的稳定来说有可能是好事。所以这三种方法很难说哪一种好，哪一种不好，需要结合具体的应用场景客观进行分析。不过话说回来，内存碎片是无论如何都避免不了的。

 

    首先，为了灵活对这三种分配算法进行配置，我们定义了宏开关，需要哪个就把那个开关放开。暂时默认打开的算法的是最快分配算法。

#define MAX_SPEED_MALLOC   1
#define MIN_SIZE_MALLOC    0
#define MAX_SIZE_MALLOC    0

    因为之前已经讨论过最快分配算法，所以这里着重讨论的最优分配算法和最差分配算法。又由于两者的差别极小，所以单独分析其中一种算法也行。就拿最优分配算法来说，为了寻找到最小的节点，我们需要对整个链表进行遍历，这个还是比较消耗时间的。

while(pCur)
    { 
        if(pCur->size > (size + sizeof(MNG_NODE)))
        {
            if(NULL == pFind || pFind->size > pCur->size)
            {
                pFind = pCur;
            }
        }

        pPre = pCur;
        pCur = pCur->next;
    }

    寻找到pFind这个我们需要的节点之后，还需要从pFreeList中删除该节点。所以，我们需要进一步的判断和分析，

if(NULL == pFind)
        return NULL;

    pPre = find_previous_node_in_list(pFind, pFreeList);
    if(NULL == pPre)
        pFreeList = pFreeList->next;
    else
        pPre->next = pFind->next;

    return pFind;

      首先判断pFind前面有没有节点，如果没有表示pFreeList就是pFind，那么pFreeList需要自行向后退缩；当然如果当前的pFind节点是有前节点的，那么只需要把前节点的next指针重新更改一下即可。当然，这里还对原来的查找节点函数作了一下修改，使之更合理更通用。

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

MNG_NODE* find_previous_node_in_list(MNG_NODE* pNode, MNG_NODE* pList)
{
    MNG_NODE* pFind = pList;
    MNG_NODE* pPre = NULL;
    
    while(pFind && pFind != pNode)
    {
        pPre = pFind;
        pFind = pFind->next;
    }

    if(NULL == pFind)
        return NULL;

    return pPre;
}

    上面也只是说了个大概，具体的内容可以参见下面的源代码。既可以在VC上编译，也可以在GCC上面编译，都没有问题。当然，如果本地os没有编译器，可以选择网上在线编译，也是个不错的选择。

/*************************************************
*      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;


/*************************************************
*          macro declaration
**************************************************/

#define MAX_SPEED_MALLOC   1
#define MIN_SIZE_MALLOC    0
#define MAX_SIZE_MALLOC    0

#define MEM_BUFFER_LENGTH   (0x1 << 24)


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

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


/*************************************************
*           function declaration
**************************************************/

MNG_NODE* find_previous_node_in_list(MNG_NODE* pNode, MNG_NODE* pList);


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

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


#if MAX_SPEED_MALLOC
/*************************************************
* function: find best fit node in max_speed
**************************************************/

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

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

    if(NULL == pFind)
        return NULL;

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

    return pFind;
}
#endif


#if MIN_SIZE_MALLOC
/*************************************************
* function: find best fit node in min size
**************************************************/

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

    while(pCur)
    { 
        if(pCur->size > (size + sizeof(MNG_NODE)))
        {
            if(NULL == pFind || pFind->size > pCur->size)
            {
                pFind = pCur;
            }
        }

        pPre = pCur;
        pCur = pCur->next;
    }   

    if(NULL == pFind)
        return NULL;

    pPre = find_previous_node_in_list(pFind, pFreeList);
    if(NULL == pPre)
        pFreeList = pFreeList->next;
    else
        pPre->next = pFind->next;

    return pFind;
}
#endif


#if MAX_SIZE_MALLOC
/*************************************************
* function: find best fit node in max size
**************************************************/

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

    while(pCur)
    { 
        if(pCur->size > (size + sizeof(MNG_NODE)))
        {
            if(NULL == pFind || pFind->size < pCur->size)
            {
                pFind = pCur;
            }
        }

        pPre = pCur;
        pCur = pCur->next;
    }   

    if(NULL == pFind)
        return NULL;

    pPre = find_previous_node_in_list(pFind, pFreeList);
    if(NULL == pPre)
        pFreeList = pFreeList->next;
    else
        pPre->next = pFind->next;

    return pFind;
}
#endif


/*************************************************
* 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 
**************************************************/

MNG_NODE* find_previous_node_in_list(MNG_NODE* pNode, MNG_NODE* pList)
{
    MNG_NODE* pFind = pList;
    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_in_list(pNode, pAllocList);
    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((MNG_NODE*)((char*)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,内存,pFind,pCur,嵌入式操作系统,内核,size,MNG
From： https://blog.51cto.com/feixiaoxing/5880700

相关文章

  • 嵌入式操作系统内核原理和开发（信号量）
        之前因为工作的原因，操作系统这块一直没有继续写下去。一方面是自己没有这方面的经历，另外一方面就是操作系统比较复杂和琐碎，调试起来比较麻烦。目前在实际项目中，使......
  • 嵌入式操作系统内核原理和开发（互斥量）
       今天下午打开邮箱，打开rawos作者给我发的邮件，甚是惊喜。感谢他对我的支持，因为自己阅读过很多os的代码，包括ucos、rtthread、vxWorks、linux等等，所以阅读rawos对于我来......
  • Java 内部类有坑。。100 % 内存泄露！
    来源：https://knife.blog.csdn.net/article/details/124946774今天给大家分享一种，Java内部类使用不当导致的内存泄露问题，最终导致内存溢出！希望能够帮助到大家！简介「说明......
  • 对象的使用 对象的方法 遍历对象 数字内置的对象 数据内存的存储
    1.1什么是对象 在JavaScript中，对象是一组无序的相关属性和方法的集合，所有的事物都是对象，例如字符串、数值、数组、函数等。对象是由属性和方法组成的。属性：事物的......
  • C++语言动态内存管理介绍和示例
     C++动态内存    在C++程序中，所有内存需求都是在程序执行之前通过定义所需的变量来确定的。但是可能存在程序的内存需求只能在运行时确定的情况。在这些情况下，程序......
  • java内存分析工具
    1、jmapmap一般可用于：jmap能够打印给定Java进程、核心文件或远程DEBUG服务器的共享对象内存映射或堆内存的详细信息内存监控分析对象内存怎么用？jmap相关命令：可通过jmap-......
  • 一步一图带你深入理解 Linux 物理内存管理
    1.前文回顾在上篇文章《深入理解Linux虚拟内存管理》中，笔者分别从进程用户态和内核态的角度详细深入地为大家介绍了Linux内核如何对进程虚拟内存空间进行布局以及......
  • Android命令行查看内存情况
    在学习如何查看内存前先来介绍几个概念VSS-VirtualSetSize虚拟耗用内存（包含共享库占用的内存）RSS-ResidentSetSize实际使用物理内存（包含共享库占用的内存）PSS......
  • Android使用MAT分析内存泄露
    一.概述首先来普及一下什么是内存泄露：内存泄露是指对象的内存在分配之后无法通过程序的执行逻辑释放对该对象的引用，导致不能回收该对象所占内存。内存泄露会导致以下情......
  • 内存表（FDMEMTABLE）
    内存表的优点是快，非常快，号称比BDE的clientdataset快很多。内存表不但快，还可以另存为XML、BIN、CSV等数据。也可直接作为stream传送。所以，追求速度的时候，获得数据后即解除锁......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99