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

    │ Компонента 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 основан на методе "первый

подходящий";    просматривается   список   свободпых  областей  и

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

Несморя на то, что выбор "наиболее подходящей" области кажется на

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

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

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

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

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

цель  которой  -  найти  неиспользуемые  области  и  занести их в

некоторый список свободных областей. Для этого FREEGARBAGE должна

быть в состоянии определить следующее:

     1) расположение в памяти каждого описанного указателя;

     2) точные  сведения  о величине, на которую ссылается каждый

указатель,  -  длина  величины  и  содержит  ли  она какие-нибудь

указатели;

     3) для  каждого  указателя,  содержащегося  в  величине,  на

которую   ссылается  другой  указатель,  длину  указателя  и  его

расположение в величине.

     Как   легко  видеть,  это  довольно  сильное  требование,  и

поэтому, используя указатели, нужно придерживаться строгих правил

Поэтому  обычно  "сбор  мусора" используется в тех случаях, когда

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

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

величин  невелико.  Хорошим примером такой системы является LISP.

Другой пример - это система обработки строк, преимущество которой

состоитв том, что величины, па которые ссылаются указатели строк,

являются  только  строками  литер,  так  что величина, на которую

ссылается указатель, никогда не содержит других указателей.

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

какие области на любом этапе свободны.

     Обычно  сбор  мусора  проходит  в  две фазы. Во время первой

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

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

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

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

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

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

Однако  при  этом   требуется   специальная  таблица   для  битов

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

объем свободной памяти очень мал!

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

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

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

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

сформировать биты маркировки.

     Иногда   используется   третья    фаза,    которая  собирает

свободные  области   вместе,   так   чтобы  они образовывали один

большой  блок.   Для  этого  требуется,   чтобы  программа  сбора

мусора изменяла значения  указателей при перемещении данных.

     Для   рассмотрения   существующих  алгоритмов  сбора  мусора

отсылаем читателя к гл. 2 книги Кнута "Искусство программирования

на ЭВМ " т.1.

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

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

памяти;   большие   блоки   внутренней   памяти   резервируются и

освобождаются   согласно   одному   методу,   в   то   время  как

каждый   большой   блок   может   быть   подразделен   с  помощью

другого  метода.

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

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

     Одной   из   существенных  причин,  приводящих  к  появлению

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

предопределенных  типов  данных.  Их  ограниченность  в сложности

адаптации под конкретную задачу.

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

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

представление  объекта  этого  типа,  так  и  операции  над  этим

объектом.

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

объектно-ориентированные   языки.  Базовым  понятием  объектно  -

ориентированного языка является класс.

     Класс   является   типом,   созданным  программистом. Внешне

описание простейшего класса схоже со структурой данных. В отличие

от  структур  рассматриваемых  ранее,  в объектно-ориентированном

языке   класс   может  включать  в  себя  не  только  переменные,

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

над   этим   типом   данных.  И  данные,  и функции, составляющие

класс,  называются  членами  класса.  Среди функций-членов класса

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

инициализацией   объектов  такого  типа - конструкторы и функции,

управляющие уничтожением обьектов - деструкторы. Они и занимаются

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

может   быть   выполнена   инициализация  этой  памяти  заданными

значениями.

     Мы будем рассматривать новые объекты в аспекте распределения

памяти   под   них.  Идеология  и механизмы использования классов

исчерпывающе описаны, например, в литературе [3], [4], [5].

     Итак,  когда  в  программе  объявляется  объект  какого-либо

класса,  или  инициализируется  указатель  на  объект этого типа,

вызывается    конструктор    класса.    Его    задачей   является

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

данные-члены  класса.  Коды  функций-членов  хранятся отдельно от

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

не  присутствуют  в  реальном  объекте;  при этом хранится только

одна  копия  каждой функции, хотя объектов в программе может быть

несколько.   Но,   с   другой   стороны,  поскольку  эти  функции

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

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

того,  они  вызываются  только для данного конкретного объекта, и

выполняемые  ими  действия  никак  не  могут  влиять на состояние

других объектов этого типа.

     Память    для    данных-членов   распределяется   аналогично

методам,  котрые  описаны  выше для структур ( см. Структуры PL/1

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

     После  того,  как  объект  выполнил  свою миссию в программе

он    уничтожается   деструктором   класса:   память   занимаемая

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

важно  заметить, что если объект содержал какие-либо указатели на

занятую    память -  эта   память   не   освобождается.   Поэтому

ответственность    за    возможное  таким  образом  возникновение

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

                        СПИСОК ЛИТЕРАТУРЫ

     1.  ГРИС   Д.  Конструирование  компиляторов  для  цифровых

         вычислительных  машин. -М.: МИР, 1975.

     2.  КАСЬЯНОВ   В.Н.,   ПОТТОСИН   И.В.   Методы  построения

         трансляторов. -Н.: НАУКА, 1986.

     3.  РОМАНОВ  В.Ю.  Программирование  на  языке  С++.  -М.:

         КОМПЬЮТЕР, 1993.

     4.  ЦИМБАЛ А.А., МАЙОРОВ А.Г., КОЗОДАЕВ М.А. Turbo C++: язык

         и его применение. -М.: Джен Ай Лтд., 1993.

     5.  ЭЛЛИС  М., СТРОУСТРУП Б. Справочное руководство по языку

         программирования С++ с комментариями. -М.: МИР, 1992.