Стек



Стек


    Стек - это структура данных, которая используется для временного
    хранения информации.  Программа может поместить данные в стек
    (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.




Содержание раздела