Стек вызовов
Стек вызовов (от англ. call stack; применительно к процессорам — просто «стек») — в теории вычислительных систем, LIFO-стек, хранящий информацию для возврата управления из подпрограмм (процедур, функций) в программу (или подпрограмму, при вложенных или рекурсивных вызовах) и/или для возврата в программу из обработчика прерывания (в том числе при переключении задач в многозадачной среде).
При вызове подпрограммы или возникновении прерывания, в стек заносится адрес возврата — адрес в памяти следующей инструкции приостановленной программы и управление передается подпрограмме или подпрограмме-обработчику. При последующем вложенном или рекурсивном вызове, прерывании подпрограммы или обработчика прерывания, в стек заносится очередной адрес возврата и т. д.
При возврате из подпрограммы или обработчика прерывания, адрес возврата снимается со стека и управление передается на следующую инструкцию приостановленной (под-)программы.
Реализация
Стек вызовов обычно реализован одним из способов:
- в большей части платформ стек располагается в оперативной памяти (или регистровом файле, как в микроконтроллере Intel 8051), специализированный регистр указывает на его вершину[1]
- вместо стека вызовов адрес возврата сохраняется в специализированный регистр, хранящий один или несколько значений адресов (например, в PowerPC)
При отсутствии стека или ограниченности его глубины, вложенные вызовы исключены или их количество ограничено. При необходимости бо́льшей вложенности, стек вызовов или его расширение могут быть реализованы программно.
Поддержка
Вызов подпрограммы и возвраты из подпрограмм и обработчиков прерываний, как правило выполняются специализированными инструкциями процессора. Кроме инструкций вызовов и возвратов, процессоры часто имеют инструкции для использования стека вызовов также и под сохранение данных — их помещения в стек, снятия со стека, модификации содержимого стека.
Инструкции вызова, возврата и работы со стеком могут отличаться по размеру сохраняемых данных (в этом случае необходимо использовать соответствующие друг другу инструкции или их эквиваленты).
Иногда процедуры возврата из подпрограммы и обработчика прерываний отличаются друг от друга, и также требуют разных команд (например, при возврате из прерывания часто необходимо восстановить из стека регистр флагов и/или разрешить обработку конкурентных прерываний, которая может автоматически запрещаться при вызове обработчика).
При отсутствии специализированных инструкций (в процессорах с сокращённым набором команд) вызовы, возвраты и прочая работа со стеком вызовов реализуются обычными инструкциями работы с памятью/регистрами и передачи управления.
Использование
Стек вызовов может использоваться для различных нужд, но основное его назначение — отслеживать место, куда каждая из вызванных процедур должна вернуть управление после своего завершения. Для этого при вызове процедуры (командами вызова) в стек заносится адрес команды, следующей за командой вызова («адрес возврата»). По завершении вызванная процедура должна выполнить команду возврата для перехода по адресу из стека.
Кроме адресов возврата в стеке могут сохраняться другие данные, например:
- значения регистров с их последующим восстановлением
- данные стекового кадра языков высокого уровня:
- аргументы, переданные в функцию
- локальные переменные — временные данные функции
- другие произвольные данные
Использование стека в многозадачных системах
В многозадачных системах каждая задача, как правило, имеет свой собственный стек, и при переключении задачи указатель стека процессора переставляется на него.
Нестандартное использование
Стек может быть использован нестандартно, например:
- вызванная подпрограмма может модифицировать адрес возврата, например при выборке аргументов расположенных следом за инструкцией вызова
- возврат не в вызывающую подпрограмму, а в предыдущую по стеку (при обработке нештатной ситуации)
Альтернативное использование
При альтернативном использовании, указатель стека переставляется на область данных и инструкции для работы со стеком используется в качестве строковых операций для обработки последовательных данных в памяти.
При альтернативном использовании обработка прерываний невозможна, так как во избежание повреждения данных прерывания должны запрещаться.
Замечания
- Императивные языки программирования высокого уровня, как правило, не имеют возможностей явного оперирования стеком вызовов, но есть и исключения. Например, в Forth есть прямой доступ к системному стеку вызовов (под названием «стек возвратов», в отличие от «стека данных» этого языка).