М. Бен-Ари - Языки программирования. Практический сравнительный анализ (2000) (1160781), страница 23

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

Текст из файла (страница 23)

G: Integer;

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. «Рабочий» стек, который мы описали, — более сложная структура, потому что мы хотим иметь эффективный доступ не только к самому последнему значе­нию, помещенному в стек, но и ко всем локальным переменным и ко всем па­раметрам. В частности, необходимо иметь возможность обращаться к этим данным относительно индекса вершины стека:

stack[top -25];

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

Параметры

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

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

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

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

находится в R1

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

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

void proc(int num_args,...);

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

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

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

procedure Proc(S: in String);

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

Рекурсия

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

Размер стека

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

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

i = get();

j = factorial(i);

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

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

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

7.7. Еще о стековой архитектуре

Доступ к переменным на промежуточных уровнях

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

Труднее обратиться к переменным на промежуточных уровнях вложения.

procedure Main is

G: Integer,

procedure Proc_1 is

L1: Integer;

procedure Proc_2 is

L2: Integer;

begin L2 := L1 + G; end Proc_2;

procedure Proc_3 is

L3: Integer;

begin L3 := L1 + G; Proc_2; end Proc_3;

begin -- Proc_1

Proc_3;

end Proc_1;

begin — Main

Proc_1;

end Main;

Мы видели, что доступ к локальной переменной L3 и глобальной переменной G является простым и эффективным, но как можно обращаться к L1 в Ргос_3? Ответ прост: значение указателя дна сохраняется при входе в процедуру и используется как указатель на запись активации объемлющей процедуры Ргос_1. Указатель дна хранится в известном месте и может быть немедленно загружен, поэтому дополнительные затраты потребуются только на косвен­ную адресацию.

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

Вызов вышележащих процедур

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

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

Одно из решений состоит в том, чтобы хранить в записи активации стати­ческий уровень вложенности каждой процедуры, потому что компилятор зна­ет, какой уровень необходим для каждого доступа. Если главная программа в примере имеет нулевой уровень, то обе процедуры Ргос_2 и Ргос_3 находятся на уровне 2. При продвижении вверх по динамической цепочке уровень вло­женности должен уменьшаться на единицу, чтобы его можно было рассматривать как часть статической цепочки; таким образом, запись для Ргос_3 про­пускается, и следующая запись, уже запись для Ргос_1 на уровне 1, использу­ется, чтобы получить индекс дна.

Другое решение состоит в том, чтобы явно включить статическую цепоч­ку в стек. На рисунке 7.10 показана статическая цепочка сразу после вызова Ргос_2 из Ргос_3 . Перед вызовом статическая цепочка точно такая же, как ди­намическая, а после вызова она стала короче динамической и содержит толь­ко главную процедуру и Ргос_1.

Характеристики

Список файлов книги