Передаваемый адрес - это адрес первой команды процедуры,
которая встретилась в качестве фактического параметра. Если это
имя само является формальным параметром, то адрес был передан
вызывающей процедуре, когда она вызывалась.
7. Динамическое распределение памяти
Для некоторых языков требуется схема динамического
распределения памяти во время выполнения программы, когда блоки
внутренней памяти выделяются, используются и затем освобождаются
для последующего использования.
Существуют два основных метода общего распределения памяти.
В обоих методах вызывается некоторая программа GETAREA(ADDRESS,
SIZE) для того, чтобы выделить область из SIZE ячеек; программа
записывает в ячейку ADDRESS, адрес этой области. В первом методе
память должна освобождаться "явно" посредством вызова программы
FREEAREA(ADDRESS,SIZE). Во втором методе память "явно" не
освобождается. Вместо этого в тех случаях, когда GETAREA не
может найти область необходимого размера, она вызывает программу
FREEGARBAGE для того, чтобы найти те области во внутренней
памяти, которые не используются программой, и вернуть их системе.
Кроме того она может уплотнить используемые области - сдвинуть
их вместе, чтобы все свободные ячейки были в одном блоке.
Опишем один из способов реализации первого метода.
Метод помеченных границ для распределения памяти
Распределение памяти происходит следующим образом. Когда
начинает выполняться программа, в качестве свободной памяти
используется один большой блок ячеек. При выполнении программы
может несколько раз вызываться GETAREA. Каждый раз она выделяет
необходимые ячейки, начиная от начала свободного блока памяти, и
блок приобретает следующий вид:
┌────────┬────────┬─────────┬────────┬──────────────────────┐
│ Занято │ Занято │ ... │ Занято │ Свободно │
└────────┴────────┴─────────┴────────┴──────────────────────┘
Заметим, что размеры занятых областей могут быть
разными. В некоторый момент будет вызвана FREEAREA, чтобы
освободить одну из использованных областей, вообще говоря, не
последнюю. После нескольких вызовов GETAREA и FREEAREA блок
может выглядеть так:
┌────────┬────────┬──────────┬─────────┬────────┬──────────┐
│ Занято │ Занято │ Свободно │ ... │ Занято │ Свободно │
└────────┴────────┴──────────┴─────────┴────────┴──────────┘
где по-прежнему размеры областей различны. Система должна
помнить расположение всех свободных областей, с тем чтобы они
могли быть снова использованы. Более того, смежные свободные
области следует сливать в одну свободную область так, чтобы
память не оказалась разбитой на области, слишком малые для
использования.
Описываемый нами метод помеченных границ принадлежит
Кнуту. Метод требует резервирования для системных нужд 2-х
ячеек на границах каждой области ( одной в начале и одной в
конце ). Это приемлемая плата, так как в случаях, в которых
применяется этот метод, требуются довольно большие области,
например области данных процедур и память для массивов.
Преимущество этого метода в том, что необходимо по существу
фиксированное время, чтобы освободить область и объединить ее
со смежными свободными областями, если это возможно. В других
методах для этой цели требуется просмотр некоторого списка.
Ниже приводится формат каждой занятой и свободной области.
Первое слово содержит поле TAG, которое указывает, свободна ли
область или нет; в поле SIZE содержится число слов области.
Свободные области связываются вместе в двусвязанный список. Поле
FLINK (ссылка вперед) указывает на следующую область списка, в
то время как поле BLINK (ссылка назад) указывает на предыдущую
область.
┌─────┬──────┬───────┬───────┐ первое ┌─────┬──────┬───────────────┐
│ TAG │ SIZE │ BLINK │ FLINK │ слово │ TAG │ SIZE │ │
├─────┴──────┴───────┴───────┤ ├─────┴──────┴───────────────┤
│ │ SIZE-2 │ │
│ │ слов │ │
│ │ │ │
├─────┬──────┬───────────────┤ послед- ├─────┬──────────────────────┤
│ TAG │ SIZE │ │ нее │ TAG │ │
└─────┴──────┴───────────────┘ слово └─────┴──────────────────────┘
Свободная область Резервированная область
Кроме того, существует одна переменная FREE следующего вида:
TAG SIZE BLINK FLINK
┌───┬──────┬──────────────────┬──────────────────┐
FREE │ + │ 0 │ на последнюю │ на первую │
│ │ │ область в списке │ область в списке │
└───┴──────┴──────────────────┴──────────────────┘
Поле BLINK первой области в списке указывает на ячейку FREE, так
же, как и поле FLINK последней области. Наконец, мы предположим,
что блоку, используемому для распределения памяти, предшествует
слово, а за блоком следует слово, содержащее '+' в поле TAG для
указания о том, что "окружающие" области заняты. Такое соглашение
упрощает процесс объединения смежных областей.
Алгоритм работы программы GETAREA основан на методе "первый
подходящий"; просматривается список свободпых областей и
выбирается первая из них, которая является достаточно большой.
Несморя на то, что выбор "наиболее подходящей" области кажется на
первый взгляд лучше, на самом деле это не так, и кроме того, на
это затрачивается, очевидно, больше времени.
Сборка мусора
При втором методе распределения памяти, когда GETAREA не
может найти подходящую область, вызывается программа FREEGARBAGE,
цель которой - найти неиспользуемые области и занести их в
некоторый список свободных областей. Для этого FREEGARBAGE должна
быть в состоянии определить следующее:
1) расположение в памяти каждого описанного указателя;
2) точные сведения о величине, на которую ссылается каждый
указатель, - длина величины и содержит ли она какие-нибудь
указатели;
3) для каждого указателя, содержащегося в величине, на
которую ссылается другой указатель, длину указателя и его
расположение в величине.
Как легко видеть, это довольно сильное требование, и
поэтому, используя указатели, нужно придерживаться строгих правил
Поэтому обычно "сбор мусора" используется в тех случаях, когда
система имеет определенную уверенность в том, что указатели
употребляются правильно, и когда число различных форматов для
величин невелико. Хорошим примером такой системы является LISP.
Другой пример - это система обработки строк, преимущество которой
состоитв том, что величины, па которые ссылаются указатели строк,
являются только строками литер, так что величина, на которую
ссылается указатель, никогда не содержит других указателей.
Другая проблема состоит в трудности точного определения
какие области на любом этапе свободны.
Обычно сбор мусора проходит в две фазы. Во время первой
фазы некоторым образом маркируются все используемые величины.
Общепринятый метод состоит в том, чтобы иметь в каждой
величине дополнительный бит специально для маркировки, хотя в
некоторых случаях это неудобно. Другой метод заключается в
том, что биты маркировки собираются в отдельную таблицу с
определенным соответствием между ячейками и битами маркировки.
Однако при этом требуется специальная таблица для битов
маркировки, а по-видимому, когда вызывается сборщик мусора,
объем свободной памяти очень мал!
Во второй фазе мы просматриваем последовательно всю память,
занося непомеченные области в список свободных областей и
гася биты маркировки. Последнее делается для того, чтобы
при следующем вызове сборщика мусора можно было бы правильно
сформировать биты маркировки.
Иногда используется третья фаза, которая собирает
свободные области вместе, так чтобы они образовывали один
большой блок. Для этого требуется, чтобы программа сбора
мусора изменяла значения указателей при перемещении данных.
Для рассмотрения существующих алгоритмов сбора мусора
отсылаем читателя к гл. 2 книги Кнута "Искусство программирования
на ЭВМ " т.1.
Системы с двухуровневым распределением памяти
В некоторых системах имеются два уровня распределения