Лекція: Управління внутрішньою пам‘яттю.

Матеріал з Фізмат Вікіпедії
Перейти до: навігація, пошук

Функції ОС щодо керування пам'яттю

Пам'ять є найважливішим ресурсом, що вимагає ретельного управління мультипрограмною операційною системою. Функціями ОС щодо керування пам'яттю є:

  1. відстеження вільної і зайнятої пам'яті;
  2. виділення пам'яті процесам і звільнення пам'яті при завершенні процесів;
  3. витіснення процесів з оперативної пам'яті на диск, якщо розміри основної пам'яті недостатні для розміщення в ній усіх процесів, і повернення їх у оперативну пам'ять, коли в ній звільняється місце.
  4. налагодження адрес програми на конкретну область фізичної пам'яті.

Усі ЕОМ використовують, у загальному випадку, два типи пам’яті: зовнішню — як правило дискові накопичувачі, і внутрішню — оперативну. Відповідно управління пам’яттю здійснюється на основі:

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

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

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

Стосовно розташування процесів у основній пам'яті, виділяють два методи:

  • метод суміжного розміщення;
  • метод несуміжного розміщення.
Рис. 1. Суміжне розміщення програми в основній пам’яті

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

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

Рис. 2. Несуміжне розміщення програми в основній пам’яті

Методи розподілу пам'яті без використання дискового простору

Розподіл пам'яті фіксованими розділами

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

Рис. 3. Розподіл пам’яті фіксованими розділами

Підсистема управління пам'яттю в цьому випадку виконує задачі:

  1. порівнюючи розмір програми, що надійшла на виконання і вільних розділів, вибирає придатний розділ,
  2. здійснює завантаження програми і настроювання адрес.

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

Розподіл пам'яті розділами змінного розміру

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

На показаний стан пам'яті в різні моменти часу при використанні динамічного розподілу. У момент /0 у пам'яті знаходиться тільки ОС, а до моменту /у пам'ять розділена між 5 задачами, причому задача 774, завершуючись, залишає пам'ять. На вивільнене місце після задачі 774 завантажується задача 776, що надійшла в момент ї3.

Рис. 4. Розподіл пам’яті з динамічними розділами

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

При реалізації даного методу управління пам'яттю необхідно забезпечити у операційній системі:

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

У порівнянні з методом розподілу пам'яті фіксованими розділами даний метод має набагато більшу гнучкість, але йому властивий недолік - фрагментація пам’яті.

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

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

Переміщувані розділи

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

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

Рис. 5. Розподіл пам’яті переміщуваними розділами

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

Методи розподілу пам'яті з використанням дискового простору

Поняття віртуальної пам'яті

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

Віртуальний ресурс - ресурс, що надається користувачу чи програмі користувача таким, що має певні властивості, якими він у дійсності не володіє. Наприклад:

  1. користувачу може бути надана віртуальна оперативна пам'ять, розмір якої перевершує всю наявну в системі фізичну оперативну пам'ять;
  2. користувач пише програми так, начебто в йогорозпорядженні є однорідна оперативна пам'ять великого обсягу, але в дійсності всі дані, які використовуються програмою, зберігаються на одному чи кількох різнорідних запам'ятовуючих пристроях, як правило - дисках, і при необхідності частинами завантажуються у реальну пам'ять.

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

Операційна система при використанні віртуальної пам'яті повинна вирішувати задачі:

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

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

Сторінковий розподіл

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

Сторінкова організація пам’яті — апаратно підтримується процесорами, починаючи з І80386 В оперативній пам'яті знаходяться тільки активні сторінки, а інші розташовані на диску, віртуальній пам’яті. При доступу процесу до пам'яті віртуальна адреса перетворюється модулем управління пам'яттю операційної системи у фізичну адресу сторінки. Доступ здійснюється відразу, якщо сторінка знаходиться в оперативній пам'яті. Якщо дана сторінка знаходиться на диску, то вона спочатку завантажується в оперативну пам'ять. При цьому одна з активних сторінок витісняється на диск.

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

Рис. 6. Сторінковий розподіл пам’яті

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

У даній ситуації може бути використано кілька різних критеріїв вибору, найбільш використовувані з них:

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

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

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

На продуктивність системи зі сторінковою організацією пам'яті впливають часові витрати, пов'язані з опрацюванням сторінкових переривань і перетворенням віртуальної адреси у фізичну. Якщо сторінкові переривання виникають часто, то система може витрачати велику кількість часу на свопінг сторінок. Щоб зменшити частоту сторінкових переривань, доцільно збільшувати розмір сторінки. Крім того, збільшення розміру сторінки зменшує розмір таблиці сторінок, а значить зменшує витрати пам'яті. З іншого боку, якщо сторінка велика, значить велика і фіктивна область в останній віртуальній сторінці кожної програми, у середньому для кожної програми втрачається половина обсягу сторінки, тому сумарний обсяг, при великій сторінці, може скласти значну величину. Час перетворення віртуальної адреси у фізичну у значній мірі визначається часом доступу до таблиці сторінок. У зв'язку з цим таблицю сторінок розміщають в „швидких” запам’ятовуючих пристроях: це може бути, наприклад, набір спеціальних регістрів чи пам'ять з асоціативним пошуком та кешуванням.

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

Сегментний розподіл

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

Наприклад:

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

Рис. 7.Сегментний розподіл пам’яті

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

Система із сегментною організацією функціонує аналогічно системі зі сторінковою організацією: час від часу відбуваються переривання, пов'язані з відсутністю потрібних сегментів у пам'яті, при необхідності звільнення пам'яті деякі сегменти вивантажуються, при кожному звертанні до оперативної пам'яті виконується перетворення віртуальної адреси у фізичну. Крім того, при звертанні до пам'яті перевіряються права доступу до даного сегмента. Віртуальна адреса при сегментній організації пам'яті може бути представлена парою (g,s) де g - номер сегмента, а s — зміщення у сегменті. Фізичну адресу отримують шляхом додавання початкової фізичної адреси сегмента, знайденого в таблиці сегментів за номером g, і зміщенням s.

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

Сторінково-сегментний розподіл

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

Свопінг

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

Свопінг — тимчасове повне вивантаження процесу, що знаходяться в стані чекання, у зовнішню пам’ять.

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

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

Ієрархія запам'ятовуючих пристроїв. Кешування даних

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

Рис. 8. Ієрархія запам’ятовуючих пристроїв

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

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

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

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

  1. переглядається вміст кеш-пам'яті з метою визначення, чи не знаходяться потрібні дані в кеш-пам'яті; кеш-пам'ять не адресується, тому пошук потрібних даних здійснюється по вмісту - значенню поля "адреси в оперативній пам'яті", узятому з запиту;
  2. якщо дані виявляються в кеш-пам'яті, то вони зчитуються з неї, результат передається процесору;
  3. якщо потрібних даних немає, то вони копіюються з оперативної пам'яті в кеш-пам'ять, і результат виконання запиту передається процесору;

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

На практиці у кеш-пам'ять зчитується не один елемент даних, до якого відбулося звертання, а цілий блок даних, це збільшує ймовірність так званого “влучання у кеш”, тобто перебування потрібних даних у кеш-пам'яті.

Покажемо, як середній час доступу до даних залежить від ймовірності влучання у кеш. Нехай маємо основний запам'ятовуючий пристрій із середнім часом доступу до даних t1 i кеш-пам'ять, що має час доступу t2, відповідно t2<t1. Позначимо через t середній час доступу до даних у системі з кеш-пам'яттю, а через р - імовірність влучання у кеш. Відповідно до формули повної імовірності:

t = t1((1 - р) + t2(1-р)

З неї видно, що середній час доступу до даних у системі з кеш-пам'яттю лінійно залежить від імовірності влучання у кеш і змінюється від середнього часу доступу до основного запам’ятовуючого пристрою (при р=0) до середнього часу доступу безпосередньо до кеш-пам'яті (при р=1). У реальних системах імовірність влучання у кеш складає приблизно 0,9. Високе значення імовірності перебування даних у кеш-пам'яті пов'язано з наявністю в даних об'єктивних властивостей: просторової і часової локальності.

Просторова локальність. Якщо відбулося звертання до деякої адреси, то існує досить велика ймовірність, що найближчим часом відбудеться звертання до сусідніх адрес.

Часова локальність. Якщо відбулося звертання до деякої адреси, то існує досить велика ймовірність, що наступне звертання до цієї ж адреси відбудеться найближчим часом.

Рис. 9. Організація дискової кеш-пам’яті

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