Приветствую, уважаемый читатель!

В первой части мы реализовали простейший аллокатор с минимальным оверхедом. Конечно же на самом деле все сложнее. Так реализация дефрагментации была наивной и не могла сливать блоки даже когда не было распределенных блоков после нескольких вызовов mem_free. Для того, что бы получить исходную картинку где будет только 2 служебных блока и один свободный нужно было бы вызвать mem_alloc с размером большим чем доступно памяти что бы искусственно запустить дефрагментацию. В этой части мы это исправим и напишем юнит тест для нашего аллокатора что бы убедится что он работает правильно.

Доброго времени суток.

При разработке ОС на с++ мы сталкиваемся с рядом трудностей, таких как отсутствие стандартной библиотеки и ABI с++ и прочее в этом духе. При чем перед реализацией PageAllocator и прочих аппаратных механизмов хотелось бы иметь какую то стандартную библиотеку позволяющую делать хоть что то. Об этом и пойдет речь.

Далее я расскажу о своем опыте разработки таких алгоритмов для своей ОС и о том, как их тестировать у себя на системе с юнит тестами и прочим прикручивая в итоговую демку проверенный тестами код, и начну я с аллокатора.

Речь пойдет о немного переделанном алгоритме Кнута "неявный список блоков с граничными тегами" который описан в конце третьего тома в разделе "Распределение памяти". Его идея предельно проста:

Мы берем некоторый отрезок памяти, назовем его кучей и разбиваем его на блоки такого вида: