Стек
Стек
Стек - это структура данных, которая используется для временного
хранения информации. Программа может поместить данные в стек
(PUSH) или забрать их оттуда (POP). Стековая структура данных
предполагает упорядочивание помещенных в него данных специальным
образом. Во всех случаях первым из стека извлекается то, что было
в нем сохранено последним. Такая организация хранения данных
сокращенно обозначается LIFO (last in, first out - последний
введенный первым выводится). Если мы поместили в стек сначала A,
затем B, то первое, что мы извлечем из него будет B. Следующая
команда извлечения (POP) вернет A. Информация возвращается из
стека в порядке, строго противоположном порядку ее помещения в
стек.
Стек противоположен очереди. Очередь - это обычная последова-
тельность, подобная очередям на почте или в магазине. Это
структура данных типа "первым вошел - первым вышел" (first in,
first out: FIFO). Тот, кто первым встал в очередь, первым и
покинет ее. Стек и очередь - очень разные вещи.
Компьютер снабжает стек зарезервированным участком памяти и
указателем, называемым указателем стека. Программа использует ука-
затель стека для того, чтобы фиксировать последние помещенные в
стек данные, в отличие от почты, где сами элементы очереди продви-
гаются вперед по мере движения очереди. В компьютере намного легче
использовать для слежения за данными указатель и при записи или
считывании данных из стека изменять только его. В ответ на
выполнение операций POP и PUSH указатель стека соответственно
увеличивается или уменьшается.
Фиг. 2.19 дает пример стека. В части (a) изображен стек после
того как в него последовательно помещены значения A, B, C. Ука-
затель стека указывает на текущую вершину стека, в данном случае на
C. В части (b) в стек помещается еще одно значение: D. Операция
PUSH уменьшает указатель стека SP (от Stack Pointer - указатель
стека), который теперь указывает на новую вершину D. Указатель
стека всегда фиксирует то, что было последним помещено в стек.
Фиг. 2.19(c) показывает состояние стека после операции POP.
Этой операцией значение D было извлечено из стека. Команда POP
помещает извлеченное из стека значение в указанное место. Если в
части (c) выполнялась команда POP AX, то процессор поместил
значение D в регистр AX (это уже дополнительный аспект, который мы
обсудим в следующей главе). POP увеличивает указатель стека.
Теперь он указывает на новую вершину, C. Заметим, что элементы
извлекаются из стека по описанному принципу LIFO. Последним
помещенным в стек элементом был D и он же первым извлечен из стека.
Обратите также внимание, что D так и осталось в памяти, однако
теперь уже не является частью стека. Логическая граница стека
находится по адресу, хранящемуся в его указателе. В данном случае
вершина стека оказывается ниже ячейки со значением D.
На Фиг. 2.19(d) видно, что происходит с D при помещении в сетк
нового элемента E. Элемент E записывается на место D и становится
новой вершиной стека. Мораль из этой истории такова, что хотя
извлеченные из стека значения могут оставаться в памяти, полагаться
на это не следует.
ГДДДґ ГДДДґ ГДДДґ ГДДДґ
і і і D і<ДД SP і D і і E і<ДД SP
ГДДДґ ГДДДґ ГДДДґ ГДДДґ
і C і<ДД SP і C і і C і<ДД SP і C і
ГДДДґ ГДДДґ ГДДДґ ГДДДґ
і B і і B і і B і і B і
ГДДДґ ГДДДґ ГДДДґ ГДДДґ
і A і і A і і A і і A і
ГДДДґ ГДДДґ ГДДДґ ГДДДґ
(a) (b) (c) (d)
Фиг. 2.19 Пример работы стека
В приведенном примере подразумевался принцип построения стека
процессора 8088. Указатель стека постоянно указывает на текущую
вершину стека. Операция PUSH уменьшает указатель стека, POP
увеличивает его. Стек растет в направлении уменьшения адресов в
памяти. Основание стека располагается в памяти по большему адресу,
чем его вершина. Если вы нарисуете изображения стека с наименьшим
адресом сверху, как на Фиг. 2.19, то вершина стека окажется в
верхней части рисунка.
Мы занялись обсуждением стека потому, что стек используется для
хранения адреса возврата из процедуры. Как это делается?
Каждая команда CALL вызывает как бы выполнению команды PUSH для
стека - сохраняет в стеке адрес возврата. Команда RET извлекает из
стека, подобно команде POP, адрес возврата и помещает его в
указатель команд. 8088 использует стек для хранения адресов
возврата потому, что это позволяет вкладывать процедуры одна в
другую. Что такое вложение? На Фиг. 2.20 показан пример
вложенных процедур.
На Фиг. 2.20 показана абсурдная программа, которую мы
используем как пример вложения процедур. Часть (a) показывает
стек перед выполнением программы. Как только начинает выполняться
процедура MAIN, она вызывает процедуру SUBROUTINE_A. В это время
процессор сохраняет в стек адрес возврата. Часть (b) показывает
адрес возврата 103 помещенным в стек. SUBROUTINE_A в процессе
своего выполнения вызывает SUBROUNINE_B. Команда этого вызова
сохраняет адрес возврата 108 в SUBROUNINE_A. Когда SUBROUNINE_B
заканчивается, команда возврата извлекает из стека значение 108,
как показано в части (d). Процессор помещает это значение в
указатель команд, как требуется при команде возврата. Как видно на
листинге ассемблера, адрес 108 относится к SUBROUNINE_A и следует
сразу за вызовом SUBROUNINE_B. Затем SUBROUNINE_A заканчивается.
Команда возврата извлекает из стека значение 103 для указателя
команд. Адрес 103 относится к процедуре MAIN и следует сразу за
вызовом SUBROUNINE_A.
Наиболее важным в примере на Фиг. 2.20 является вложение
процедур. Одна процедура может вызывать другую, а команда возврата
всегда обеспечивает правильный возврат управления. Единственное,
Microsoft (R) Macro Assembler Version 5.00 11/10/88 23:18:17
Фиг. 2.20 Вызов вложенных процедур Page 1-1
PAGE ,132
TITLE Фиг. 2.20 Вызов вложенных процедур
0000 CODE SEGMENT
ASSUME CS:CODE
0100 ORG 100H
0100 E8 0104 R MAIN: CALL SUBROUTINE_A
0103 40 INC AX
;----- Здесь главная процедура продолжается . . .
0104 SUBROUTINE_A PROC NEAR
0104 43 INC BX
0105 E8 0109 R CALL SUBROUTINE_B
0108 C3 RET
0109 SUBROUTINE_A ENDP
0109 SUBROUTINE_B PROC NEAR
0109 41 INC CX
010A C3 RET
010B SUBROUTINE_B ENDP
010B CODE ENDS
END
ГДДДґ ГДДДґ ГДДДґ ГДДДґ
і і і і і108іДД SP і108і
ГДДДґ ГДДДґ ГДДДґ ГДДДґ
і і і103іДД SP і103і і103іДД SP
ГДДДґ ГДДДґ ГДДДґ ГДДДґ
іxxxіДД SP іxxxі іxxxі іxxxі
ГДДДґ ГДДДґ ГДДДґ ГДДДґ
(a) (b) (c) (d)
Фиг. 2.20 Вызов вложенных процедур
что ограничивает глубину вложения процедур (сколько процедур может
вызывать другие) - это размер стека. Пока в стеке имеется место
для очередного адреса возврата, можно производить вложенный вызов
процедуры. Структура стека LIFO дает гарантию правильной
последовательности возвратов.
Пример программы на Фиг. 2.20 показывает также использование
еще одной псевдооперации ассемблера - PROC. Оператор PROC
используется ассемблером для идентификации процедур. Как мы
дальше увидим, ассемблер должен знать, как далеко располагается
процедура и как возвращаться к точке ее вызова. Операнд NEAR
определяет процедуру как расположенную в пределах легкой
досигаемости вызывающей программы. Мы еще вернемся к оператору
PROC, когда будем обсуждать реальное действие команд CALL и JMP.
