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

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

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

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

· формальные аргументы процедуры;

· локальные данные (переменные и константы) данной процедуры.

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

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

· статическая организация;

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

· стековая организация.

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

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

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

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

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

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

· заполнить значения параметров процедуры и адрес возврата;

· запомнить состояние регистра адресации в точке вызова;

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

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

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

· выбрать из области памяти процедуры адрес возврата (сразу за точкой вызо­ва) и передать туда управление;

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

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

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

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

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

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

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

· поместить в стек все параметры процедуры;

· запомнить в стеке адрес возврата и передать управление вызываемой проце­дуре;

· запомнить в стеке значение базового регистра;

· запомнить состояние регистра стека в базовом регистре;

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

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

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

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

· выбрать из стека значение базового регистра;

· выбрать из стека адрес возврата;

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

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

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

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

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