Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Взаємодія з диском під час керування пам'яттю
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра електронні обчислювальні машини
Інформація про роботу
Рік:
2013
Тип роботи:
Доповідь
Предмет:
Інші
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Кафедра «Електронні обчислювальні машини»
/
Доповідь на тему:
«Взаємодія з диском під час керування пам'яттю»
Причини використання диска під час керування пам'яттю
Тимчасове збереження окремих частин адресного простору на диску допомагає розв'язати одну з основних проблем, що виникають під час реалізації керування пам'яттю в ОС, а саме: організацію завантаження і виконання програм, які окремо або разом не вміщаються в основній пам'яті. Найпростішим і найдавнішим підходом є завантаження і вивантаження всього адресного простору процесу за один прийом. Процеси завантажуються у пам'ять повністю, виконуються певний час, а потім так само повністю вивантажуються на диск. Отже, процес або весь перебуває у пам'яті, або цілком зберігається на диску (про такий процес прийнято говорити, що він перебуває у вивантаженому стані).
Така технологія має низку недоліків:
• її використання призводить до значної фрагментації зовнішньої пам'яті;
• вона не дає змоги виконувати процеси, які мають потребу у більшому обсязі пам'яті, ніж доступно у системі;
• погано підтримуються процеси, які можуть виділяти собі додаткову динамічну пам'ять (це необхідно робити з урахуванням можливого розширення адресного простору процесу).
Вивантаження всього процесу із пам'яті у сучасних ОС можна використовувати як засіб зниження навантаження, але лише на доповнення до інших технологій взаємодії з диском.
2. Поняття підкачування
Описана технологія повного завантаження і вивантаження процесів традиційно називалася підкачуванням або простим підкачуванням. У сучасних ОС під підкачуванням (swapping) розуміють увесь набір технологій, які здійснюють взаємодію із диском під час реалізації віртуальної пам'яті, щоб дати можливість кожному процесу звертатися до великого діапазону логічних адрес за рахунок використання дискового простору.
Розглянемо загальні принципи підкачування. Як відомо, зняття вимоги неперервності фізичного простору, куди відображається адресний простір процесу, і можливість переміщення процесу в пам'яті під час його виконання дає змогу не тримати одночасно в основній пам'яті всі блоки пам'яті (сторінки або сегменти), які утворюють адресний простір цього процесу. Під час завантаження процесу в основну пам'ять у ній розміщають лише кілька його блоків, які потрібні для початку роботи. Частину адресного простору процесу, що у конкретний момент часу відображається на основну пам'ять, називають резидентною множиною процесу (resident set). Поки процес звертається тільки до пам'яті резидентної множини, виконання процесу не переривають. Як тільки здійснюється посилання на блок, що перебуває за межами резидентної множини (тобто відображений на диск), відбувається апаратне переривання. Оброблювач цього переривання призупиняє процес і запускає дискову операцію читання потрібного блоку із диска в основну пам'ять. Коли блок зчитаний, операційну систему сповіщають про це, після чого процес переводять у стан готовності й, зрештою, поновлюють, після чого він продовжує свою роботу, ніби нічого й не сталося; на момент його поновлення потрібний блок уже перебуває в основній пам'яті, де процес і розраховував як його знайти.
Реалізація підкачування використовує правило «дев'яносто до десяти». Ідеальною реалізацією керування пам'яттю є надання кожному процесові пам'яті, за розміром порівнянної із жорстким диском, а за швидкістю доступу — з основною пам'яттю. Оскільки за правилом «дев'яносто до десяти» на 10 % адресного простору припадає 90 % посилань на пам'ять, як деяке наближення до ідеальної реалізації можна розглядати такий підхід: зберігати ці 10 % в основній пам'яті, а інший адресний простір відображати на диск. Як показано на рис. 9.1, частіше використовують сторінки 0,3,4,6, тому їхній вміст зберігають в основній пам'яті, а сторінки 1, 2, 5, 7 використовують рідше, тому їхній вміст зберігають на диску. Головною проблемою залишається ухвалення рішення про те, які із блоків па м'яті мають в конкретний момент відображатися на основну пам'ять, а які — на диск. Внаслідок використання технології підкачування кількість виконуваних процесів збільшується (для кожного з них в основній пам'яті перебуватиме тільки частина блоків). Підкачування дає також змогу виконувати процеси, які за розміром більші, ніж основна пам'ять (для таких процесів у різні моменти часу в основ ну пам'ять відображатимуться різні блоки).
/
3. Завантаження сторінок на вимогу. Особливості підкачування сторінок
Базовий підхід, який використовують під час реалізації підкачування сторінок із диска, називають технологією завантаження сторінок на вимогу (demand paging). Ця технологія діє у припущенні, що не всі сторінки процесу мають завантажуватися у пам'ять негайно. Завантажуються тільки ті, що необхідні для початку його роботи, інші — коли стають потрібні. Процес переносу сторінки із диска у пам'ять називають завантаженням із диска (swapping in), процес переносу сторінки із пам'яті на диск — вивантаженням на диск (swapping out).
Для організації апаратної підтримки підкачування кожний елемент таблиці сторінок має містити спеціальний біт — біт присутності сторінки у пам'яті Р. Коли він дорівнює одиниці, то це означає, що відповідна сторінка завантажена в основну пам'ять, і їй відповідає деякий фрейм. Якщо біт присутності сторінки дорівнює нулю, це означає, що дана сторінка перебуває на диску і має бути завантажена в основну пам'ять перед використанням (рис. 9.2)./
Для сторінки може бути заданий біт модифікації М. Його спочатку (під час завантаження сторінки із диска) покладають рівним нулю, потім - одиниці, якщо сторінку модифікують, коли вона завантажена у фрейм основної пам'яті. Наявність такого біта дає змогу оптимізувати операції вивантаження сторінок на диск. Коли намагаються вивантажити на диск вміст сторінки, для якої біт М дорівнює нулю, це означає, що записування на диск можна проігнорувати, бо вміст сторінки не змінився від часу завантаження у пам'ять. У розділі 9.5 побачимо, як цей біт можна використати для реалізації заміщення сторінок (визначення сторінки, яку потрібно вивантажити на диск у разі нестачі фреймів фізичної пам'яті). У таблиці сторінок архітектури ІА-32 даний біт називають Dirty. Якщо процес працює тільки зі сторінками, для яких біт Р дорівнює одиниці (його резидентна множина не змінюється), складається враження, що всі його сторінки є у пам'яті, хоча насправді це може бути і не так. (просто сторінок, яких немає у пам'яті, у цьому разі взагалі не використовують).
Поняття сторінкового переривання
Kоли процес робить спробу доступу до сторінки, для якої біт Р дорівнює нулю, то, як ми вже бачили під час вивчення загальної стратегії підкачування, відбувається апаратне переривання. Його називають сторінковим перериванням або сторінковою мовою (page fault). ОС має обробити це переривання.
• Сторінку перевіряють на доступність для цього процесу (діапазон доступної пам'яті зберігається у структурі даних процесу).
• Якщо сторінка недоступна, процес переривають, якщо доступна, знаходять вільний фрейм фізичної пам'яті та ставлять у чергу дискову операцію читання потрібної сторінки в цей фрейм.
• Після читання модифікують відповідний запис таблиці сторінок (біт присутності покладають рівним одиниці).
• Перезапускають інструкцію, що викликала апаратне переривання. Тепер процес може отримати доступ до сторінки, ніби вона завжди була в па м'яті. Процес поновлюють у тому самому стані, в якому він був перед перериванням. Чисте завантаження сторінок на вимогу зводиться до того, що жодну сторінку не завантажують у пам'ять завчасно. При цьому після запуску процесу жодна з його сторінок не перебуватиме в пам'яті: усі вони будуть довантажуватися внаслідок сторінкових переривань за потребою. Є альтернативні підходи (наприклад, попереднє завантаження сторінок), які будуть описані далі. Зазначимо, що в загальному випадку сторінкове переривання не обов'язково спричиняє підкачування сторінки з диска; воно може бути результатом звертання до сторінки, що не належить до адресного простору процесу. У цьому разі має бути згенерована помилка. З іншого боку, причиною сторінкового переривання під час чистого завантаження на вимогу може бути звертання до зовсім нової сторін ки пам'яті, яка жодного разу не була використана процесом. Оброблювач може зарезервувати новий фрейм, проініціалізувати його (наприклад, заповнити нуля ми) і поставити йому у відповідність сторінку.
Продуктивність завантаження на вимогу
Реалізація завантаження на вимогу із підкачуванням сторінок із диска може істотно впливати на продуктивність ОС. Зробимо найпростіший розрахунок такого впливу. Спрощену характеристику, яку використовують для оцінки продуктивності системи із завантаженням сторінок на вимогу, називають ефективним часом доступу і розраховують за такою формулою:
/
де Ppf - імовірність сторінкового переривання; Тта - середній час доступу до пам'яті; Трf — середній час обробки сторінкового переривання. У сучасних системах час доступу до пам'яті Тта становить від 20 до 200 не. Розрахуємо час обробки сторінкового переривання Трf.
Коли відбувається сторінкове переривання, система виконує багато різноманітних дій (генерацію переривання, виклик оброблювача, збереження регістрів процесора, перевірку коректності доступу до пам'яті, початок операції читання із диска, перемикання контексту на інший процес, обробку переривання від диска про завершення операції читання, корекцію таблиці сторінок тощо). У результаті кількість інструкцій процесора, необхідних для обробки сторінкового переривання, виявляється дуже великою (десятки тисяч), і середній час обробки сягає кількох мілісекунд (одна мілісекунда відповідає мільйону наносекунд). Припустимо, що величина Тта становить 100 нc, Tpf — 10 мс, а ймовірність виникнення сторінкового переривання - 0,001 (одне переривання на 1000 звертань до пам'яті, цю величину називають рівнем сторінкових переривань — page fault rate). Тоді ефективний час доступу буде рівний:
Теа - (1 - 0,001) х 100 + 0,001 х 10 000 000 = 10 099,9 не.
Як бачимо, внаслідок сторінкових переривань, що виникають з імовірністю одна тисячна, ефективний час доступу виявився в 100 разів більшим, ніж під час роботи з основною пам'яттю, тобто продуктивність системи знизилася в 100 ра зів. Щоб здобути зниження продуктивності на прийнятну величину, наприклад на 10 %, необхідно, щоб імовірність сторінкового переривання була приблизно одна мільйонна:
Рр/ = (0,1 х Тта) / (Гр/ - Тта) =10/9 999 900 - 1 / 999 990.
Для досягнення прийнятної продуктивності системи із завантаженням сторінок на вимогу рівень сторінкових переривань має бути надзвичайно низьким, тому будь-які поліпшення в алгоритмах керування пам'яттю, що знижують цей рівень, завжди виправдані. По суті, будь-які витрати часу на виконання найскладніших алгоритмів окупатимуться, якщо зменшується кількість сторінкових переривань, оскільки одне таке переривання обробляється повільніше, ніж виконується алгоритм майже будь-якої складності.
4. Проблеми реалізації підкачування сторінок
Під час реалізації підкачування потрібно дати відповідь на такі запитання.
1. Які сторінки потрібно завантажити із диска і в який час? Відповідь на це запитання визначає прийнята в цій системі стратегія вибірки сторінок. Однією з таких стратегій є завантаження сторінок на вимогу, яку щойно було розглянуто, коли сторінку завантажують у пам'ять тільки під час обробки сторінкового переривання. Іншою стратегією такого роду є попереднє завантаження сторінок (prepaging), коли у пам'ять завантажують кілька сторінок, розташованих на диску послідовно для того щоб зменшити кількість таких сторінкових переривань. Ця технологія ґрунтується на принципі локалізації, але переваги у продуктивності у разі її застосування довести не вдалося.
2. Яку сторінку потрібно вивантажити на диск, коли вільних фреймів у основній пам'яті більше немає?
Відповідь на це запитання визначає стратегія заміщення сторінок.
З. Де у фізичній пам'яті мають розміщуватися сторінки процесу? Відповідь на це запитання визначає стратегія розміщення. Вона відіграє важливу роль під час реалізації підкачування на основі сегментації, у разі підкачування на основі сторінкової організації вона не така важлива, оскільки всі сторінки рівноправні й можуть перебувати у пам'яті де завгодно.
4. Яким чином організувати керування резидентною множиною? Головне завдання такого керування — забезпечити, щоб у резидентній множині були тільки сторінки, які дійсно потрібні процесу.
5. Заміщення сторінок. Оцінка алгоритмів заміщення сторінок.
Під час генерації сторінкового переривання може виникнути ситуація, коли жодного вільного фрейму у фізичній пам'яті немає. Причини появи цієї проблеми полягають в особливостях використання завантаження сторінок на вимогу. Припустимо, що в нашій системі кожен процес у конкретний момент часу в середньому звертається тільки до половини своїх сторінок. Завантаження сторінок на вимогу залишає половину Сторінок кожного процесу на диску, вивільняючи половину фреймів фізичної пам'яті, які міг би зайняти цей процес, для ви конання інших процесів. Тому можна завантажити у пам'ять більше процесів. Нехай основна пам'ять містить 60 фреймів. Якщо не використовувати завантаження на вимогу, в основну пам'ять можна завантажити шість процесів, кожен із яких використає 10 сторінок, причому кожній сторінці буде відповідати певний фрейм. У разі використання завантаження на вимогу ці шість процесів у конкретний момент часу використовуватимуть тільки ЗО фреймів пам'яті, а інші ЗО за лишатимуться вільними, тому можна завантажити в них ще до шести процесів (у сумі — до дванадцяти). Припустимо, що у пам'ять завантажено одночасно вісім процесів; у цьому разі процесор використовуватиметься активніше, ніж для шести запущених процесів, крім того, вивільниться 20 фреймів. Однак загальний обсяг адресного простору завантажених процесів перевищуватиме обсяг фізичної пам'яті. Поки процеси використовують свої сторінки звичайним чином (на 50 %), всі вони будуть виконуватися в основній пам'яті без проблем. Але завжди може ви никнути ситуація, коли процеси зажадають більше пам'яті, ніж їм це потрібно в середньому. Згадані вісім процесів можуть у якийсь момент зажадати весь свій адресний простір, тому всього їм знадобиться 80 фреймів основної пам'яті (а їх тільки 60). Що більше процесів одночасно виконується в системі, то вища ймовірність виникнення такої ситуації. Як домогтися того, щоб вона виникала не дуже часто, розглянемо в розділі 9.7. У цьому розділі зупинимося на діях, яких вимагають від ОС, коли така ситуація вже виникла. За відсутності вільного фрейму в пам'яті ОС має вибрати, яку сторінку вилучити із пам'яті для того щоб вивільнити місце для нової сторінки. Процес цього вибору визначає стратегія заміщення сторінок. Коли сторінка, яку вилучають,
була змінена, необхідно вивантажити її на диск для відображення цих змін, коли ж вона залишилася незмінною (наприклад, це була сторінка із програмним кодом), цього робити не потрібно. Для індикації того, чи була сторінка змінена, використовують біт модифікації сторінки М (про нього йшлося в розділі 9.3.1). Яку саме сторінку потрібно вилучати із пам'яті, визначає алгоритм заміщення сторінок (page replacement algorithm). Вибір такого алгоритму відчутно впливає на продуктивність системи, тому що вдало підібраний алгоритм зменшує кіль кість сторінкових переривань, а невдала його реалізація може її значно збільшити (якщо вилучити часто використовувану сторінку, то вона незабаром може знову знадобитися і т. д.). Навіть невеликі поліпшення в методах заміщення сторінок можуть спричинити великий загальний виграш у продуктивності. Слід зазначити, що алгоритми заміщення сторінок (особливо ті, які справді дають виграш у продуктивності) досить складні в реалізації і майже завжди потребують апаратної підтримки (хоча б у вигляді наявності біта модифікації сторінки М). Ось який вигляд матиме алгоритм завантаження сторінки з урахуванням заміщення сторінок. 1. Знайти вільний фрейм у фізичній пам'яті: а) якщо вільний фрейм є, використати його (перейти до кроку 2); б) якщо вільного фрейму немає, використати алгоритм заміщення сторінок для того щоб знайти фрейм-жертву (victim frame); в) записати фрейм-жертву на диск (якщо біт модифікації для нього ненульо- вий), відповідно змінити таблицю сторінок і таблицю вільних фреймів. 2. Знайти потрібну сторінку на диску. 3. Прочитати потрібну сторінку у вільний фрейм (якщо раніше були виконані кроки 6\ в п. 1, цим фреймом буде той, котрий щойно вивільнився). 4. Знову запустити інструкцію, на якій відбулося переривання.
Оцінка алгоритмів заміщення сторінок.
Рядок посилань Оскільки реалізація алгоритмів заміщення сторінок важлива з погляду продуктивності системи, вони ретельно досліджувалися, були виділені критерії їхнього порівняння і формат даних для тестування. Критерієм для порівняння алгоритмів заміщення звичайно є рівень сторінкових переривань: що він нижчий, то кращим вважають алгоритм. Оцінку алгоритму здійснюють через підрахунок кількості сторінкових переривань, які виникли внаслідок його запуску для конкретного набору посилань на сторінки у пам'яті. Набір посилань на сторінки подають рядком посилань (reference string) із номера ми сторінок. Такий рядок можливо згенерувати випадково, а можна отримати відстеженням посилань на пам'ять у реальній системі (у цьому разі даних може бути зібрано дуже багато). Групу із кількох посилань, що йдуть підряд, на одну й ту саму сторінку в рядку відображають одним номером сторінки, оскільки такий набір посилань не може спричинити сторінкового переривання.
У цьому розділі використовуватимемо такий рядок посилань:
1,2,3,5,2,4,2,4,3,1,4. Щоб оцінити алгоритми заміщення, потрібно також зазначити кількість доступ них фреймів. Чим вона більша, тим меншим буде рівень сторінкових переривань, тому алгоритми оцінюють для однакових її значень. Зазначимо, що, коли доступ ний один фрейм, кожен елемент рядка посилань викликатиме сторінкове переривання; з іншого боку, якщо кількість доступних фреймів дорівнює кількості різних сторінок у рядку посилань, сторінкових переривань не буде зовсім. Алгоритми оцінюватимемо для трьох доступних фреймів.
Оскільки реалізація алгоритмів заміщення сторінок важлива з погляду продуктивності системи, вони ретельно досліджувалися, були виділені критерії їхнього порівняння і формат даних для тестування. Критерієм для порівняння алгоритмів заміщення звичайно є рівень сторінкових переривань: що він нижчий, то кращим вважають алгоритм. Оцінку алгоритму здійснюють через підрахунок кількості сторінкових переривань, які виникли внаслідок його запуску для конкретного набору посилань на сторінки у пам'яті. Набір посилань на сторінки подають рядком посилань (reference string) із номера ми сторінок. Такий рядок можливо згенерувати випадково, а можна отримати відстеженням посилань на пам'ять у реальній системі (у цьому разі даних може бути зібрано дуже багато). Групу із кількох посилань, що йдуть підряд, на одну й ту саму сторінку в рядку відображають одним номером сторінки, оскільки такий набір посилань не може спричинити сторінкового переривання.
20.05.2013 23:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора