Организация памяти

С точки зрения разработчика компилятора, по крайней мере для большинства применений, скомпилированная программа работает в собственном адресном пространстве. Это адресное пространство, строго говоря, является логическим, а не физическим, т.е. не обязательно 1:1 соответствует физической памяти. Управление адресным пространством разделяется между компилятором, ОС и целевой машиной. Обычно, задачей сопоставления логических и физических адресов занимается ОС, скорее всего – с использованием средств, встроенных в исполнительное устройство.

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

Количество памяти, необходимое для размещения объекта, определяется его типом.

На схему размещения объектов в памяти могут оказывать существенное влияние ограничения целевой машины. Так, например, многие архитектуры требуют выравнивания: размещения в адресах, кратных какой-то константе, например 4. Тогда, хотя для хранения массива размером 10 байт, достаточно 10 байт, компилятор может выделить для него 12 байт, оставляя 2 байта неиспользуемыми, чтобы удовлетворить требованиям выравнивания.

Размер целевого кода однозначно определяется на этапе компиляции, поэтому он может быть размещён в статической области памяти, обычно близко к началу логического адресного пространства. Так же в статической области памяти могут быть размещены какие-то данные, размер которых известен на момент компиляции. Это могут быть глобальные переменные или константы, а также информация сгенерированная компилятором.

Стек и куча часто располагаются по разные стороны оставшегося свободного адресного пространства для максимально эффективного использования адресов. Размеры кучи и часто стека могут изменяться при необходимости в процессе работы программы, при этом они “растут” навстречу друг другу.

Мы называем решение о выделении памяти “статическим”, если оно может быть принято в процессе компиляции. В противном случае, мы называем его “динамическим”.

Большинство компиляторов для динамического выделения памяти используют некоторую комбинацию двух стратегий:

1. Выделение в стеке.
2. Выделение в куче.

Обычно, локальные данные процедуры размещаются в стеке, как и вспомогательная информация, сопутствующая вызову процедуры (называемая запись активации). Данные, время жизни которых не ограничено одной процедурой, обычно хранятся в куче.

Выделение памяти в стеке

Выделение памяти в стеке позволяет эффективно переиспользовать память для хранения локальных переменных не перекрывающихся по времени процедур. Кроме того, использование стека позволяет компилировать код процедур таким образом, чтобы относительные адреса её нелокальных переменных не зависели от последовательности вызовов.

Записи активации

Говоря о выделении памяти на стеке, вызов процедуры принято называть активацией, а процедуры, которые в настоящий момент выполняются – активными.

Вызовы процедур и возвраты из них обычно управляются стеком, именуемым стеком управления. Каждая активная в настоящий момент процедура имеет запись активации на стеке. Записи активации также иногда называются кадрами или фреймами.

Всю последовательность активаций, которые происходят при выполнении программы, можно представить в виде дерева активации. Корнем дерева является процедура, являющаяся главной точкой входа в программу (часто main), дочерними элементами – вызовы процедур, происходящими внутри тела “родительской” процедуры. В каждый момент времени, на стеке размещены записи активации, соответствующие пути на дереве активации от корня до текущей активации. Запись последней по времени активации находится всегда на вершине стека.

Содержимое записи активации будет варьироваться в зависимости от языка программирования, но вот (не исчерпывающий) список данных, которые могут находиться в записи активации:

1. Область памяти для временных значений, которые не удаётся разместить в регистрах
2. Локальные данные процедуры
3. Информация о состоянии машины перед вызовом процедуры. Обычно включает адрес возврата и содержимое регистров, которые используются в целевом коде данной процедуры и должны быть восстановлены при выходе.
4. Связь доступа – служебная информация, необходимая для доступа к нелокальным данным.
5. Связь управления – указатель на запись активации вызывающей процедуры.
6. Область памяти для возвращаемого значения (часто для большей эффективности значение возвращается в регистре)
7. Параметры вызова процедуры (тоже для часто передаются в регистрах)

Последовательности вызова и возврата

Вызовы процедур реализуются с помощью последовательности вызова – кода, которые выделяет память в стеке для записи активации и вносит в неё информацию. Последовательность возврата – это обратная операция, восстанавливающая состояние машины при выходе из процедуры, чтобы вызывающий код мог продолжить работу.

Последовательности вызова обычно разделяются между вызывающей и вызываемой процедурами. В общем случае, максимальный объём этого кода предпочтительно помещать в начале вызываемой процедуры (этот код иногда называется пролог), поскольку тогда его достаточно сгенерировать один раз, в то время как если этот код размещать в месте вызова, его надо сгенерировать столько раз, сколько раз осуществляется вызов. Аналогичные соображения действуют и касательно последовательности возврата (этот код иногда называется эпилог).

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

1. Параметры вызываемой процедуры располагаются в начале записи активации. Смысл в том, чтобы эту часть записи активации могла сконструировать вызывающая процедура, даже если у неё нет информации для построения оставшейся части.
2. Элементы фиксированного размера помещаются посередине. Обычно это связь управления, связь доступа и состояние машины.
3. Элементы, размер которых может быть заранее неизвестен, помещаются в конец записи активации. Например, это могут быть (локальные) массивы, длина которых определяется во время выполнения программы.

Доступ к нелокальным данным

Рассмотрим ситуацию, когда процедура обращается к данным, не принадлежащим ей.

Для языков, не допускающих вложенные процедуры (например, C), доступ к нелокальным переменным осуществляется достаточно просто: переменные либо глобальные, и тогда память для них выделена статически, и адреса известны на момент компиляции, либо это локальные к текущей активации переменные, и они расположены в текущей записи активации.

Ситуация существенно усложняется, если язык программирования разрешает вложенные объявления процедур, такие, что переменные, локальные для внешней процедуры, должны быть доступны и во внутренней.

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

Если в исходном тексте программы процедура P непосредственно вложена в процедуру Q, то связь доступа каждой активации P указывает на последнюю активацию Q. Связи доступа таким образом образуют цепочку записей активации, в которых расположены все данные, доступные процедуре P.

Введём понятие глубины вложенности. Для процедур, не вложенных ни в какую другую, глубина вложенности – 0. Для процедур, определённых непосредственно внутри процедуры с глубиной вложенности \(n\), глубина вложенности будет \(n+1\).

Если процедура p с глубиной вложенности \(n_p\) пытается получить доступ к данным, локальным к процедуре q, имеющей вложенность \(n_q\), то понятно, что \(n_q \le n_p\), причём равенство возможно только если p и q – это одна и та же процедура. Тогда код в процедуре p должен найти последнюю запись активации для q, которая может быть найдена через \(n_p-n_q\) переходов по связям доступа. Соответствующая локальная переменная затем может быть найдена по фиксированному смещению от записи активации для q.

Если язык допускает передачу процедур в качестве параметров, это ещё немного усложняет ситуацию: если процедура передана параметром, то при её вызове может отсутствовать информация, что это за процедура и где она определена, и соответственно невозможно становится определить связь доступа. Решение для этой трудности достаточно простое – при передачи процедуры в качестве параметра, вместе с ней передавать и связь доступа.

Отдельно отметим, что при большой вложенности процедур может потребоваться многократный переход по связям доступа, что может негативно сказаться на производительности. Можно обменять использование памяти на производительность, и вместо одной связи доступа хранить в каждой записи активации массив связей доступа, индексированный глубиной вложенности. Такие массивы называются дисплеями. Тогда, правда, при каждом вызове процедуры придётся копировать дисплей.

Управление кучей

Мы рассмотрим подсистему, отвечающую за выделение и освобождение памяти – диспетчер памяти. Эта подсистема является своего рода интерфейсом между прикладной частью программы и операционной системой.

При выделении памяти, диспетчер памяти ищет в куче свободный блок нужного размера. Если такой блок не найден, то производится попытка увеличить кучу путём запроса памяти у операционной системы.

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

Хороший диспетчер памяти должен:

• Эффективно использовать память. Минимизировать общий размер кучи, требующейся программе. Пространственная эффективность в первую очередь достигается путём уменьшения фрагментации.
• Так размещать объекты в памяти, чтобы программа выполнялась максимально быстро. Это в основном достигается специальным размещением объектов в памяти (так, чтобы максимизировать локальность данных)
• Иметь низкие накладные расходы. Следует отметить, что стоимость выделения доминирует при выделении маленьких участков памяти; для больших участков, как правило, выделение памяти перемежается с долгими вычислениями (использующими эту память).

Снижение фрагментации кучи

В начале работы программы, куча представляет собой один непрерывный блок свободной памяти. Когда программа запрашивает и освобождает память, весь объём кучи разбивается на свободные и используемые блоки памяти, причём свободные блоки не обязательно образуют непрерывную область.

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

При запросах на освобождение памяти, блоки помечаются как свободные. Смежные свободные блоки должны сливаться, поскольку иначе их размер будет монотонно уменьшаться.

Если диспетчер памяти недостаточно “умный”, свободная память может стать сильно фрагментированной, т.е. состоящей из большого количества несмежных мелких свободных блоков. В таком случае может оказаться, что для очередного запроса на выделение памяти, несмотря на большое количество свободной, подходящего блока нет.

Снижения фрагментации можно достичь, управляя размещением объектов в куче. Эмпирически обнаружено, что хорошая стратегия минимизации фрагментации в реальных программах – выделение запрошенной памяти в наименьшем из подходящих блоков. Такая стратегия называется стратегией наилучшего подходящего (best-fit). Стратегия первого подходящего (first-fit), выделяющая память в первом найденном достаточно большом блоке, проигрывает такому подходу в смысле фрагментации памяти, но может быть заметно быстрее.

Более эффективная реализация стратегии лучшего подходящего разделяет блоки свободной памяти на “корзины” в соответствии с их размерами. Обычно идея в том, чтобы иметь много блоков в корзине с малым размером, и меньше – с большим. Так, например, диспетчер памяти dlmalloc (написанный Дагом Леа), использовавшийся раньше в компиляторах gcc, выравнивает блоки на 8-байтовые границы. Имеется по одной корзине для блоков каждого кратного 8 байтам размера от 16 до 512 байт. Корзины размеров, больших 512 байт, имеют логарифмические промежутки, т.е. минимальный размер каждой корзины вдвое больше предыдущего, а внутри корзины блоки упорядочены в соответствии с их размерами. Один блок свободной памяти имеет изменяемый размер и считается самым большим. Такая схема позволяет достаточно быстро находить блоки нужного размера.

“Корзины” по сути представляют из себя списки указателей на начальные адреса блоков, и хранятся в массиве.

Стратегия лучшего подходящего может негативно сказываться на локальности данных программы. Поэтому часто её модифицируют таким образом, чтобы для идущих подряд запросов на выделение памяти, память выделялась из смежных блоков, если это возможно. Эта стратегия называется “стратегия следующего подходящего” (next-fit)

Управление свободной памятью

При освобождении памяти, смежные свободные блоки может понадобиться объединить.

При наличии “корзин” для блоков фиксированного размера, объединение может не иметь смысла. Тогда блоки в корзине просто помечаются как занятые или свободные в битовой карте, где соответствующий блоку бит показывает, занят блок или свободен. При нехватке свободных блоков при выделении памяти, можно запросить у системы новую страницу памяти и разбить её на блоки соответствующего размера, и расширить битовую карту.

Если же слияние блоков необходимо, то можно использовать комбинацию двух подходов:

1. Дескрипторы границ. С обоих концов блока хранится информация, указывающая, свободен блок или занят, а также его размер.

2. Двусвязный список свободных блоков. Свободные блоки связываются в двусвязный список. Указатели этого списка хранятся в самих блоках. Порядок блоков в списке может быть произвольный, но вообще говоря список может быть и отсортирован, например, по размеру, чтобы облегчить поиск подходящих блоков.

Тогда каждый раз при освобождении памяти проверяются дескрипторы границ смежных блоков. Если один или оба из них свободны – они объединяются. По сути объединение сводится к удалению всех, кроме первого, блоков из списка свободных блоков и увеличению длины блока в дескрипторах границ.