Структуры данных: стек на аппаратном уровне
Обычное использование стеков на уровне архитектуры - это средство выделения и доступа к памяти.
Базовая архитектура стека
Типичный стек - это область памяти компьютера с фиксированным началом и переменным размером. Первоначально размер стека равен нулю. Указатель стека, обычно в форме аппаратного регистра, указывает на самое последнее упомянутое местоположение в стеке; когда размер стека равен нулю, указатель стека указывает на начало стека.
Две операции, применимые ко всем стекам:
- операция push, в которой элемент данных размещается в месте, указанном указателем стека, а адрес в указателе стека регулируется размером элемента данных;
- операция pop или pull: элемент данных в текущем местоположении, на который указывает указатель стека, удаляется, а указатель стека регулируется размером элемента данных.
Существует много вариантов базового принципа стековых операций. Каждый стек имеет фиксированное место в памяти, с которого он начинается. Когда элементы данных добавляются в стек, указатель стека смещается, чтобы указать текущий экстент стека, который расширяется от источника.
Указатели стека могут указывать на источник стека или на ограниченный диапазон адресов выше или ниже источника (в зависимости от направления, в котором растет стек); однако указатель стека не может пересекать начало стека. Другими словами, если источник стека находится по адресу 1000, а стек растет вниз (к адресам 999, 998 и т.д.), Указатель стека никогда не должен увеличиваться больше 1000 (до 1001, 1002 и т.д.). Если операция pop в стеке приводит к перемещению указателя стека за начало стека, происходит переполнение стека. Если операция push вызывает увеличение или уменьшение указателя стека сверх максимального размера стека, происходит переполнение стека.
В некоторых средах, которые сильно зависят от стеков, могут быть предусмотрены дополнительные операции, например:
- Дублировать (duplicate): верхний элемент выталкивается, а затем Добавляется (push) снова (дважды), так что дополнительная копия прежнего верхнего элемента теперь находится сверху, а оригинал - под ним.
- Просмотр (peek): самый верхний элемент проверяется (или возвращается), но указатель стека и размер стека не изменяются (это означает, что элемент остается в стеке). Это также часто называется top операцией.
- Обмен (swap или exchange): два верхних предмета в стеке меняются местами.
- Поворот (или вращение) (rotate или roll): n верхних элементов перемещаются в стеке вращающимся способом. Например, если n = 3, элементы 1, 2 и 3 в стеке перемещаются в позиции 2, 3 и 1 в стеке соответственно. Возможны многие варианты этой операции, наиболее распространенным из которых является поворот влево и поворот вправо.
Стеки часто визуализируются растущими снизу вверх (как в реальных стеках). Они также могут быть визуализированы растущими слева направо, так что "самый верхний" становится "самым правым", или даже растущий сверху вниз. Важной особенностью является то, что дно стека находится в фиксированном положении.
При повороте вправо первый элемент переместится в третью позицию, вторая - в первую, а третья - во вторую. Вот две эквивалентные визуализации этого процесса:
apple banana
banana ===right rotate==> cucumber
cucumber apple
cucumber apple
banana ===left rotate==> cucumber
apple banana
Стек обычно представлен в компьютерах блоком ячеек памяти с фиксированным местоположением "дна" (bottom) и указателем стека, содержащим адрес текущей "верхней" (top) ячейки в стеке. top и bottom терминология используются независимо от того, действительно ли стек увеличивается в сторону более низких адресов памяти или более высоких адресов памяти.
При добавлении элемента в стек указатель стека корректируется по размеру элемента (уменьшающегося или увеличивающегося в зависимости от направления роста стека в памяти), указывая на следующую ячейку и копируя новый верхний элемент в область стека. Опять же, в зависимости от конкретной реализации, в конце операции push указатель стека может указывать на следующее неиспользуемое место в стеке или указывать на самый верхний элемент в стеке. Если стек указывает на текущий верхний элемент, указатель стека будет обновлен до того, как новый элемент будет помещен в стек; если он указывает на следующее доступное место в стеке, он будет обновлен после того, как новый элемент помещен в стек.
Удаление (pop) элемента из стека - это просто обратная сторона push. Самый верхний элемент в стеке удаляется, а указатель стека обновляется в порядке, противоположном тому, который используется в операции push.
Стек в основной памяти
Многие конструкции ЦП CISC-типа, включая x86, Z80 и 6502, имеют выделенный регистр для использования в качестве указателя стека вызовов со специальными инструкциями call, return, push и pop, которые неявно обновляют выделенный регистр, таким образом увеличивая плотность кода. Некоторые процессоры CISC, такие как PDP-11 и 68000, также имеют специальные режимы адресации для реализации стеков, как правило, с полуотделенным указателем стека (например, A7 в 68000). Напротив, большинство конструкций ЦП RISC не имеют выделенных инструкций стека, и поэтому большинство, если не все регистры, могут быть использованы в качестве указателей стека по мере необходимости.
Стек в регистрах или выделенной памяти
Архитектура с плавающей запятой x87 является примером набора регистров, организованных в виде стека, где также возможен прямой доступ к отдельным регистрам (относительно текущей вершины). Как и в случае со стековыми машинами в целом, использование вершины стека в качестве неявного аргумента позволяет использовать небольшой машинный код с хорошим использованием пропускной способности шины и кэшей кода, но также предотвращает некоторые типы оптимизации, которые возможны на процессорах, позволяющих произвольный доступ к регистровому файлу для всех (двух или трех) операндов. Структура стека также делает суперскалярные реализации с переименованием регистров (для умозрительного выполнения) несколько более сложными для реализации, хотя это все еще выполнимо, о чем свидетельствуют современные реализации x87.
Sun SPARC, AMD Am29000 и Intel i960 - все это примеры архитектур, использующих окна регистров в стеке регистров в качестве еще одной стратегии, позволяющей избежать использования медленной основной памяти для аргументов функций и возвращаемых значений.
Существует также ряд небольших микропроцессоров, которые реализуют стек непосредственно в оборудовании, а некоторые микроконтроллеры имеют стек фиксированной глубины, который не доступен напрямую. Примерами являются микроконтроллеры PIC, Computer Cowboys MuP21, линейка Harris RTX и Novix NC4016. Многие основанные на стеке микропроцессоры использовались для реализации языка программирования Forth на уровне микрокода. Стеки также использовались в качестве основы для ряда мэйнфреймов и мини-компьютеров. Такие машины назывались стековыми машинами, самой известной из которых является Burroughs B5000.
Читайте также:
Комментарии
Отправить комментарий