Урок №111. Стек і Купа

  Юрій  | 

  Оновл. 21 Січ 2021  | 

 35

На цьому уроці ми розглянемо стек і купу в мові С++.

Сегменти

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

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

   Сегмент 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 Зірок (1 оцінок, середня: 5,00 з 5)
Loading...

Залишити відповідь

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