Переполнение стека

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В программном обеспечении переполнение стека (англ. stack overflow) возникает, когда в стеке вызовов хранится больше информации, чем он может держать. Обычно ёмкость стека задаётся при старте программы/потока. Когда указатель стека выходит за границы, программа аварийно завершает работу.[1]

Эта ошибка случается по двум причинам.[2]

Бесконечная рекурсия[править | править исходный текст]

Основная причина переполнения стека — излишне глубокая или бесконечная рекурсия. Простейший пример бесконечной рекурсии на Си:

int foo() {
     return foo();
}

Функция будет вызывать сама себя, расходуя пространство в стеке, пока стек не переполнится и не случится ошибка сегментации.[3]

Многие языки делают оптимизацию, именуемую «хвостовая рекурсия». Рекурсия, находящаяся в конце функции, превращается в цикл и не расходует стека.[4]

Большие переменные в стеке[править | править исходный текст]

Вторая большая причина переполнения стека — одноразовое выделение огромного количества памяти крупными локальными переменными. Многие авторы рекомендуют выделять память, превышающую несколько килобайт, в «куче», а не на стеке.[5]

Пример на Си:

int foo() {
     double x[1000000];
}

Массив занимает 8 мегабайт памяти; если в стеке нет такого количества памяти, случится переполнение.

Всё, что уменьшает эффективный размер стека, увеличивает риск переполнения. Например, потоки обычно берут стека меньше, чем основная программа — поэтому программа может работать в однопоточном режиме и отказывать в многопоточном. Работающие в режиме ядра подпрограммы часто пользуются чужим стеком, поэтому при программировании в режиме ядра стараются не применять рекурсию и большие локальные переменные.[6][7]

См. также[править | править исходный текст]

Примечания[править | править исходный текст]