Урок №105. Стек и Куча

  Юрий  | 

  |

  Обновл. 4 Сен 2021  | 

 112578

 ǀ   7 

На этом уроке мы рассмотрим стек и кучу в языке C++.

Сегменты

Память, которую используют программы, состоит из нескольких частей — сегментов:

   Сегмент кода (или «текстовый сегмент»), где находится скомпилированная программа. Обычно доступен только для чтения.

   Сегмент bss (или «неинициализированный сегмент данных»), где хранятся глобальные и статические переменные, инициализированные нулем.

   Сегмент данных (или «сегмент инициализированных данных»), где хранятся инициализированные глобальные и статические переменные.

   Куча, откуда выделяются динамические переменные.

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

Куча


Сегмент кучи (или просто «куча») отслеживает память, используемую для динамического выделения. Мы уже немного поговорили о куче на уроке о динамическом выделении памяти в языке С++.

В языке C++ при использовании оператора new динамическая память выделяется из сегмента кучи самой программы:

Адрес выделяемой памяти передается обратно оператором new и затем он может быть сохранен в указателе. О механизме хранения и выделения свободной памяти нам сейчас беспокоиться незачем. Однако стоит знать, что последовательные запросы памяти не всегда приводят к выделению последовательных адресов памяти!

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

Куча имеет свои преимущества и недостатки:

   Выделение памяти в куче сравнительно медленное.

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

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

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

Стек вызовов

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

Стек вызовов реализуется как структура данных «Стек». Поэтому, прежде чем мы поговорим о том, как работает стек вызовов, нам нужно понять, что такое стек как структура данных.

Стек как структура данных


Структура данных в программировании — это механизм организации данных для их эффективного использования. Вы уже видели несколько типов структур данных, например, массивы или структуры. Существует множество других структур данных, которые используются в программировании. Некоторые из них реализованы в Стандартной библиотеке C++, и стек как раз является одним из таковых.

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

   Посмотреть на поверхность первой тарелки (которая находится на самом верху).

   Взять верхнюю тарелку из стопки (обнажая таким образом следующую тарелку, которая находится под верхней, если она вообще существует).

   Положить новую тарелку поверх стопки (спрятав под ней самую верхнюю тарелку, если она вообще была).

В компьютерном программировании стек представляет собой контейнер (как структуру данных), который содержит несколько переменных (подобно массиву). Однако, в то время как массив позволяет получить доступ и изменять элементы в любом порядке (так называемый «произвольный доступ»), стек более ограничен.

В стеке вы можете:

   Посмотреть на верхний элемент стека (используя функцию top() или peek()).

   Вытянуть верхний элемент стека (используя функцию pop()).

   Добавить новый элемент поверх стека (используя функцию push()).

Стек — это структура данных типа LIFO (англ. «Last In, First Out» = «Последним пришел, первым ушел»). Последний элемент, который находится на вершине стека, первым и уйдет из него. Если положить новую тарелку поверх других тарелок, то именно эту тарелку вы первой и возьмете. По мере того, как элементы помещаются в стек — стек растет, по мере того, как элементы удаляются из стека — стек уменьшается.

Например, рассмотрим короткую последовательность, показывающую, как работает добавление и удаление в стеке:

Stack: empty
Push 1
Stack: 1
Push 2
Stack: 1 2
Push 3
Stack: 1 2 3
Push 4
Stack: 1 2 3 4
Pop
Stack: 1 2 3
Pop
Stack: 1 2
Pop
Stack: 1

Стопка тарелок довольно-таки хорошая аналогия работы стека, но есть лучшая аналогия. Например, рассмотрим несколько почтовых ящиков, которые расположены друг на друге. Каждый почтовый ящик может содержать только один элемент, и все почтовые ящики изначально пустые. Кроме того, каждый почтовый ящик прибивается гвоздем к почтовому ящику снизу, поэтому количество почтовых ящиков не может быть изменено. Если мы не можем изменить количество почтовых ящиков, то как мы получим поведение, подобное стеку?

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

Сегмент стека вызовов

Сегмент стека вызовов содержит память, используемую для стека вызовов. При запуске программы, функция main() помещается в стек вызовов операционной системой. Затем программа начинает свое выполнение.

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

Наша аналогия с почтовыми ящиками — это действительно то, как работает стек вызовов. Стек вызовов имеет фиксированное количество адресов памяти (фиксированный размер). Почтовые ящики являются адресами памяти, а «элементы», которые мы добавляем или вытягиваем из стека, называются фреймами (или «кадрами») стека. Кадр стека отслеживает все данные, связанные с одним вызовом функции. «Наклейка» — это регистр (небольшая часть памяти в ЦП), который является указателем стека. Указатель стека отслеживает вершину стека вызовов.

Единственное отличие фактического стека вызовов от нашего гипотетического стека почтовых ящиков заключается в том, что, когда мы вытягиваем элемент из стека вызовов, нам не нужно очищать память (т.е. вынимать всё содержимое из почтового ящика). Мы можем просто оставить эту память для следующего элемента, который и перезапишет её. Поскольку указатель стека будет ниже этого адреса памяти, то, как мы уже знаем, эта ячейка памяти не будет находиться в стеке.

Стек вызовов на практике


Давайте рассмотрим детально, как работает стек вызовов. Ниже приведена последовательность шагов, выполняемых при вызове функции:

   Программа сталкивается с вызовом функции.

   Создается фрейм стека, который помещается в стек. Он состоит из:

   адреса инструкции, который находится за вызовом функции (так называемый «обратный адрес»). Так процессор запоминает, куда ему возвращаться после выполнения функции;

   аргументов функции;

   памяти для локальных переменных;

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

   Процессор переходит к точке начала выполнения функции.

   Инструкции внутри функции начинают выполняться.

После завершения функции, выполняются следующие шаги:

   Регистры восстанавливаются из стека вызовов.

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

   Обрабатывается возвращаемое значение.

   ЦП возобновляет выполнение кода (исходя из обратного адреса).

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

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

Пример стека вызовов

Рассмотрим следующий фрагмент кода:

Стек вызовов этой программы выглядит следующим образом:

a:

main()

b:

boo() (включая параметр b)
main()

c:

main()

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

Стек имеет ограниченный размер и, следовательно, может содержать только ограниченный объем информации. В операционной системе Windows размер стека по умолчанию составляет 1МБ. На некоторых Unix-системах этот размер может достигать и 8МБ. Если программа пытается поместить в стек слишком много информации, то это приведет к переполнению стека. Переполнение стека (англ. «stack overflow») происходит, когда запрашиваемой памяти нет в наличии (вся память уже занята).

Переполнение стека является результатом добавления слишком большого количества переменных в стек и/или создания слишком большого количества вложенных вызовов функций (например, когда функция A() вызывает функцию B(), которая вызывает функцию C(), а та, в свою очередь, вызывает функцию D() и т.д.). Переполнение стека обычно приводит к сбою в программе, например:

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

Вот еще одна программа, которая вызовет переполнение стека, но уже по другой причине:

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

Стек имеет свои преимущества и недостатки:

   Выделение памяти в стеке происходит сравнительно быстро.

   Память, выделенная в стеке, остается в области видимости до тех пор, пока находится в стеке. Она уничтожается при выходе из стека.

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

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

Оценить статью:

Звёзд: 1Звёзд: 2Звёзд: 3Звёзд: 4Звёзд: 5 (379 оценок, среднее: 4,91 из 5)
Загрузка...

Комментариев: 7

  1. Константин:

    Юра, разреши логическое противоречие

    «Наклейка» — это регистр (небольшая часть памяти в ЦП), который является указателем стека.

    Всё, что находится ниже наклейки — находится в стеке. Всё, что находится в ящике с наклейкой и выше — находится вне стека.

    vs

    когда мы вытягиваем элемент из стека вызовов, нам не нужно очищать память (т.е. вынимать всё содержимое из почтового ящика). Мы можем просто оставить эту память для следующего элемента, который и перезапишет её.

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

  2. Дмитрий:

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

  3. Аркаша:

    Если код такой

    Понятно, что b и x будут во фрейме стека boo.
    1) В каком сегменте будет находится результат вычисления из return b + x + 3 ? Т. е. будет ли он сначала занимать место в стеке boo перед тем, как попадёт в стек main ?
    2) На какую инструкцию будет указывать обратный адрес стека boo? На "n=" ?
    Т.е. не очень понял, что значит отдельный шаг завершения функции — обработка возвращаемого значения. Ну и это: при завершении функции сначала указан шаг 'Фрейм стека вытягивается из стека… ', а потом шаг 'ЦП возобновляет выполнение кода (исходя из обратного адреса)'. А откуда ЦП знает обратный адрес, если фрейм, в котором он хранился, уже вытеснен из стека на предыдущем шаге?

  4. Muzzy:

    Получается, функция boo будет вызвана 262 144 раза и произойдет переполнение стека, если его размер 1mb?

  5. Spardoks:

    В стеке можно разместить исполняемый код, если постараться. Есть даже такая уязвимость, связанная с переполнением стека. Тем не менее, в адекватной ситуации код там не хранинтся.

  6. bazik210:

    По поводу вот этого утверждения: "Когда программа встречает вызов функции, то эта функция помещается в стек вызовов." От того преподавателя с ITVDN: "Исполняемый код НИКОГДА!!! не может оказаться в стеке, это статическая область памяти, instruction pointer (регистр процессора) никогда не перейдет туда, чтобы её выполнять, процессор никогда не зайдет в стек и не начнет там выполнять програмные коды. Это просто коробка для хранения адресов и локальных переменных."

    1. Upaut:

      Разумеется в стеке исполняемого кода быть не может. При вызове функции все ее аргументы помещаются в стек в обратном порядке, а следом происходит вызов функции, который изымет из стека эти аргументы и поместит в стек свой вызов.
      На примере автора: когда функция boo рекурсивно вызывает саму себя, переполнение стека произойдет и это факт! При каждом вызове в стек будет помещаться по 4 байта (32 разрядные системы), но изъятия из стека происходить не будет так как функция не доходит до завершения.

Добавить комментарий

Ваш E-mail не будет опубликован. Обязательные поля помечены *