Переполнение стека
В программном обеспечении переполнение стека происходит, если указатель стека вызовов превышает границу стека . Стек вызовов может состоять из ограниченного объема адресного пространства , часто определяемого в начале программы. Размер стека вызовов зависит от многих факторов, включая язык программирования, архитектуру машины, многопоточность и объем доступной памяти. Когда программа пытается использовать больше места, чем доступно в стеке вызовов (то есть, когда она пытается получить доступ к памяти за пределами стека вызовов, что по сути является переполнением буфера ), говорят, что стек переполняется , что обычно приводит к ошибке программы сбой . [1]
Причины [ править ]
Бесконечная рекурсия [ править ]
Наиболее распространенной причиной переполнения стека является чрезмерно глубокая или бесконечная рекурсия, при которой функция вызывает себя так много раз, что пространство, необходимое для хранения переменных и информации, связанной с каждым вызовом, превышает размер стека. [2]
Пример бесконечной рекурсии C. в
int foo()
{
return foo();
}
Функция foo при ее вызове продолжает вызывать саму себя, каждый раз выделяя дополнительное пространство в стеке, пока стек не переполнится, что приведет к ошибке сегментации . [2] Однако некоторые компиляторы реализуют оптимизацию хвостовых вызовов , позволяющую осуществлять бесконечную рекурсию определенного типа — хвостовую рекурсию — без переполнения стека. Это работает, поскольку вызовы хвостовой рекурсии не занимают дополнительного места в стеке. [3]
Некоторые параметры компилятора C позволяют эффективно оптимизировать хвостовой вызов ; например, скомпилировав приведенную выше простую программу с использованием gcc с -O1 приведет к ошибке сегментации, но не при использовании -O2 или -O3, поскольку эти уровни оптимизации предполагают -foptimize-sibling-calls вариант компилятора. [4] Другие языки, такие как Scheme , требуют, чтобы все реализации включали хвостовую рекурсию как часть стандарта языка. [5]
Очень глубокая рекурсия [ править ]
Рекурсивную функцию, которая теоретически завершается, но на практике вызывает переполнение буфера стека вызовов, можно исправить, превратив рекурсию в цикл и сохранив аргументы функции в явном стеке (вместо неявного использования стека вызовов). Это всегда возможно, поскольку класс примитивно-рекурсивных функций эквивалентен классу LOOP-вычислимых функций. Рассмотрим этот пример в псевдокоде, подобном C++ :
void function (argument)
{
if (condition)
function (argument.next);
}
|
stack.push(argument);
while (!stack.empty())
{
argument = stack.pop();
if (condition)
stack.push(argument.next);
}
|
Примитивную рекурсивную функцию, подобную той, что изображена слева, всегда можно преобразовать в цикл, подобный изображенному в правой части.
Функция, подобная приведенному выше примеру слева, не будет проблемой в среде, поддерживающей оптимизацию хвостового вызова ; однако в этих языках все еще возможно создать рекурсивную функцию, которая может привести к переполнению стека. Рассмотрим приведенный ниже пример двух простых целочисленных функций возведения в степень.
int pow(int base, int exp) {
if (exp > 0)
return base * pow(base, exp - 1);
else
return 1;
}
|
int pow(int base, int exp) {
return pow_accum(base, exp, 1);
}
int pow_accum(int base, int exp, int accum) {
if (exp > 0)
return pow_accum(base, exp - 1, accum * base);
else
return accum;
}
|
Оба pow(base, exp) приведенные выше функции вычисляют эквивалентный результат, однако функция слева склонна вызывать переполнение стека, поскольку для этой функции невозможна оптимизация хвостового вызова. Во время выполнения стек этих функций будет выглядеть так:
pow(5, 4)
5 * pow(5, 3)
5 * (5 * pow(5, 2))
5 * (5 * (5 * pow(5, 1)))
5 * (5 * (5 * (5 * pow(5, 0))))
5 * (5 * (5 * (5 * 1)))
625
|
pow(5, 4)
pow_accum(5, 4, 1)
pow_accum(5, 3, 5)
pow_accum(5, 2, 25)
pow_accum(5, 1, 125)
pow_accum(5, 0, 625)
625
|
Обратите внимание, что функция слева должна хранить в своем стеке exp количество целых чисел, которое будет умножено, когда рекурсия завершится и функция вернет 1. Напротив, функция справа должна хранить только 3 целых числа в любой момент времени и вычисляет промежуточный результат, который передается ее следующему вызову. Поскольку никакая другая информация, кроме текущего вызова функции, храниться не должна, оптимизатор хвостовой рекурсии может «отбросить» предыдущие кадры стека, исключая возможность переполнения стека.
Очень большие переменные стека [ править ]
Другая основная причина переполнения стека возникает в результате попытки выделить в стеке больше памяти, чем поместится, например, путем создания слишком больших переменных локального массива. По этой причине некоторые авторы рекомендуют выделять массивы размером более нескольких килобайт динамически, а не в виде локальной переменной. [6]
Пример очень большой переменной стека в C :
int foo()
{
double x[1048576];
}
В реализации C с 8-байтовыми числами двойной точности объявленный массив потребляет 8 мегабайт данных; если это больше памяти, чем доступно в стеке (как установлено параметрами создания потока или ограничениями операционной системы), произойдет переполнение стека.
Переполнение стека усугубляется всем, что уменьшает эффективный размер стека данной программы. Например, одна и та же программа, запущенная без нескольких потоков, может работать нормально, но как только многопоточность будет включена, программа выйдет из строя. Это связано с тем, что большинство программ с потоками имеют меньше места в стеке на поток, чем программы без поддержки потоков. Поскольку ядра, как правило, являются многопоточными, людям, плохо знакомым с разработкой ядра, обычно не рекомендуется использовать рекурсивные алгоритмы или большие буферы стека. [7]
См. также [ править ]
Ссылки [ править ]
- ^ Берли, Джеймс Крейг (1 июня 1991 г.). «Использование и портирование GNU Fortran» . Архивировано из оригинала 6 февраля 2012 г.
- ↑ Перейти обратно: Перейти обратно: а б В чем разница между ошибкой сегментации и переполнением стека? Архивировано 13 сентября 2021 г. на Wayback Machine в Stack Overflow.
- ^ «Введение в схему и ее реализация» . 19 февраля 1997 г. Архивировано из оригинала 10 августа 2007 г.
- ^ «Использование коллекции компиляторов GNU (GCC): параметры оптимизации» . Архивировано из оригинала 20 августа 2017 г. Проверено 20 августа 2017 г.
- ^ Ричард Келси; Уильям Клингер; Джонатан Рис; и др. (август 1998 г.). «Пересмотренный 5 Отчет об алгоритмической языковой схеме» . Вычисления высшего порядка и символические вычисления . 11 (1): 7–105. doi : 10.1023/A:1010051815785 S2CID 14069423. Архивировано . из оригинала 05 января 2007 г. Проверено 8 января 2012 г. -09 .
- ^ Фельдман, Ховард (23 ноября 2005 г.). «Современное управление памятью, часть 2» . Архивировано из оригинала 20 сентября 2012 г. Проверено 14 августа 2007 г.
- ^ «Руководство по программированию ядра: советы по производительности и стабильности» . Apple Inc. 2 мая 2014 г. Архивировано из оригинала 3 мая 2014 г. Проверено 2 мая 2014 г.
Внешние ссылки [ править ]
- Причины, по которым 64-битным программам требуется больше стековой памяти. Архивировано 4 ноября 2017 г. на Wayback Machine.
| Аппаратное обеспечение |
|
|---|---|
| Виртуальная память | |
| Сегментация памяти | |
| Распределитель памяти | |
| Ручное управление памятью | |
| Сбор мусора | |
| Безопасность памяти | |
| Проблемы | |
| Другой | |
