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

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

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

Первый из таких алгоритмов распределения памяти называется методом граничных маркеров. Для того чтобы избежать просмотра списка свободных
Алгоритмы распределения памяти
313
блоков при возврате ранее выданного участка памяти в систему, в этом алгоритме каждый блок памяти — и свободный, и занятый — помечаются специальными маркерами в начале и в конце блока. Всего существуют два типа маркеров: маркер свободного блока и маркер занятого блока. Теперь метод release может вместо просмотра списка сразу определить, какой из блоков — занятый или свободный — примыкает к освобождаемому. Это может сильно ускорить работу алгоритма, однако наличие маркеров несколько увеличивает внутреннюю фрагментацию в системе. Поиск свободного блока в реализации метода get в этой системе производится точно так же, как и в методе двусвязных списков, поэтому вся организация этого списка остается без изменений.
Описанная система распределения памяти реализована нами в листинге 5.7 в виде определения класса BoardMarkersMemory. По сравнению с реализацией класса BiListMemory в этом классе мы не стали определять структуры свободных и занятых участков памяти в виде явных описаний структур. Вместо этого мы используем прямое обращение к байтовому буферу с помощью явно заданных адресов и смещений. Строго говоря, такая реализация несколько чище, поскольку не зависит от того, как размещает компилятор отдельные элементы структуры внутри памяти, отведенной под структуру. На рис. 5.4 изображены структуры свободного и занятого участков памяти при использовании метода граничных маркеров. На рисунке видно, что помимо собственно граничных маркеров по сравнению с методом двусвязного списка имеется еще одно дополнение: размер свободного блока содержится не только в начале блока, но также и в его конце. Это нужно для того, чтобы алгоритм возврата памяти в систему, найдя конец свободного блока, примыкающего к возвращаемому участку, смог бы сразу же определить, где находится начало блока, не просматривая при этом список свободных блоков.
Указатель на предыдущий свободный блок в списке
Указатель на следующий свободный блок в списке

Размер блока
л
Свободное пространство Размер блока
а) Структура свободного блока памяти
Размер блока
Выделенное пространство
б) Структура выделенного блока памяти
Рис. 5.4. Структура блоков памяти в методе граничных маркеров распределения памяти
314
Гпава 5
Граничные маркеры показаны на рисунке в виде заштрихованных квадратиков, при этом свободный блок отмечен штриховкой одного вида, а занятый блок — штриховкой другого вида.
В алгоритмах, приведенных в листинге 5.7, трудным для понимания местом является работа со списками. Так, например, для того чтобы по заданному адресу свободного блока найти адрес следующего блока в списке, используется такая конструкция:
*(char**)&freeBlock[MARKER_SIZE + SIZE_SIZE + PTR_SIZE]
Здесь подразумевается, что freeBlock— это адрес свободного блока типа (char*), a marker_size, size_size и ptr_size— размеры в байтах полей, содержащих маркер блока, размер блока и указатель на другой блок соответственно. Индекс в этом выражении используется, чтобы позиционировать указатель на нужное поле, содержащее адрес следующего блока; далее он квалифицируется как указатель на поле, содержащее указатель; наконец, берется значение по вычисленному указателю, чтобы извлечь нужный адрес.
{ Листинг 5.7. Реализация методов get и release в алгоритме I распределения памяти с помощью граничных маркеров ; j
//------- boardmarkers.h --------------------------------------------
//============================_===================================
// Класс BiListMemory представляет буферный пул памяти и систему // управления ею для размещения в ней блоков переменного размера. // Свободные блоки связаны в двунаправленный упорядоченный список //=“===========================================================
class BoardMarkersMemory {
// Коды граничных маркеров можно выбрать произвольно: static const unsigned char FREE_MARKER = OxCC;
static const unsigned char BUSY_MARKER = 0x33;
// Размеры в байтах элементов управляющей информации static const int MARKERJSIZE = sizeof (unsigned char) ; static const int SIZE_SIZE = sizeof(size_t); static const int PTR_SIZE = sizeof(char*);
char * buffer; // Указатель на буфер
size_t size; // Размер буфера в байтах
// Указатель на элемент кольцевого списка свободных блоков: char * freePtr;
public :
// Конструктор:
BoardMarkersMemory(size_t n) : size(n), buffer(new char[n]) {
Алгоритмы распределения памяти
315
clear();
}
// Деструктор:
~BoardMarkersMemory() { delete[] buffer; }
// Очистка памяти, void clear() {
//В буфере создается кольцевой список из единственного // блока, размер которого равен размеру всего буфера freePtr = buffer;
// Формирование начального сектора блока *freePtr = FREE_MARKER;
*(size_t*)&freePtr[MARKER_SIZE] = size;
*(char**)&freePtr[MARKER_SIZE + SIZE_SIZE] = freePtr;
*(char**)&freePtr[MARKER_SIZE + SIZE_SIZE + PTR_SIZE] = freePtr;
// Формирование конечного сектора блока
Предыдущая << 1 .. 103 104 105 106 107 108 < 109 > 110 111 112 113 114 115 .. 161 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Завалишин Д. "Интернетско-русский разговорник" (Web-программирование)

Заенцев И.В. "Нейронные сети: основные модели" (Web-программирование)

Владимиров А.А. "Wi-фу: «боевые» приемы взлома и защиты беспроводных сетей" (Web-программирование)

Вьейра Р. "SQL Server 2000. Программирование в 2 ч." (Web-программирование)

Веллинг Л.Т. "Разработка web приложений с помощью php и mysql" (Web-программирование)
Авторские права © 2013 ComputersBooks. Все права защищены.

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed