Принципы распределения памяти

Распределение памяти – это процесс, который ставит в соответствие лексиче­ским единицам исходной программы адрес, размер и атрибуты области памяти, необходимой для этой лексической единицы. Область памяти – это блок ячеек памяти, выделяемый для данных, каким-то образом объединенных логически. Логика таких объединений задается семантикой исходного языка.

Распределение памяти работает с лексическими единицами языка – перемен­ными, константами, функциями и т. п. – и с информацией об этих единицах, полученной на этапах лексического и синтаксического анализа. Как правило, исходными данными для процесса распределения памяти в компиляторе служат таблица идентификаторов, построенная лексическим анализатором, и деклара­тивная часть программы (так называемая “область описаний”), полученная в ре­зультате синтаксического анализа. Не во всех языках программирования декла­ративная часть программы присутствует явно, некоторые языки предусматривают дополнительные семантические правила для описания констант и переменных; кроме того, перед распределением памяти надо выполнить идентификацию лексических единиц языка. Поэтому распределение памяти выполняется уже после семантического анализа текста исходной программы.

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

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

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

Перечислим правила распределения памяти под основные виды структур данных:

· для массивов – произведение числа элементов в массиве на размер памяти для одного элемента (то же правило применимо и для строк, но во многих языках строки содержат еще и дополнительную служебную информацию фик­сированного объема);

· для структур (записей с именованными полями) – сумма размеров памяти по всем полям структуры;

· для объединений (союзов, общих областей, записей с вариантами) – размер максимального поля в объединении;

· для реализации объектов (классов) – размер памяти для структуры с такими же именованными полями плюс память под служебную информацию объект­но-ориентированного языка (как правило, фиксированного объема).

Для более сложных структур данных входного языка объем памяти, отводимой под эти структуры данных, вычисляется рекурсивно. Например, если имеется массив структур, то при вычислении объема отводимой под этот массив памяти для вычисления объема памяти, необходимой для одного элемента массива, бу­дет вызвана процедура вычисления памяти структуры. Такой подход определе­ния объема занимаемой памяти очень удобен, если декларативная часть языка представлена в виде дерева типов. Тогда для вычисления объема памяти, зани­маемой типом из каждой вершины дерева, нужно вычислить объем памяти для всех потомков этой вершины, а потом применить формулу, связанную непосред­ственно с самой вершиной (этот механизм подобен механизму СУ-перевода, применяемому при генерации кода). Как раз такого типа древовидные конструк­ции строит синтаксический разбор для декларативной части языка.

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

Говоря об объеме памяти, занимаемой различными лексическими единицами и структурами данных языка, следует упомянуть еще один момент, связанный с выравниванием отводимых для различных лексических единиц границ облас­тей памяти. Архитектура многих современных вычислительных систем преду­сматривает, что обработка данных выполняется более эффективно, если адрес, по которому выбираются данные, кратен определенному числу байт (как прави­ло, это 2, 4, 8 или 16 байт). Современные компиляторы учитывают особенности вычислительных систем, на которые ориентирована результирующая программа. При распределении данных они могут размещать области памяти под лексиче­ские единицы наиболее оптимальным образом. Поскольку не всегда размер па­мяти, отводимой под лексическую единицу, кратен указанному числу байт, то в общем объеме памяти, отводимой под результирующую программу, могут появ­ляться неиспользуемые области.

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