Почему стек вызовов имеет статический максимальный размер?

Работая с несколькими языками программирования, я всегда задавался вопросом, почему стек потоков имеет предопределенный максимальный размер, а не расширяется автоматически по мере необходимости. 

Для сравнения, некоторые очень распространенные высокоуровневые структуры (списки, карты и т. Д.), Встречающиеся в большинстве языков программирования, разрабатываются по мере необходимости при добавлении новых элементов, ограничиваясь по размеру только доступной памятью или вычислительными ограничениями ( например, 32-битная адресация).

Я не знаю ни о каких языках программирования или средах выполнения, где максимальный размер стека не ограничен каким-либо параметром по умолчанию или компилятором. Вот почему слишком большая рекурсия очень быстро приведет к вездесущей ошибке / исключению переполнения стека, даже если для стека используется только минимальный процент памяти, доступной для процесса.

Почему в большинстве (если не во всех) средах выполнения установлен максимальный предел размера, который стек может увеличивать во время выполнения?

Можно написать операционную систему, которая не требует, чтобы стеки были непрерывными в адресном пространстве. По сути, вам нужно немного поработать в соглашении о вызовах, чтобы убедиться, что:

1. если в текущем экстенте стека недостаточно места для вызываемой функции, вы создаете новый экстент стека и перемещаете указатель стека, чтобы он указывал на начало его как часть выполнения вызова.

2. когда вы возвращаетесь из этого вызова, вы переводите обратно в исходный экстент стека. Скорее всего, вы сохраните созданный в (1) для последующего использования тем же потоком. В принципе, вы можете освободить его, но в этом случае возникают довольно неэффективные случаи, когда вы продолжаете перебегать назад и вперед через границу в цикле, и каждый вызов требует выделения памяти.

3. setjmpи longjmp, или любой другой эквивалент, который ваша ОС имеет для нелокальной передачи управления, включен в действие и может корректно вернуться к старому стековому экстенту, когда потребуется.

Я говорю «соглашение о вызовах» - если быть точным, я думаю, что это, вероятно, лучше всего делать в прологе функции, а не в вызывающей стороне, но моя память об этом туманна.

Причина, по которой довольно много языков задают фиксированный размер стека для потока, заключается в том, что они хотят работать с использованием собственного стека в ОС, которые этого не делают. Как и ответы всех остальных, в предположении, что каждый стек должен быть смежным в адресном пространстве и не может быть перемещен, вам необходимо зарезервировать определенный диапазон адресов для использования каждым потоком. Это означает, что нужно выбрать размер заранее. Даже если ваше адресное пространство огромно, а выбранный вами размер действительно велик, вам все равно придется выбирать его, как только у вас будет два потока.

«Ага, - говорите вы, - что это за предполагаемые ОС, которые используют несмежные стеки? Держу пари, это какая-то неясная академическая система, которая мне не нужна!». Ну, это еще один вопрос, который, к счастью, уже задан и дан ответ.

Эти структуры данных обычно имеют свойства, которых нет у стека ОС:

• Связанные списки не требуют непрерывного адресного пространства. Таким образом, они могут добавить часть памяти, где они хотят, когда они растут.

• Даже коллекции, которым требуется непрерывное хранилище, например вектор C ++, имеют преимущество перед стеками ОС: они могут объявлять все указатели / итераторы недействительными, когда они растут. С другой стороны, стек ОС должен сохранять указатели на стек действительными до тех пор, пока не вернется функция, кадру которой принадлежит цель.

Язык программирования или среда выполнения могут выбрать реализацию своих собственных стеков, которые являются несмежными или подвижными, чтобы избежать ограничений стеков ОС. Golang использует такие пользовательские стеки для поддержки очень большого числа сопрограмм, первоначально реализованных в виде несмежной памяти, а теперь через подвижные стеки благодаря отслеживанию указателя (см. Комментарий Хобба). Python без стеков, Lua и Erlang также могут использовать собственные стеки, но я не подтвердил это.

В 64-битных системах вы можете настроить относительно большие стеки с относительно низкой стоимостью, поскольку адресного пространства достаточно, и физическая память выделяется только при его фактическом использовании.

На практике это сложно (а иногда и невозможно) увеличить стек. Чтобы понять, почему требуется некоторое понимание виртуальной памяти.

В старые времена однопоточных приложений и непрерывной памяти три составляли три компонента адресного пространства процесса: код, куча и стек. То, как эти три были разбиты, зависело от ОС, но, как правило, сначала шел код, начиная с нижней части памяти, затем следовала куча, которая росла вверх, а стек начинался сверху памяти и рос вниз. Была также некоторая память, зарезервированная для операционной системы, но мы можем игнорировать это. Программы в те дни имели несколько более драматические переполнения стека: стек мог вылетать в кучу, и в зависимости от того, что обновлялось первым, вы либо работали с неверными данными, либо возвращались из подпрограммы в какую-то произвольную часть памяти.

Управление памятью несколько изменило эту модель: с точки зрения программы у вас все еще были три компонента карты памяти процесса, и они в целом были организованы одинаково, но теперь каждый из компонентов управлялся как независимый сегмент, и MMU будет сигнализировать ОС, если программа пыталась получить доступ к памяти вне сегмента. Когда у вас была виртуальная память, не было необходимости или желания предоставлять программе доступ ко всему ее адресному пространству. Таким образом, сегментам были назначены фиксированные границы.

Так почему же нежелательно предоставлять программе доступ ко всему ее адресному пространству? Потому что эта память представляет собой «поручить» против обмена; в любой момент может понадобиться перезаписать любую или всю память для одной программы, чтобы освободить место для памяти другой программы. Если каждая программа потенциально может потребовать 2 ГБ подкачки, то вам нужно будет предоставить достаточно подкачки для всех ваших программ или воспользоваться тем, что двум программам потребуется больше, чем они могут получить.

На этом этапе, при условии достаточного виртуального адресного пространства, вы можете расширить эти сегменты, если это необходимо, и сегмент данных (куча) действительно со временем увеличивается: вы начинаете с небольшого сегмента данных, и когда распределитель памяти запрашивает больше места, когда это нужно На этом этапе с помощью одного стека физически можно было бы расширить сегмент стека: ОС могла бы перехватить попытку вытолкнуть что-то за пределы сегмента и добавить больше памяти. Но это тоже не особо желательно.

Введите многопоточность. В этом случае каждый поток имеет независимый сегмент стека, опять же фиксированный размер. Но теперь сегменты располагаются один за другим в виртуальном адресном пространстве, поэтому невозможно расширить один сегмент, не перемещая другой - что вы не можете сделать, потому что программа потенциально может иметь указатели на память, находящуюся в стеке. Вы также можете оставить некоторое пространство между сегментами, но это пространство будет потрачено впустую почти во всех случаях. Лучшим подходом было возложить бремя на разработчика приложений: если вам действительно нужны глубокие стеки, вы можете указать это при создании потока.

Сегодня, с 64-битным виртуальным адресным пространством, мы можем создавать эффективно бесконечные стеки для практически бесконечного числа потоков. Но опять же, это не особенно желательно: почти во всех случаях переполнение стека указывает на ошибку в вашем коде. Предоставление вам стека в 1 ГБ просто откладывает обнаружение этой ошибки.

Стек, имеющий фиксированный максимальный размер, не является вездесущим.

Также трудно получить правильные результаты: глубина стека соответствует распределению по степенному закону, что означает, что независимо от того, насколько мал размер стека, вы будете иметь значительную долю функций с еще меньшими стеками (т. Е. Вы тратите пространство), и независимо от того, насколько большой вы его сделаете, все равно будут функции с еще большими стеками (поэтому вы вызываете ошибку переполнения стека для функций, которые не имеют ошибок). Другими словами: какой бы размер вы ни выбрали, он всегда будет и слишком маленьким, и слишком большим одновременно.

Вы можете исправить первую проблему, позволив стекам начинаться с малого и динамически расти, но тогда у вас все еще будет вторая проблема. И если в любом случае вы позволяете стеку динамически расти, тогда зачем устанавливать на него произвольное ограничение?

Существуют системы, в которых стеки могут динамически расти и не иметь максимального размера: например, Erlang, Go, Smalltalk и Scheme. Есть много способов реализовать что-то подобное:

• подвижные стеки: когда непрерывный стек больше не может расти, потому что на пути есть что-то еще, переместите его в другое место в памяти, с большим количеством свободного места
• непрерывные стеки: вместо выделения всего стека в одном непрерывном пространстве памяти, выделите его в нескольких пространствах памяти
• стеки, выделенные для кучи: вместо того, чтобы иметь отдельные области памяти для стека и кучи, просто выделите стек в куче; Как вы сами заметили, структуры данных, выделенные в куче, обычно не имеют проблем с ростом и сокращением по мере необходимости.
• не использовать стеки вообще: это также опция, например, вместо отслеживания состояния функции в стеке, пусть функция передает продолжение вызываемой стороне.

Как только у вас появятся мощные нелокальные конструкции потока управления, идея единого непрерывного стека в любом случае уходит в окно: например, возобновляемые исключения и продолжения «разветвляют» стек, так что вы фактически получаете сеть стеков (например, реализовано с помощью стека спагетти). Кроме того, системы с первоклассными модифицируемыми стеками, такие как Smalltalk, в значительной степени требуют стеки спагетти или что-то подобное.

ОС должна выдавать непрерывный блок при запросе стека. Единственный способ сделать это - указать максимальный размер.

Например, предположим, что во время запроса память выглядит следующим образом (X представляют использованные, а неиспользуемые):

XOOOXOOXOOOOOX

Если запрос на размер стека равен 6, ОС ответит «нет», даже если доступно более 6. Если запрос на стек размером 3, ответ ОС будет одной из областей 3 пустых слотов (Os) подряд.

Кроме того, можно увидеть трудности с разрешением роста, когда занят следующий слот.

Другие упомянутые объекты (списки и т. Д.) Не попадают в стек, они оказываются в куче в несмежных или фрагментированных областях, поэтому, когда они растут, они просто захватывают пространство, им не требуются смежные, как они есть управлял по-разному.

Большинство систем устанавливают разумное значение для размера стека, вы можете переопределить его при создании потока, если требуется больший размер.

В Linux это чисто ресурсный лимит, который существует для уничтожения сбежавших процессов до того, как они потребят вредоносное количество ресурса. В моей системе Debian следующий код

#include <sys/resource.h>
#include <stdio.h>

int main() {
    struct rlimit limits;
    getrlimit(RLIMIT_STACK, &limits);
    printf("   soft limit = 0x%016lx\n", limits.rlim_cur);
    printf("   hard limit = 0x%016lx\n", limits.rlim_max);
    printf("RLIM_INFINITY = 0x%016lx\n", RLIM_INFINITY);
}

производит вывод

   soft limit = 0x0000000000800000
   hard limit = 0xffffffffffffffff
RLIM_INFINITY = 0xffffffffffffffff

Обратите внимание, что для жесткого ограничения установлено значение RLIM_INFINITY: процессу разрешено повышать свой мягкий предел до любой величины. Однако, если у программиста нет оснований полагать, что программе действительно нужны необычные объемы стековой памяти, процесс будет остановлен, когда он превысит размер стека в восемь мегабайт.

Из-за этого предела сбойный процесс (непреднамеренная бесконечная рекурсия) уничтожается задолго до того, как он начинает потреблять так много памяти, что система вынуждена начать обмен. Это может иметь значение между сбойным процессом и сбойным сервером. Однако это не ограничивает программы с законной потребностью в большом стеке, им просто нужно установить мягкое ограничение на какое-то подходящее значение.

Технически, стеки действительно растут динамически: если для soft-limit установлено восемь мегабайт, это не означает, что этот объем памяти фактически был отображен. Это было бы довольно расточительно, так как большинство программ никогда не приближаются к соответствующим программным ограничениям. Скорее, ядро ​​будет обнаруживать доступ ниже стека и просто отображать страницы памяти по мере необходимости. Таким образом, единственным реальным ограничением размера стека является доступная память в 64-битных системах (фрагментация адресного пространства является довольно теоретической при размере адресного пространства в 16 зебибайт).

Максимальный размер стека является статическим , потому что это определение «максимум» . Любой максимум на чем-либо является фиксированной, согласованной предельной величиной. Если он ведет себя как спонтанно движущаяся цель, это не максимум.

Стеки в операционных системах виртуальной памяти на самом деле растут динамически, до максимума .

Говоря об этом, это не должно быть статичным. Скорее, он может быть конфигурируемым, даже для каждого процесса или для каждого потока.

Если вопрос «почему это есть максимальный размер стеки» (искусственно ввел один, как правило , намного меньше , чем доступная память)?

Одна из причин заключается в том, что большинству алгоритмов не требуется огромное количество стекового пространства. Большой стек указывает на возможную рекурсию беглеца . Хорошо бы остановить убегающую рекурсию до того, как она выделит всю доступную память. Проблема, которая выглядит как убегающая рекурсия, заключается в использовании вырожденного стека, возможно, вызванного неожиданным тестовым примером. Например, предположим, что синтаксический анализатор для двоичного инфиксного оператора работает путем рекурсии правого операнда: синтаксический анализ первого операнда, оператор сканирования, синтаксический анализ остальной части выражения. Это означает , что глубина стека пропорциональна длине выражения: a op b op c op d .... Огромный тестовый пример этой формы потребует огромного стека. Прерывание программы, когда она достигает разумного предела стека, поймает это.

Другая причина фиксированного максимального размера стека состоит в том, что виртуальное пространство для этого стека может быть зарезервировано посредством специального вида отображения и, таким образом, гарантировано. Гарантированное означает, что пространство не будет отдано другому распределению, которое стек столкнется с ним перед достижением предела. Параметр максимального размера стека требуется для запроса этого отображения.

Потоки нуждаются в максимальном размере стека по аналогичной причине. Их стеки создаются динамически и не могут быть перемещены, если они сталкиваются с чем-то; виртуальное пространство должно быть зарезервировано заранее, и для этого выделения требуется размер.