Що таке стек, навіщо він потрібен і як влаштований

Стеки повсюдно використовують у програмуванні, оскільки дозволяють організувати зручну структуру зберігання даних. Це забезпечує безвідмовну роботу програм та пристроїв під час виконання послідовності дій. Так, стеки дозволяють "відкочувати" дії в браузерах або Photoshop. «РБК Тренди» розбиралися, якими бувають і як працюють стеки, а також де і як вони використовуються.

Що таке стек

Стек (від англ. stack - "Стопка") - це спосіб організації даних у пам'яті комп'ютера, який відповідає принципу LIFO (англ. last in - first out, "останнім прийшов - першим вийшов"). Таким чином, останній елемент у стеку використовується першим, а додавати нові елементи та видаляти їх можна лише з одного кінця, який називається вершиною. Візуально це схоже на гірку посуду, колоду карт або іграшкову пірамідку, де, щоб дістати другий предмет зверху, потрібно спочатку прибрати перший. Схему стека описав математик Алан Т'юрінг у 1946 році, проте він використав для неї поняття «burying» (від англ. «поховання»).

Стеки безпосередньо не взаємодіють з жодною з мов програмування, а просто дозволяють сформувати послідовність використання даних. У цьому дані можуть зберігатися у різних форматах: списків, «дерев», схем, множин, таблиць тощо.

Елементи зі стеку беруться і використовуються лише по черзі. Вони йдуть один за одним у строгому порядку, і порушувати послідовність не можна. Коли всі елементи стека використані, він зникає.

Для роботи зі стеками використовується кілька основних команд:

• push - додавання елемента на вершину стека;
• pop - видалення елемента з вершини;
• top - Повернення елемента на вершину;
• peek – зчитування елемента з вершини стека без видалення;
• isEmpty - перевірка порожнечі стека;
• isFull - перевірка заповненості стека;
• size – кількість елементів, доступних у стеку;
• change - заміна елемента в заданій позиції;
• display — показує всі елементи, доступні у стеку.

Для чого використовують стеки

При керуванні пам'яттю будь-який сучасний комп'ютер використовує стек як основний засіб своєї роботи. Кожна програма, що працює у системі, має власний стек пам'яті. Така організація даних також допомагає реалізувати виклик функцій комп'ютерах.

Крім того, стеки застосовуються:

• в операціях скасування у текстових та графічних редакторах;
• для скасування дій у браузерах;
• для скасування або повторення операцій у базах даних;
• у додатках штучного інтелекту, коли необхідно виконати обчислення у порядку;
• для передачі параметрів між програмами та ядром операційної системи.

Які бувають стеки

Стек викликів

Стек дзвінків (call stack) – це структура даних, яка керує викликами функцій під час виконання програми. Коли програма виконується на комп'ютері, він по черзі викликає різні функції, відповідальні конкретні дії (підпрограми). При цьому в стеку зберігаються дані про виклик функції у вигляді точок переходу - моментів, коли комп'ютер перервав виконання однієї функції і перейшов до іншої. Тож якщо всередині однієї функції викликається інша, то комп'ютер ставить на паузу виконання першої, зберігає у стеку точку переходу, та був виконує другу. Коли виконано останню функцію, комп'ютер повертається до першої, а програма продовжує роботу з того ж місця. При цьому стек спустошується.

Наведемо приклад. Допустимо, нам потрібно приготувати яєчню з беконом на сніданок.Задамо послідовність дій, кожна з яких виконуватиметься як функція в стеку певної послідовності. Починаємо з додавання бекону і ця функція буде виконуватися першою, а далі описуємо послідовність дій. При цьому функція додавання спецій виконуватиметься всередині обсмажування бекону.

console.log ("Обсмажуємо яйця.");

console.log ("Додаємо яйця. ");

console.log ("Додаємо спеції. ");

console.log ("Обсмажуємо бекон.");

console.log ("Додаємо бекон. ");

addBacon(); // Починаємо готувати яєчню

Стек даних

Стек даних - така організація структури, коли можна читати та видаляти тільки останній елемент. Цей вид стеків використовують для роботи з розгалуженими типами даних: деревами, графами, документами XML, JSON-об'єктами та іншими.

Наприклад, стек можна застосувати для обходу дерев у глибину, щоб вивести всі значення його вузлів. Для цього робота починається з кореня, потім поступово розширюється на гілки дерева. Кожен пройдений вузол (розгалуження) додається в стек, а при отриманні значення видаляється з нього.

Ще один приклад - стек на основі купи (heap). У ньому елементи зберігаються у купі, але кожен має пріоритет. Такий тип застосовується у вирішенні завдань, пов'язаних з пріоритетами, наприклад, для пошуку мінімального або максимального елемента.

Розглянемо приклад реалізації стека на основі купи у мові програмування JavaScript. Пам'ять купи не впорядкована певним чином, тому посилання (адреси) на об'єкти в ній (вдома) потрібно зберігати у стеку. JavaScript об'єкти і функції зберігаються в купі, а примітивні значення і посилання - в стеку.

Реалізація стеку

Існує кілька типів реалізації стеків:

• На масиві фіксованої довжини. Такий стек складається з ланцюга елементів наперед заданого розміру, а нові елементи додаються тільки до останнього. Під час виконання функцій може виникнути ризик переповнення та збоїв.
• На динамічному масиві. Для виконання такого стека у процесі виділяється нова ділянка пам'яті більшого розміру і все копіюється туди, що дозволяє виконувати вставку нового елемента. При цьому операції додавання та видалення можна виконувати як з кінця, так і початку масиву.
• На зв'язковому списку. Для виконання цього стека потрібен перелік і список операцій на ньому. Елементи до списку додаватимуться через прив'язку до першого.

Вибір реалізації залежить від завдання. Так, якщо потрібний швидкий доступ до елементів, але сам стек має фіксований розмір або змінюється рідко, то краще вибрати динамічний масив. Однак, коли величина стека заздалегідь невідома, варто звернутися до зв'язаного списку.

Переваги та недоліки стеків

Завдяки простоті організації стеки використовуються повсюдно в адмініструванні, дизайні, інтернет-маркетингу, програмуванні та розробці. Така організація даних має як переваги, і недоліки.

• простота - це зрозуміла структура даних для широкого спектра додатків;
• ефективність: операції push та pop у стеку можуть виконуватися постійно, забезпечуючи ефективний доступ до даних;
• використання принципу LIFO, що корисно у багатьох сценаріях, коли потрібно постійно викликати функції;
• обмежене споживання пам'яті, тому що в ній зберігаються ті елементи, які поміщені в стеки.

• обмежений доступ до даних за принципом піраміди;
• можливість переповнення, коли в стек міститься більше елементів, ніж він може вмістити, що призводить до втрати даних;
• відсутність довільного доступу до елементів;
• обмежена ємність.

Переповнення стеку

Переповнення стека (stack overflow) - це ситуація, коли він заповнюється елементами, що перевищують його максимальний розмір, встановлений під час створення. У цьому випадку стек більше не може зберігати елементи і будь-яка спроба додавання нового викликає помилку. Ця помилка настільки поширена, що на честь неї назвали найпопулярніший сервіс питань та відповідей для IT-фахівців — Stack Overflow.

Чим загрожує переповнення стеку:

• аварійним завершенням програми, що може призвести до втрати даних чи інших наслідків;
• помилками у програмі, у тому числі зависанням під час її роботи;
• власне, втрати даних: ті елементи, які не містяться у стек, можуть бути видалені;
• вразливості безпеки: зловмисники можуть використовувати переповнення стека для виконання шкідливого коду або інших дій.

Причини переповнення стеку:

• рекурсія: коли функція викликає саму себе дуже багато разів, то кожен новий виклик додає новий елемент у стек. При надто великій глибині рекурсії стек може переповнитися;

• нескінченний цикл: коли цикл не зупиняється при додаванні нових елементів, стек може швидко заповнитися;
• помилки в коді, які призводять до надто швидкого заповнення стека. Це можливо, коли функція додає елементи, але не видаляє їх;
• недостатній розмір стека.

При розробці стека необхідно враховувати, що у різних мовах програмування різняться ліміти виклики функцій. Так, у Python глибина рекурсії за умовчанням обмежена 1 тис. викликів, але її можна збільшити вручну, а в мовах C або C++ цей ліміт вище. Крім того, потрібно заздалегідь визначити розмір стека, оскільки великі масиви або інші дані в програмах можуть вимагати додаткової ємності.

Читайте також:

Що таке стек і як він влаштований

Ми поступово освоюємо способи організації та зберігання даних. Вже було про дерева, спробуємо про стеки. Це для тих, хто хоче в майбутньому серйозно працювати в ІТ, тому що стек — одна з фундаментальних концепцій, яка впливає на якість вашого коду, але не стосується якоїсь конкретної програми.

Що таке стек

👉 Стек (stack) - це одна з абстрактних структур даних. Структура даних - це те, як вони організовані та зберігаються в комп'ютері: наприклад, масиви, зв'язані списки, черги, дерева, хеш-таблиці, графи і навіть купи (heap).

Стек зберігає послідовність даних. Ці дані пов'язані так: кожен елемент вказує на той, який потрібно використовувати наступним. Це лінійний зв'язок - дані йдуть одна за одною і потрібно брати їх по черзі. З середини стека брати не можна.

👉 Головний принцип роботи стеку - дані, які потрапили в стек нещодавно, використовуються першими. Що раніше потрапив, то пізніше використовується. Після використання елемент стека зникає і верхнім стає наступний елемент.

Класичний спосіб пояснення принципів стека звучить так: уявіть, що миєте посуд і складаєте однакові чисті тарілки чаркою один на одного. Кожна нова тарілка - це елемент стека, а ви просто додаєте їх по одній у стек.

Коли комусь знадобиться тарілка, він не братиме її знизу чи з середини — він візьме першу зверху, потім наступну і таке інше.

🤔 Є структура даних, схожа на стек, називається черга, або queue. Якщо в стеку хтось останній прийшов, того першим заберуть, то в черзі навпаки: хтось раніше прийшов, той раніше пішов.Можна уявити чергу в магазині: хто раніше зайняв її, той перший дійшов до каси. Черга це теж лінійний набір даних, але обробляється по-іншому.

Реалізація стеку

Реалізація стека – це коли стек створюють за допомогою якоїсь мови програмування. Яким би він не був, основні операції зі стеком будуть називатися однаково:

• push - додати елемент у вершу стека,
• pop - видалити та повернути елемент з вершини стека,
• peek (іноді top) - повернути елемент з вершини стека без видалення,
• is_empty - перевірити, чи порожній стек.

Наприклад покажемо, як може виглядати реалізація стека на Python. Щоб було зрозуміліше, ми додали коментарі до кожного рядка коду:

class Stack: # ініціалізація стека з використанням списку def __init__(self): self.items = [] # метод для додавання елемента в стек def push(self, item): # додаємо елемент в кінець списку (вершина стека) self.items. append(item) # метод для видалення та повернення елемента з вершини стека def pop(self): # якщо стек не порожній if not self.is_empty(): # видаляємо та повертаємо елемент з кінця списку return self.items.pop() # якщо стек порожній else: # викидаємо виняток raise IndexError("Спроба видалення з порожнього стека") # метод для повернення елемента з вершини стека без його видалення def peek(self): # якщо стек не порожній if not self.is_empty(): # повертаємо останній елемент списку return self.items[-1] # якщо стек порожній else: raise IndexError("Спроба повернення з порожнього стека") # Якщо стек порожній, викидаємо виняток # метод для перевірки, чи порожній стек def is_empty(self): # Повертаємо True, якщо список порожній, інакше False return len(self.items) == 0 # метод для отримання кількості елементів у стеку def size(self): # повертаємо довжину списку return len(self.items) # приклад використання стека # створюємо новий екземпляр стека stack = Stack() # додаємо елемент 1 в стек stack.push(1) # додаємо елемент 2 у стек stack.push(2) # додаємо елемент 3 у стек stack.push(3) # видаляємо та виводимо верхній елемент стека (3) print(stack.pop()) # виводимо верхній елемент стека (2) без його видалення print(stack.peek()) # перевіряємо, чи пустий стек print(stack.is_empty()) # виводимо кількість елементів у стеку (2) print(stack.size())

Якщо запустити цей код, отримаємо такий результат у консолі:

Стек викликів

У програмуванні є два види стека - стек викликів та стек даних.

Коли в програмі є підпрограми (процедури та функції), то комп'ютера потрібно пам'ятати, де він перервався в основному коді, щоб виконати підпрограму. Після виконання він має повернутися і продовжити виконувати основний код. При цьому якщо підпрограма повертає якісь дані, їх теж потрібно запам'ятати і передати в основний код.

Щоб це реалізувати, комп'ютер використовує стек викликів - спеціальну область пам'яті, де зберігає дані про точки переходу між фрагментами коду.

Припустимо, у нас є програма, всередині якої є три функції, причому одна з них викликає всередині іншу. Намалюємо, щоб було зрозуміліше:

Програма запускається, потім іде виклик синьої функції. Вона виконується і програма продовжує з того місця, де зупинилася. Потім виконується зелена функція, що викликає червону. Поки червона не закінчить роботу, всі інші чекають. Як тільки червона закінчилася — продовжується зелена, а після закінчення програми продовжує свою роботу з того ж місця.

А ось як стек допомагає це реалізувати на практиці:

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

Із зеленою функцією все те саме — в стек заноситься точка повернення, і програма починає виконувати зелену функцію. Але всередині неї ми викликаємо червону, і ось що відбувається:

При виклику червоної функції в стек міститься новий елемент з інформацією про дані, точку повернення та вказівкою на наступний елемент.Це означає, що коли червона функція закінчить роботу, комп'ютер візьме з стека адресу повернення і поверне управління знову зеленої функції, а червоний елемент зникне. Коли і зелена закінчить роботу, то комп'ютер із стека візьме нову адресу повернення і продовжить роботу зі старого місця.

Переповнення стеку

У більшості випадків стек викликів зберігається в оперативній пам'яті і має певний розмір. Якщо у вас буде багато вкладених викликів або рекурсія з дуже великою глибиною вкладеності, то може статися така ситуація:

• рекурсія все працює та працює;
• при кожному новому витку рекурсії до стек додаються новий елемент;
• коли елементів буде занадто багато, пам'ять закінчиться, нові елементи нікуди складатиме і відбудеться переповнення стека.

Переповнення це погано: дані можуть залазити в чужу область пам'яті і записувати себе замість колишніх даних. Це може призвести до несправності інших програм або самого комп'ютера. Ще таким чином можна впровадити в оперативну пам'ять шкідливий код: якщо програма погано працює зі стеком, можна спеціально викликати переповнення та записати на згадку щось шкідливе.

Стек даних

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

Стек даних працює за таким же принципом, як і стек викликів - елемент, який додали останнім, має використовуватися першим.

Що далі

А далі поговоримо про тип даних під назвою купа. Так, такий є, і з ним також можна ефективно працювати. Стей тюнед.

Сегментація пам'яті (Схема пам'яті комп'ютера)

Представляю Вам переклад статті одного з розробників PHP, в тому числі версії 7 і вище, сертифікованого інженера ZendFramework. В даний момент працює в SensioLabs і більшу частину займається низькорівневими речами, у тому числі програмуванням під Unix. Оригінал статті тут.

Помилка Сегментації: (Комп'ютерна верстка пам'яті)

Декілька слів, про що цей запис у блозі

Я планую надалі писати технічні статті про PHP, пов'язані з глибоким розумінням пам'яті. Мені потрібно, щоб мої читачі мали такі знання, які їм допоможуть зрозуміти деякі поняття подальшого пояснення. Для того, щоб відповісти на це питання, нам доведеться перемотати час назад у 1960-ті роки. Я збираюся пояснити вам, як працює комп'ютер, а точніше, як відбувається доступ до пам'яті в сучасному комп'ютері, а потім ви зрозумієте, через що відбувається це дивне повідомлення про помилку. Segmentation Fault.

Те, що ви читатимете тут, короткий виклад основ дизайну комп'ютерної архітектури. Я не заходитиму занадто далеко, якщо це не потрібно, і використовуватиму добре відомі формулювання, так що, хто працює з комп'ютером кожен день може зрозуміти такі важливі поняття про те, як працює ПК. Існує багато книг про комп'ютерну архітектуру. Якщо ви хочете заглибитись далі в цій темі, я пропоную вам дістати деякі з них і почати читати. Крім того, відкрийте вихідний код ядра ОС і вивчіть його, чи то ядро ​​Linux, чи будь-яке інше.

Трохи історії computer science

Ще в той час, коли комп'ютерами були величезні машини, важчі за тонну, всередині ви могли б знайти один процесор з чимось на зразок 16Kb оперативної пам'яті (RAM).Не заглиблюватимемося далі =) У цей період комп'ютер коштував приблизно $ 150 000 і міг виконати одно завдання в момент часу. Якби ми тоді намалювали схему його пам'яті, то архітектура виглядала так:

• Область пам'яті операційної системи (4kb)
• Область пам'яті запущених процесів (12Kb)

Але одна з головних проблем такої моделі полягає в тому, що комп'ютер (вартістю $150 000) міг виконувати лише одне завдання одноразово, і це завдання дуже довго виконувалося: цілі дні, щоб обробити кілька Кб даних. За такою величезною ціною явно неможливо купити кілька машин, щоб виконати кілька процедур одночасно. Тож люди намагалися розподілити ресурси машини. Це був час народження багатозадачності. Майте на увазі, що тоді було ще дуже рано говорити про багатопроцесорні ПК. Як ми можемо змусити одну машину з одним процесором і насправді вирішити кілька різних завдань? Відповідь на це питання – планування. Поки один процес зайнятий в очікуванні введення/виведення (очікує переривання), процесор може запустити інший процес. Ми не говоритимемо про планування на всіх рівнях (надто широкій темі), тільки про пам'ять. Якщо машина може виконувати кілька завдань, один процес за іншим, то це означає, що пам'ять розподілятиметься приблизно таким чином:

Обидві завдання А і В зберігаються в оперативній пам'яті, тому що копіювати їх туди і назад на диск - надто ресурсозатратний процес. Дані повинні залишатися в оперативній пам'яті на постійній основі, тому що їх відповідні завдання, як і раніше, працюють. Планувальник дає деякий час процесора, то задачі А, то B, і т.д ... щоразу надаючи доступ до її області пам'яті. Але зачекайте, що тут є проблема.Коли один програміст писатиме код завдання B, він повинен знати адреси меж пам'яті. Наприклад, завдання буде розташовуватися з 10Kb пам'яті до 12Кб. Тому кожна адреса у програмі має жорстко записатися саме в ці межі. Якщо машина потім виконуватиме ще 3 завдання, то адресний простір буде розділено на більшу кількість областей, і межі пам'яті задачі зрушаться. Програмістові довелося б переписати свою програму, щоб використовувати менше пам'яті, і переписувати кожну адресу покажчика пам'яті.

Тут очевидна також інша проблема: що, якщо завдання B отримає доступ до пам'яті задачі А? Це легко може статися, тому що коли ви маніпулюєте вказівниками, невелика помилка при обчисленні призводить до зовсім іншої адреси. Це може зіпсувати ці завдання А (перезаписати їх). Також існує проблема безпеки, якщо завдання А працює з дуже чутливими даними? Немає ніякого способу, щоб запобігти читанню завданням B деякої області пам'яті задачі А. І останнє: що, якщо завдання B помилково перезапише пам'ять ОС? Наприклад, пам'ять ОС від 0Kb до 4Kb, якщо завдання B перепише цю ділянку, то операційна система напевно зазнає краху.

Адресний простір

Таким чином, потрібна допомога операційної системи та апаратного забезпечення, щоб отримати можливість запускати кілька завдань, що знаходяться в пам'яті. Один із способів допомогти, є створення того, що називається адресний простір. Адресний простір є абстракцією пам'яті, яку операційна система дасть процесу, і ця концепція є абсолютно фундаментальною, оскільки в даний час кожна частина комп'ютера, яку ви зустрінете у вашому житті, розроблена таким чином.Зараз не існує жодної іншої моделі (у громадянському суспільстві армія може зберігати таємницю).

Кожна система в даний час організована з таким макетом пам'яті як “код – стек – купа”, і це засмучує.

Адресний простір містить усі завдання (процеси), які необхідно запустити:

• Код: це машинні інструкції, які процесор повинен обробити
• Дані: дані машинних команд, які обробляються разом з ними.

• Стек — це область пам'яті, де програма зберігає інформацію про функції, їх аргументи і кожну локальну змінну в функції.
• Купа - Це область пам'яті де програміст вільний робити все, що завгодно.
• Код — область пам'яті, де зберігатимуться інструкції ЦП скомпільованої програми. Ці вказівки генеруються компілятором, але можуть бути написані вручну. Зверніть увагу, що сегмент коду зазвичай ділиться на три частини (текст, дані та BSS), але ми не будемо так глибоко занурюватись.
• Код завжди фіксованого розміру створюється компілятором і важитиме (у прикладі) 1Кб.
• Стек, однак, є зоною, що змінюється, так як програма працює. Коли функції викликаються, стек розширюється, коли з функції: стек зменшується.
• Купа теж є зоною, що змінюється, коли програміст виділяє пам'ять з купи (malloc()), вона розширюється, а коли програміст звільняє пам'ять назад (free()), купа звужується.

Віртуалізація пам'яті

Якщо задача А отримала адресний простір, такий, що ми бачили, як і завдання B. То як ми можемо розмістити їх у пам'яті? Це здається дивним, але адресний простір завдання А починається від 0KB до 16Kb, як і завдання B. Хитрість полягає у створенні віртуального середовища. Насправді картина розміщення А та В у пам'яті:

Коли завдання А спробує отримати доступ до пам'яті у своєму адресному просторі, наприклад, індекс 11К, десь у своєму власному стеку, операційна система виконає хак і насправді завантажить індекс пам'яті 1500, тому що індекс 11K належить задачі B. Насправді, весь адресний простір кожної програми в пам'яті - це просто віртуальна пам'ять. віртуальним адресам, за допомогою деяких апаратних чіпів ОС буде обманювати процес, коли він намагатиметься отримати доступ до будь-якої зони пам'яті.

ОС віртуалізує пам'ять та гарантує, що будь-яка задача не зможе отримати доступ до пам'яті, якої не володіє. прозоро для завдань на рівні користувача, завдяки тоннам складного коду ОС. Таким чином, операційна система обслуговує кожен запит пам'яті процесу. надто багато різних програм. Для досягнення цієї мети процес отримує допомогу від апаратного забезпечення, головним чином від процесора та деяких електронних компонентів навколо нього, таким як блок управління пам'яттю (MMU), з'явився на початку 70-х років, разом з IBM, як окремі чіпи. Зараз вони вбудовуються безпосередньо в наші чіпи CPU і є обов'язковими для будь-якої сучасної ОС для запуску. покладається деякі апаратні особливості поведінки, які полегшать доступом до пам'яті.

Ось невелика програма на C, яка показує деякі адреси пам'яті:

#include #include int main (int argc, символ **argv)

На моїй LP64 x86_64 машині він показує:

Code is at 0x40054c Stack is at 0x7ffe60a1465c Heap is at 0x1ecf010

Ми можемо бачити, що адреса стека знаходиться набагато вище за адресу купи, а код розташований нижче стека. Але кожна з цих 3-х адрес є підробками: у фізичній пам'яті, за адресою 0x7ffe60a1465c точно не розташоване ціле число 3. Пам'ятайте, що кожна програма користувача маніпулює адресами віртуальної пам'яті, тоді як програми рівня ядра, таких як саме ядро ​​ОС ( або апаратний код драйвера) можуть маніпулювати фізичними адресами RAM.

Трансляція адреси

Адресна трансляція — це формулювання, за яким ховається якась магічна техніка. Апаратне забезпечення (ММУ) транслює кожну віртуальну адресу програми рівня користувача на правильну фізичну адресу. Таким чином, операційна система пам'ятає для кожного завдання відповідність між його віртуальними адресами та фізичними. І це є складним завданням. Операційна система управляє всією пам'яттю завдань лише на рівні користувача кожному за вимоги доступу до пам'яті, забезпечуючи цим повну ілюзію процесу. Таким чином, операційна система перетворює всю фізичну пам'ять на корисну, потужну і просту абстракцію.

Давайте докладно розглянемо простий сценарій:
Коли процес запускається, операційна система бронює фіксовану ділянку фізичної пам'яті, скажімо, 16KB. Потім зберігає початкову адресу цього простору спеціальну змінну, звану базою. Потім встановлює іншу спеціальну змінну, яка називається межами (або межею) ширини простору — 16КВ. Далі операційна система збереже ці значення у таблиці процесів, званої PCB (Process Control Block).
А ось як виглядає процес віртуального адресного простору:

А ось його фізичне зображення:

ОС вирішила зберегти його у фізичній пам'яті в діапазоні адрес від 4K до 20K. Таким чином, базова адреса встановлюється в 4K, а межа встановлена ​​на 4+16=20К. Коли цей процес планується (враховуючи деякий час процесора), операційна система зчитує назад граничні значення PCB і копіює їх у конкретні регістри процесора. Коли CPU під час роботи спробує завантажити, наприклад, віртуальну адресу 2K (щось у його купі), CPU додасть цю адресу бази, отриману від операційної системи. Таким чином, процес доступу пам'яті призведе до фізичного розташування 2K + 4K = 6К.

Фізична адреса = віртуальна адреса + межа

Якщо отримана фізична адреса (6К) знаходиться поза межами (-4K | 20K-), це означає, що процес спробував отримати доступ до неправильної ділянки пам'яті, якою вона не володіє. Процесор згенерує виняток, і оскільки в ОС є обробник винятків для цієї події, ОС активується процесором і знатиме, що виняток пам'яті щойно відбувся на CPU. Потім ОС за промовчанням передасть сигнал пошкодженому процесу "SIGSEGV". Помилка сегментації, яка за замовчуванням (це може бути змінено) завершить завдання з повідомленням - "Відбувся збій у роботі з неприпустимим доступом до пам'яті".

Переміщення пам'яті

Ще краще, якщо завдання А не заплановано, це означає, що вона витягується з CPU, оскільки планувальник попросив запустити інше завдання (скажімо, завдання B). При виконанні задачі B ОС може вільно перемістити весь фізичний адресний простір задачі A. Операційна система часто отримує час процесора при виконанні завдань користувача.Коли завершується останній системний виклик, керування ЦП повертається до ОС, і до виконання системного виклику ОС може робити все, що захоче, керуючи пам'яттю, переміщуючи весь простір процесу різні фізичні слоти карт пам'яті.

Це відносно просто: операційна система переміщає область 16K в іншу 16K вільного простору, і просто оновлює базові та пов'язані змінні завдання A. Коли завдання буде відновлено і передана CPU, процес перетворення адреси, як і раніше, буде працювати, але це не призведе до того ж фізичною адресою, як раніше.

Завдання А не помітила нічого, з її точки зору, її адресний простір, як і раніше, починається від 0К до 16К. Операційна система та апаратне забезпечення MMU беруть повний контроль над кожним доступом до пам'яті завдання А, даючи їй повну ілюзію. Програміст завдання A маніпулює своїми дозволеними віртуальними адресами, від 0 до 16, а MMU дбатиме про позиціонування у фізичній пам'яті.

Образ пам'яті після переміщення виглядатиме так:

В даний час програміст більше не повинен ставити питання, де його програма перебувати в оперативній пам'яті, якщо інше завдання працює поруч з його власною, і якими адресами маніпулювати. Це робить сама ОС разом з дуже продуктивним та розумним апаратним засобом - "Блок управління пам'яті" (MMU).

Сегментація пам'яті

Зверніть увагу на зовнішній вигляд слова "сегментація" - ми близькі до пояснення, чому відбуваються помилки сегментації. У попередньому розділі ми пояснили про трансляцію та переміщення пам'яті, але модель, яку ми використовували має свої недоліки:
Ми припустили, що кожен віртуальний адресний простір фіксується завширшки 16Kb. Очевидно, що це не так насправді.Операційна система повинна підтримувати список фізичної пам'яті вільних слотів (шириною 16 Kb), щоб мати можливість знайти місце для будь-якого нового процесу з проханням розпочати або перемістити запущений процес. Як зробити це ефективно, щоби не сповільнити всю систему? Як ви можете бачити, кожен процес займає ділянку пам'яті 16 Kb, навіть якщо процес не використовує весь свій адресний простір, що дуже ймовірно. Ця модель явно витрачає багато пам'яті, процес споживає 1KB пам'яті, яке ділянку пам'яті у фізичної пам'яті 16Кб. Такі відходи називають внутрішньою фрагментацією: пам'ять зарезервована, але ніколи не використовується.

Для вирішення деяких із цих проблем, ми збираємося поринути у складнішу організацію пам'яті в ОС — сегментацію. Сегментацію легко зрозуміти: ми розширюємо ідею «бази та кордонів» трьох логічних сегментів пам'яті: купи, коду та стека; кожного процесу замість того, щоб просто розглядати образ пам'яті як один унікальний об'єкт.

За такої концепції пам'ять між стеком і купою більше не марнується. Ось так:

Тепер легко помітити, що вільний простір у віртуальній пам'яті для завдань А більше не виділяється у фізичній пам'яті, використання пам'яті стає набагато ефективнішим. Єдиною відмінністю є те, що в даний час для будь-якого завдання, ОС повинна запам'ятовувати не одну пару баз/кордонів, а три по одній парі для кожного типу сегмента. ММУ дбає про переклад, так само, як і раніше, і тепер підтримує, 3 базові величини, і 3 кордони.

Наприклад, тут купа завдання A має базу 126K і межі 2К. Потім завдання вимагає доступу до віртуальної адреси 3KB, у купі; фізична адреса 3Kb - 2Кб (початок купи) = 1Kb + 126K (зміщення) = 127K.127K знаходиться перед 128К - це правильна адреса пам'яті, яка може бути виконана.

Спільне використання сегментів

Сегментування фізичної пам'яті не тільки вирішує проблему вільної віртуальної пам'яті, звільняючи більше фізичної пам'яті, але також дозволяє розділити фізичні сегменти за допомогою різних процесів віртуальних адресних просторів. Якщо запустити двічі те саме завдання, завдання А наприклад, сегмент коду такий самий: обидві завдання виконують одні й самі команди процесора. Обидві завдання будуть використовувати свій власний стек та купу, звертатися до власних наборів даних. Неефективно дублювати сегмент коду пам'яті. ОС тепер може розділити його та заощадити ще більше пам'яті. Наприклад так:

На малюнку вище, А і мають свою власну область коду в їх відповідному віртуальному просторі пам'яті, але під капотом. Операційна система поділяє цю область в тих самих фізичних сегментах пам'яті. Обидві завдання А та В абсолютно не бачать цього, для них обох вони володіють своєю пам'яттю. Для досягнення цієї мети ОС має реалізувати ще одну особливість: біт захисту сегмента. ОС буде для кожного фізичного сегменту створювати, реєструвати межі/межі для правильної роботи блоку MMU, але вона також зареєструє прапор роздільної здатності.

Оскільки код не змінюється, сегменти коду всі створені з прапором роздільної здатності RX. Процес може завантажити цю область пам'яті для виконання, але будь-який процес, що спробував писати в цю область пам'яті, буде завершено операційну систему.Інші два сегменти: купа і стек є RW, процеси можуть читати і писати від свого власного стека / купи, але вони не можуть виконувати код з нього (це запобігає недолікам безпеки програми, де поганий користувач може захотіти пошкодити купу або стек, щоб ввести код Для запуску, якому буде доступно ядро ​​ОС. Це неможливо, тому що купа та стек сегментів часто не є. Зверніть увагу, що це було не завжди, оскільки вимагає додаткової підтримки апаратного забезпечення для ефективної роботи, це називається "біт NX" під процесором Intel). p align="justify"> Сегменти пам'яті дозволів змінюються під час виконання: завдання може вимагати mprotect () від ОС. Ці сегменти пам'яті чітко видно під Linux, використовуйте утиліти /proc//maps або /usr/bin/pmap

Нижче наведено приклад для PHP:

$ pmap -x 31329 0000000000400000 10300 2004 0 r-x-- php 000000000100e000 832 460 76 rw--- php 000000002 rw--- [ anon ] 000000000197a000 2784 2696 2696 rw--- [ anon ] 00007ff772bc4000 12 12 0 r-x-- libuuid.so.000.0.0. 1020 0 0 ----- libuuid.so.0.0.0 00007ff772cc6000 4 4 4 rw --- libuuid.so.0.0.0 . .

Тут ми детально бачимо усі відображення пам'яті. Адреси є віртуальними і відображають їх роздільну здатність області пам'яті. Як ми можемо бачити, кожен загальний об'єкт (.so) відображається в адресний простір як кілька відображень (ймовірно коду та даних), і області коду є здійсненними, а під капотом вони поділяються у фізичній пам'яті між кожним процесом, що відображає такий загальний об'єкт у його власний адресний простір.

Найбільша перевага об'єктів, що розділяються під Linux (і Unix) - це економія пам'яті.Можна також створити загальну зону, що веде до загального фізичного сегменту пам'яті, за допомогою системного виклику mmap().

Межі Сегментації

Ми бачили, що сегментація вирішує проблему віртуальної пам'яті, що не використовується. 16Kb купи? ОС, швидше за все, створить сегмент фізичної пам'яті розміром 16КБ. Але якщо користувач потім звільняє 2Кб такої пам'яті?Тоді, ОС повинна зменшити сегмент 14Kb. Що робити, якщо тепер програміст запитує 30Kb купи? перешкоджаючи його зростанню. Тоді ОС доведеться шукати вільний простір 30 КБ, а потім переміщати сегмент.

Велика проблема з сегментами в тому, що вони призводять до дуже фрагментованої фізичної пам'яті, тому що вони продовжують зростати, оскільки завдання користувача запитують і звільняють пам'ять.

Іноді, ОС шляхом підсумовування всіх вільних сегментів отримує деяке доступне простір, але оскільки воно не стикається, вона не може використовувати цей простір і повинна відмовити від вимоги процесів, навіть якщо існує простір у фізичній пам'яті.p align="justify"> Операційна система може спробувати стиснути пам'ять шляхом злиття всіх вільних ділянок в один великий шматок, який можна було б використовувати в майбутньому, щоб задовольнити запит пам'яті.

Але такий алгоритм ущільнення складний для CPU, і в цей час жоден процес користувача не зможе отримати CPU: операційна система повністю завантажена реорганізацією своєї фізичної пам'яті, таким чином, система стає непридатною для використання. Сегментація пам'яті вирішує безліч проблем управління пам'яттю та багатозадачності, але вона також показує реальні недоліки. Таким чином, існує необхідність у розширенні можливостей сегментації та виправленні цих недоліків. Звідси утворилося ще одне поняття - "пагінація пам'яті".

Пагінація пам'яті

Пагінація сторінок пам'яті поділяє деякі концепції сегментації пам'яті та намагається вирішити її проблеми. Ми побачили, що основною проблемою сегментації пам'яті є те, що сегменти будуть збільшуватися і зменшуватися дуже часто, так як процес користувача запитує і звільняє пам'ять. Іноді операційна система стикається з проблемою. Вона не може знайти велику область вільного місця, щоб задовольнити запит пам'яті користувача процесу, тому що фізична пам'ять стала сильно фрагментована з часом: вона містить багато сегментів різного розміру по всій фізичній пам'яті, що призводить до сильно фрагментованої фізичної пам'яті.

Розбивка вирішує цю проблему за допомогою простої концепції: що якщо для кожного фізичного розподілу ядро ​​виділятиме фіксований розмір? Сторінки – це сегменти фізичної пам'яті фіксованого розміру.Якщо операційна система використовує розподілу фіксованого розміру, то набагато легше керувати простором, що в результаті зводить нанівець фрагментацію пам'яті.
Давайте покажемо приклад ще раз, припускаючи невеликий 16Кб віртуальний адресний простір, щоб полегшити подання:

З пагінацією ми не говоримо про купу, стек або сегмент коду. Ми розділимо весь процес віртуальної пам'яті на зони фіксованого розміру: ми називаємо їхні сторінки. На наведеному вище прикладі ми розділили адресний простір у вигляді 4 сторінок, 4КБ кожен.

Потім ми робимо те саме з фізичною пам'яттю.

І операційна система просто зберігає те, що називається "Таблиця процесорних сторінок" - зв'язок між однією сторінкою віртуальної пам'яті процесу та базовою фізичною сторінкою (який ми називаємо "сторінка кадру").

За допомогою цього способу управління пам'яттю більше немає проблем у вільному керуванні простором. Кадр сторінки відображається (використовується) чи ні, ядру легко знайти достатню кількість сторінок, щоб задовольнити запит пам'яті процесу користувача. Він просто зберігає список вільних сторінок кадрів, а також переглядає його під час кожного запиту пам'яті. Сторінка є найменшою одиницею пам'яті, якою ОС може керувати. Сторінка (на нашому рівні) є неподільною. Разом зі сторінками до кожного процесу додається таблиця сторінок, яка зберігає адресні переклади. Переклади більше не використовують значення кордону, як це було з сегментацією, а використовує номер віртуальної сторінки (VPN) і зміщення на цій сторінці.

Покажемо приклад перетворення адрес з нумерацією сторінок. Віртуальне адресне місце розміром 16Kb, тобто. нам потрібно 14 біт для подання адреси (2^14 = 16Kb).Розмір сторінки 4 Кб, тому нам потрібно 4kb (16/4), щоб вибрати нашу сторінку:

Тепер, коли процес хоче завантажити, наприклад, адресу 9438 (з 16384 можливостей), це дає 10.0100.1101.1110 у двійковій системі, що призводить до наступного:

Тобто 1246й байт віртуальної сторінки 2 («0100.1101.1110» го байта в «10» сторінці). Тепер операційна система повинна шукати цю сторінку таблиці процесів, щоб дізнатися на якій сторінці 2я карта. Відповідно до того, що ми запропонували, сторінка 2 - це 8К байт у фізичній пам'яті. Таким чином, віртуальна адреса 9438 призводить до фізичної адреси 9442 (8k + 1246 усунення). Ми знайшли наші дані! Як ми вже говорили, існує лише одна таблиця сторінок для кожного процесу, оскільки кожен процес матиме свої власні переклади адреси, так само, як із сегментами. Але зачекайте, де ці таблиці сторінок зберігаються насправді? Вгадайте. у фізичній пам'яті, так, а де ж їй ще бути? Якщо таблиці сторінок самі зберігаються у пам'яті, отже, для кожного доступу до пам'яті, пам'ять повинна мати доступ для отримання VPN. Таким чином, зі сторінками один доступ до пам'яті дорівнює фактично двом доступам до пам'яті: один для отримання запису таблиці сторінок, і один, щоб отримати доступ до «реальних» даних. Знаючи, що доступ до пам'яті повільний процес, отримуємо, що це не найкраща ідея.

Перекладно-асоціативний буфер: TLB

Використання пошукового виклику як механізм ядра для підтримки віртуальної пам'яті може призвести до високої продуктивності витрат. Подрібнення адресного простору на невеликі фіксованого розміру одиниці (сторінки) потребує великої кількості інформації про карту. Тому що інформація про карту, як правило, зберігається у фізичній пам'яті.Логічний пошук підкачки вимагає додаткового пошуку в пам'яті кожної віртуальної адреси, згенерованого програмою. І тут знову приходять апаратні засоби, щоб прискорити та допомогти ОС. У пагінації, як і в сегментації, апаратні засоби допомагають ядру ОС перевести адреси ефективним прийнятним способом. TLB є частиною MMU, лише простий кеш деяких VPN перекладів. TLB буде запобігати доступу ОС до пам'яті від доступу до таблиці сторінок процесу, для отримання фізичної адреси пам'яті з віртуальної. Апаратне забезпечення MMU спрацьовуватиме на кожному віртуальному доступі до пам'яті, витягуючи VPN з цієї адреси, і виконуючи пошук TLB, якщо він збігається для цього конкретного VPN. Якщо він збігся, він просто виконав свою роль. Якщо він отримує промах, то він шукатиме таблицю сторінок процесу, і якщо посилання на пам'ять дійсне, воно оновить TLB, тому будь-який подальший доступ пам'яті цієї сторінки потрапить у TLB.

Як і в будь-якому кеші, ви частіше потрапите, ніж отримаєте промах, оскільки ситуація промах викликає сторінку пошуку, внаслідок чого доступ до пам'яті буде повільним. Ви здогадаєтеся про це. Чим більше сторінок, тим краще TLB потрапляє, але тим більше простору, що не використовується, ви будете мати на кожній сторінці. Тут має бути знайдено компроміс. Сучасні ядра використовують різні розміри сторінки. Ядро Linux може використовувати те, що називається «величезні сторінки», сторінки, розміром 2Mb, що більше традиційних 4Kb. Крім того, інформацію краще зберігати у суміжних адресах пам'яті. Якщо ви скоротите свої дані в пам'яті, то швидше за все страждатимете від перепусток TLB або від переповнення TLB.Це те, що називається Ефективність просторової локальності TLB: Дані, що знаходяться безпосередньо поряд з вами, можуть бути збережені на тій же фізичній сторінці, таким чином, отримуючи вигоду з поточного доступу до пам'яті з TLB.

Для перемикання контексту TLB зберігає також те, що називається ASID у кожному зі своїх записів. Це ідентифікатор адресного простору, який є чимось на зразок PID. Кожен запланований процес має власний ASID, отже TLB може керувати будь-якою адресою процесу без ризику недійсних адрес з інших процесів. Також, якщо процес користувача спробує завантажити неправильну адресу, адреса, швидше за все, не буде збережена в TLB, отже відбудеться промах у пошуку в записі таблиці сторінок процесу. Тепер адреса зберігатиметься, але з невірним бітом. Під X86 кожен переклад використовує 4 байти, таким чином є багато біт. І нерідко можна знайти дійсний біт разом з іншими складовими, такими як брудний біт, біти захисту, опорного біта тощо. ми більше не говоримо про сегменти. Ви повинні знати, що підкачування складніше в сучасних ОС, ніж я пояснив. Сучасні ОС, зазвичай, використовують багаторівневі таблиці сторінок, багатосторінкові розміри, і навіть важливу концепцію, яку ми пояснюватимемо. Сторінка виселення, відома як «swaping» (Процес, коли ядро ​​обмінює сторінки пам'яті на дисковий простір, щоб ефективно використовувати головну пам'ять і створити ілюзію для процесів користувача, що основна пам'ять не обмежена в просторі).

Висновок

Тепер ви знаєте, що знаходиться під повідомленням «Помилка сегментації». Операційна система використовує сегменти для відображення віртуальної пам'яті у фізичній пам'яті. якщо ця адреса не правильна, з меж фізичного сегмента, або якщо права захисту сегменту не підходять, то ОС за замовчуванням посилає сигнал процесу, що викликав відмову: SIGSEGV, який має обробник за умовчанням. Він вбиває процес і виводить повідомлення: «Помилка сегментації». ми маємо можливість доступу до вихідного коду, тут є місце вихідного коду для X86/64 платформ, яке управляє помилками доступу до пам'яті, так само тут і SIGSEGV. Якщо ви зацікавлені в розробці сегментів для X86 / 64 платформ, ви можете подивитися на їх визначення в ядрі Linux. шлях сегментування пам'яті, ніж використання класичних сегментів. Мені сподобалося писати цю статтю, вона перенесла мене в кінець дев'яностих, коли я програмував свій перший CPU: Motorola 68HC11 з використанням C, VHDL і прямого монтажу. але мої перші знання прийшли від електроніки, систем, які ми використовуємо щодня.