No Image

Что такое стек и куча

СОДЕРЖАНИЕ
0 просмотров
22 января 2020
  • Переводы, 2 января 2017 в 21:02
  • Иван Бирюков

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

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

Стек — это область оперативной памяти, которая создаётся для каждого потока. Он работает в порядке LIFO (Last In, First Out), то есть последний добавленный в стек кусок памяти будет первым в очереди на вывод из стека. Каждый раз, когда функция объявляет новую переменную, она добавляется в стек, а когда эта переменная пропадает из области видимости (например, когда функция заканчивается), она автоматически удаляется из стека. Когда стековая переменная освобождается, эта область памяти становится доступной для других стековых переменных.

Из-за такой природы стека управление памятью оказывается весьма логичным и простым для выполнения на ЦП; это приводит к высокой скорости, в особенности потому, что время цикла обновления байта стека очень мало, т.е. этот байт скорее всего привязан к кэшу процессора. Тем не менее, у такой строгой формы управления есть и недостатки. Размер стека — это фиксированная величина, и превышение лимита выделенной на стеке памяти приведёт к переполнению стека. Размер задаётся при создании потока, и у каждой переменной есть максимальный размер, зависящий от типа данных. Это позволяет ограничивать размер некоторых переменных (например, целочисленных), и вынуждает заранее объявлять размер более сложных типов данных (например, массивов), поскольку стек не позволит им изменить его. Кроме того, переменные, расположенные на стеке, всегда являются локальными.

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

Куча — это хранилище памяти, также расположенное в ОЗУ, которое допускает динамическое выделение памяти и не работает по принципу стека: это просто склад для ваших переменных. Когда вы выделяете в куче участок памяти для хранения переменной, к ней можно обратиться не только в потоке, но и во всем приложении. Именно так определяются глобальные переменные. По завершении приложения все выделенные участки памяти освобождаются. Размер кучи задаётся при запуске приложения, но, в отличие от стека, он ограничен лишь физически, и это позволяет создавать динамические переменные.

Вы взаимодействуете с кучей посредством ссылок, обычно называемых указателями — это переменные, чьи значения являются адресами других переменных. Создавая указатель, вы указываете на местоположение памяти в куче, что задаёт начальное значение переменной и говорит программе, где получить доступ к этому значению. Из-за динамической природы кучи ЦП не принимает участия в контроле над ней; в языках без сборщика мусора (C, C++) разработчику нужно вручную освобождать участки памяти, которые больше не нужны. Если этого не делать, могут возникнуть утечки и фрагментация памяти, что существенно замедлит работу кучи.

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

Заключение

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

Обновл. 31 Дек 2019 |

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

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

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

Читайте также:  Треугольник в круге геометрия

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

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

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

В этом уроке мы рассмотрим только кучу и стек в C++, поскольку всё самое интересное происходит именно здесь.

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

В 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() помещается в стек вызовов операционной системой. Затем программа начинает своё выполнение.

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

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

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

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

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

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

Фрейм стека создаётся и помещается в стек. Он состоит из:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Что такое стек?

Сегмент стека — это метод управления памятью, используемый для распределения статической памяти. Это специальная область памяти компьютера, которая используется для хранения локальных переменных функции. Когда вызывается функция, память распределяется по всем локальным переменным где-то, и вы можете получить доступ к этим переменным, как вы знаете их местоположения. Блоки памяти освобождаются, когда функция завершается. Стек — один из способов эффективного осуществления этого процесса. Подумайте об этом как о базовой структуре данных, где элементы расположены поверх друг друга, как стек. Аналогичным образом, локальные переменные могут быть доступны с нажатием и нажатием. Pushing означает добавление элементов в стек, а popping — извлечение элементов из стека. Элементы могут быть доступны из стека в порядке «последний-в-первом-выход» (LIFO).

Читайте также:  Смартфоны с диагональю 7 дюймов и больше

Что такое куча?

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

Разница между стеком и кучей

Значение стека и кучи

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

Распределение памяти для стека и кучи

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

Доступ к стеку и куче

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

Переменные в стеке и куче

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

Стек против кучи: сравнительная таблица

Резюме стека против кучи

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

Комментировать
0 просмотров
Комментариев нет, будьте первым кто его оставит

Это интересно
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
Adblock detector