5.1 Стек.Операции PUSH и POP .Назначение. Реализация.

Стек - это абстрактный тип данных, с определенными свойствами. Последний помещенный в стек объект извлекается из него первым. Такая схема называется LIFO (last in first out - последний вошел, первый вышел). Над данными в стеке определены операции Push и Pop.Push помещает элемент данных в вершину стека. Pop, наоборот, уменьшает размер стека на единицу, удаляя последний элемент из его вершины. Стек применяется для динамического размещения локальных переменных в функциях, передачи параметров в функцию и получения результатов ее работы. Регистр SP (stack pointer - указатель стека) указывает на вершину стека, адрес которой меняется. Основание стека - фиксированный адрес памяти.Размер стека динамически контролируется ядром.Операции push и pop непосредственно реализованы в процессоре.Стек логически подразделяется на фреймы, которые состоят из параметров, передающихся в функцию, локальных переменных функции и данных, необходимых для возврата в основную функцию. В зависимости от реализации, стек может расти либо вверх, либо вниз (используя адреса памяти в сторону уменьшения ).В наших примерах будет подразумеваться, что стек растет вниз. Этот вариант используется в процессорах Intel, Motorola, SPARC и MIPS.На что указывает SP, также зависит от реализации. Это может быть либо на последний элемент стека либо на следующий свободный адрес. Мы будем использовать первый вариант.
Итак,SP будет указывать на вершину стека (наименьшее значение из адресов памяти, используемых под стек).Часто удобно иметь указатель на какой-либо адрес внутри фрейма (FP frаme pointer). Некоторые источники называют его LB(local base ponter). Вообще, абсолютный адрес в стеке локальных переменных может быть получен с помощью смещения относительно SP. Однако по мере записи и чтения из стека эти смещения изменяются. Несмотря на то, что компилятор следит за количеством данных в стеке и соответственно корректирует эти смещения, бывают ситуации, когда это становится невозможным, и требуется дополнительное вмешательство. К тому же для некоторых процессоров (например ,Intel) , доступ к переменной с известным смещением требует нескольких операций. Поэтому многие компиляторы используют второй регистр ,FP, для ссылки на локальные переменные и параметры, так как их смещение относительно FP не изменяется по мере использования операций push и pop. В процессорах Intel для этой цели используется регистр BP( EBP ), в Motorola - для этого можно использовать любой адресный регистр, кроме А7. Поскольку в нашем случае стек растет вниз, то смещения для доступа к параметрам будут положительными, а для локальных переменных относительно FP отрицательными. Первое, что должна сделать функция, после своего вызова - сохранить предыдущее значение FP, иначе оно не сможет быть восстановлено после того, как она отработает. Затем происходит копирование SP в FP с целью создания нового FP и уменьшается значение SP для резервирования места под локальные переменные функции. Этот алгоритм называет входом в процедуру. После завершения работы функции стек должен иметь первоначальный вид.
В стековой памяти (памяти магазинного типа, организованной по принципу «Последним вошел – первым вышел» - LIFO – "Last In - First Out”) все операции чтения и записи осуществляются относительно указателя стека (SP-stack pointer). Указатель стека указывает на ячейку памяти, содержащую последнее внесенное в стек слово. Стековая память может организовываться программно-аппаратным или аппаратным способом. Команды обращения к стеку не содержат адресной части, либо эта часть является относительной величиной, прибавляемой к
указателю. Это позволяет сократить длину программы, так как нет необходимости указывать достаточно длинные адреса, а также – упростить схему ЗУ при аппаратной реализации стека.
В то же время при работе со стековой памятью приходится осуществлять фактически последовательный доступ, кроме того, может происходить т.н. переполнение стека – при попытке записать в полностью заполненный стек очередное значение, либо при считывании из пустого стека.
Использование стековой памяти будет более эффективным, если процессор, работающий со стеком, будет поддерживать специальные стековые команды - не только «занести в стек» и «считать из стека», но и такие, как - «сложить два числа на вершине стека», «переставить элементы стека» и т.д.
Такие команды часто используются в RISC-процессорах, в микроконтроллерах,