Меню сайта

Урок 15. Стек

Стек — это структура данных, котораяиспользуется для временного
— — — хранения информации. — Программа может поместить данные в стек
— — — (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 і&lt-ДД SP — — — і Dі — — — — — -і E і&lt-ДД SP
— — — — — — ГДДДґ — — — — — — — — — — ГДДДґ — — — — ГДДДґ — — — — ГДДДґ
— — — — — — і C і&lt-ДД SP — — — і C і — — — — — — і C і&lt-ДД SP — — — і C і
— — — — — — ГДДДґ — — — — — — — — — — ГДДДґ — — — — ГДДДґ — — — — ГДДДґ
— — — — — — і B і — — — — — — — — — — і B і — — — — і B і — — — — і B і
— -&nb
sp- — — — ГДДДґ — — — — — — — — — — ГДДДґ — — — — ГДДДґ — — — — ГДДДґ
— — — — — — і 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

— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —— Здесь главная процедурапродолжается . . .


&nbs
p- — — — — — — — — -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.

Категория: Программирование на Ассемблере | Дата: 02.03.13

Меню раздела
Блок