Приложение б. Управление процедурами

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

Реализация стека

Стек — это упорядоченный набор элементов, причем при обращении к нему можно получить доступ лишь к одному из элементов. Этот элемент называется вершиной стека. Число элементов стека (его длина) является переменным. Добавления или удаления можно делать только на вершине стека, поэтому его называют магазинным списком, или списком, организованным по принципу "последним вошел - первым вышел" (last-in-first-out — LIFO).

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

• Указатель стека. Содержит адрес вершины стека. Если в стек добавляется новый элемент (PUSH) или из него удаляется элемент (POP), указатель соответственно увеличивается или уменьшается на единицу. После этого он вновь содержит адрес вершины стека.

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

• Предел стека. Содержит адрес второго конца, т.е. вершины зарезервированного блока. При попытке добавить новый элемент в заполненный стек генерируется сигнал ошибки.

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

Вызов процедуры и возврат из нее

Общепринятым методом управления вызовами процедур и возвратами из них является использование стека. При обработке вызова процессор помещает в стек адрес возврата. При возврате из процедуры процессор использует адрес с вершины стека. На рис. 1.26 и 1.27 показано использование стека при работе с вложенными процедурами.

Часто вместе с вызовом процедуры бывает необходимо передать ей некоторые параметры. Это можно сделать при помощи регистров; другой возможностью является хранение параметров в памяти сразу после команды вызова. В этом случае возврат должен осуществляться к ячейке памяти, расположенной сразу после параметров. Оба этих подхода имеют свои недостатки. При использовании передачи параметров в регистрах необходимо согласование вызывающей и вызываемой процедур, гарантирующее одинаковое распределение параметров по регистрам. При сохранении параметров в памяти усложняется передача переменного числа параметров.

Большую гибкость при передаче параметров обеспечивает стек. При обработке вызова процессор заносит в стек не только адрес возврата, но и параметры, передаваемые вызываемой процедуре, которая легко может получить доступ к ним. При возврате из процедуры возвращаемые значения также можно занести в стек, располагая их под адресом возврата. Набор всех параметров (включая адрес возврата), который сохраняется при обращении к процедуре, называется кадром стека (stack frame).

Рассмотрим пример программы, в которой используются процедуры Р и Q. В процедуре Р объявлены локальные переменные х1 и х2, а в Q — локальные переменные у1 и у2. Процедура Q может быть вызвана из Р. Схема работы стека при выполнении такой программы показана на рис. 1.28. На этом рисунке точка возврата из каждой процедуры является первой ячейкой соответствующего стекового кадра. Следующим сохраняется указатель на начало предыдущего кадра. Это необходимо на случай, если количество или размер заносимых в стек параметров являются переменными.