Стек - это структура данных, которая используется для временного хранения информации. Программа может поместить данные в стек (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 и становится новой вершиной стека. Мораль из этой истории такова, что хотя извлеченные из стека значения могут оставаться в памяти, полагаться на это не следует.
| Таблица испрочена в оригинале |
|---|
Фиг. 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 1 PAGE ,132 2 TITLE Фиг. 2.20 Вызов вложенных процедур 3 4 0000 CODE SEGMENT 5 ASSUME CS:CODE 6 0100 ORG 100H 7 0100 E8 0104 R MAIN: CALL SUBROUTINE_A 8 0103 40 INC AX ;----- Здесь главная процедура продолжается 9 0104 SUBROUTINE_A PROC NEAR 10 0104 43 INC BX 11 0105 E8 0109 R CALL SUBROUTINE_B 12 0108 C3 RET 13 0109 SUBROUTINE_A ENDP 14 0109 SUBROUTINE_B PROC NEAR 15 0109 41 INC CX 16 010A C3 RET 17 010B SUBROUTINE_B ENDP 18 010B CODE ENDS 19 END
| IP | SP top+0 | SP top+4 | SP==> | execute command |
|---|---|---|---|---|
| 100 | xxx | xxx | xxx | call SUBROUTINE_A |
| 104 | 103 | xxx | 103 | inc bx |
| 109 | 108 | 103 | 108 | inc cx |
| 108 | 103 | xxx | 103 | ret |
| 103 | xxx | xxx | xxx | inc ax |
Фиг. 2.20 Вызов вложенных процедур
Единственное, что ограничивает глубину вложения процедур (сколько процедур может вызывать другие) - это размер стека. Пока в стеке имеется место для очередного адреса возврата, можно производить вложенный вызов процедуры. Структура стека LIFO дает гарантию правильной последовательности возвратов.
Пример программы на Фиг. 2.20 показывает также использование еще одной псевдооперации ассемблера - PROC. Оператор PROC используется ассемблером для идентификации процедур. Как мы дальше увидим, ассемблер должен знать, как далеко располагается процедура и как возвращаться к точке ее вызова. Операнд NEAR определяет процедуру как расположенную в пределах легкой досигаемости вызывающей программы. Мы еще вернемся к оператору PROC, когда будем обсуждать реальное действие команд CALL и JMP.