Компьютерные книги
Главное меню
Главная Поиск по сайту Добавить материал О нас Карта книг Карта сайта
Реклама
computersbooks.net -> Добавить материал -> Языки программирования -> Кубенский А.А. -> "Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++" -> 112

Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++ - Кубенский А.А.

Кубенский А.А. Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++ — Спб.: БВХ-Петербург , 2004. — 464 c.
ISBN 5-94157-506-8
Скачать (прямая ссылка): strukturiialgoritmiobrabotkidannih2004.djvu
Предыдущая << 1 .. 106 107 108 109 110 111 < 112 > 113 114 115 116 117 118 .. 161 >> Следующая

Самым трудным в этом методе оказывается нахождение для каждого из блоков его близнеца. Для этого используется арифметика относительных адресов, в которой в качестве всех адресов (указателей) используются смещения в байтах блоков внутри всего буфера памяти, отведенного для работы системы. Если полный размер буфера равен 2", то все смещения внутри буфера расположены в диапазоне от нуля до 2"-1, причем смещения блоков памяти, размер которых равен 2к, будут всегда кратны значению 2к. Если рассматривать смещения блоков в двоичной системе счисления, то младшие к битов в адресе блока размером 2к всегда будут равны нулю.
Рис. 5.5. Структура памяти в методе двоичных близнецов распределения памяти
Алгоритмы распределения памяти
321
Чтобы для данного блока определить адрес его близнеца, рассмотрим тот блок размером 2к+\ который мог бы получиться при объединении блока размером 2к с его близнецом. Адрес такого объединенного блока будет иметь уже (А+1) нулей в младших битах. Ясно, что если адрес блока размером 2к имеет на конце (?+1) нуль, то он должен совпадать с адресом объединенного блока, а значит, адрес его близнеца будет на 2к больше адреса самого блока. Наоборот, если адрес блока имеет на конце лишь к нулей, а (А+1)-й бит оказался равен единице, то адрес его близнеца должен совпасть с адресом объединенного блока, т. е. его можно вычислить, отняв от адреса самого блока 2к. Другими словами, имея адрес блока, можно получить адрес его близнеца, если инвертировать в этом адресе (А+1)-й бит.
Проверить, является ли близнец данного блока свободным блоком памяти, можно просто просмотрев список свободных блоков данного размера. Конечно, это чуть медленнее, чем в методе граничных маркеров, однако в данном методе выигрыш достигается за счет того, что поиск по списку не проводится при резервировании памяти. Кроме того, поскольку вместо одного списка свободных блоков мы имеем несколько списков, причем поиск производится только в одном из них, можно надеяться, что этот поиск будет не очень долгим.
Алгоритмы резервирования и освобождения памяти в методе двоичных близнецов удобно оформлять в виде рекурсивных функций, одним из параметров которых служит размерность блока— показатель степени двойки, определяющий размер выделяемого или освобождаемого блока. Размерность блока — величина небольшая, Современные компьютеры не работают с блоками памяти размером больше 232 байтов, так что для хранения размерности достаточно всего одного байта памяти. Для того чтобы при возврате блока в систему знать, какой величины блок был выделен, можно записать в первый байт выделяемого блока его размерность.
Итак, реализация системы распределения памяти, основанной на методе двоичных близнецов, приведена в листинге 5.8. В этом листинге операции get и release просто вызывают соответствующие рекурсивные версии этих функций. Вся работа с адресами блоков происходит с помощью операций побитовой арифметики. Сами эти адреса представлены значениями типа size t, а окончание списка отмечается специальным адресом, равным Oxffffffff.
Листинг 5.8. Реализация системы распределения памяти методом двоичных близнецов
//==============================================================
// Класс BinTwinsMemory представляет буферный пул памяти и систему // управления ею для размещения в ней блоков переменного размера. // Свободные блоки образуют систему двоичных близнецов / / —————————————=—————=———
322
Гпава 5
//--------- bitwins.h ----------------------------------------------------------
class BinTwinsMemory {
// Адрес, отмечающий конец списка: static const size_t null = OxFFFFFFFF;
char * buffer; // Указатель на буфер
int power; // Двоичный показатель размера буфера
// Массив списков свободных блоков одного размера:
// элемент с индексом к содержит адрес списка // свободных блоков размером 2**к size_t * freeLists;
public :
// Конструктор:
BinTwinsMemory(int n)
: power(n), freeLists(new size_t[n +1]), buffer(new char[l « n]) { clear();
}
// Деструктор:
-BinTwinsMemory() { delete[] buffer; delete[] freeLists;
}
// Очистка памяти: инициализация списков свободных // блоков - все списки кроме одного - пустые, void clear() {
for (int i = 0; i < power; i++) freeLists[i] = null; freeLists[power] = 0;
*(size_t *)buffer = null;
}
// Операция выделения свободного блока памяти заданного размера void * get(size_t sz);
// Операция возврата выделенного блока памяти в систему void release (void * ptr) ;
private :
// Вспомогательные рекурсивные функции. Аргумент р - размерность блока. size_t getRec(char р);
void BinTwinsMemory::releaseRec(size_t block, char p);
};
Алгоритмы распределения памяти
323
//--------- bitwins.срр -------------------------------------------------------
// Операция выделения свободного блока памяти заданного размера void * BinTwinsMemory::get (size_t sz) {
sz += sizeof(char); // один байт резервируется дополнительно
// Вычисление размерности блока, который необходимо зарезервировать char р = 2;
while (sz != (1 « р) && Ы(lu « р)-1) & sz) != 0) р++;
Предыдущая << 1 .. 106 107 108 109 110 111 < 112 > 113 114 115 116 117 118 .. 161 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Вирт Н. "Систематическое программирование " (Теория программирования)

Эком "Microsoft Excel 2000 шаг за шагом Русская версия самоучитель " (Самоучитель)

Поляков А.Ю. "Методы и алгоритмы компьютерной графики в примерах Vizual C++" (Графика)

Баяковский Ю.М. "Графическая библиотека Open GL " (Графика)

Валиков А. "Технология " (Языки программирования)
Авторские права © 2013 ComputersBooks. Все права защищены.