Распределение памяти

┌│

Введение

1. Области данных

2. Описатели

3. Память для данных элементарных типов

4. Память для массивов

Векторы

Матрицы

Многомерные массивы

5. Память для структур

Записи по Хоору

Структуры PL/1

Структуры данных по Стендишу

6. Соответствие фактических и формальных параметров

Вызов по ссылке

Вызов по значению

Вызов по результату

Фиктивные аргументы

Вызов по имени

Имена массивов в качестве фактических параметров

 Имена процедур в качестве фактических параметров

7. Динамическое распределение памяти

Метод помеченных границ для распределения памяти

Сборка мусора

Системы с двухуровневым распределением памяти

8. Объектно-ориентированные языки. Новые информационные

структуры и память для них

Введение

Задачей распределения памяти является вычисление адресов

для фрагментов программы и информационных объектов, исходя из

фиксируемого при генерации взаимного их расположения, причем

для адресов тех объектов, расположение которых в памяти нельзя

определить статически ( при трансляции ), генерируются

динамические вычисления этих адресов.

Информационные объекты в процессе эволюции языков

программирования также развивались - от простых переменных

целого, символьного типов до субстанций которыми оперируют

современные объектно-ориентированные языки. Ниже будут

изложены механизмы распределения памяти для самых

разнообразных информационных объектов.

1. Области данных

Областью данных является ряд последовательных ячеек - блок

оперативной памяти, - выделенный для данных, каким-то образом

объединенных логически. Часто ( но не всегда ) все ячейки

области данных принадлежат одной и той же области действия в

программе на исходном языке; к ним может обращаться один и тот

же набор инструкций ( т.е. этой областью действия может быть блок

или тело процедуры ).

 Во время компиляции ячейка для любой переменной времени

счета может быть представлена упорядоченной парой чисел ( номер

области данных, смещение ), где номер области данных - это

некоторый единственный номер, присвоенный области данных, а

смещение - это адрес переменной относительно начала области

данных. Когда мы генерируем команды обращения к переменной, эта

пара переводится в действительный адрес переменной. Это обычно

выполняется установкой адреса базы ( машинного адреса первой

ячейки ) области данных на регистр и обращению к переменной по

адресу, равному смещению плюс содержимое регистра. Пара ( номер

области данных, смещение ) таким образом переводится в пару

( адрес базы, смещение ).

Области данных делятся на два класса - статический и

динамический. Статическая область данных имеет постоянное число

ячеек, выделенных ей перед началом счета. Эти ячейки выделяются

на все время счета. Следовательно, на переменную в статической

области данных возможна ссылка по ее абсолютному адресу вместо

пары ( адрес базы, смещение ).

Динамическая область данных не всегда присутствует во время

счета. Она появляется и исчезает, и всякий раз, когда она

исчезает, теряются все величины, хранящиеся в ней.

2. Описатели

Если компилятор знает все характеристики переменных во

время компиляции, то он может сгенерировать полностью команды

обращения к переменным, основываясь на этих характеристиках. Но

во многих случаях информация может задаваться динамически во

время счета. Например, в АЛГОЛе не известны нижняя и верхняя

границы размерностей массивов, а в некоторых языках тип

фактических параметров не соответствует точно типу формальных

параметров. В таких случаях компилятор не может сгенерировать

простые и эффективные команды, так как он должен учитывать все

возможные варианты характеристик.

Чтобы решить эту задачу, компилятор выделяет память не

только для переменных, но и для их описателей, которые содержат

атрибуты ( характеристики ), определяемые во время счета. Этот

описатель заполняется и изменяется по мере того, как становятся

известными и меняются характеристики при счете.

Возьмем простой пример: если формальный параметр является

простой переменной и тип соответствующего фактического параметра

может меняться, фактический параметр, передаваемый процедуре,

может выглядеть, например, так:

 ┌──────────────────────────────────────────────────────────────┐

 │ Описатель 0 = действительный, 1 = целый, 2 = булевый и т.д. │

 ├──────────────────────────────────────────────────────────────┤

 │ Адрес значения ( или само значение ) │

 └──────────────────────────────────────────────────────────────┘

Если в процедуре есть обращение к формальному параметру,

процедура должна запрашивать или интерпретировать этот описатель

и затем выполнить любое необходимое преобразование типа. Эти

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

Во многих случаях компилятор не может выделитъ память для

значений переменных, так как неизвестны атрибуты размерности.

Так происходит с массивами в АЛГОЛе. Все, что компилятор может

сделать, - это выделить память в области данных для описателя

фиксированной длины, описывающего переменную. Во время

выполнения программы, когда станут известны размерности, будет

вызвана программа GETAREA ( которая чаще всего является функцией

операционной системы ), которая выделит память и занесет в

описатель адрес этой памяти. При этом ссылка на значение всегда

выполняется с помощью такого описателя.

Для структур или записей требуются более сложные описатели,

в которых указывается, как связаны между собой компоненты и

подкомпоненты. Эти механизмы будут рассмотрены ниже.

Чем больше атрибутов могут меняться при счете, тем больше

приходится выполнять работы во время счета.