Динамическое распределение памяти, c++ Опции

[Rocket]

Доброго времени суток, Уважаемые Форумчане! Вот столкнулся с заданием, которое необходимо реализовать, как можно быстрей... Значит, нужно написать программу, моделирующую динамическое распределение памяти в операционной системе. В качестве модели оперативной памяти программа должна использовать байтовый массив размера не менее 256 байт. Использование других глобальных переменных в программе запрещено. В программе в обязательном порядке должны присутствовать следующие функции:
а) Выделить участок заданного размера. В случае успеха вывести начальный адрес выделенного участка. Если участка подходящего для выделения не найдено, необходимо вывести диагностическое сообщение о нехватке памяти.
б) Освободить ранее выделенный участок. В качестве параметра функция должна принимать начальный адрес освобождаемого участка. Ранее выделенный участок может быть освобожден только целиком (освобождение части участка не допускается).
в) Получение информации о свободных/занятых участках в «оперативной памяти» (количество участков каждого типа, начальные адреса, размеры, общее количество занятой и свободной памяти).
А хранить всю информацию, я должен ввиде списков блоков; алгоритм выделения- двоичное разбиение.
Помогите, пожалуйста с реализацией! Возможно у кого-ибудь найдутся соответветсвующие наработки....
Что вообще из себя представляет двоичное разбиение?...

[volvo]

Перевод текста по ссылке:

В buddy-системах распределитель выделяет только блоки определённых размеров, и содержит несколько списков свободных блоков: по одному на каждый допустимый размер. Допустимые размеры обычно - либо степень двойки, либо последовательность Фибоначчи (пример см. ниже). Так что любой блок за исключением блока минимального размера может быть поделён на 2 меньших блока допустимого размера.

Когда распределитель получает запрос на выделение памяти, он округляет запрашиваемый размер вверх (в большую сторону), и возвращает первый блок из списка свободных блоков этого размера. Если список свободных блоков для округлённого размера пуст, распределитель разбивает блок из списка бОльшего размера, и возвращает один из кусков. Оставшийся кусок добавляется к списку блоков соответствующего размера...

Когда блоки возвращаются, возможны попытки объединить находящиеся рядом свободные блоки в блоки бОльшего допустимого размера (coalescence). Для облегчения этого размера списки свободных блоков могут храниться по возрастанию адресов. Основное преимущество buddy-систем это "дешевизна" объединения, поскольку "приятель" любого свободного блока может быть вычислены по его адресу.

(здесь картинка)

К примеру, распределитель бинарной buddy-системы может работать с размерами 16, 32, 64,... 64 kB. Он может начать с единственного блока размером в 64К. Если приложение запрашивает блок в 8К, распределитель проверит список 8-ми килобайтных свободных блоков и не найдет свободных блоков такого размера. После чего он разобьёт 64К блок на 2 блока по 32К, один из которых в свою очередь разобьёт на два 16К блока. Один из 16К будет разбит на два 8К блока. Один из 8-ми Кб блоков будет отдан запрашивающему приложению, а 3 блока размерами 8Кб 16К и 32К - будут сохранены в соответствующих списках свободных блоков. Если после этого приложение запросит блок размером 10К, распределитель округлит размер до 16К, и вернет 16-ти Кб блок из списка для этого размера, при этом 6К будут потрачены впустую.

Buddy-система Фибоначчи может использовать блоки размером 16, 32, 48, 80, 128, 208, ... байт (размер очередного блока - сумма предыдущих двух размеров). Когда разбивается блок из одного списка свободных блоков, две части добавляются к спискам двух предыдущих размеров...

Buddy-системы могут работать очень хорошо, а могут - очень плохо, в зависимости от того, как выбранные размеры соответствуют типичным запросам системы. Округление обычно ведет к значительным количествам потраченной впустую (wasted) памяти, называемой внутренней фрагментацией (internal fragmentation). Она может быть уменьшена сближением допустимых размеров для выделяемых блоков.

А теперь - от меня... Мне все-таки думается, что вот тут:

Суть моего задания заключается в том, чтобы использовать только массив байт (256 байт), а в этом массиве как бы организовать структуру

ты очень сильно ошибаешься, ибо в таком случае если у тебя запросить блок размером в 2 байта, ты потратишь почти всю память на список свободных блоков... Не в этом твоя задача, насколько я ее вижу... А в том, чтобы создать такую структуру данных, которая могла бы выделять по запросу память и корректно оперировать списками свободных блоков, хранящимися в самой структуре. То есть, у тебя есть 256 (или больше, в задании написано минимум 256) байт "оперативной" памяти, и есть менеджер памяти, который хранит все, что тебе нужно... Занимаемая им память не касается "оперативной".

Ограничение

Использование других глобальных переменных в программе запрещено.

обходится элементарно: нельзя глобальные - используй локальные, тем более, что С++ позволяет локально описать класс:

#include <iostream>
int main() {

    class A {
    public:
        A() {
            std::cout << "A created" << std::endl;
        }
    };

    A obj;
    return 0;
}

Где ты здесь видел глобальные переменные?