Реферат: Распределение памяти
│ подмассив 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 - ((...(L1*d2+L2)*d3+L3)*d4+...+Ln-1)*dn+Ln)
VAR_PART = (...((i*d2)+j)*d3+...+1)*dn + m
Значение CONST_PART необходимо вычислить только 1 раз и
запомнить, т.к. оно зависит лишь от нижних и верхних границ
индексов и местоположения массива в памяти. VAR_PART зависит от
значений индексов i,j,...,m и от размеров измерений d2,d3,...,
dn. Вычисление VAR_PART можно представить в более наглядном виде:
VAR_PART = первый индекс (i)
VAR_PART = VAR_PART*d2 + второй индекс (j)
VAR_PART = VAR_PART*d3 + третий индекс (k)
.....
VAR_PART = VAR_PART*dn + n-й индекс (m)
Информационные векторы
В некоторых языках верхняя и нижняя границы массивов известны
во время трансляции, поэтому компилятор может выделить память для
массивов и сформировать команды, ссылающиеся на элементы массива,
┌────┬────┬────┐
│ L1 │ U1 │ d1 │
├────┼────┼────┤
│ L2 │ U2 │ d2 │
│ . │ . │ . │ Описание массива
│ . │ . │ . │ A[L1:U1,...,Ln:Un]
│ . │ . │ . │
│ Ln │ Un │ dn │
├────┼────┴────┤
│ n │CONSTPART│
├────┴─────────┤
│ BASELOC │
└──────────────┘
Рис. . Информационный вектор для массива
используя верхние и нижние границы и постоянные значения d1,d2,..
.,dn. В других языках это невозможно т.к. границы могут
вычисляться во время счета. Поэтому нужен описатель для массива,
содержащий необходимую информацию. Этот описатель для массива
называется допвектор ( dope vector ) или информационный вектор.
Информационный вектор имеет фиксированный размер, который
известен при компиляции, следовательно, память для него может
быть отведена во время компиляции в области данных, с которой
ассоциируется массив. Память для самого массива не может быть
отведена до тех пор, пока во время счета не выполнится вход в
блок, и котором описан массив. При входе в блок вычисляются
границы массива и производится обращение к программе
распределения памяти для массивов. Здесь же вносится в
информационный вектор необходимая информация.
Какая информация заносится в информационный вектор? Для
предложенной выше n-мерной схемы нам как минимум нужны d2,...dn
и CONST_PART. Если перед обращением к массиву нужно проверять
правильность задания индексов, то следует также занести в
информационный вектор значения верхних и нижних границ.
5. Память для структур
Существует несколько альтернатив для определения новых
типов данных как структур, составленных из типов данных,
определенных ранее. Величины такого типа мы называем
структурными величинами. Существуют различные подходы к
реализации этих конструкций. Отличия обычно касаются следующих
вопросов:
Как выделять память для структурных величин?
Как строить структурные величины?
Как ссылаться на компоненту структурной величины?
Как освобождать память?
Записи по Хоору
Определение нового типа данных имеет вид
RECORD <идентификатор> ( <компонента>,
<компонента>, . . . , <компонента> )
где каждая компонента имеет вид
<простой тип> <идентификатор>
Причем <простой тип> является одним из основных типов языка -
REAL, INTEGER, POINTER и т.д. Здесь во время компиляции известны
все характеристики всех компонент, включая тип данных, на которые
могут ссылаться указатели. Во время счета не нужны описатели ни
для самой структуры, ни для ее компонент, причем может быть
сгенерирована эффективная программа.
Любая структурная величина с n компонентами может храниться в
памяти в виде:
┌──────────────┬──────────────┬─────────┬──────────────┐
│ Компонента 1 │ Компонента 2 │ ... │ Компонента n │
└──────────────┴──────────────┴─────────┴──────────────┘
Поскольку при компиляции известны все характеристики, то
известен также объем памяти, необходимый для каждой компоненты,
и, следовательно, компилятор знает смещение каждой компоненты
относительно начала структурной величины. Для упрощения сбора
мусора лучше всего присвоить номер каждому типу данных ( включая
типы, определенные программистом) и иметь описатель для каждого
указателя. Описатель будет содержать номер, описывающий тип
величины, на которую в данный момент ссылается указатель.
Память для указателей и их описателей может быть выделена
компилятором в области данных, с которой они связаны; это не
трудно, так как они имеют фиксированную длину. Для хранения
текущих значений структурных величин может быть использована
отдельная статическая область данных и специальная программа для
выделения памяти в этой области. В рассматриваемых языках нет
явного оператора для освобождения памяти, так что, когда память
исчерпана, система обращается к программе "сбора мусора".
Заметим, что для того, чтобы иметь возможность обнаружить мусор,
нужно знать, где расположены все указатели, включая те, которые
являются компонентами структурных величин.
Структуры PL/1
Более сложную конструкцию имеют структуры, в которых
компоненты могут сами иметь подкомпоненты. Пример таких
структур - структуры языка PL/1. Такая структура есть дерево,
узлы которого связаны с именами компонент, а концевые узлы
имеют значения данных.
Если бы возможность иметь подкомпоненты была бы
единственным различием между записями по Хоору и структурами
PL/1 не было бы существенной разницы во время выполнения
программы; можно было бы разместить все компоненты и
подкомпоненты так, чтобы каждая имела фиксированное смещение
относительно начала структуры и это смещение было бы известно во
время компиляции. Однако в языке PL/1 существует еще два
расширения. С целью экономии памяти атрибут CELL для компоненты
требует, чтобы все ее подкомпоненты непременно занимали одно и
тоже место в памяти. В любое заданное время только одна из
нескольких переменных может иметь значение. Присваивание значения
подкомпоненте приводит к тому, что подкомпонента, к которой
обращались ранее утрачивает свое значение.
Подобная возможность вызовет осложнения во время компиляции,
но в действительности не очень изменяет код готовой программы,
если только объектная программа не должна проверять при каждом
обращении к подкомпоненте, что значение подкомпоненты
действительно существует.
Для другого расширения требуются более сложные
административные функции во время выполнения программы. В PL/1
корневой узел структурного дерева или любая из подкомпонент могут
быть снабжены размерностями.
Так как выражения, которые определяют границы изменения
индексов, должны быть вычислены при выполнении программы, для
них, как и в случае массивов, следует употреблятъ опители, или
информационные векторы. Т.е. нам необходимы информационные
векторы для всех компонент имеющих размерность большую единицы.
Структуры данных по Стендишу
Следующий шаг в развитии - структуры данных, которые не
могут быть реализованы эффективно, но которые богаче и мощнее.
Структуры данных предложенные Стендишом изменяются во время
работы программы. Динамически могут изменяться не только
размерности компонент, но и число компопонент и их типы.
Обычно во время компиляции ничего не известно, а все делается
во время выполнения программы на основе описателей, которые
сами строятся в это же время.
Во время выполнения программы необходимо хранить описатель
для каждой структурной величины. Действительно, этот описатель
аналогичен набору элементов таблицы символов, используемому
компилятором при компиляции, скажем, структур 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 для любого формального параметра Х,
