Распределение памяти
1. Области данных
2. Описатели
3. Память для данных элементарных типов
4. Память для массивов
Векторы
Матрицы
Многомерные массивы
5. Память для структур
Записи по Хоору
Структуры PL/1
Структуры данных по Стендишу
6. Соответствие фактических и формальных параметров
Вызов по ссылке
Вызов по значению
Вызов по результату
Фиктивные аргументы
Вызов по имени
Имена массивов в качестве фактических параметров
Имена процедур в качестве фактических параметров
7. Динамическое распределение памяти
Метод помеченных границ для распределения памяти
Сборка мусора
Системы с двухуровневым распределением памяти
8. Объектно-ориентированные языки. Новые информационные
структуры и память для них
Введение
Задачей распределения памяти является вычисление адресов
для фрагментов программы и информационных объектов, исходя из
фиксируемого при генерации взаимного их расположения, причем
для адресов тех объектов, расположение которых в памяти нельзя
определить статически ( при трансляции ), генерируются
динамические вычисления этих адресов.
Информационные объекты в процессе эволюции языков
программирования также развивались - от простых переменных
целого, символьного типов до субстанций которыми оперируют
современные объектно-ориентированные языки. Ниже будут
изложены механизмы распределения памяти для самых
разнообразных информационных объектов.
1. Области данных
Областью данных является ряд последовательных ячеек - блок
оперативной памяти, - выделенный для данных, каким-то образом
объединенных логически. Часто ( но не всегда ) все ячейки
области данных принадлежат одной и той же области действия в
программе на исходном языке; к ним может обращаться один и тот
же набор инструкций ( т.е. этой областью действия может быть блок
или тело процедуры ).
Во время компиляции ячейка для любой переменной времени
счета может быть представлена упорядоченной парой чисел ( номер
области данных, смещение ), где номер области данных - это
некоторый единственный номер, присвоенный области данных, а
смещение - это адрес переменной относительно начала области
данных. Когда мы генерируем команды обращения к переменной, эта
пара переводится в действительный адрес переменной. Это обычно
выполняется установкой адреса базы ( машинного адреса первой
ячейки ) области данных на регистр и обращению к переменной по
адресу, равному смещению плюс содержимое регистра. Пара ( номер
области данных, смещение ) таким образом переводится в пару
( адрес базы, смещение ).
Области данных делятся на два класса - статический и
динамический. Статическая область данных имеет постоянное число
ячеек, выделенных ей перед началом счета. Эти ячейки выделяются
на все время счета. Следовательно, на переменную в статической
области данных возможна ссылка по ее абсолютному адресу вместо
пары ( адрес базы, смещение ).
Динамическая область данных не всегда присутствует во время
счета. Она появляется и исчезает, и всякий раз, когда она
исчезает, теряются все величины, хранящиеся в ней.
2. Описатели
Если компилятор знает все характеристики переменных во
время компиляции, то он может сгенерировать полностью команды
обращения к переменным, основываясь на этих характеристиках. Но
во многих случаях информация может задаваться динамически во
время счета. Например, в АЛГОЛе не известны нижняя и верхняя
границы размерностей массивов, а в некоторых языках тип
фактических параметров не соответствует точно типу формальных
параметров. В таких случаях компилятор не может сгенерировать
простые и эффективные команды, так как он должен учитывать все
возможные варианты характеристик.
Чтобы решить эту задачу, компилятор выделяет память не
только для переменных, но и для их описателей, которые содержат
атрибуты ( характеристики ), определяемые во время счета. Этот
описатель заполняется и изменяется по мере того, как становятся
известными и меняются характеристики при счете.
Возьмем простой пример: если формальный параметр является
простой переменной и тип соответствующего фактического параметра
может меняться, фактический параметр, передаваемый процедуре,
может выглядеть, например, так:
????????????????????????????????????????????????????????????????
? Описатель 0 = действительный, 1 = целый, 2 = булевый и т.д. ?
????????????????????????????????????????????????????????????????
? Адрес значения ( или само значение ) ?
????????????????????????????????????????????????????????????????
Если в процедуре есть обращение к формальному параметру,
процедура должна запрашивать или интерпретировать этот описатель
и затем выполнить любое необходимое преобразование типа. Эти
действия можно, конечно, выполнить, обращаясь к другой программе.
Во многих случаях компилятор не может выделитъ память для
значений переменных, так как неизвестны атрибуты размерности.
Так происходит с массивами в АЛГОЛе. Все, что компилятор может
сделать, - это выделить память в области данных для описателя
фиксированной длины, описывающего переменную. Во время
выполнения программы, когда станут известны размерности, будет
вызвана программа GETAREA ( которая чаще всего является функцией
операционной системы ), которая выделит память и занесет в
описатель адрес этой памяти. При этом ссылка на значение всегда
выполняется с помощью такого описателя.
Для структур или записей требуются более сложные описатели,
в которых указывается, как связаны между собой компоненты и
подкомпоненты. Эти механизмы будут рассмотрены ниже.
Чем больше атрибутов могут меняться при счете, тем больше
приходится выполнять работы во время счета.
3. Память для данных элементарных типов
Типы данных исходной программы должны быть отображены на
типы данных машины. Для некоторых типов это будет соответствием
один к одному ( целые, вещественные и т. д. ), для других могут
понадобиться несколько машинных слов. Можно отметить следующее:
1) Целые переменные обычно содержатся в одном слове или
ячейке области данных; значение хранится в виде стандартного
внутреннего изображения целого числа в машине.
2) Вещественные переменные обычно содержатся в одном слове.
Если желательна большая точность, чем возможно представить в
одном слове, то может быть употреблен машинный формат двойного
слова с плавающей запятой. В машинах, где отсутствует формат с
плавающей запятой, могут быть употреблены два слова - одно
для показателя степени, второе для ( нормализованной ) мантиссы.
Операции с плавающей запятой в этом случае должны выполняться с
помощью подпрограмм.
3) Булевы или логические переменные могут содержаться в
одном слове, причем нуль изображает значение FALSE, а не нуль или
1 -- значение TRUE. Конкретное представление для TRUE и FALSE
определяется командами машины, осуществляющими логические
операции. Для каждой булевой переменной можно также использовать
один бит и разместить в одном слове несколько булевых переменных
или констант.
4) Указатель - это адрес другого значения ( или ссылка на
него ). В некоторых случаях бывает необходимо представлять
указатель в двух последовательных ячейках; одна ячейка содержит
ссылку на описатель или является описателем текущей величины,
на которую ссылается указатель, в то время как другая указывает
собственно на значение величины. Это бывает необходимо в случае
когда во время компиляции невозможно определить для каждого
использования указателя тип величины, на которую он ссылается.
4. Память для массивов
Мы предполагаем, что каждый элемент массива или вектора
занимает в памяти одну ячейку. Случай большего числа ячеек
полностью аналогичен.
Векторы
Элементы векторов ( одномерных массивов ) обычно помещаются
в последовательных ячейках области данных в порядке возрастания
или убывания адресов. Порядок зависит от машины и ее системы
команд.
Мы предполагаем, что используется стандартный возрастающий
порядок, т. е. элементы массива, определенного описанием
ARRAY А [1:10], размещаются в порядке А [1], А [2], ..., А [10].
Матрицы
Существует несколько способов размещения двумерных массивов.
Обычный способ состоит в хранении их в области данных по строкам
в порядке возрастания, т. е. ( для массива, описанного как
ARRAY А [1:M, 1:N], в порядке
А [1, 1], А [1, 2], ..., А [1, N],
А [2, 1], А [2, 2], ..., А [2, N],
...
А [M, 1], А [M, 2], ..., А [M, N].
Вид последовательности показывает, что элемент А[i, j] находится
в ячейке с адресом ADDRESS ( A[1, 1] ) + (i-1)*N + (j-1) который
можно записать так: ( ADDRESS ( A[1, 1] ) - N - 1 ) + ( i*N + j )
Первое слагаемое является константой, и его требуется вычислить
только один раз. Таким образом, для определения адреса А[i, j]
необходимо выполнить одно умножение и два сложения.
Второй метод состоит в том, что выделяется отдельная область
данных для каждой строки и имеется вектор указателей для этих
областей данных. Элементы каждой строки размещаются в соседних
ячейках в порядке возрастания. Так, описание ARRAY А [1:M, 1:N]
порождает
?????????????????????????? ???????????????????????
? Указатель на строку 1 ??????????? A[1, 1] ... A[1, N] ?
?????????????????????????? ???????????????????????
? Указатель на строку 2 ????????? ???????????????????????
?????????????????????????? ??? A[2, 1] ... A[2, N] ?
? ... ? ???????????????????????
?????????????????????????? ???????????????????????
? Указатель на строку M ??????????? A[M, 1] ... A[M, N] ?
?????????????????????????? ???????????????????????
Вектор указателей строк хранится в той области данных, с которой
ассоциируется массив, в то время как собственно массив хранится
в отдельной области данных. Адрес элемента массива А[i, j] есть
CONTENTS(i-1) + (j-1).
Первое преимущество этого метода состоит в том, что при
вычислении адреса не нужно выполнять операцию умножения. Другим
является то, что не все строки могут находиться в оперативной
памяти одновременно. Указатель строки может содержать некоторое
значение, которое вызовет аппаратное или программное прерывание
в случае, если строка в памяти отсутствует. Когда возникает
прерывание, строка вводится в оперативную память из на место
другой строки.
Если все строки находятся в оперативной памяти, то массив
требует больше места, поскольку необходимо место и для вектора
указателей.
Когда известно, что матрицы разреженные ( большинство
элементов - нули ), используются другие методы. Может быть
применена схема хеш-адресации, которая базируется на значениях i
и j элемента массива А[i, j] и ссылается по хеш-адресу на
относительно короткую таблицу элементов массива. В таблице
хранятся только ненулевые элементы матрицы.
Многомерные массивы
Мы рассмотрим размещение в памяти и обращение к
многомерным массивам, описанным, следующим образом:
ARRAY A[L1:U1, L2:U2, ..., Ln:Un]
Метод заключается в обобщении первого метода, предложенного для
двумерного случая; он также применим и для одномерного массива.
Подмассив A[i,*, ..., *] содержит последовательность
A[L1,*, ..., *], A[L1+1,*, ..., *], и т.д. до A[U1,*, ..., *].
Внутри подмассива A[i,*, ..., *] находятся подмассивы
A[i,L2,*, ..., *], A[i,L2+1,*, ..., *], ... и A[i,U2,*, ..., *].
Это повторяется для каждого измерения. Так, если мы продвигаемся
в порядке возрастания по элементам массива, быстрее изменяются
последние индексы:
????????????????????????????????????????? ??????????? ?????????
? подмассив A[L1] ? ? A[L1+1] ? ? A[U1] ?
? ?????????? ???????????? ??????????? ? ? ? ?
? ?A[L1,L2]? ?A[L1,L2+1]? ... ?A[L1,U2]?? ? ? ... ? ?
? ?????????? ???????????? ??????????? ? ? ? ?
????????????????????????????????????????? ??????????? ?????????
Вопрос заключается в том, как обратиться к элементу
A[i,j,k, ..., l,m]. Обозначим
d1 = U1-L1+1, d2 = U2-L2+1, ..., dn = Un-Ln+1.
То есть d1 есть число различных значений индексов в i-том
измерении. Следуя логике двумерного случая, мы находим начало
подмассива A[i,*, ..., *]
BASELOC + (i-L1)*d2*d3*...*dn
Где BASELOC - адрес первого элемента A[L1,L2,...,Ln], а
d2*d3*...*dn - размер каждого подмассива A[i,*,...,*]. Начало
подмассива A[i,j,*,...,*] находится затем добавлением
(j-L2)*d3*...*dn к полученному значению.
Действуя дальше таким же образом, мы окончательно получим:
BASELOC + (i-L1)*d2*d3*...*dn + (j-L2)*d3*...*dn
+ (k-L3)*d4*...*dn + ... + (i - Ln-1)*dn + m - Ln
Выполняя умножения, получаем CONST_PART + VAR_PART, где
CONST_PART = BASELOC - (