编写自己的优秀内存管理器

早上好，读者。 也许您已经阅读了我以前的文章，并且知道我正在编写自己的操作系统。 今天，我们将讨论并考虑一种简单且相当快速的内存管理算法-内存管理器是操作系统的关键部分，因为快速，可靠且无浪费的内存工作是良好操作系统的关键。
无论是在Runet还是在英语网站上，我都在为经理寻求简单而适当的想法-我仍然找不到关于适当而不是O（N）分配器的任何好文章。 好吧，今天，我们将考虑为内存管理器提供一个更好的主意，我将延续性放在首位。

理论

从Wiki：内存管理器-计算机程序（应用程序和操作系统）的一部分，用于处理RAM分配和释放的请求，或者（对于某些计算机体系结构）处理请求，以在处理器的地址空间中包含给定的存储区域。

我还建议在继续阅读本文之前 。

Watermak分配器

好吧，可能所有分配器中最简单的就是Watermark Allocator。 它的本质大致如下：整个存储器分为多个块，该块具有一个包含该块和上一个块的大小的标头，该块的状态（忙/闲），知道该块的地址，我们可以获得O（1）的下一个和上一个块的地址。

内存分配

要分配内存，我们只需要遍历各个块，然后查找一个其大小大于或等于分配所需的内存大小的块。 正如您已经了解的那样，O（N）的渐近行为很差。

内存释放

要释放内存，对于我们而言，将块的状态设置为“空闲”就足够了-O（1）-超级！

但是，正如您所了解的，可以开始形成对2个或更多可用块进行碎片整理的孔，释放后，可以查看相邻的块，如果有一个或两个空闲的块，则将它们合并为一个。

对数分配器

我们知道我们只需要在空闲块中搜索。 仅免费运行一次可以平均提高速度两次，但这仍然是一条线。 好吧，如果我们可以从免费的区块中组织一棵树，那为什么还要遍历所有区块，寻找规模！ 最初，我们只有一个空闲块，然后将空闲块添加到二进制搜索树中，关键是块大小。 因此，为了分配内存，我们足以在树中找到一个大小大于或等于所需块的块。 我们沿着树静静地为O（log N）执行此操作。 此外，我们要么将块切成两半，要么将其完全交给请求内存的那个。 接下来，我们从树中删除O（1）的块。 并且，如有必要，将其余块插入O后面（日志N）。 对于发布，我们只需要向后插入块，不要忘记碎片。

逻辑上，您不需要使用简单的树，而需要使用自平衡树（Red-Black或AVL）。 您可以将块树存储在静态数组中，也可以弄清楚如何做不同的事情。

实际上，代码是：

char * malloc(size_t size) { if (!size) { return 0; } char * addr = 0; int i; for (i = 0; i < allocationAvlTree.size; ) { int r; node_t *n; n = &allocationAvlTree.nodes[i]; /* couldn't find it */ if (!n->key) { return NULL; } r = allocationAvlTree.cmp(n->key, size); if (r <= 0) { //We're lucky today. //Get memory block header alloc_t * block = (size_t)n->val - sizeof(alloc_t); //Set to used block->status = 1; //Set size block->size = size; alloc_t * next = (size_t)n->val + size; next->prev_size = size; next->status = 0; next->size = n->key - size - 16; avltree_remove(&allocationAvlTree, n->key, n->val); if (n->key - size - 16) avltree_insert(&allocationAvlTree, next->size, (size_t)next + sizeof(alloc_t)); memset((size_t)block + sizeof(alloc_t), 0, block->size); block->signature = 0xDEADBEEF; unlockTaskSwitch(); return (size_t)block + sizeof(alloc_t); } else if (r > 0) i = __child_r(i); else assert(0); } return 0; } void free(void * mem) { if (!mem) return; //Get current alloc alloc_t * alloc = ((unsigned int)mem - sizeof(alloc_t)); if (alloc->signature != 0xDEADBEEF) return; alloc->status = 0; alloc_t * left = ((unsigned int)alloc - sizeof(alloc_t) - alloc->prev_size); if (left->signature == 0xDEADBEEF&&left->status == 0&&left->size==alloc->prev_size) { //Merge blocks if (avltree_remove(&allocationAvlTree, left->size, (uint)left + sizeof(alloc_t))) { left->size += sizeof(alloc_t) + alloc->size; alloc = left; } else assert(0); } alloc_t * right = (uint)alloc + sizeof(alloc_t) + alloc->size; if (right->prev_size&&right->status == 0&&right->signature == 0xDEADBEEF) { if (avltree_remove(&allocationAvlTree, right->size, (uint)right + sizeof(alloc_t))) alloc->size += sizeof(alloc_t) + right->size; else assert(0); } avltree_insert(&allocationAvlTree, alloc->size, (uint)alloc + sizeof(alloc_t)); } 

祝你好运和道德黑客！ 任何客观的批评都值得欢迎，本文的目的不是要说它是某种分配器，而只是说说一个比简单分配器的愚蠢实现更好的分配器。