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

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

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

Второй вид фрагментации может возникнуть из-за того, что система фактически выдает по запросу блок памяти размера большего, чем запрошенный. Это может произойти из-за того, что система не в состоянии разделить блок на две части так, чтобы учесть оставшуюся часть в системе в качестве самостоятельного свободного блока. Конечно, когда этот блок вернется в систему, то вся выделенная память вновь будет доступна для распределения, однако если таких блоков оказывается много, то это также может привести к значительным потерям памяти. Такой вид фрагментации обычно называют внутренней фрагментацией. Память, потерянную в результате внутренней фрагментации, невозможно вернуть в систему до тех пор, пока весь выделенный блок не будет целиком отдан системе.
Очень часто алгоритмы систем распределения памяти представляют собой различные способы достижения некоторого компромисса между внешней и внутренней фрагментацией, при этом системы, которые позволяют сильно уменьшить внешнюю фрагментацию памяти, теряют память из-за внутренней фрагментации, и наоборот. Дело осложняется еще и тем, что теоретически очень трудно точно оценить алгоритм по величине потерь памяти из-за фрагментации. Иногда можно дать качественную оценку алгоритма, но все же реальные потери можно оценить только при моделировании реальных запросов к памяти. Не существует идеальных алгоритмов, которые были бы лучшими независимо от конкретной ситуации. Некоторые алгоритмы ведут себя лучше в условиях, когда имеется сравнительно небольшое число запросов к памяти большими фрагментами, другие предпочитают много мелких запросов.
В этом разделе мы рассмотрим три метода организации памяти: метод двусвязных списков, метод граничных маркеров и метод двоичных близнецов. Из этих методов первые два имеют сравнительно небольшую внутреннюю фрагментацию, но тратят много времени на борьбу с внешней фрагментацией. В последнем методе внешняя фрагментация практически отсутствует, однако довольно много памяти может оказаться неиспользуемой из-за сильной внутренней фрагментации.
Алгоритмы распределения памяти
303
Все рассматриваемые и многие другие методы распределения памяти используются не только в прикладных программах, но и в языковых системах программирования и даже в операционных системах. Так, например, в простой операционной системе MS DOS фирмы Microsoft для реализации системы управления памятью процессов использовался метод, близкий к описываемому методу двусвязных списков. Подобные методы используются и при реализации систем динамического распределения памяти для различных языков программирования, в частности для стандартных алгоритмов реализации операторов new и delete в системах программирования на C++ или реализации системных функций malloc, calloc и free для систем программирования на языке С.
Система распределения памяти с помощью двусвязного списка блоков несколько напоминает рассмотренную в предыдущем разделе систему управления памятью для запросов с постоянной длиной блоков. Как и в той системе, свободная память организована в виде списка свободных блоков, однако, поскольку блоки могут иметь разную длину, в этих блоках кроме указателей, связывающих их в список, хранится еще и размер блока. Когда блок или его часть выделяются по запросу к системе, в этом выделенном блоке также сохраняется его длина, которая используется позже при возврате его в систему. На рис. 5.2 показана структура свободных и выделенных блоков памяти в этой системе.
Свободный блок памяти содержит информацию, используемую системой управления памятью, а именно размер этого блока в байтах и адреса предыдущего и следующего свободных блоков в буфере. Информация о длине в каждом выделенном блоке памяти, которую необходимо хранить для правильной работы алгоритма, — это непроизводительные расходы памяти, расходы на внутреннюю фрагментацию.
Указатель на предыдущий Указатель на следующий
свободный блок в списке свободный блок в списке
Размер блока f Свободное пространство
а) Структура свободного блока памяти
Размер блока Выделенное пространство
б) Структура выделенного блока памяти
Рис. 5.2. Структура свободного и выделенного блоков памяти в системе распределения памяти методом организации двусвязного списка свободных блоков
304
Гпава 5
Свяжем все свободные блоки памяти в двусвязный список, управление которым и составляет основное содержание алгоритма распределения памяти по данному методу. Когда в систему поступает запрос на выделение некоторого участка памяти, система, прежде всего, пытается найти свободный блок в списке, размер которого не меньше, чем запрошенное число байтов плюс необходимое количество байтов для хранения длины блока. Если такой свободный блок в системе отсутствует, то выделение памяти невозможно. Если свободный блок подходящего размера найден, то можно либо целиком отдать его в качестве результата запроса (это можно сделать, если размер свободного блока лишь незначительно превышает запрашиваемый размер участка памяти), либо выделить часть блока в качестве результата запроса и соответственно уменьшить длину этого свободного блока.
Предыдущая << 1 .. 99 100 101 102 103 104 < 105 > 106 107 108 109 110 111 .. 161 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Вирт Н. "Систематическое программирование " (Теория программирования)

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

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

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

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