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 time\n", __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=%p\n",
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 time\n", __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=%p\n",

                          __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)

网课

附录

无