引言
- 疑问：在前面的操作系统开发过程中，我们都是使用全局变量或者数组的形式来使用内存的，为什么不使用 malloc() 函数动态分配内存呢？
- 答案：因为没有 malloc() 函数呀，操作系统中的一切功能都需要我们自己去实现
- 那么，如何实现 malloc() 呢？
动态内存管理
- 动态内存管理的本质是一个算法设计问题，时间换空间，通过动态内存分配和回收“扩大”物理内存。通常在一块较大且连续的内存空间上进行分配和回收
- 动态内存管理解决的问题：内存资源稀缺，通过内存复用增加任务的并发性
动态内存管理的关键
- 时间效率：从发出内存申请到获得内存的时间越短越好
- 空间效率：内存管理本身所占用的内存越少越好
- 碎片化：最大可分配内存占空闲内存总和比例越大越好
动态内存管理的分类
- 定长内存管理：将内存分为大小相同的单元，每次申请一个单元的内存
- 变长内存管理：每次申请需要的内存（大小不固定，以字节为单位）
定长内存管理的设计
- 将内存分为两个部分：管理单元和分配单元
- 管理单元与分配单元一一对应
- 定长内存管理的精髓就是查找标记管理单元，从而管理对应的分配单元
- 从上图看，最简单最直接的方式就是通过 for 循环的方式来遍历管理单元，然而这种方式虽然简单，但却有个致命的缺点，那就是时间复杂度太高了，换句话说就是 for 循环比较浪费时间
- 我们准备采用链表来管理管理单元，将管理单元组织成链表（空闲定长内存管理链表）
- 管理内存时仅需要操作链表头即可。内存申请：从链表头获取一个管理单元，并计算下标，根据下标计算分配单元内存起始地址；释放内存：计算分配单元的下标，并将对应下标的管理单元插入链表
定长内存管理的实现
- 现在可能不理解上面具体说的是啥，下面我们直接从代码中体会吧，具体代码见：memory.c、memory.h
- 创建 “memory.c” 文件，放到 “core” 目录下，对应的 “memory.h” 放到 “include” 目录下，修改 “core” 目录下的 “BUILD.json”，"src" 项中增加 “memory.c”
- 先来实现几个关键性数据结构
- 先来定义一个数据结构用来一个定长内存分配单元，每个单元占 32 个字节
// 定长内存分配单元 typedef U08 (FM_UNIT)[32];
- 其次再定义一个数据结构用来表示内存管理单元，仔细看，我们使用 union 关键字而不是使用 struct 关键字，其原因就是管理单元要尽量少的占用内存，这也算设计的一种小技巧吧
typedef union _FM_NODE FM_NODE; // 定长内存管理单元，使用 union 是为了尽量少的使用内存，其实应该使用 struct union _FM_NODE { FM_NODE* next; // 指向下一个节点 FM_UNIT* unit; // 指向分配单元 };
- 采用链表来管理管理单元，那么链表头我们还是要定义一下的
// 定长内存管理链表头类型 typedef struct FM_LIST { FM_NODE* node; // 管理单元节点 FM_NODE* nbase; // 管理单元基址 FM_UNIT* ubase; // 分配单元基址 U32 max; // 最多可分配的空闲单元个数 } FM_LIST; FM_LIST FM_LIST_HEAD; // 空闲定长内存管理单元链表头
- 接下来，我们的目标就是实现三个功能函数，1.初始化；2.申请内存；3.释放内存
- 先从初始化函数开始实现，接口定义如下
- 函数名称: E_RET FixedMemInit(U08* mem, U32 size)
- 输入参数: U08* mem --定长内存基址；U32 size --定长内存长度
- 输出参数: 无
- 函数返回: E_OK:成功; E_ERR:失败
- 函数实现的关键点：我们把一块连续的内存分成两个部分，前半部分为管理单元，后半部分紧跟着分配单元，以管理单元为节点，将管理单元组织成单向链表
- FixedMemInit 函数具体实现如下
E_RET FixedMemInit(U08* mem, U32 size) { U32 max = 0; U32 i = 0; FM_NODE* current = NULL; // 当前管理单元节点 FM_NODE* next = NULL; // 下一个管理单元节点 // 检查参数合法性 if(NULL == mem || size < (FM_NODE_SIZE + FM_ALLOC_SIZE)) return E_ERR; // 计算一块内存最多可以分成多少个内存单元（1内存单元 = 1管理单元+1分配单元） max = size / (FM_NODE_SIZE + FM_ALLOC_SIZE); // 初始化定长内存链表，以管理单元为节点，将所有的管理单元组织成一个单向链表 FM_LIST_HEAD.max = max; FM_LIST_HEAD.nbase = (FM_NODE *)mem; // 管理单元基址 FM_LIST_HEAD.ubase = (FM_UNIT *)((U32)mem + max*FM_NODE_SIZE); // 分配单元基址 FM_LIST_HEAD.node = (FM_NODE *)mem; for(i = 0; i < max - 1; i++) { // 当前节点（管理单元）的 next 指针指向下一个节点（管理单元） current = FM_LIST_HEAD.node + i; next = FM_LIST_HEAD.node + i + 1; current->next = next; } // 最后一个节点（管理单元）的 next 指针指向 NULL next->next = NULL; return E_OK; }
- 初始化工作完成，接下来实现申请内存函数，先看接口定义
- 函数名称: E_RET FixedMemInit(U08* mem, U32 size)
- 输入参数: U08* mem --定长内存基址；U32 size --定长内存长度
- 输出参数: 无
- 函数返回: E_OK:成功; E_ERR:失败
- 函数实现的关键点：FM_LIST_HEAD 链表中所有节点（管理单元）都是可用的，申请时只要将第一个节点（管理单元）所对应的分配单元地址返回，并将该节点从链表中删除即可
- FixedMemInit 函数具体实现如下
void* FixedMemAlloc(void) { void* alloc = NULL; FM_NODE* node = NULL; U32 index = 0; // 如果头结点为空，表明已经没有空闲的内存可分配了 if(NULL == FM_LIST_HEAD.node) return NULL; // 取空闲定长内存管理单元链表第一个节点 node = FM_LIST_HEAD.node; // 计算出是第几个管理单元，其在管理单元中的偏移个数就等同于在分配单元中的偏移个数 // 根据这个偏移量就能算出对应的分配单元地址，最后再将这个分配单元地址返回 index = (U32)(node - FM_LIST_HEAD.nbase); alloc = FM_LIST_HEAD.ubase + index; // 从链表头删除节点，即将 FM_LIST_HEAD 的头结点指向下一个节点 FM_LIST_HEAD.node = node->next; // 用于释放内存时校验 node->unit = alloc; return alloc; }
- 再接下来自然就是实现释放内存函数了，其接口定义如下
- 函数名称: E_RET FixedMemFree(void* ptr)
- 输入参数: void* ptr --要释放的分配单元地址
- 输出参数: 无
- 函数返回: E_OK:成功; E_ERR:失败
- 函数实现的关键点：根据传入的分配单元地址 ptr，计算出对应的管理单元，将其加入到 FM_LIST_HEAD 链表中
- FixedMemFree 函数具体实现如下
E_RET FixedMemFree(void* ptr) { U32 index = 0; FM_NODE* node = NULL; // 检查参数合法性 if(NULL == ptr) return E_ERR; // 计算出是第几个分配单元，其在分配单元中的偏移个数就等同于在管理单元中的偏移个数 // 根据这个偏移值就能算出对应的管理单元地址，最后再将这个管理单元插入链表头 index = (U32)((FM_UNIT *)ptr - FM_LIST_HEAD.ubase); // 合法性检查 if(index >= FM_LIST_HEAD.max) return E_ERR; node = FM_LIST_HEAD.nbase + index; // node->unit 在 FixedMemAlloc 被赋值，只有当申请内存地址与释放内存地址相同是才合法 if(node->unit != ptr) return E_ERR; // 将节点插入链表头 node->next = FM_LIST_HEAD.node; FM_LIST_HEAD.node = node; return E_OK; }
变长内存管理的设计与实现
- 定长内存管理法能够满足开发需要吗？
- 答案：不能，例如前面我们实现的定长内存管理方案，当申请内存小于 32 字节时，定长内存管理可以满足需求，但是当申请内存大于 32 字节时，定长内存管理方案就无法满足需求了
- 所以，我们不得不实现变长内存管理
- 将内存分为三个部分：管理头 & 已用区域 & 空闲区域
- 管理头：记录已用区域和空闲区域的位置
- 已用区域：已分配的内存区域（使用中）
- 空闲区域：可分配的内存区域（空闲）
- 在定长内存管理中，我们将管理单元组织成链表，而在变长内存管理中，我们将管理头组织成链表
- 在定长内存管理中，管理单元一开始初始化的时候就已经分配好了内存空间，而在变长内存管理中，初始化时仅有一个管理头，每申请一次内存，增加一个管理头，管理头管理两个部分，一个是已用区域，一个是空闲区域
- 初始化：对于一整块内存，我们取开头一点内存当做管理头，负责管理剩余部分内存，剩余的部分内存全部都是空闲内存。VM_LIST 链表此时插入第一个 VM_HEAD 管理头节点，此时已用内存为 0
- 申请一块大小为 A 的内存：初始化工作完成之后，那么就可以分配这片内存了，当前我们申请第一块大小为 A 的内存空间，我们规划从空闲内存区域最后面分割出大小等于 A 的内存空间，为了管理内存 A，我们还得分出一点内存用于管理内存 A，把这个管理头插入到链表中
- 有了第一个申请内存，后面申请内存 B、C 原理都是一样的，只不过在插入链表时不是插入到链表末尾，而是插入到当前节点的后面
- 看完了内存申请的流程，再来看一下内存释放的流程
- 在已申请内存 A B C 的基础上，假如此时我们要释放内存 B，把内存 B 和其管理头看成空闲内存，交由 B 的上一个节点（C 节点）的管理头管理，我们在前面就介绍过了，每个管理头管理着两个部分的内存，一是使用内存，另一个是空闲内存
- 再释放内存 A 时，那么我们就把 A 区和原来的 B 区内存合并成一整个空闲内存，统一交由 A 的上一个节点（C 节点）的管理头管理
- 至此，变长内存管理的申请与释放过程我们有了一个直观的认识
- 在有了上面的了解之后，再来实现变长内存的三个函数就简单了，他们分别是：
/****************************************************************************** * 函数名称: E_RET VolatileMemInit(U08* mem, U32 size) * 功能说明: 变长内存管理初始化 * 输入参数: U08* mem --变长内存基址 U32 size --变长内存长度 * 输出参数: 无 * 函数返回: E_OK:成功; E_ERR:失败 * 其它说明: ******************************************************************************/ E_RET VolatileMemInit(U08* mem, U32 size) { VM_HEAD* head = (VM_HEAD *)mem; // 检查参数合法性 if(NULL == mem || size < VM_HEAD_SIZE) return E_ERR; // 初始化变长内存管理链表 ListInit(&VM_LIST); // 初始化第一个节点的管理头 head->usedSize = 0; // 初始化时已分配的内存大小为 0 head->freeSize = size - VM_HEAD_SIZE; // 空闲区域大小要除去管理头本身所占的内存空间 // 将第一个节点插入链表 VM_LIST 末尾 ListAddTail(&VM_LIST, (LIST_NODE *)head); return E_OK; } /****************************************************************************** * 函数名称: void* VolatileMemAlloc(U32 size) * 功能说明: 变长内存申请 * 输入参数: U32 size --要申请的内存大小 * 输出参数: 无 * 函数返回: void* --申请到的内存首地址 * 其它说明: ******************************************************************************/ void* VolatileMemAlloc(U32 size) { LIST_NODE* pListNode = NULL; VM_HEAD* head = NULL; VM_HEAD* newHead = NULL; U32 allocSize = size + VM_HEAD_SIZE; // 申请内存的总大小要包含管理头本身所占的内存空间 // 遍历 VM_LIST LIST_FOR_EACH(&VM_LIST, pListNode) { head = (VM_HEAD *)LIST_NODE(pListNode, VM_HEAD, node); // 找到空闲内存且空闲内存大小要足够分配 if(head->freeSize >= allocSize) { // 原空闲内存的后面分配出 allocSize 大小的内存 // 新的管理头指针指向分配出的新内存首地址 newHead = (VM_HEAD *)((U32)head + VM_HEAD_SIZE + head->usedSize + head->freeSize - allocSize); newHead->usedSize = size; // 已分配内存大小 newHead->freeSize = 0; // 空闲内存大小 head->freeSize -= allocSize; // 减掉分配出去的内存大小 ListAddAfter((LIST_NODE *)head, (LIST_NODE *)newHead); // 新节点 newHead 插入到 head 节点后面 break; } } // 判断 newHead 是否为 NULL，若为 NULL，则表明未找到可分配的内存，返回 NULL // 如果 newHead 不为 NULL，则表明已成功分配到内存空间，返回实际空闲可用内存的首地址 return newHead ? (void *)((U32)newHead + VM_HEAD_SIZE) : NULL; } /****************************************************************************** * 函数名称: E_RET VolatileMemFree(void* ptr) * 功能说明: 变长内存释放 * 输入参数: void* ptr --要释放的内存首地址 * 输出参数: 无 * 函数返回: E_OK:成功; E_ERR:失败 * 其它说明: ******************************************************************************/ E_RET VolatileMemFree(void* ptr) { LIST_NODE* pListNode = NULL; VM_HEAD* head = NULL; VM_HEAD* prev = NULL; // 检查参数合法性 if(NULL == ptr) return E_ERR; // 遍历 VM_LIST LIST_FOR_EACH(&VM_LIST, pListNode) { head = (VM_HEAD *)LIST_NODE(pListNode, VM_HEAD, node); // 传入地址 ptr 与要释放的内存首地址相同时才能释放内存 if((U32)head + VM_HEAD_SIZE == (U32)ptr) { prev = (VM_HEAD *)(head->node.prev); prev->freeSize = prev->freeSize + head->usedSize + VM_HEAD_SIZE; ListDelNode(pListNode); // 删除链表节点 return E_OK; } } return E_ERR; }
动态内存分配代码最终实现
- 前面我们已经实现了定长内存管理与变长内存管理两种方法，现在我们把这两种方法合并一下，实现最终的动态内存分配
- 申请策略：先判断申请内存大小是否大于 32 字节，若不大于 32 字节，则使用定长内存申请，若大于 32 字节，则使用变长内存申请，详细流程见下图
- 代码实现：
void* Malloc(U32 size) { void* ret = NULL; if(size > 32) ret = VolatileMemAlloc(size); else { ret = FixedMemAlloc(); if(NULL == ret) // 如果定长内存申请失败，则再尝试变长内存申请 ret = VolatileMemAlloc(size); } return ret; }
- 释放策略：先尝试定长内存释放，定长内存释放不成功再尝试变长内存释放
- 代码实现：
E_RET Free(void* ptr) { if(E_ERR == FixedMemFree(ptr)) return VolatileMemFree(ptr); return E_OK; }
- 申请和释放都有了，还漏了一个初始化，将内存区分两半，前半部分用定长内存管理法，后半部分用变长内存管理法
E_RET MemInit(U08* mem, U32 size) { E_RET ret = E_ERR; U08* fmem = mem; U32 fsize = size / 2; U08* vmem = (U08 *)((U32)fmem + fsize); U32 vsize = size - fsize; ret = FixedMemInit(fmem, fsize); ret &= VolatileMemInit(vmem, vsize); return ret; }
- 还有最后一点工作没完成，那就是得规划一下内核堆所在的位置，我们把内核堆放在 0x70000 内存地址处，长度为 0x10000
- 我们只要在 “main.c” 中初始化就可以动态申请内存了
MemInit(0x70000,0x10000);
疑问
- 变长内存管理就已经可以实现任意大小的内存申请和释放了，为啥我们非要实现定长内存管理呢？
- 答案当然是效率啦，我们设计操作系统，不能只考虑功能实现，还要考虑到运行效率，显而易见，变长内存管理每次查找都是要遍历链表的，节点越多，越耗费时间
解决异常问题
- 当我把内存分配相关代码写完，进行测试时，却发现程序出异常了，任务根本没有跑起来，更诡异的是并没有调用 “memory.c” 中实现的任何函数，就算是内存分配的相关代码有问题，但是在没调用的情况下是不可能出问题的啊
- 经过反复摸索查找，最终发现，在从 “a.img” 中把内核程序 kernel.bin 读取到内存 0xB000 地址的 rd_disk_to_mem 函数存在 BUG，我把具体原因写在了 内核雏形 最后的 “补充” 中，因为这个问题跟本章节 “动态内存分配” 毫无关系，放在这里不合适
- 临时解决方案见：loader.asm
实战
- 由于之前我们还没有实现动态内存分配，所以任务所需的内存是提前开辟好 TASK_OOP taskOop[MAX_TASK_NUM] 数组
- 现在我们去掉这个数组，改用动态内存分配管理任务所需内存空间
- 首先，删除 TASK_OOP taskOop[MAX_TASK_NUM] 和 TASK OOP 类型定义，在 TASK 类型定义中加上 node 节点，用于链表或队列的操作
typedefstructTASK
{ QUEUE_NODE node; // 链表节点 U32 id; // 任务 id U08* name; // 任务名称 ... } TASK;
- 主要改动之处，TaskInit 函数中申请任务所需内存，SYS_TaskDestory 函数中释放任务使用的内存空间，其它改动地方可以根据编译报错提示来修改
- 本次代码实现见：task.c、task.h、schedule.c
