Proj4：改进LiteOS中物理内存分配算法

Posted on by hackdl

Proj4：改进LiteOS中物理内存分配算法

实验目的

掌握LiteOS系统调用的自定义方法

实验环境

Ubantu和IMX6ULL mini

实验内容

（从代码角度详细描述实验的步骤和过程）

原先代码:

 1 /*
 2 
 3  * Description : find suitable free block use "best fit" algorithm
 4 
 5  * Input       : pool      --- Pointer to memory pool
 6 
 7  *               allocSize --- Size of memory in bytes which note need allocate
 8 
 9  * Return      : NULL      --- no suitable block found
10 
11  *               tmpNode   --- pointer a suitable free block
12 
13  */
14 
15 STATIC INLINE LosMemDynNode *OsMemFindSuitableFreeBlock(VOID *pool, UINT32 allocSize)
16 
17 {
18 
19     LOS_DL_LIST *listNodeHead = NULL;
20 
21     LosMemDynNode *tmpNode = NULL;
22 
23     UINT32 maxCount = (LOS_MemPoolSizeGet(pool) / allocSize) 1;
24 
25     UINT32 count;
26 
27 #ifdef LOSCFG_MEM_HEAD_BACKUP
28 
29     UINT32 ret = LOS_OK;
30 
31 #endif
32 
33     for (listNodeHead = OS_MEM_HEAD(pool, allocSize); listNodeHead != NULL;
34 
35          listNodeHead = OsDLnkNextMultiHead(OS_MEM_HEAD_ADDR(pool), listNodeHead)) {
36 
37         count = 0;
38 
39         LOS_DL_LIST_FOR_EACH_ENTRY(tmpNode, listNodeHead, LosMemDynNode, selfNode.freeNodeInfo) {
40 
41             if (count++ >= maxCount) {
42 
43                 PRINT_ERR("[%s:%d]node: execute too much timen", __FUNCTION__, __LINE__);
44 
45                 break;
46 
47             }
48 
49 #ifdef LOSCFG_MEM_HEAD_BACKUP
50 
51             if (!OsMemChecksumVerify(&tmpNode->selfNode)) {
52 
53                 PRINT_ERR("[%s]: the node information of current node is bad !!n", __FUNCTION__);
54 
55                 OsMemDispCtlNode(&tmpNode->selfNode);
56 
57                 ret = OsMemBackupRestore(pool, tmpNode);
58 
59             }
60 
61             if (ret != LOS_OK) {
62 
63                 break;
64 
65             }
66 
67 #endif
68 
69             if (((UINTPTR)tmpNode & (OS_MEM_ALIGN_SIZE - 1)) != 0) {
70 
71                 LOS_Panic("[%s:%d]Mem node data error:OS_MEM_HEAD_ADDR(pool)=%p, listNodeHead:%p,"
72 
73                           "allocSize=%u, tmpNode=%pn",
74 
75                           __FUNCTION__, __LINE__, OS_MEM_HEAD_ADDR(pool), listNodeHead, allocSize, tmpNode);
76 
77                 break;
78 
79             }
80 
81             if (tmpNode->selfNode.sizeAndFlag >= allocSize) {
82 
83                 return tmpNode;
84 
85             }
86 
87         }
88 
89     }
90 
91     return NULL;
92 
服务器托管网93 }

修改后的代码:

/*

 * Description : find suitable free block use "best fit" algorithm

 * Input       : pool      --- Pointer to memory pool

 *               allocSize --- Size of memory in bytes which note need allocate

 * Return      : NULL      --- no suitable block found

 *               tmpNode   --- pointer a suitable free block

 */

STATIC INLINE LosMemDynNode *OsMemFindSuitableFreeBlock(VOID *pool, UINT32 allocSize)

{

    LOS_DL_LIST *listNodeHead = NULL;

    LosMemDynNode *tmpNode = NULL;

    UINT32 maxCount = (LOS_MemPoolSizeGet(pool) / allocSize) 1;

    UINT32 count;

#ifdef LOSCFG_MEM_HEAD_BACKUP

    UINT32 ret = LOS_OK;

#endif//I have updated the listNodeHead so that we can have a better performence in time,but also waste some space

    for (listNodeHead = OsDLnkNextMultiHead(OS_MEM_HEAD_ADDR(pool), OS_MEM_HEAD(pool, allocSize))==NULL?OS_MEM_HEAD(pool, allocSize):OsDLnkNextMultiHead(OS_MEM_HEAD_ADDR(pool), OS_MEM_HEAD(pool, allocSize));

    listNodeHead != NULL;

         listNodeHead = OsDLnkNextMultiHead(OS_MEM_HEAD_ADDR(pool), listNodeHead)) {

        count = 0;

        LOS_DL_LIST_FOR_EACH_ENTRY(tmpNode, listNodeHead, LosMemDynNode, selfNode.freeNodeInfo) {

            if (count++ >= maxCount) {

                PRINT_ERR("[%s:%d]node: execute too much timen", __FUNCTION__, __LINE__);

                break;

            }

#ifdef LOSCFG_MEM_HEAD_BACKUP

            if (!OsMemChecksumVerify(&tmpNode->selfNode)) {

                PRINT_ERR("[%s]: the node information of current node is bad !!n", __FUNCTION__);

                OsMemDispCtlNode(&tmpNode->selfNode);

                ret = OsMemBackupRestore(pool, tmpNode);

            }

            if (ret != LOS_OK) {

                break;

            }

#endif

            if (((UINTPTR)tmpNode & (OS_MEM_ALIGN_SIZE - 1)) != 0) {

                LOS_Panic("[%s:%d]Mem node data error:OS_MEM_HEAD_ADDR(pool)=%p, listNodeHead:%p,"

                          "allocSize=%u, tmpNode=%pn",

                          __FUNCTION__, __LINE__, OS_MEM_HEAD_ADDR(pool), listNodeHead, allocSize, tmpNode);

                break;

            }

            if (tmpNode->selfNode.sizeAndFlag >= allocSize) {

                return tmpNode;

            }

        }

    }

    return NULL;

}

主要修改了这一块:

原理如下:

  1. 起初对这个代码与它的注释挺疑惑的,best-fit是在我们可以分配的空闲块中找到一个最适合目前申请内存的空间,并且我们申请内存后(还有剩余时,还会分割)
  2. 但是函数代码逻辑上是直接找到就返回,而按道理我们应该是需要遍历所有空闲块的,但是没有,那么答案就很可能是空闲块是从小到大有序排放的(某种数据结构)
  3. 于是把他for循环起始位置+1,自然可以优化时间复杂度(相当于跳过这个目前最小的空闲块,这么改不会有损代码健壮性(如果直接+1的话,是不可行的,因为它的数据结构是链表(不连续存储),然后我写的复杂了点,主要是为了防服务器托管网止我们这个最小空间在能够使用的情况下永远不会去使用到),for里的判断条件排除了我们这么改有问题的可能))

实验结果

把best-fit算法改为good-fit算法

实验分析

  • 测试了以往的算法,发现可用
  • 相比以往算法实现,时间复杂度上有所优势

参考文献

Ppt

LiteOS内核源码分析：动态内存之Bestfit分配算法 – 知乎 (zhihu.com)

网课

附录

无

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net

相关推荐: 学习记录： requests 不同请求方式传参和常用的方法requests库常用的方法requests库的使用1、不带参数的get请求2、带参数的get请求3、传统表单类POST请求（x-www-form-urlencoded）4、JSON

requests库常用的方法 　　requests.Request(url) 构造一个请求，支持以下各种方式 　　requests.get() 发送get请求 　　requests.post() 发送post请求 　　requests.head() 获取HTM…

服务器托管，北京服务器托管，服务器租用，机房机柜带宽租用

服务器托管

咨询：董先生

电话13051898268 QQ/微信93663045！

上一篇:
下一篇: