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

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 │ ... │ Компонента 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 для любого формального параметра Х,

объявленного параметром RESULT, справедливо следующее:

1. Для параметра Х отводится ячейка в области данных

процедуры. Эта ячейка используется в процедуре как локализованная

ячейка для переменной Х.

2. Как и в случае параметра VALUE, при рызоре при вызове

процедуры вычисляется и передается адрес фактического параметра.

3. Когда выполнение процедуры заканчивается, полученное

значение Х запоминается по адресу, описанному в п.2.

Другими словами, параметр RESULT есть переменная,

локализованная в процедуре, значение которой при выходе

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

должен быть конечно, переменной ). Понятие RESULT было

предназначено для того, чтобы дополнить в АЛГОЛе вызов по имени

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

обладает большими возможностями, чем это необходимо в

большинстве случаев.

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

В развитых языках следующие фактические параметры

обрабатываются по-разному:

1) константы;

2) выражения, которые не являются переменными;

З) переменные, чьи характеристики отличаются от характеристик

указанных для соответствующих формальных параметров.

Для такого фактического параметра в вызывающей процедуре

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

и запоминается во временной переменпой, и адрес этой переменной

передается в списке параметров. Такая переменная называется

фиктивным аргументом.

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

Согласно сообщению о языке АЛГОЛ, использование вызова

параметра по имени означает буквальную замену имени формального

параметра фактическим параметром.

Получить эффективную реализацию с помощью такой текстовой

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

эквивалентный способ.

Обычный способ реализации вызова параметров по имени

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

объектном коде для каждого такого параметра. Для такой программы

был введен термин "санк" ( thunk ). Когда происходит вызов санка,

он вычисляет значение фактического параметра ( если этот параметр

не переменная ) и передает адрес этого значения. В теле процедуры

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

после чего для обращения к нужному значению используется

переданный санком адрес.

Различие между вызовом по ссылке и вызовом по имени

заключается в следующем: адрес фактического параметра,

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

фактическим входом в процедуру, в то время как для вызова по

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

обращение к формальному параметру.

Имя массива в качестве фактического параметра

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

быть массивами. Процедуре передается адрес первого элемента

массива ( для языков, которые не требуют информационных

векторов ) или адрес информационного вектора, и этот адрес

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

Имя процедуры в качестве фактического параметра

Передаваемый адрес - это адрес первой команды процедуры,

которая встретилась в качестве фактического параметра. Если это

имя само является формальным параметром, то адрес был передан

вызывающей процедуре, когда она вызывалась.

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

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

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

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

для последующего использования.

Существуют два основных метода общего распределения памяти.

В обоих методах вызывается некоторая программа GETAREA(ADDRESS,

SIZE) для того, чтобы выделить область из SIZE ячеек; программа

записывает в ячейку ADDRESS, адрес этой области. В первом методе

память должна освобождаться "явно" посредством вызова программы

FREEAREA(ADDRESS,SIZE). Во втором методе память "явно" не

освобождается. Вместо этого в тех случаях, когда GETAREA не

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

FREEGARBAGE для того, чтобы найти те области во внутренней

памяти, которые не используются программой, и вернуть их системе.

Кроме того она может уплотнить используемые области - сдвинуть

их вместе, чтобы все свободные ячейки были в одном блоке.

Опишем один из способов реализации первого метода.

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

Распределение памяти происходит следующим образом. Когда

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

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

может несколько раз вызываться GETAREA. Каждый раз она выделяет

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

блок приобретает следующий вид:

┌────────┬────────┬─────────┬────────┬──────────────────────┐

│ Занято │ Занято │ ... │ Занято │ Свободно │

└────────┴────────┴─────────┴────────┴──────────────────────┘

Заметим, что размеры занятых областей могут быть

разными. В некоторый момент будет вызвана FREEAREA, чтобы

освободить одну из использованных областей, вообще говоря, не

последнюю. После нескольких вызовов GETAREA и FREEAREA блок

может выглядеть так:

┌────────┬────────┬──────────┬─────────┬────────┬──────────┐

│ Занято │ Занято │ Свободно │ ... │ Занято │ Свободно │

└────────┴────────┴──────────┴─────────┴────────┴──────────┘

где по-прежнему размеры областей различны. Система должна

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

могли быть снова использованы. Более того, смежные свободные

области следует сливать в одну свободную область так, чтобы

память не оказалась разбитой на области, слишком малые для

использования.

Описываемый нами метод помеченных границ принадлежит

Кнуту. Метод требует резервирования для системных нужд 2-х

ячеек на границах каждой области ( одной в начале и одной в

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

применяется этот метод, требуются довольно большие области,

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

Преимущество этого метода в том, что необходимо по существу

фиксированное время, чтобы освободить область и объединить ее

со смежными свободными областями, если это возможно. В других

методах для этой цели требуется просмотр некоторого списка.

Ниже приводится формат каждой занятой и свободной области.

Первое слово содержит поле TAG, которое указывает, свободна ли

область или нет; в поле SIZE содержится число слов области.

Свободные области связываются вместе в двусвязанный список. Поле

FLINK (ссылка вперед) указывает на следующую область списка, в

то время как поле BLINK (ссылка назад) указывает на предыдущую

область.

┌─────┬──────┬───────┬───────┐ первое ┌─────┬──────┬───────────────┐

│ TAG │ SIZE │ BLINK │ FLINK │ слово │ TAG │ SIZE │ │

├─────┴──────┴───────┴───────┤ ├─────┴──────┴───────────────┤

│ │ SIZE-2 │ │

│ │ слов │ │

│ │ │ │

├─────┬──────┬───────────────┤ послед- ├─────┬──────────────────────┤

│ TAG │ SIZE │ │ нее │ TAG │ │

└─────┴──────┴───────────────┘ слово └─────┴──────────────────────┘

Свободная область Резервированная область

Кроме того, существует одна переменная FREE следующего вида:

TAG SIZE BLINK FLINK

┌───┬──────┬──────────────────┬──────────────────┐

FREE │ + │ 0 │ на последнюю │ на первую │

│ │ │ область в списке │ область в списке │

└───┴──────┴──────────────────┴──────────────────┘

Поле BLINK первой области в списке указывает на ячейку FREE, так

же, как и поле FLINK последней области. Наконец, мы предположим,

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

слово, а за блоком следует слово, содержащее '+' в поле TAG для

указания о том, что "окружающие" области заняты. Такое соглашение

упрощает процесс объединения смежных областей.

Алгоритм работы программы GETAREA основан на методе "первый