WikiSort.ru - Программирование

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

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

Бесконечная рекурсия

Простейший пример бесконечной рекурсии на Си:

int foo() {
     return foo();
}

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

Это рафинированный пример, и в реальном коде бесконечная рекурсия может появиться по двум причинам:

int factorial (int n)
{
  if (n == 0)
    return 1;
  return n * factorial(n - 1);
}

int Obj::getData(int index, bool& isChangeable)
{
  isChangeable = true;
  return getData(index);
}

int Obj::getData(int index)
{
  bool noMatter;
  return getData(index, noMatter);
}

Очень глубокая рекурсия

Уничтожить односвязный список можно таким кодом:

void destroyList(struct Item* it)
{
    if (it == NULL)
        return;
    destroyList(it->next);
    free(it);
}

Этот алгоритм, если список не испорчен, теоретически выполнится за конечное время, затребовав при этом O(n) стека. Разумеется, при длинном списке программа откажет. Возможные решения:

• Найти нерекурсивный алгоритм (работает в данном примере).
• Перенести рекурсию из системного стека в динамически выделяемый (например, при обходе разного рода сетей^[5]).
• Если рекурсия зашла глубоко, применять другой метод. Например, быстрая сортировка — чрезвычайно эффективный метод сортировки, который в крайних случаях может задействовать немалый объём стека. Поэтому реализации сортировки в языках программирования ограничивают глубину рекурсии, а если «упёрлись» в предел, используют более медленные методы наподобие пирамидальной. Так работает, например, Introsort.

Большие переменные в стеке

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

Пример на Си:

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

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

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

См. также

• Переполнение буфера
• Стек вызовов
• Переполнение памяти
• Ошибка на единицу

Примечания