понедельник, 25 мая 2009 г.

Стек

Стеком называют область программы для временного хранения произвольных данных. Разумеется, данные можно сохранять и в сегменте данных, однако в этом случае для каждого сохраняемого на время данного надо заводить отдельную именованную ячейку памяти, что увеличивает размер программы и количество используемых имен. Удобство стека заключается в том, что его область используется многократно, причем сохранение в стеке данных и выборка их оттуда выполняется с помощью эффективных команд push и pop без указания каких-либо имен.
Стек традиционно используется, например, для сохранения содержимого регистров, используемых программой, перед вызовом подпрограммы, которая, в свою очередь, будет использовать регистры процессора "в своих личных целях". Исходное содержимое регистров извлекается из стека после возврата из подпрограммы. Другой распространенный прием - передача подпрограмме требуемых ею параметров через стек. Подпрограмма, зная, в каком порядке помещены в стек параметры, может забрать их оттуда и использовать при своем выполнении.
Отличительной особенностью стека является своеобразный порядок выборки содержащихся в нем данных: в любой момент времени в стеке доступен только верхний элемент, т.е. элемент, загруженный в стек последним. Выгрузка из стека верхнего элемента делает доступным следующий элемент.
Элементы стека располагаются в области памяти, отведенной под стек, начиная со дна стека (т.е. с его максимального адреса) по последовательно уменьшающимся адресам. Адрес верхнего, доступного элемента хранится в регистре-указателе стека SP. Как и любая другая область памяти программы, стек должен входить в какой-то сегмент или образовывать отдельный сегмент. В любом случае сегментный адрес этого сегмента помещается в сегментный регистр стека SS. Таким образом, пара регистров SS:SP описывают адрес доступной ячейки стека: в SS хранится сегментный адрес стека, а в SP - смещение последнего сохраненного в стеке данного (смотрим рисунок). Обратите внимание на то, что в исходном состоянии указатель стека SP указывает на ячейку, лежащую под дном стека и не входящую в него.

а - исходное состояние, б - после загрузки одного элемента (в данном примере - содержимого регистра АХ), в - после загрузки второго элемента (содержимого регистра DS), г - после выгрузки одного элемента, д - после выгрузки двух элементов и возврата в исходное состояние.

Загрузка в стек осуществляется специальной командой работы со стеком push (протолкнуть). Эта команда сначала уменьшает на 2 содержимое указателя стека (SP), а затем помещает операнд по адресу в SP. Если, например, мы хотим временно сохранить в стеке содержимое регистра АХ, следует выполнить команду

push АХ

Стек переходит в состояние, показанное на рис. б. Видно, что указатель стека смещается на два байта вверх (в сторону меньших адресов) и по этому адресу записывается указанный в команде проталкивания операнд. Следующая команда загрузки в стек, например,

push DS

переведет стек в состояние, показанное на рис. в. В стеке будут теперь храниться два элемента, причем доступным будет только верхний, на который указывает указатель стека SP. Если спустя какое-то время нам понадобилось восстановить исходное содержимое сохраненных в стеке регистров, мы должны выполнить команды выгрузки из стека pop (вытолкнуть):

pop DS
pop AX

Состояние стека после выполнения первой команды показано на рис. г, а после второй - на рис. д. Для правильного восстановления содержимого регистров выгрузка из стека должна выполняться в порядке, строго противоположном загрузке - сначала выгружается элемент, загруженный последним, затем предыдущий элемент и т.д.
Совсем не обязательно при восстановлении данных помещать их туда, где они были перед сохранением. Например, можно поместить в стек содержимое DS, а извлечь его оттуда в другой сегментный регистр - ES;

push DS
pop ES ; Теперь ES=DS, а стек пуст

Это распространенный прием для перенесения содержимого одного регистра в другой, особенно, если второй регистр - сегментный.
Обратите внимание (см. рисунок) на то, что после выгрузки сохраненных в стеке данных они физически не стерлись, а остались в области стека на своих местах. Правда, при "стандартной" работе со стеком они оказываются недоступными. Действительно, поскольку указатель стека SP указывает под дно стека, стек считается пустым; очередная команда push поместит новое данное на место сохраненного ранее содержимого АХ, затерев его. Однако пока стек физически не затерт, сохраненными и уже выбранными из него данными можно пользоваться, если помнить, в каком порядке они расположены в стеке. Этот прием часто используется при работе с подпрограммами.
Какого размера должен быть стек? Это зависит от того, насколько интенсивно он используется в программе. Если, например, планируется хранить в стеке массив объемом 10 000 байт, то стек должен быть не меньше этого размера. При этом надо иметь в виду, что в ряде случаев стек автоматически используется системой, в частности, при выполнении команды прерывания int 21h. По этой команде сначала процессор помещает в стек адрес возврата, а затем DOS отправляет туда же содержимое регистров и другую информацию, относящуюся к прерванной программе. Поэтому, даже если программа совсем не использует стек, он все же должен присутствовать в программе и иметь размер не менее нескольких десятков слов.
Что произойдет, если программист по ошибке или умышленно не опишет стек в своей программе? Изменим нашу мега программу, удалив из нее описание стека.

В регистр DX помещен код двух знаков @. Это сделано для наглядности примера.
Запустим программу под отладчиком.

Видим, что в SS находится тот же адрес, что и в CS; от сюда можно сделать вывод, что сегменты команд и стека совпадают. Однако содержимое SP равно нулю. Первая же команда push уменьшит содержимое SP на 2, то есть поместит в SP число -2, значит ли это, что стек будет расти как ему и положено, ввех, но не внутри сегмента команд, а над ним, по адресам -2, -4, -6 и т.д. относительно верхней границы сегмента команд. Оказывается это не так.
Если взять 16-разрядный двоичный счетчик, в котором записн 0, и послать в него два вычитающих импульса, то после первого в нем окажется число FFFFh, а после второго – FFFEh. При желании мы можем рассматривать число FFFEh как -2 (что имеет место при работе со знаковыми числами, о которых поговорим чуть позже), однако процессор при вычислении адресов рассматривает содержимое регистров как целые числа без знака и число FFFEh оказывается эквивалентным не -2, а 65534. В результате первая же команда занесения данного в стек (в нашем случае push dx) поместит это данное не над сегментом команд, а в самый его конец, в последнее слово по адресу CS:FFFEh (что, в данном примере, эквивалентно SS:FFFEh). При дальнейшем использовании стека его указатель будет смещаться в сторону меньших адресов, проходя значения FFFCh, FFFAh и т.д.
Таким образом, если в программе отсутствует явное определение стека, система сама создает стек по умолчанию в конце сегмента команд или, точнее, по адресу FFFEh относительно начала сегмента команд (см. рисунок).

Выполним программу дальше и убедимся в этом. По ходу выполнения программы с первой команды до седьмой, мы сможем видеть, что в стек помещаются какие-то значения, но при этом регистр SP не изменяется (предположительно, все это самодеятельность отладчика), и только после выполнения седьмой команды – push dx, SP принимает значение FFFEh, и на дне стека мы видим два символа @.

Рассмотренное явление, когда при уменьшении адреса после адреса 0 у нас получается адрес FFFEh, т.е. от начала сегмента мы прыгнули сразу в его конец, носит название циклического возврата или оборачивания адреса. С этим явлением приходится сталкиваться довольно часто.
Расположение стека в конце сегмента команд не приводит к каким-либо неприятностям, пока размер программы далек от граничной величины 64Кбайт. В этом случае начало сегмента команд занимают коды команд, конец – стек, а между ними располагаются данные (если сегмент данных описан в программе после сегмента команд). Если, однако, размер сегментов команд или данных приближается к 64Кбайт, то фактически стек будет наложен на тот или иной сегмент программы и возникнет опасность затирания данных или кода. Очевидно, что этого нельзя допускать. В тоже время, система не проверяет, что происходит со стеком и ни как не реагирует на затирание команд или данных. Таким образом, оценка размеров собственно программы, данных и стека является важным этапом разработки программы.

7 комментариев:

Unknown комментирует...

Если 64 КБ сегмент не имеет достаточно места для стека, то DOS устанавливает стек в конце памяти. Как это делается? Какие адреса в этом случае будут иметь регистры SS и SP?

ЛевыйКоронныйПравыйПохоронный комментирует...
Этот комментарий был удален автором.
ЛевыйКоронныйПравыйПохоронный комментирует...
Этот комментарий был удален автором.
ЛевыйКоронныйПравыйПохоронный комментирует...

Почему в случае со считыванием, сначала идет считывание, а потом уменьшение значения SP, а в случае записи идёт сначала запись, а потом увеличение значения SP?

Давайте разберёмся подробнее:

Для операции push (запись в стек):
1. SP уменьшается на размер данных, которые будут записаны.
2. Данные записываются по адресу в стеке, который теперь указывает SP.

Для операции pop (считывание из стека):
1. Данные считываются из стека по адресу, который указывает SP.
2. SP увеличивается на размер считанных данных.

Таким образом, в случае операции pop, сначала происходит считывание данных из стека, а затем SP увеличивается, чтобы указать на следующий элемент в стеке. В случае операции push, SP сначала уменьшается, чтобы освободить место для нового элемента, и только после этого происходит запись данных в стек.

Для push:
SP = SP - размер данных
[SS:SP] = значение для записи

Для pop:
значение для чтения = [SS:SP]
SP = SP + размер данных

Это обеспечивает корректное использование структуры стека и предотвращает потерю данных или перезапись уже существующих данных в стеке.

ЛевыйКоронныйПравыйПохоронный комментирует...
Этот комментарий был удален автором.
ЛевыйКоронныйПравыйПохоронный комментирует...
Этот комментарий был удален автором.
ЛевыйКоронныйПравыйПохоронный комментирует...
Этот комментарий был удален автором.