Базовый CS с нуля
Стек и куча
Память — один длинный ряд байтово-адресуемых ячеек, это ты уже знаешь. Но программа не обращается к ячейкам случайным образом. Если посмотреть на адреса, к которым реально обращается работающая программа, обнаружится чёткая закономерность: одни адреса группируются вверху, другие — внизу, а середина почти не используется.
Это не случайность. Операционная система и CPU договариваются разбить адресное пространство на именованные области, у каждой из которых — своё назначение и свой срок жизни. Две самые важные области — это стек и куча. Понять их — значит понять, как любая программа, которую ты когда-либо напишешь, управляет своей памятью.
После этого урока ты сможешь описать адресное пространство как разбитое на области, объяснить, что такое область стека и почему она растёт и сжимается при вызовах функций, объяснить, что такое область кучи и почему она хранит долгоживущие данные, и указать, что обе области — части одной физической памяти.
Адресное пространство: взгляд программы на память. Работающая программа не видит напрямую аппаратную память. Операционная система предоставляет каждой программе приватный взгляд на память — её адресное пространство: диапазон адресов (например, от 0 до 2^64 − 1 на 64-битной ОС), которыми программа может пользоваться. ОС управляет отображением этого виртуального взгляда на реальную физическую оперативную память.
Внутри адресного пространства ОС и среда выполнения языка договариваются о разметке: определённые диапазоны адресов зарезервированы под определённые цели. Конкретная разметка различается между ОС, языками и архитектурами, но стек и куча присутствуют в каждом крупном языке и каждой ОС, всегда играя одни и те же роли.
Область стека: память, которая растёт и сжимается при вызовах функций. Стек — это область адресного пространства, управляемая автоматически. При каждом вызове функции система резервирует небольшой блок ячеек для исключительного использования этой функции — этот блок называется фреймом стека (или записью активации). Фрейм хранит локальные переменные функции, её параметры и служебную информацию (например, адрес возврата — куда продолжить выполнение после завершения функции).
Когда функция возвращается, её фрейм отбрасывается: те ячейки немедленно становятся доступными для повторного использования. Стек растёт при вызовах функций и сжимается при их возврате. В любой момент стек содержит ровно фреймы всех выполняющихся сейчас функций — цепочку вызовов от самой внешней функции до текущей.
Стек работает по принципу LIFO (последним вошёл — первым вышел). Порядок добавления и удаления фреймов подчиняется строгому правилу: последний добавленный фрейм всегда удаляется первым. Это называется LIFO (last-in, first-out). Представь стопку тарелок: новые тарелки кладёшь сверху и всегда снимаешь верхнюю. Нижняя тарелка уходит последней.
На стеке:
- Когда функция A вызывает функцию B, фрейм B добавляется поверх фрейма A.
- Когда B возвращается, фрейм B удаляется — теперь фрейм A снова на вершине.
- Фрейм A существовал до фрейма B и переживает его, как нижняя тарелка предшествует верхней и остаётся после её снятия.
Порядок LIFO — не произвольное конструкторское решение. Это следствие того, как вложены вызовы функций: самая недавно вызванная функция должна завершиться до того, как может продолжить вызывающая.
Область кучи: память, которая переживает один вызов функции. Куча — это область
адресного пространства для данных, которым нужно существовать дольше, чем один вызов
функции. В отличие от стека, куча не управляется автоматически. Программа явно запрашивает
блок ячеек из кучи (с помощью вызовов вроде malloc в C или new в Java/C++) и позже
явно освобождает его (free, delete или полагаясь на сборщик мусора — часть среды
выполнения языка, которая автоматически возвращает блоки кучи, которые программа больше
не использует).
Поскольку данные кучи могут пережить создавшую их функцию — и поскольку несколько функций могут держать указатели на один и тот же объект кучи — у кучи нет простого порядка LIFO. В ней может быть мозаика занятых и свободных блоков разного размера, созданных и освобождённых в разное время.
Почему это работает
Зачем вообще две области? Почему не одна?
Стек работает крайне быстро для распространённого случая: данные функции живут ровно столько, сколько выполняется функция, поэтому система может выделять и освобождать фреймы одним движением указателя — просто сдвигает одно число («указатель стека») вверх или вниз. Никакого поиска, никакого учёта свободных блоков.
Куча обрабатывает всё, с чем стек не справляется: данные, которые должны пережить создателя, большие объекты, размер которых неизвестен до запуска программы, объекты, разделяемые между многими функциями. Выделение и освобождение кучи дороже, потому что аллокатор должен находить и отслеживать доступные блоки. Две области позволяют программе платить меньшую цену там, где достаточно стекового времени жизни, и большую — только при необходимости.
Обе области — одна физическая память. Стек и куча — не разные аппаратные компоненты. Это оба диапазона адресов внутри одного плоского ряда байтово-адресуемых ячеек, о которых ты узнал в первом уроке этого блока. Разница — только в способе управления и сроке жизни данных, а не в том, чем являются нижележащие ячейки.
В 64-битном процессе Linux, например, стек занимает область в верхней части адресного пространства, а куча — в нижней. Обе подкреплены теми же чипами оперативной памяти. Операционная система и программа взаимодействуют, чтобы гарантировать отсутствие перекрытия (если стек вырастает настолько, что сталкивается с кучей, возникает ошибка переполнения стека).
Трассировка фреймов стека при простой цепочке вызовов.
Рассмотрим программу, где функция main вызывает функцию add, которая больше никого
не вызывает.
Начальное состояние — выполняется только main.
Стек содержит: [фрейм main]
Фрейм main хранит локальные переменные main.
main вызывает add.
Стек содержит: [фрейм main] [фрейм add]
Фрейм add помещён поверх. В нём — параметры и локальные переменные add. Main приостановлена —
её фрейм всё ещё там, ожидает.
add возвращается.
Фрейм add выталкивается (отбрасывается). Занятые им ячейки свободны для повторного
использования.
Стек содержит: [фрейм main]
Main возобновляется с того места, где остановилась. Возвращаемое значение add передаётся
обратно в main (как правило, через регистр), а не через долгоживущую ячейку.
main возвращается.
Фрейм main выталкивается.
Стек содержит: [] (пусто)
Процесс завершается.
Ни один фрейм ни разу не пережил принадлежащую ему функцию. В этом — определяющее свойство стека.
Тем временем: если бы add создала большую структуру данных в куче, эта структура всё
ещё существовала бы в куче после возврата add — до тех пор, пока main (или другой код)
держит на неё указатель. Данные кучи переживают функцию; фрейм стека — нет.
Граничные случаи
Переполнение стека. Область стека имеет конечный размер, устанавливаемый ОС (как правило, 1–8 МБ). Если программа вызывает функции настолько глубоко — особенно через неограниченную рекурсию — что стек превышает свой предел, происходит аварийное завершение с ошибкой «переполнение стека» (stack overflow). Это не логическая ошибка в алгоритме программы; это физическое ограничение зарезервированного диапазона адресов. Рекурсивным алгоритмам с миллионами уровней вложенности нужна итеративная переработка или явно выделенные на куче структуры данных, чтобы избежать этого.
Функция A вызывает функцию B, которая вызывает функцию C. Сколько фреймов стека находится в стеке во время выполнения C?
Функция C возвращается. Сколько фреймов остаётся в стеке?
Стек работает по принципу LIFO. Какой фрейм удаляется первым: фрейм первой вызванной функции или фрейм последней вызванной? Введи 1 для «последней вызванной».
Объект кучи создан внутри функции X. После возврата X объект всё ещё может существовать в памяти? Введи 1 (да) или 0 (нет).
Стек и куча физически расположены на разных чипах памяти? Введи 1 (да) или 0 (нет).
В чём ключевое различие между памятью стека и памятью кучи?
Адресное пространство программы разбито на области. Область стека управляется автоматически: каждый вызов функции добавляет фрейм стека с локальными данными функции, а этот фрейм отбрасывается при её возврате. Фреймы добавляются и удаляются в порядке LIFO (последним вошёл — первым вышел): самая недавно вызванная функция всегда завершается первой. Область кучи хранит данные, переживающие отдельные вызовы функций; она управляется явно — с выделением и освобождением (или сборкой мусора) без фиксированного порядка. Обе области являются частями одной плоской байтово-адресуемой памяти: это диапазоны адресов в одной и той же ОЗУ, различающиеся только стратегией управления и временем жизни данных.