Стеки в вычислительных архитектурах — это области памяти , в которых данные добавляются или удаляются по принципу «последним пришел — первым ушел» (LIFO) .
В большинстве современных компьютерных систем каждый поток имеет зарезервированную область памяти, называемую его стеком. Когда функция выполняется, она может добавлять некоторые из своих локальных данных состояния в верхнюю часть стека; когда функция завершает работу, она отвечает за удаление этих данных из стека. Как минимум, стек потока используется для хранения местоположения адреса возврата, предоставленного вызывающей стороной, чтобы позволить операторам возврата вернуться в правильное местоположение.
Стек часто используется для хранения переменных фиксированной длины, локальных для текущих активных функций. Программисты могут также явно использовать стек для хранения локальных данных переменной длины. Если область памяти лежит в стеке потока, то говорят, что эта память была выделена в стеке, т. е. распределение памяти на основе стека (SBMA). Это контрастирует с распределением памяти на основе кучи (HBMA). SBMA часто тесно связана со стеком вызовов функций .
Поскольку данные добавляются и удаляются по принципу «последним пришел — первым ушел», распределение памяти на основе стека очень простое и, как правило, намного быстрее, чем распределение памяти на основе кучи (также известное как динамическое распределение памяти ), например, в языке C.malloc
Другая особенность заключается в том, что память в стеке автоматически и очень эффективно освобождается при выходе из функции, что может быть удобно для программиста, если данные больше не требуются. [1] (То же самое относится к longjmp , если он переместился в точку до того, как произошел вызов alloca.) Однако, если данные необходимо сохранить в какой-либо форме, их необходимо скопировать из стека в кучу до выхода из функции. Поэтому распределение на основе стека подходит для временных данных или данных, которые больше не требуются после выхода из текущей функции.
Назначенный размер стека потока может быть всего лишь несколькими байтами на некоторых небольших процессорах. Выделение большего объема памяти в стеке, чем доступно, может привести к сбою из-за переполнения стека . Вот почему функции, которые используют , allocaобычно не допускают встраивания: [2] если такая функция будет встраиваться в цикл, вызывающая сторона пострадает от непредвиденного роста использования стека, что значительно повысит вероятность переполнения.
Стековое распределение также может вызывать незначительные проблемы с производительностью: оно приводит к кадрам стека переменного размера, поэтому необходимо управлять указателями стека и кадра (при фиксированном размере кадра стека указатель стека избыточен из-за умножения указателя кадра стека на размер каждого кадра). Обычно это намного менее затратно, чем вызов mallocи freeв любом случае. В частности, если текущая функция содержит как вызовы, так allocaи блоки, содержащие локальные данные переменной длины, то возникает конфликт между попытками alloca увеличить текущий кадр стека до тех пор, пока текущая функция не завершит работу, и необходимостью компилятора размещать локальные переменные переменной длины в том же месте в кадре стека. Этот конфликт обычно разрешается путем создания отдельной цепочки хранения кучи для каждого вызова alloca. [3] Цепочка записывает глубину стека, на которой происходит каждое выделение, последующие вызовы allocaв любой функции обрезают эту цепочку до текущей глубины стека, чтобы в конечном итоге (но не сразу) освободить любое хранилище в этой цепочке. Вызов allocaс аргументом, равным нулю, также может использоваться для запуска освобождения памяти без выделения дополнительной такой памяти. Вследствие этого конфликта между allocaи локальным хранилищем переменных использование allocaможет оказаться не более эффективным, чем использование malloc.
Многие Unix-подобные системы, а также Microsoft Windows реализуют функцию, вызываемую allocaдля динамического выделения стековой памяти способом, аналогичным основанному на куче malloc. Компилятор обычно транслирует ее во встроенные инструкции, манипулирующие указателем стека, аналогично тому, как обрабатываются массивы переменной длины . [4] Хотя нет необходимости явно освобождать память, существует риск неопределенного поведения из-за переполнения стека. [5] Функция присутствовала в системах Unix еще в 32/V (1978), но не является частью стандарта C или любого стандарта POSIX .
Более безопасная версия , allocaназываемая _malloca, которая выделяет память в куче, если размер выделения слишком велик, и сообщает об ошибках переполнения стека, существует в Microsoft Windows. Она требует использования _freea. [6] gnulib предоставляет эквивалентный интерфейс, хотя вместо того, чтобы выдавать исключение SEH при переполнении, он делегирует , mallocкогда обнаруживается слишком большой размер. [7] Похожую функцию можно эмулировать с помощью ручного учета и проверки размера, например, при использовании в alloca_accountglibc. [8]
Некоторые семейства процессоров, такие как x86 , имеют специальные инструкции для управления стеком текущего исполняемого потока. Другие семейства процессоров, включая RISC-V , PowerPC и MIPS , не имеют явной поддержки стека, а вместо этого полагаются на соглашение и делегируют управление стеком двоичному интерфейсу приложений операционной системы (ABI).
Кроме того, начиная с версии C C99 (необязательно с C11), можно автоматически создавать массив в стеке внутри функции, что известно как auto VLA ( массив переменной длины ). [9]
void f ( int arrayLength ) { int b [ arrayLength ]; // auto VLA — длина этого массива устанавливается во время вызова функции/генерации стека. for ( int i = 0 ; i < arrayLength ; i ++ ) b [ i ] = 1 ; // в конце этой функции b[] находится внутри стекового фрейма и исчезнет при выходе из функции, поэтому явный вызов free() не требуется. }