Стеки в вычислительных архитектурах — это области памяти , в которых данные добавляются или удаляются по принципу «последним пришел — первым обслужен» (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 .
В Microsoft Windows существует более безопасная версия allocacall _malloca, которая выполняет выделение в куче, если размер выделения слишком велик, и сообщает об ошибках переполнения стека. Это требует использования _freea. [6] gnulib предоставляет эквивалентный интерфейс, хотя вместо выдачи исключения SEH при переполнении он делегирует его mallocпри обнаружении слишком большого размера. [7] Подобную функцию можно эмулировать с помощью ручного учета и проверки размера, например, при использовании alloca_accountв glibc. [8]
Некоторые семейства процессоров, такие как x86 , имеют специальные инструкции для управления стеком текущего выполняющегося потока. Другие семейства процессоров, включая RISC-V , PowerPC и MIPS , не имеют явной поддержки стека, а вместо этого полагаются на соглашение и делегируют управление стеком двоичному интерфейсу приложений (ABI) операционной системы .
Кроме того, начиная с версии C C99 (необязательно, начиная с C11), можно автоматически создавать массив в стеке внутри функции, известной как auto VLA ( массив переменной длины ). [9]
void f ( int arrayLength ) { int b [ arrayLength ]; // auto VLA - длина этого массива устанавливается // во время вызова функции/генерации стека. for ( int я = 0 ; я < arrayLength ; я ++ ) б [ я ] = 1 ; // в конце этой функции b[] находится внутри кадра стека и // исчезнет при выходе из функции, поэтому явный вызов free() не требуется. }