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

Дисплей памяти процедуры (функции) – это область данных, доступных для обработки в этой процедуре (функции).

Как правило, дисплей памяти процедуры включает следующие составляющие:

глобальные данные (переменные и константы) всей программы;
формальные аргументы процедуры;
локальные данные (переменные и константы) данной процедуры.

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

Сложнее с локальными параметрами и переменными процедуры. Они относятся к локальной памяти процедуры и потому должны быть как-то связаны с нею. Существует несколько вариантов связывания локальных переменных и параметров с кодом соответствующей процедуры или функции. Им соответствуют варианты организации дисплея памяти процедуры:

статическая организация;
динамическая организация;
стековая организация.

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

Схема статической организации памяти проиллюстрирована на рис. 10.

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

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

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

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

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

При возврате из процедуры необходимо выполнить следующие действия:

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

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

Данная схема, хотя и допускает рекурсивные вызовы, не получила широкого распространения. Это вызвано целым рядом причин. Во-первых, она требует постоянного динамического перераспределения памяти – это достаточно сложная операция, которая замедляет выполнение вызовов. Во-вторых, такая схема предполагает достаточно сложную схему адресации локальных данных. Наконец, она требует хранения промежуточных данных непосредственно в исполняемом коде программы, что представляет определенную сложность.

В настоящее время эта схема не используется, поскольку уступает почти по всем показателям схеме стековой организации дисплея памяти.

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

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

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

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

При возврате из процедуры необходимо выполнить следующие действия:

выбрать из стека все локальные данные процедуры;
выбрать из стека значение базового регистра;
выбрать из стека адрес возврата;
передать управление по адресу возврата и выбрать из стека все параметры процедуры.

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

На рис. 11 показано, как изменяется содержание стека параметров при выполнении трех последовательных вызовов процедур: сначала процедуры А, затем процедуры В и снова процедуры А. При вызовах стек заполняется, а при возврате из кода процедур – освобождается в обратном порядке.

Из рис. 11 видно, что при рекурсивном вызове все локальные данные последовательно размещаются в стеке и при этом каждая процедура работает только со своими данными. Более того, такая схема легко обеспечивает поддержку вызовов вложенных процедур, которые допустимы, например, в языке Pascal.

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

Статьи к прочтению:

Лекция 29: Стековая память и аппаратный стек

Похожие статьи: