Главная » Хабрахабр » Написание собственного неплохого менеджера памяти

Написание собственного неплохого менеджера памяти

Доброе время суток, читатель. Возможно, вы уже читали мои предыдущие статьи, и знаете, что я занимаюсь написанием собственной ОС. Сегодня мы поговорим, и рассмотрим несложный и достаточно быстрый алгоритм для управления памятью — менеджер памяти — критически важная часть ОС, ведь быстрая, надежная и нерастратная работа с памятью залог хорошей ОС.
Искал я несложные и адекватные идеи для менеджера и в рунете, и на англоязычных сайтах — всё никак не мог найти никаких хороших статей про адекватный, работающий не за O(N) аллокатор. Что же, сегодня мы рассмотрим более хорошую идею для менеджера памяти, продолжение помещаю под кат.

Теория

Из вики: Менеджер памяти — часть компьютерной программы (как прикладной, так и операционной системы), обрабатывающая запросы на выделение и освобождение оперативной памяти или (для некоторых архитектур ЭВМ) запросы на включение заданной области памяти в адресное пространство процессора.

Предлагаю так же перед продолжением прочитать эту статью.

Watermak Allocator

Что же, наверное самый простой из всех аллокаторов — Watermark Allocator. Суть его примерно следующая: вся память разбита на блоки, у блока есть заголовок, в котором лежит размер этого и предыдущего блока, статус блока(занят/свободен), зная адрес блока мы за O(1) можем получить адрес следующего и предыдущего блока.

Выделение памяти

Для выделения памяти нам просто напросто нужно бежать по блокам, и искать блок, размер которого больше или равен размеру требуемой для выделения памяти. Как вы уже поняли, асимптотика O(N) — плохо.

Высвобождение памяти

Для высвобождения памяти нам достаточно установить статус блока как «свободный» — O(1) — супер!

Но, как вы понимаете, могут начать образовываться дыры, в которых 2 и более свободных блоков — память дефрагментированна, при высвобождении можно просматривать соседние блоки, и в случае, когда один или два свободны — мержить их в один.

Аллокатор за логарифмическую скорость

Мы знаем, что нам надо искать только среди свободных блоков. Бегать только по свободным улучшает скорость в среднем в два раза, но это всё равно линия. Что же, зачем нам бегать по всем блокам, ища размер, если мы можем организовать дерево из свободных блоков! Изначально у нас только один свободный блок, а дальше мы добавляем свободные блоки в бинарное дерево поиска, ключом будет — размер блока. Таким образом, чтобы выделить память нам достаточно найти блок в дереве, у которого размер больше или равен тому, что нам нужен. Это мы спокойно делаем за O(log N), просто спускаясь по дереву вниз. Дальше мы либо режем блок на два, либо полностью отдаем его тому, кто запросил память. Дальше мы удаляем блок из дерева за O(1). И, если надо, вставляем оставшуюся часть блока обратно за O(log N). Для высвобождения нам достаточно вставить блок обратно, и не надо забывать про фрагментацию.

Хранить дерево блоков можно в статическом массиве, или же придумать как это сделать по-другому. Логично, что использовать простое дерево не надо, надо использовать самобалансирующееся дерево, Red-Black или AVL.

Собственно, код:

char * malloc(size_t size) 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)); }

Удачи и этичного хакинга! Любая объективная критика приветствуется, цель статьи не сказать, что это вах какой аллокатор, а просто рассказать о аллокаторе, который будет лучше, чем тупые реализации простых аллокаторов.


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

[Из песочницы] Haiku β1 — сделаем /b/ OS великой снова

Совсем недавно (почти 4 месяца назад) вышла новая Haiku (далее — просто BeOS, ибо проект гораздо удачнее ReactOS — настолько, что разница между Haiku и BeOS уже пренебрежимо мала). Да и недавно прочитанный киберпанк-роман Александра Чубарьяна давал понять, что BeOS ...

Минкомсвязи одобрило законопроект об изоляции рунета

Министерство цифрового развития, связи и массовых коммуникаций РФ поддержало законопроект №608767-7 об автономной работе рунета, внесённый в Госдуму 14 декабря 2018 года. Об этом сегодня сообщил замглавы Минкомсвязи Олег Иванов в ходе расширенного заседания комитета Госдумы по информационной политике, информационным технологиям ...