выделить место в памяти для значений переменных и т.п. и помес-
тить соответствующие адреса, где это необходимо, в таблицу симво-
лов. Фаза распределения памяти почти не зависит от языка и маши-
ны и практически одинакова для подавляющего большинства языков,
имеющих блочную структуру и реализуемых на многих типичных ЭВМ.
Распределение памяти, по существу, заключается в отображении зна-
чений, появляющихся в программе, на запоминающем устройстве маши-
ны. Если допустить, что мы реализуем типичный язык с блочной
структурой, а машина имеет линейное запоминающее устройство, то
наиболее подходящим устройством, на котором мы будем базировать
распределение памяти, представляет стек или память магазинного
типа.
Ниже мы рассмотрим классическую структуру стека времени про-
гона для локального распределения памяти и покажем, как можно
произвести глобальное распределение памяти в отдельной области,
называемой "кучей".
В каждом компиляторе предусмотрена схема распределения памя-
ти, которая до некоторой степени зависит от компилируемого языка.
В Фортране память, выделенная для значений идентификаторов, ни-
когда не освобождается, так что здесь подходящей структурой для
нее является одномерный массив. Если считается, что массив имеет
левую и правую стороны, память можно выделять слево направо. При
этом применяется указатель, показывающий первый свободный эле-
мент в массиве. Например, в результате описания
INTEGER A,B,X,Y
выделяется память, как показано на рис. 20.1.
┌───┬───┬───┬───┬───────────────
│ A │ B │ X │ Y │
└───┴───┴───┴───┴───────────────
^
│
Рис. 20.1 Схема выделения памяти в Фортране
Такая схема не учитывает тот факт, что рабочая память (па-
мять для промежуточных результатов) используется неоднократно и
весьма неэффективна (в смысле использования объема памяти) для
языка с блочной структурой.
В языке, имеющем блочную структуру, память обычно высвобож-
дается при выходе из блока, которому она выделена. В этом случае
оптимальным решением было бы разрешить указателю в вышеприведен-
ном примере отодвигаться обратно влево при высвобождении памяти.
Такой механизм распределения эквивалентен стеку времени прогона
или памяти магазинного типа, хотя принято показывать стек запол-
няющимся снизу вверх.
│ │ │ │ │ │ (1) begin real x,y
│ │ │ │ │ │ .
│ │ ├───┤ ├───┤ .
│ │ │ d │ │ q │ .
│ │ ├───┤ ├───┤ (2) begin int c,d
│ │ │ c │ │ p │ .
├───┤ ├───┤ ├───┤ .
│ │ │ │ │ │ end;
│ │ │ │ │ │ (3) begin int p,q
│ Y │ │ Y │ │ Y │
├───┤ ├───┤ ├───┤ .
│ │ │ │ │ │ .
│ │ │ │ │ │ end;
│ X │ │ X │ │ X │ .
└───┘ └───┘ └───┘ .
end.
(1) (2) (3)
Рис. 20.2 Схема распределения памяти под переменные в раз-
личные моменты в программе на языке с блочной структурой
На рис. 20.2 показаны "моментальные снимки" стека фрагмента
программы во время прогона.
Часть стека, соответствующую определенному блоку, называют
РАМКОЙ стека. Считается, что указатель стека показывает на его
первый свободный элемент.
Кроме указателя стека, требуется также указатель на дно те-
кущей рамки (УКАЗАТЕЛЬ РАМКИ). При входе в блок этот указатель
устанавливается равным текущему значению указателя стека. При вы-
ходе из блока сначала указатель стека устанавливается равным зна-
чению, соответствующему включающему блоку.
Указатель рамки включающего блока может храниться в нижней
части текущей рамки стека, образуя часть статической цепи или
(как мы будем считать) массива, который называется ДИСПЛЕЕМ.
Его можно использовать для хранения во время прогона указа-
телей на начало рамок стека, соответствующих всем текущим блокам
(рис. 20.3).
│ │
│ │
│ │
│ │ ├───┤
│ │ │ q │
│ │ ├───┤
│ │ │ p │
│ │ /───> ├───┤
│ │ / │ │
├──┤ / │ Y │
│ │──/ ├───┤
├──┤ │ │
│ │─────────> │ X │
└──┘ └───┘
Дисплей Стек
Рис. 20.3 Схема связи Дисплея и стека во время выполнения
без учета динамически выделяемой памяти
Это несколько упрощает перенастройку указателя рамки при вы-
ходе из блока.
Если бы вся память была статической, адреса времени прогона
могли бы распределяться во время компиляции, и значения элемен-
тов дисплея также были бы известны во время компиляции.
Рассмотрим следующий отрезок программы на языке Алгол-60:
...
begin int n; read(n);
[1:n] int numbers;
real p;
begin real x,y;
...
Место для numbers должно выделяться в первой рамке стека, а
для x и y - в рамке над ней. Но во время компиляции неизвестно,
где должна начинаться вторая рамка, так как не известен размер
чисел.
Одно из решений в этой ситуации - иметь два стека: один для
статической памяти, распределяемой в процессе компиляции, а дру-
гой - для динамической памяти, распределяемой в процессе прогона.
Однако этого обычно не делают, возможно, из-за тех проблем, кото-
рые возникают в связи с наличием более чем одного увеличивающего-
ся и уменьшающегося стека во время прогона.
Другое решение заключается в том, чтобы при компиляции выде-
лять статическую память в каждом блоке в начале каждой рамки, а
при прогоне - динамическую память над статической в каждой рамке.
Это значит, что когда происходит компиляция, мы все еще не знаем,
где начинаются рамки (кроме первой), но можем распределять стати-
ческие адреса относительно начала определенной рамки. При прого-
не точный размер рамок, соответствующих включающим блокам, извес-
тен, так что при входе в блок нужный элемент дисплея всегда мож-
но установить так, чтобы он указывал на начало новой рамки (рис.
20.4).
│ Рамка 2
│ │ │
│ │ │
│ │ /
├───────┤ \
│ y │ Динами- │
├───────┤ │
│ x │ ческая │
/───> ├───────┤ │
│ │ / │ Числа │ память > Рамка 1
│ │ / │ │ │
├─────┤ / ├───────┤ - - - - │
│ │/ │ p │ Стати- │
├─────┤ ├───────┤ ческая │
│ │──\ │ n │ память │
└─────┘ \────> └───────┘ /
Дисплей Стек
Рис. 20.4 Схема связи Дисплея и стека во время выполнения с
учетом динамически выделяемой памяти
На этом рисунке массив занимает только динамическую память.
Однако некоторая информация о массиве обычно известна во время
компиляции, например, его размерность (а следовательно, и число
границ - две на каждую размерность), и при выборке определенного
элемента массива она может потребоваться. Во многих языках сами
границы могут быть не известны при компиляции, но почти наверня-
ка мы знаем их число, и для значений этих границ можно выделить
статическую память. Тогда мы вправе считать, что массив состоит
из статической и динамической частей. Статическая часть массива
может размещаться в статической части рамки, а динамическая - в
динамической. Кроме информации о границах, в статической части
может храниться указатель на сами элементы массива. Модифицируем
рис. 20.4 в рис. 20.5 с учетом этих особенностей.
│ Рамка 2
│ │ │
│ │ │
│ │ /
├────────┤ \
│ y │ Динами- │
├────────┤ │
│ x │ ческая │
/───> ├────────┤ │
│ │ / │Элемен- │ часть > Рамка 1
│ │ / │ты чисел│ │
├─────┤ / ┌─> ├────────┤ - - - - │
│ │/ │ │ p │ Стати- │
│ │ │ ├────────┤ │
│ │ │ │ Стат. │ │
│ │ └───│ часть │ ческая │
│ │ │ чисел │ │
├─────┤ ├────────┤ │
│ │──\ │ n │ часть │
└─────┘ \────> └────────┘ /
Дисплей Стек
Рис. 20.5 Схема связи Дисплея и стека во время выполнения с
учетом представления массивов в виде статической и динамической
частей
1.2 Выделение памяти под рамку в процессе трансляции
Динамическая рабочая память должна распределяться во время
прогона, статическая же может распределяться во время компиляции.
Объем статической рабочей памяти, который должен выделяться каж-
дой рамке, определяться не рабочей памятью, требуемой в конце
каждого блока (обычно она является нулем), а МАКСИМАЛЬНОЙ рабо-
чей памятью, требуемой в любой точке внутри блока. Для статичес-
кой рабочей памяти эту величину можно установить в процессе ком-
пиляции, если в фазе распределения памяти мы ассоциируем с рабо-
чей стековой областью текущей рамки два указателя, причем один из
них указывает на текущую границу статической рабочей памяти, а