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

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

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

Когда выделенный ранее участок памяти будет возвращен в систему вызовом метода release, то в этом участке можно организовать свободный блок и присоединить его к списку свободных блоков системы. В дальнейшем этот свободный блок может быть снова выдан по запросу get, если его длина окажется достаточно большой. Для того чтобы избежать потерь памяти из-за внешней фрагментации, алгоритм пытается соединять расположенные рядом в буфере свободные блоки в один. Такую попытку соединения можно делать при каждом возврате выделенного ранее участка памяти в систему или же только тогда, когда система начинает ощущать последствия фрагментации, т. е. поиск свободного блока памяти происходит слишком долго. В нашей реализаций мы будем делать попытку слияния свободных блоков при каждом ВЫЗОВе метода release.
Если возвращаемый блок примыкает к какому-либо свободному блоку, то можно просто расширить этот свободный блок за счет возвращаемого участка памяти. Самая сложная ситуация возникает, если возвращаемый в систему участок примыкает сразу к двум свободным блокам памяти, т. е. занимает пространство буфера между этими блоками. В этом случае необходимо не просто расширить свободные блоки, но соединить два блока в один, при этом один из блоков исключается из списка свободных, и его память целиком включается в состав другого блока.
На рис. 5.3 показаны все ситуации, которые могут возникнуть при возврате в систему ранее выделенного блока памяти. Двойной штриховкой выделены те участки памяти, которые система уже выделила ранее. Возвращаемый в систему участок памяти показан однократной штриховкой. На рисунке показаны ситуации перед началом работы метода release и сразу же после его работы. Длины блоков обозначены /ь /2, /3.
При реализации методов get и release в системе распределения памяти со свободными блоками, организованными в двусвязный список, удается срав-
Алгоритмы распределения памяти
305
нительно просто организовать добавление свободных блоков и удаление блоков из системы. Проблема, однако, состоит в том, чтобы при возврате занятого участка памяти в систему определить, где находятся соседние с ней блоки. Для этого надо просмотреть весь список свободных блоков и найти в нем блоки с максимальным адресом из всех лежащих левее освобождаемого и с минимальным адресом из всех лежащих правее освобождаемого. Если список блоков велик, то на его просмотр может потребоваться много времени. Можно сократить затраты времени примерно вдвое, если поддерживать в списке упорядоченность по возрастанию адресов блоков. Алгоритм возврата занятого участка памяти становится немного сложнее, но зато и работает он быстрее.
До После
а) нет примыкающих свободных блоков
б) примыкающий свободный блок слева
в) примыкающий свободный блок справа
/ 1 >2 'з 1
'Л+'з г
г) примыкающие свободные блоки слева и справа
Рис. 5.3. Структура свободных и занятых блоков памяти при возврате участка памяти в систему
В листинге 5.6 приводится реализация методов get и release для описанного метода управления памятью. Большую часть текста занимает разбор различных случаев, которые могут встретиться при захвате и освобождении памяти, хотя сам по себе каждый из этих случаев достаточно прост. Структуры свободного и занятого блоков памяти определены с помощью описаний типов FreeBiock и BusyBiock, при этом на самом деле описаны только управляющие
306
Гпава 5
части этих блоков, содержащие длину и указатели на соседние по списку блоки. Работа с памятью требует аккуратности из-за того, что все время приходится трактовать различные участки памяти по-разному, в зависимости от того, какое содержание вложено в тот или иной участок. Для этого часто приходится прибегать к явному приведению указателей на участки памяти к разным типам: (char*), когда требуются побайтовые вычисления; (FreeBiock*), когда требуется работа с управляющей частью свободного блока памяти, или (BusyBiock*), когда нужно определить размер памяти, необходимой для хранения управляющей части занятого участка памяти.
.........;.......:....:..:......:........................................
Листинг 5.6. систем»распределений;па1^тй^^:‘>'--^ '-4 *¦'.'
с помощью двусвдзного списка свободных блоков . v
//===========================================================
// Класс BiListMemory представляет буферный пул памяти и систему // управления ею для размещения в ней блоков переменного размера.
// Свободные блоки связаны в двунаправленный упорядоченный список //====^===========================^=============================
class BiListMemory {
// Структура свободного блока памяти: struct FreeBiock { size_t length;
FreeBiock * next, * pred;
};
// Структура выделенного блока памяти: struct BusyBiock { size_t length;
};
char * buffer; // Указатель на буфер
size_t size; // Размер буфера в байтах
// Указатель списка свободных блоков:
FreeBiock * freePtr;
public :
// Конструктор:
BiListMemory(size_t n) {
buffer = new char[size = n]; clear();
}
Алгоритмы распределения памяти
307
// Деструктор:
Предыдущая << 1 .. 100 101 102 103 104 105 < 106 > 107 108 109 110 111 112 .. 161 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Вирт Н. "Систематическое программирование " (Теория программирования)

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

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

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

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