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

[Rocket]

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

[volvo]

Ну смотри: вот процесс работы с твоей программой. Состояние - после выделения 16, 4, 8 байт:

4 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 0 0 2 0 0 0 3 1 0 0 0 0 0 0
Free Memory: 4 Occupied Memory: 28

Так? Так... Теперь удаляем 4 байта:

4 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 2 0 0 0 3 1 0 0 0 0 0 0
Free Memory: 8 Occupied Memory: 24

Вот видишь, память освобождена, но ты не объединил то, что освободилось только что - красный блок - с тем, что справа от него - синий, они же оба свободны, и для того, чтобы выделить этот самый "красный", ты разбил то, что сейчас цветное на 2 части !!! Вот теперь ты должен их снова объединить.

Теперь, как проверить, с какой стороны тот блок, с которым надо попытаться объединить? Просто: если начальная позиция только что освобожденного блока - степень двойки, то "связанный" с ним блок надо искать непосредственно справа, иначе - слева. Вот тебе и алгоритм:

после освобождения блока: если индекс его первого элемента - степень двойки, то смотрим блок справа, иначе - слева. Если он такого же размера и пуст - то объединяем их, и повторяем операцию поиска "соседа" до тех пор, пока не дойдем до НЕпустого блока, или пока не объединишь все блоки в один

По поводу второго бага:

по идеи два блока 20002000 должны слиться, в результате должен получиться блок 31000000

Знаешь, я в твоей программе (с ее наворотами и хитросплетениями) не нашел того места, где ты хотя бы пытаешься объединить свободные блоки. Опять же, у тебя эти 2 блока 20002000 свободны и НЕ объединены только потому, что один из них был занят, и при его освобождении ты не посмотрел на соседа и не объединил (алгоритм - выше). Не надо "откладывать на потом", освободил - немедленно сливай...

[Rocket]

Так а я в принципе и не пытаюсь начинать объединять блоки, после освобождения какого-либо блока...всё равно как-то очень странно, потому в такой ситуации : 20002000300000004000000000000000 блок в 32 выделяется с легкостью...

Сообщение отредактировано: volvo - 14.01.2009 0:33