1.4 Зачем в компьютерах нужны стеки ?



==19

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

1.4.1 Стек для вычисления выражений

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

Чтобы понять, почему стек хорошо подходит для вычисления выражений, рассмотрим, как вычисляется следующая последовательность арифметических действий:

X = (A + B) * (C + D) 

==20

Сначала следует сложить «A» и «B». Затем этот промежуточный результат надо где-нибудь сохранить. Предположим, что он положен в стек для вычисления выражений. Далее складываются «C» и «D» и результат также кладётся туда же. Наконец, два верхних элемента стека ( «A+B» и «C+D» ) перемножаются между собой, а результат сохраняется в переменной «X». Стек для вычисления выражений обеспечивает автоматическую обработку промежуточных результатов и позволяет иметь столько уровней вложенности в выражениях, сколько элементов помещается в стек. Читатели, которые работают с калькуляторами Hewlett Packard, использующими обратную польскую запись, имеют опыт непосредственного общения со стеком для вычисления выражений.

Использование стека при вычислениях выражений имеет настолько основополагающее значение, что даже компиляторы для регистровых машин часто распределяют регистры так, как если бы они формировали такой стек.

1.4.2 Стек адресов возврата

С появлением рекурсии, как полезного свойства языка в поздних 1950-х, появилась необходимость в сохранении адреса возврата из подпрограммы в области динамически распределяемой памяти. Проблема заключалась в том, что общеупотребительным методом сохранения адреса возврата из подпрограммы в нерекурсивных языках, типа FORTRAN, было резервирование под него места в теле самой подпрограммы. Такой способ, естественно, не позволял процедуре вызывать саму себя прямо или косвенно, так как предыдущий адрес возврата был бы затёрт новым вызовом.

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

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

1.4.3 Стек для размещения временных переменных

Использование рекурсии, особенно в условиях обязательной повторной входимости кода ( возможность множественного и одновременного использования кода различными ветвями программы ), приводит к ещё одной проблеме - к контролю за оборотом временных переменных. В уже упоминавшихся нерекурсивных языках, типа FORTRAN, управление данными для подпрограммы решается простым резервированием места в коде. Такой вариант резервирования - статический - подходит только для нерекурсивных программ, не допускающих повторное вхождение.



==21

В любом случае, как только возникает возможность вызова подпрограммы из нескольких ветвей управления одновременно либо рекурсивного вызова, корректное управление статически распределёнными переменными становится практически невозможным. Значения переменных для одной ветви исполнения могут быть легко повреждены конкурирующим процессом. [* Т.е. повторно входимая процедура «A» может быть вызвана из кода основного цикла программы, а в ходе выполнения «A» может возникнуть прерывание, которое, в свою очередь, использует ту же процедуру «A» ] . Чаще всего используемый выход - выделение места под временные переменные в стеке. При каждом вызове подпрограммы в стеке локальных переменных заводится новый блок памяти. Даже если для промежуточных вычислений используются только регистры, перед их использованием прежние значения, принадлежащие вызывающей процедуре, надо сохранить в каком-либо стеке.

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

1.4.4 Стек аргументов

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

1.4.5 Комбинированные стеки

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

Стековые машины, описываемые в этой книге, используют раздельные аппаратные стеки. Один для вычисления выражений, передачи параметров и размещения временных переменных, второй для адресов возврата. Иногда, при использовании обычных языков программирования, таких как Си или Pascal, регистр-указатель на стековый кадр используется для обращения к локальным переменным в программной памяти.



==21