Поддержка стековой организации памяти

Принцип стековой организации памяти относят к одному из ведущих принципов, используемых при разработке ВС и их ОС, а также систем программирования.

Стек представляет собой простейший способ управления динамически распределяемой памятью во время выполнения.

В общем случае модель стека можно описать следующим образом:

– тело стека представляет собой совокупность смежных элементов хранения информации (регистров, ячеек оперативной памяти);

– элемент стека, хранящий в текущий момент времени информацию, которая была помещена в стек последней, называют вершиной стека;

– адрес вершины стека изменяется каждый раз при выполнении операции записи в стек или считывания информации из стека; при “вталкивании” информации новой вершиной стека становится слово, адрес которого на 1 меньше, чем у старой вершины; если информация считывается из стека, то она “выталкивается” из него (информация выбирается из вершины стека, а затем проводится коррекция адреса вершины стека и новая вершина будет располагаться по адресу на 1 большему, чем адрес прежней вершины);

– длина стека определяется количеством его элементов, которые в данный момент содержат информацию; длина является переменной величиной: при размещении нового элемента в стеке его длина увеличивается на 1, каждый раз при извлечении элемента из стека (по правилу LIFO – “Last In-First Out” – первым извлекается элемент, помещенный в стек последним) длина его тела уменьшается на 1, поэтому стек может выродиться (длина становится равной 0).

В общем случае в стеке может размещаться информация, которая занимает более одного элемента.

При реализации стека в оперативной памяти он представляет собой блок памяти, состоящий из слов с последовательными адресами. При запросе на размещение информации в стеке для нее выделяется слово или массив (блок) из последовательных (смежных) слов этого стека, начиная с его головы (вершины). При этом стек “растет”, причем рост стека, его расширение всегда выполняется в одном направлении. При выборе информации из стека память должна освобождаться в порядке, обратном его заполнению, то есть блок освобождаемой памяти всегда находится в вершине стека.

Следовательно, исходя из приведенного описания модели стека, решение задачи управления стеком становится тривиальным: для реализации стековой памяти на основе оперативной памяти необходимо хранить всего один указатель – адрес вершины стека.

При использовании относительной адресации (адрес вычисляется по формуле “база + смещение”) стек получает свойство перемещаемости, а для его реализации необходимо хранить два адреса: базовый адрес стека и относительный адрес его вершины (смещение головы стека относительно его базового адреса).

При выполнении операций записи в стек и считывания из стека происходит соответствующее изменение относительного адреса его вершины. Причем наличие двух компонентов при адресации стека позволяет контролировать его размер, предупреждая возможные нарушения границ выделенного под стек блока памяти.

Модель стека широко используется при разработке программного обеспечения.

Стеки представляют удобный механизм для вычисления арифметических и логических выражений. Промежуточные результаты вычислений могут размещаться в стеке. Стек, используемый для вычислений, называют стеком выражений.

Блочно-ориентированная структура программ в наибольшей степени ориентирована на стековую обработку.

Программа с блочной структурой может содержать в своем составе одну или более функционально выделенных частей (блоков), каждая из которых может быть динамически вызвана для исполнения. Перед исполнением блок может быть настроен с помощью параметров. Форма реализации блоков может быть различной.

Наиболее часто блок выражается в форме процедуры.

Любая процедура перед ее использованием должна быть описана в программе. В описании задается имя процедуры, указываются ее параметры, определяется тело процедуры, включающее описания локальных данных и последовательность операторов, выполняемую при вызове процедуры. Если процедура описана в некотором блоке, то говорят, что она вложена в этот блок. На описание процедуры также распространяется возможность вложения других процедур.

Адресный контекст процедуры определяет область видимости имен, которые могут быть доступны внутри этого блока для обработки. В адресный контекст процедуры входят глобальные и локальные данные и другие программные структурные элементы (например, другие процедуры). Локальные элементы – описанные непосредственно в процедуре, вложенные в нее. Глобальные элементы для данной процедуры – это данные и программные компоненты, находящиеся (описанные) в составе других процедур, входящих в статическую цепочку данной процедуры (то есть в последовательность вложений, которую можно установить для данной процедуры, прослеживая описания от главной программы). В адресный контекст входят также параметры, передаваемые процедуре.

Всякий раз, когда вызывается для исполнения какая-либо процедура, для нее устанавливается адресный контекст.

Управляющие и информационные связи между процедурами могут быть установлены с помощью стеков.

Локальные данные каждой процедуры по своему функциональному назначению являются промежуточными данными. Их значения существуют и доступны только при исполнении процедуры.

При исполнении программы как последовательности вызовов процедур, вложенных друг в друга, последовательность таких вызовов и возвратов описывается дисциплиной LIFO. Порядок появления и уничтожения локальных данных и параметров процедур точно соответствует порядку вызовов и возвратов. Поэтому хранить локальные данные и значения параметров вызываемых процедур можно в специальном стеке – стеке данных. Каждая область стека данных – это память для хранения локальных данных, параметров и служебной информации, соответствующей одному вызову отдельной процедуры (то есть при каждом вызове в стеке создается новая копия локальных данных, параметров и служебной информации). На адресное пространство этой области и производится отображение виртуального адресного пространства описательной части процедуры.

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

При выполнении каждой процедуры для нее следовало бы организовать собственный стек выражений, но такой вариант практически неосуществим, поэтому различные по назначению стеки на практике объединяются в один стек: память под стеки выражений для хранения промежуточных данных выделяется в области локальных данных процедуры в стеке данных.

Операционные системы Windows NT и Windows 95 используют стек для организации выполнения программ. Система сама резервирует какие-то регионы в адресном пространстве выполняющихся процессов (например, в памяти размещаются блоки переменных окружения). Регионы памяти резервируются ОС так же для размещения стеков потоков.

У каждого потока, создаваемого процессом, есть свой стек. Для его размещения система резервирует регион адресного пространства, передавая ему некоторый объем физической памяти (по умолчанию система резервирует 1 Мб адресного пространства, а передает ему 2 страницы физической памяти, но значения, устанавливаемые по умолчанию, можно изменить при компоновке программы (параметр компоновщика /STACK) или количество физической памяти, первоначально передаваемой стеку можно варьировать вызовом функции CreateThread или _beginthreadex).

При недостатке выделенной физической памяти для размещения данных в стеке подключается механизм организации виртуальной памяти, рассматриваемый ниже.

Таким образом, стек является эффективным средством организации вычислительного процесса.

Эффективная работа с памятью, организованной в виде стека, требует аппаратной поддержки адресации элементов стека. Обычно для реализации стека в современных ВС используются специальные регистры.

В ВС на базе процессоров Intel для работы со стеком используются регистры SS (сегментный регистр, содержащий базовый адрес блока памяти, используемого под стек) и SP/ESP (указатель вершины стека – смещение головного элемента стека относительно начала занимаемого им сегмента).

Для размещение информации в стеке используется набор операций PUSH/PUSHA/PUSHAD.

Операция PUSH – включение (“проталкивание”) в стек операнда (уменьшает смещение в регистре SP/ESP на размер операнда и сохраняет операнд в стеке).

Операция PUSHA – включение в стек содержимого всех восьми 16-разрядных регистров общего назначения (удобно использовать для сохранения регистров при вызовах процедур).

Операция PUSHAD – включение в стек содержимого всех восьми 32-разрядных регистров общего назначения.

Для выбора информации из стека применяются соответственно операции POP/POPA/POPAD.

Операция POP – извлечение (“выталкивание”) операнда из стека. Эта команда обратна команде PUSH.

Для команд PUSHA/PUSHAD парными являются команды POPA/POPAD соответственно.

Команды PUSHF/PUSHFD и POPF/POPFD позволяют включить в стек и извлечь из стека содержимое регистра флагов FLAGS/EFLAGS.

Эти команды можно использовать для временного сохранения информации, например, из регистров, в стеке во время вычислений. При восстановлении информации она должна выбираться в порядке обратном тому, который был использован при сохранении.

Кроме того, стек используется при выполнении операций вызова процедуры (команда CALL перед передачей управления на вход процедуры размещает в стеке адрес возврата) и возврата из процедуры (команда RET выбирает адрес точки возврата из стека и передает на нее управление), а также при прерывании программы (команда INT перед передачей управления на соответствующий обработчик прерывания помещает в стек содержимое регистра флагов и точку возврата (адрес команды, перед выполнением которой произошло прерывание), а завершающая всякий обработчик прерывания команда IRET выбирает эту информацию из стека и использует ее для возврата к выполнению прерванной программы).

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

Для удобства при организации передачи списка параметров вызываемой процедуре через стек в процессорах Intel при работе со стеком можно использовать еще один регистр – BP/EBP (указатель базы), который может быть установлен на начало передаваемого списка параметров и позволяет извлекать их значения из стека, не перемещая его вершину и не исключая выбранные элементы.

При работе в защищенном режиме аппаратно контролируется возможность выхода за границы стека, права доступа к нему.