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; }
主要修改了这一块:
原理如下:
- 起初对这个代码与它的注释挺疑惑的,best-fit是在我们可以分配的空闲块中找到一个最适合目前申请内存的空间,并且我们申请内存后(还有剩余时,还会分割)
- 但是函数代码逻辑上是直接找到就返回,而按道理我们应该是需要遍历所有空闲块的,但是没有,那么答案就很可能是空闲块是从小到大有序排放的(某种数据结构)
- 于是把他for循环起始位置+1,自然可以优化时间复杂度(相当于跳过这个目前最小的空闲块,这么改不会有损代码健壮性(如果直接+1的话,是不可行的,因为它的数据结构是链表(不连续存储),然后我写的复杂了点,主要是为了防止我们这个最小空间在能够使用的情况下永远不会去使用到),for里的判断条件排除了我们这么改有问题的可能))
实验结果
把best-fit算法改为good-fit算法
实验分析
- 测试了以往的算法,发现可用
- 相比以往算法实现,时间复杂度上有所优势
参考文献
Ppt
LiteOS内核源码分析：动态内存之Bestfit分配算法 – 知乎 (zhihu.com)
网课
附录
无
