Стек, подпрограммы, рекурсия

Понятие стека и его предназначение

Под стеком в программировании подразумевают структуру данных, построенную по принципу ПОСЛЕДНИЙ ВОШЁЛ - ПЕРВЫЙ ВЫШЕЛ (LIFO, last in first out), т.е. такой объект, над которым определены операции "добавить элемент" и "извлечь элемент", причём элементы, которые были добавлены, извлекаются в обратном порядке.

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

Стек можно использовать, например, для временного хранения значений регистров; если некоторый регистр хранит важное для нас значение, а нам при этом нуно временно задействовать этот регистр для хранения другого значения, то самый простой способ выйти из положения - это сохранить значение регистра в стеке, затем использовать регистр под другие нужды, и, наконец, восстановить исходное значение регистра путём извлечения этого значения из стека обратно в регистр. Но гораздо более важно другое: стек используется при вызовах подпрограмм для хранения адресов возврата, для передачи фактических параметров и для хранения локальных переменных. Именно использование стека позволяет реализовать механизм рекурсии, при котором подпрограммма может прямо или косвенно вызвать сама себя.

Организация стека в процессоре

Команды работы со стеком позволяют заносить в стек и извлекать из него двухбайтные слова и четырёхбайтные двойные слова; отдельные байты записывать в стек нельзя, так что адрес вершины стека всегда остаётся чётным.

Регистр ESP, формально относящийся к группе регистров общего назначения, тем не менее практически никогда не используется ни в какой иной роли, кроме роли указателя стека; название этого регистра как раз и означает stack pointer. Считается, что адрес, содержащийся в ESP, указывает на вершину стека, то есть на ту область памяти, где находится последнее занесённое в стек значение. Стек растёт в сторону уменьшения адресов, т.е. при занесении в стек нового значения ESP уменьшается, при извлечении значения - увеличивается.

Занесение значения в стек производится командой push, имеющей один операнд. Этот операнд может быть непосредственным, регистровым или типа "память" и иметь размер word или dword (если операнд не регистровый, то размер необходимо указать явно). Для извлечения значения из стека используется команда pop, операнд которой может быть регистровым или типа "память"; естественно, операнд должен иметь размер word или dword.

Поддержите проект, если он помог вам

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