7.6. Стековая архитектура

Стек — это структура данных, которая принимает и выдает данные в порядке LIFO — Last-In, First-Out (последним пришел, первым вышел). Конструкции LIFO существуют в реальном мире, например стопка тарелок в кафетерии или пачка газет в магазине. Стек может быть реализован с помощью массива или списка (см. рис. 7.5). Преимущество списка в том, что он не имеет границ, а его размер ограничен только общим объемом доступной памяти. Массивы же намного эффективнее и неявно используются при реализации языков про­граммирования.

Кроме массива (или списка) в состав стека входит еще один элемент — указатель вершины стека (top-of-stack pointer). Это индекс первой доступной пустой позиции в стеке. Вначале переменная top будет указывать на первую позицию в стеке. На стеке допустимы две операции — push (поместить в стек) и pop (извлечь из стека), push — это процедура, получающая элемент как па­раметр, который она помещает в вершину стека, увеличивая указатель вершины стека top. pop — это функция, которая возвращает верхний элемент стека, уменьшая top, чтобы указать, что эта позиция стала новой пустой пози­цией.

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

C

#define Stack_Size 100

int stack[Stack_Size];

int top = 0;

void push(int element)

{

if (top == Stack_Size) /* Переполнение стека, предпримите

что-нибудь! * I

else stack[top++] = element;

}

int pop(void)

{

if (top == 0) /* Выход за нижнюю границу стека,

предпримите то-нибудь! */

else return stack[--top];

}

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

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

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

Рассмотрим программу с локальными процедурами:

procedure Main is

G: Integer;

Ada

procedure Proc_1 is

L1: Integer;

begin ... end Proc_1 ;

procedure Proc_2 is

L2: Integer;

begin... end Proc_2;

begin

Proc_1;

Proc_2;

end Main;

Когда начинает выполняться Main, должна быть выделена память для G. Ког­да вызывается Ргос_1, должна быть выделена дополнительная память для L1 без освобождения памяти для G (см. рис. 7.6а). Память для L1 освобождается перед выделением памяти для L2, так как Ргос_1 завершается до вызова Ргос_2 (см. рис. 7.66). Вообще, независимо оттого, каким образом процедуры вызывают друг друга, первый элемент памяти, который освобождается, явля­ется последним занятым элементом, поэтому память для переменных и пара­метров может отводиться в стеке.

Рассмотрим теперь вложенные процедуры:

procedure Main is

G: Integer;

Ada

procedure Proc_1 (P1: Integer) is

L1: Integer;

procedure Proc_2(P2: Integer) is

L2: Integer;

begin

L2 := L1 + G + P2;

end Proc_2;

begin -- Proc_1

Proc_2(P1);

end Proc_1;

begin -- Main

Proc_1 (G);

end Main;

Ргос_2 может вызываться только из Ргос_1. Это означает, что Ргос_1 еще не завершилась, ее память не освобождена, и место, выделенное для L1, должно все еще оставаться занятым (см. рис. 7.7). Конечно, Ргос_2 завершается рань­ше Ргос_1, которая в свою очередь завершается раньше Main, поэтому память может быть освобождена с помощью операции pop.

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

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

1. В стек помещаются фактические параметры. К ним можно обращаться по смещению от начала записи активации.

2. В стек помещается адрес возврата RA (return address). Адрес возврата — это адрес оператора, следующего за вызовом процедуры.

3. Индекс вершины стека увеличивается на общий объем памяти, требуе­мой для хранения локальных переменных.

4. Выполняется переход к коду процедуры.

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

1. Индекс вершины стека уменьшается на величину объема памяти, выде­ленной для локальных переменных.

2. Адрес возврата извлекается из стека и используется для восстановления указателя команд.

3. Индекс вершины стека уменьшается на величину объема памяти, выде­ленной для фактических параметров.

Хотя этот алгоритм может показаться сложным, на большинстве компью­теров он фактически может быть выполнен очень эффективно. Объем памя­ти для переменных, параметров и дополнительной информации, необхо­димой для организации вызова процедуры, известен на этапе компиляции, а описанная технология всего лишь требует изменения индекса стека на кон­станту,

Доступ к значениям в стеке

В классическом стеке единственно допустимые операции — это push и pop. «Рабочий» стек, который мы описали, — более сложная структура, потому что мы хотим иметь эффективный доступ не только к самому последнему значе­нию, помещенному в стек, но и ко всем локальным переменным и ко всем па­раметрам. В частности, необходимо иметь возможность обращаться к этим данным относительно индекса вершины стека:

C

stack[top -25];

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

Параметры

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

load R1 ,bottom_pointer Указатель дна

add R1 ,#offset-of-parameter + смещение

load R2,(R1) Загрузить значение, адрес которого

находится в R1

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

При использовании этого метода в языке С возникает проблема, связан­ная с тем, что С разрешает иметь в процедуре переменное число парамет­ров:

C

void proc(int num_args,...);

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

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

Обратите внимание, что иногда нельзя сохранить параметр непосредст­венно в стеке. Как вы помните, формальный параметр в языке Ada может иметь неограниченный тип массива, границы которого неизвестны во время компиляции:

Ada

procedure Proc(S: in String);

Таким образом, фактический параметр не может быть помещен непосредст­венно в стек. Вместо него в стек помещается дескриптор массива (dope vector) (см. рис. 5.4), который содержит указатель на массив.

Рекурсия

Архитектура стека непосредственно поддерживает рекурсию, поскольку каж­дый вызов процедуры автоматически размещает новую копию локальных пе­ременных и параметров. Например, при каждом рекурсивном вызове функ­ции факториала требуется одно слово памяти для параметра и одно слово па­мяти для адреса возврата. То, что издержки на рекурсию больше, чем на ите­рацию, связано с дополнительными командами, затрачиваемыми на вход в процедуру и выход из нее. Некоторые компиляторы пытаются выполнить оп­тимизацию, называемую оптимизацией хвостовой рекурсии (tail-recursion) или оптимизацией последнего вызова (last-call). Если единственный рекурсивный вызов в процедуре — последний оператор процедуры, то можно автома­тически перевести рекурсию в итерацию.

Размер стека

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

Однако при применении рекурсии размер стека во время выполнения тео­ретически неограничен:

C

i = get();

j = factorial(i);

В упражнениях приведена функция Акерманна, которая гарантированно пе­реполнит любой стек! Но на практике обычно нетрудно оценить размер сте­ка, даже когда используется рекурсия. Предположим, что размер записи ак­тивации приблизительно равен 10, а глубина рекурсии не больше несколь­ких сотен. Добавления к стеку лишних 10 Кбайт более чем достаточно.

Читатели, которые изучали структуры данных, знают, что рекурсией удобно пользоваться при работе с древовидными структурами в таких алго­ритмах, как быстрая сортировка и приоритетные очереди. Глубина рекур­сии в алгоритмах обработки древовидных структур данных — приблизи­тельно Iog₂ от размера структуры. Для реальных программ глубина рекур­сии не превышает 10 или 20, поэтому опасность переполнения стека очень невелика.

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