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)

網課

附錄

無