2.5. ДИНАМИЧЕСКОЕ ВЫДЕЛЕНИЕ ПАМЯТИ

В ПРЕДЫДУЩИХ РАЗДЕЛАХ было показано, как использование связей приводит к тому, что структуре*; данных могут располагаться в памяти непоследовательно; несколько таблиц могут независимо расти и уменьшаться в области общего пула памяти. Однако мы всегда молчаливо предполагали, что узлы имеют один и тот же размер, т. е. каждый узел занимает некоторое фиксированное количество ячеек памяти.

Для очень многих приложений можно найти компромиссное решение, при котором в действительности используется один размер узла для всех структур (например, см. упр. 2), Вместо максимального размера (н потери памяти в малых узлах) зачастую выбирается меньший размер узла и применяется метод, который можно назвать классической философией связанной памяти: "Если для размещения информации в одном месте не хватает памяти, разместим ее в другом месте и установим с ней связь".

Однако для очень большого количества приложений использовать единый размер узлов неразумно, ведь часто необходимы узлы различных размеров, разделяющие обш,ую область памяти, т. е. нужны алгоритмы для резервирования и освобождения блоков переменного размера в большой области памяти, причем эти блоки должны состоять из последовательных ячеек памяти. Такие технологии, в целом, называются алгоритмами динамическодо выделения памяти.

Зачастую в моделирующих программах требуется динамическое выделение пат мяти для узлов весьма малого размера (скажем, от одного до десяти слов). В других случаях, чаш,е всего -в операционных системах, мы, в первую очередь, работаем с довольно большими блоками информации. Такие "точки зрения" приводят к несколько отличающимся подходам к динамическому выделению памяти, хотя в ЭТИХ методах много общего. Чтобы унифицировать терминологию рассматриваемых подходов, в данном разделе для обозначения множества последовательных ячеек памяти вместо термина узел будем использовать термины блок и область.

Некоторые авторы начиная примерно с 1075 года называют пул доступной памя» тн кучей (heap), однако в настояш,ем издании этот термин используется только в болев традиционном смысле, связанном с приоритетными очередями (см. раздел 5.2,3).

А. Резервироваяие. На рис, 42 представлена типичная карта памяти, или "шахматная доска",--диаграмма, отображающая текущее состояние некоторого пула памяти. В приведенном примере она разбита на 53 блока, которые "зарезервированы" (reserved), т, е, используются вперемешку с 21 "свободным" (free) или "доступным" (available) блоком, который не используется. Память компьютера спустя некоторое время работы системы динамического выделения, вероятно, будет выглядеть примерно так. Наша первая задача состоит в поиске ответов на два вопроса,

a) Как можно представить такое разбиение свободной памяти в компьютере?

b) Какой алгоритм при данном распределении свободной памяти достаточно хорош для поиска блока из п последовательных свободных ячеек и его резервирования?-

Ответ иа вопрос (а) кроется, конечно, в содержании списка свободной памяти в некотором месте; почти всегда для этой цели лучше всего использовать ту самую свободную память, сведения о которой содержатся в списке (исключением из этиги

00000 20000 40000 бОООО

eoooo

100000 130000

о lOOn 2000 3000 4П00 5000 6000 7000 8000 9000 10000

-wh-rf I)-II I i-! I -i--I-

•4 I

Зарезервированная область:

С)вободная область: I I

Рис. 43. Карта памяти.

правила uom&f быть дисковая или другая память с различным временем доступа; в таком случае лучше иметь каталог доступного пространства отдельно).

Следовательно, можно связать вместе доступные сегменты; первое слово каждой свободной области памяти может содержать размер этого блока и адрес следующей свободной области. Свободные блоки могут быть связаны в порядке возрастания или убывания по размерам, адресам памяти либо в произвольном порядке.

Рассмотрим, например, рис. 42, на котором иллюстрируется состояние памяти объемом 131072 слова, адресуемых от О до 131071. Чтобы связать свободные блоки в порядке их адресов, потребуется переменная AVAIL, указывающая на первый свободный блок (в нашем случае AVAIL равна 0); другие же блоки будут представлены следующим образом.

Дфее SIZE LINK

О 101 632 032 42 1468

! 1 : [17 подобных записей]

73654 1909 77519

77519 63553 Л [Специальный маркер для последней свяаи]

Следовательно, ячейки 0-100 образуют первый свободный блок; после занятых областей в ячейках 101-290 и 291-631, Показанных на рис 42, имее-гся свободное про» странство с адресами 632-673; и т. д.

По поводу вопроса (Ь) понятно, что, если необходима область размером п после» доваельных слое, нужно выполнить поиск некоторого блока из m > п доступных слов и уменьшить его размер до m - п. (Кроме того, при m ss п следует удали1ь данный блок из списка свободных.) В наличии может быть несколько блоков размером п или более ячеек, а потому один вопрос превращается в другой; "Какая имвнт область должна быть выделена?".

Два основных otaeta на этот вопрос напрашиваются сами собой! можно исполь» зоваь метод тилучшеёо подходлщеёо или метод первом по$£одлщеео. D первом случае мы выбираем область с т ячейками памяти, где m -- наименьшее значение из имеющихся, не меньшее п. Для такого выбора может потребоваться поиск по всему списку свободного пространства, Метод первого подходящего, с другой стороны, просто выбирает нерйую попавшуюся область размером не менее п слов.

Исторически чаще использовался метод наилучшего подходящего, так как более разумным представляется подход, сохраняющий большие свободные области "на потом", когда они могут понадобиться. Однако имеется ряд претензий к этому методу: он достаточно медленный, поскольку требует длинного полного поиска, и если он не намного лучше метода первого подходящего в других отношениях, то временем выделения памяти при оценке метода пренебречь нельзя. Еще более важно то, что метод лучшего подходящего имеет тенденцию к увеличению количества блоков свободной памяти малого размера, что обычно нежелательно. Существует ряд ситуаций, в которых метод первого подходящего превосходит метод наилучшего подходящего. Так, например, предположим, что есть тольо две свободные области памяти размером 1300 и 1200 и три последовательных запроса на выделение блоков памяти размером 1000, 1100 и 250.

Запрос Доступные области, Доступные области, блока метод первого метод наилучшего

размером подходящего подходящего

- 1300, 1200 1300, 1200 (1)

1000 300, 1200 1300, 200

1100 300, 100 200, 200

250 50, 100 Нужного блока нет

(Противоположный пример приведен в упр. 7.) Поскольку ни один метод явно не превосходит другой, можно порекомендовать метод первого подходящего*.

Алгоритм А (Метод первого подходящего). Пусть AVAIL указьшает на первый доступный блок памяти, и предположи.м, что каждый свободный блок с адресом Р имеет два поля: SIZE(P) -количество слов в блоке и LINK(P) -указатель на следующий свободный блок. Последний указатель равен Л (что указьшает на завершение списка блоков свободной памяти). Алгоритм находит и выделяет блок размером N слов (и.пи сообщает о невозможности выделения запрошенной памяти).

А1. [Инициализация.] Установить Q LOC(AVAIL). (Везде в алгоритме используются два указателя, Q и Р, которые, вообще говоря, связаны соотношением Р = LINK(Q). Мы полагаем, что LINK(LOC(AVAIL)) = AVAIL.)

А2. [Конец списка?] Установить Р <- LINK(Q). Если Р = А, алгоритм завершается неудачно и блок размером N последовательных слов не может быть выделен.

A3. [Достаточен ли размер блока?] Если SIZE(P) > N, перейти к шагу А4; в противном случае установить Q Р и вернуться к шагу А2.

А4. [Выделение блока.] Установить К SIZE(P) - N. Если К = О, установить LINK (О) LINK(P) (тем самым удаляя пустую область из списка); в противном случае установить SIZE(P) К. Алгоритм успешно завершается, выделяя область памяти длиной N, которая начинается с адреса Р -f- К.

* Видимо, именно из-за отсутствия явного превосходства какого-либо метода над другим программисту во времена DOS предоставлялось право (хотя и не рекомендовалось) изменять стратегию выделения памяти операционной системой при помощи функции 58h прерывания 21h путем выбора метода первого подходящего, лучшего подходящего или последнего подходящего (включая в более поздних версиях указание на возможность использования верхней (high) памяти). Прим. перев.