Стек. Аппаратурные аспекты: от команд процессора до встречных стеков

Модуль "Стек" • урок 3 из 8 • ~8 минут

Стек. Аппаратурные аспекты: зачем процессору стек

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

• Частичная аппаратная поддержка. Процессоры общего назначения (семейства PDP и VAX, современный x86) имеют регистр указателя стека (SP, Stack Pointer) и команды PUSH, POP, CALL, RET, которые автоматизируют работу со стеком вызовов.
• Существенно стековая архитектура. Некоторые машины - Burroughs, отечественные комплексы "Эльбрус", инженерные калькуляторы - спроектированы так, что стек является основным рабочим органом вычислений. Они используют нуль-адресную систему команд.

Нуль-адресные машины

В обычном процессоре команда сложения указывает операнды: "сложить регистр A с регистром B". В нуль-адресной машине команда сложения не указывает ничего: она берет два верхних числа со стека, складывает и кладет результат обратно на вершину. Это в точности стековая модель вычислений из прошлого урока, реализованная в железе.

Программы для таких машин получаются в 3-4 раза короче - экономятся биты, которые обычно уходят на адреса операндов. Так сочетается выразительность сложных CISC-архитектур с простотой RISC.

Как стек вызывает функции

Главная работа аппаратного стека в классических машинах - механизм вызова процедур и функций, включая рекурсию.

При вызове функции (команда CALL) процессор автоматически кладет в стек адрес возврата - адрес следующей команды. Туда же помещаются переданные параметры и выделяется место под локальные переменные. Когда функция завершается (команда RET), процессор снимает адрес возврата со стека и продолжает выполнение с того места, откуда функцию вызвали.

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

Встречные стеки

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

Решение - расположить стеки навстречу друг другу: дно первого - в начале массива (индекс 0), он растет вправо; дно второго - в конце массива (индекс N-1), он растет влево.

Что это дает:

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