Реферат: Распределение памяти
компилятором при компиляции, скажем, структур PL/1. Такие
описания структур лучше всего реализуются в виде дерева, где
для каждого узла должно быть по крайней мере известно:
1) концевой ли это узел или нет;
2) если узел концевой, то каков его тип;
3) если узел концевой, то указатель на значение, если
таковое существует;
4) если узел не концевой, то указатели на узлы для
подкомпонент;
5) размерности подкомпонент.
Всякий раз при обращении к значению компоненты должен быть
проинтерпретирован описатель. Начиная с корневого узла, находится
путь к узлу, к которому обращаются, проверяется тип этого узла и,
наконец, используется или изменяется его значение.
6. Соответствие фактических и формальных параметров
Рассмотрим различные типы формальных параметров и их
соответствие фактическим параметрам и покажем, как каждый из них
может быть реализован. Под формальным параметром мы понимаем
идентификатор в процедуре, который заменяется другим
идентификатором или выражением при вызове процедуры.
При обращении к процедуре, скажем, устанавливается некоторым
образом связь между формальными параметрами и фактическими
параметрами.
Когда в каком-нибудь языке происходит обращение к процедуре,
ей передается список адресов аргументов. Процедура переписывает
эти адреса в свою собственную область данных и использует их для
установления соответствия фактических и формальных параметров.
Кроме фактических параметров, часто имеется несколько неявных
параметров, о которых программист не знает. Один из них это,
конечно, адрес возврата. Следовательно, вызываемой процедуре
передается список такого вида:
неявный параметр 1
.
.
.
неявныи параметр m
адрес фактического параметра 1
.
.
.
адрес фактического параметра n
Что представляют собой адреса в списке? Это зависит от языка
и от типа параметра. Нише перечислены типы параметров, которые
мы будем рассматривать:
1) вызов по ссылке;
2) вызов по значению;
3) вызов по результату;
4) фиктивные аргументы;
5) вызов по имени;
6) имена массивов в качестве фактических параметров;
7) имена процедур в качестве фактических параметров.
Вызов по ссылке ( by reference )
Этот тип параметра самый простой для реализации.
Фактический параметр обрабатывается во время выполнения
программы перед вызовом; если он не является переменной или
константой, он вычисляется и запоминается во временной ячейке.
Затем вычисляется адрес ( переменной, константы или временной
ячейки ), и этот адрес передается вызываемой процедуре.
Вызываемая процедура использует его для ссылки на ячейку (ячейки),
содержащую значение.
Вызов по значению ( by value )
При этом типе соответствия формального и фактического
параметров вызываемая процедура имеет ячейку, выделенную в ее
области данных для значения формального параметра этого типа. Как
и при вызове по ссылке, адрес фактического параметра вычисляется
перед вызовом и передается вызываемой процедуре в списке
параметров. Однако перед фактическим началом выполнения процедура
выбирает значение по адресу и заносит его в свою собственную
ячейку. Эта ячейка затем используется как ячейка для величины
точно так же, как любая переменная, локализованная в процедуре.
Таким образом, нет никакого способа изменить в процедуре значение
фактического параметра.
Вызов по результату ( by result )
В языке АЛГОЛ W для любого формального параметра Х,
объявленного параметром RESULT, справедливо следующее:
1. Для параметра Х отводится ячейка в области данных
процедуры. Эта ячейка используется в процедуре как локализованная
ячейка для переменной Х.
2. Как и в случае параметра VALUE, при рызоре при вызове
процедуры вычисляется и передается адрес фактического параметра.
3. Когда выполнение процедуры заканчивается, полученное
значение Х запоминается по адресу, описанному в п.2.
Другими словами, параметр RESULT есть переменная,
локализованная в процедуре, значение которой при выходе
запоминается в соответствующем фактическом параметре (который
должен быть конечно, переменной ). Понятие RESULT было
предназначено для того, чтобы дополнить в АЛГОЛе вызов по имени
( который описан ниже ), так как последний весьма неэффективен и
обладает большими возможностями, чем это необходимо в
большинстве случаев.
Фиктивные аргументы
В развитых языках следующие фактические параметры
обрабатываются по-разному:
1) константы;
2) выражения, которые не являются переменными;
З) переменные, чьи характеристики отличаются от характеристик
указанных для соответствующих формальных параметров.
Для такого фактического параметра в вызывающей процедуре
заводится временная переменная. Фактический параметр вычисляется
и запоминается во временной переменпой, и адрес этой переменной
передается в списке параметров. Такая переменная называется
фиктивным аргументом.
Вызов по имени
Согласно сообщению о языке АЛГОЛ, использование вызова
параметра по имени означает буквальную замену имени формального
параметра фактическим параметром.
Получить эффективную реализацию с помощью такой текстовой
замены, конечно, нельзя, и мы должны разработать соответствующий
эквивалентный способ.
Обычный способ реализации вызова параметров по имени
состоит в том, чтобы иметь отдельную программу или процедуру в
объектном коде для каждого такого параметра. Для такой программы
был введен термин "санк" ( thunk ). Когда происходит вызов санка,
он вычисляет значение фактического параметра ( если этот параметр
не переменная ) и передает адрес этого значения. В теле процедуры
при каждой ссылке на формальный параметр происходит вызов санка,
после чего для обращения к нужному значению используется
переданный санком адрес.
Различие между вызовом по ссылке и вызовом по имени
заключается в следующем: адрес фактического параметра,
вызываемого по ссылке, вычисляется только один раз, перед
фактическим входом в процедуру, в то время как для вызова по
имени адрес вычисляется всякий раз, когда в теле процедуры есть
обращение к формальному параметру.
Имя массива в качестве фактического параметра
В этом случае и фактический, и формальный параметр должны
быть массивами. Процедуре передается адрес первого элемента
массива ( для языков, которые не требуют информационных
векторов ) или адрес информационного вектора, и этот адрес
используется процедурой для ссылки на элементы массива.
Имя процедуры в качестве фактического параметра
Передаваемый адрес - это адрес первой команды процедуры,
которая встретилась в качестве фактического параметра. Если это
имя само является формальным параметром, то адрес был передан
вызывающей процедуре, когда она вызывалась.
7. Динамическое распределение памяти
Для некоторых языков требуется схема динамического
распределения памяти во время выполнения программы, когда блоки
внутренней памяти выделяются, используются и затем освобождаются
для последующего использования.
Существуют два основных метода общего распределения памяти.
В обоих методах вызывается некоторая программа GETAREA(ADDRESS,
SIZE) для того, чтобы выделить область из SIZE ячеек; программа
записывает в ячейку ADDRESS, адрес этой области. В первом методе
память должна освобождаться "явно" посредством вызова программы
FREEAREA(ADDRESS,SIZE). Во втором методе память "явно" не
освобождается. Вместо этого в тех случаях, когда GETAREA не
может найти область необходимого размера, она вызывает программу
FREEGARBAGE для того, чтобы найти те области во внутренней
памяти, которые не используются программой, и вернуть их системе.
Кроме того она может уплотнить используемые области - сдвинуть
их вместе, чтобы все свободные ячейки были в одном блоке.
Опишем один из способов реализации первого метода.
Метод помеченных границ для распределения памяти
Распределение памяти происходит следующим образом. Когда
начинает выполняться программа, в качестве свободной памяти
используется один большой блок ячеек. При выполнении программы
может несколько раз вызываться GETAREA. Каждый раз она выделяет
необходимые ячейки, начиная от начала свободного блока памяти, и
блок приобретает следующий вид:
┌────────┬────────┬─────────┬────────┬──────────────────────┐
