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;

}

主要修改了這一塊:

原理如下:

起初對這個程式碼與它的註釋挺疑惑的,best-fit是在我們可以分配的空閒塊中找到一個最適合目前申請記憶體的空間,並且我們申請記憶體後(還有剩餘時,還會分割)
但是函數程式碼邏輯上是直接找到就返回,而按道理我們應該是需要遍歷所有空閒塊的,但是沒有,那麼答案就很可能是空閒塊是從小到大有序排放的(某種資料結構)
於是把他for迴圈起始位置+1,自然可以優化時間複雜度(相當於跳過這個目前最小的空閒塊,這麼改不會有損程式碼健壯性(如果直接+1的話,是不可行的,因為它的資料結構是連結串列(不連續儲存),然後我寫的複雜了點,主要是為了防止我們這個最小空間在能夠使用的情況下永遠不會去使用到),for裡的判斷條件排除了我們這麼改有問題的可能))

實驗結果

把best-fit演演算法改為good-fit演演算法

實驗分析

測試了以往的演演算法,發現可用
相比以往演演算法實現,時間複雜度上有所優勢

參考文獻

Ppt

LiteOS核心原始碼分析：動態記憶體之Bestfit分配演演算法 - 知乎 (zhihu.com)

網課

附錄

無