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

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

┌│

Введение

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 - ((...(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