Базовий годинниковий алгоритм

Годинниковий алгоритм

Хоч алгоритм LRU реалізувати дуже важко і його апаратна підтримка є лише в деяких системах, все-таки сучасні апаратні архітектури дають змогу хоча б частково використати закладену в ньому ідею – виконати його наближення. Насампе­ред вони підтримують біт використання сторінки (reference bit, R), що перебуває в елементі таблиці сторінок і стає рівним одиниці у разі звертання до відповідної сторінки. Наявність такого біта дає змогу з’ясувати факт звертання до сторінки (не даючи змоги, однак, упорядкувати сторінки за часом звертання до них, що необхідно для LRU-алгоритму). Як було вже показано (розділ 8.3.4), в архітектурі ІА-32 біт R називають прапорцем доступу (Accessed).

Наявність біта використання сторінки є основою алгоритму другого шансу, або годинникового алгоритму (clock algorithm), – одного з найефективніших реально застосовуваних алгоритмів.

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

Спочатку беруть сторінку, що найдовше перебуває у пам’яті (як для FIFO). Якщо її біт використання (R) дорівнює 0, то сторінку негайно замінюють, поміщаючи на її місце нову. Якщо ж біт R дорівнює 1 (до сторінки зверталися), то його покладають рівним 0 (начебто ця сторінка тільки що завантажена у пам’ять), і прохід за списком триває далі, поки не буде знайдена сторінка з R = 0 (а доти біт R для всіх сторінок покладають рівним 0). Знайдену сторінку замінюють, після чого для нової сторінки задають R = 1 і наставляють на неї стрілку (рис. 9.6). У найгіршому випадку (якщо для всіх сторінок біт R дорівнює одиниці) почнеться друге коло обходу списку (другий шанс) і буде замінена найстарша сторінка із тих, що були пройдені на першому колі. У цьому разі алгоритм зводиться до алгоритму FIFO.

Рис. 9.6. Годинниковий алгоритм заміщення сторінок

На рис. 9.7 зображено результат застосування годинникового алгоритму для попереднього рядка посилань; на кожному кроці показане поточне положення стрілки і значення R для кожного фрейму. Зазначимо, що для цього рядка і трьох фреймів годинниковий алгоритм повністю ідентичний LRU (на практиці так буває не завжди).

Рис. 9.7. Результат застосування годинникового алгоритму заміщення с торінок

Годинниковий алгоритм із додатковими бітами

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

У разі використання цього алгоритму кожну сторінку супроводжують не один, а n бітів, які є лічильником використання сторінки Сu (наприклад, при n=8 лічильник можна розглядати як ціле завдовжки один байт), а також біт R. Під час використання сторінки біт R покладають рівним 1. Час від часу (за перериванням від таймера) ОС обходить циклічний список сторінок і поміщає значення біта R у старший біт лічильника, а інші біти зсуває вправо на 1 біт, при цьому молодший біт відкидають. Формула перерахування має такий вигляд:

Біти лічильника в цьому випадку містять історію використання сторінки впродовж останніх n періодів часу між обходами списку. Наприклад, якщо сторінка за цей час не була використана жодного разу, всі біти С_u для неї будуть рівні 0, якщо її використовували щоразу – одиниці. Кожне звертання до сторінки робить значення лічильника використання для неї більшим, ніж для всіх сторінок, які на цьому інтервалі не були використані. Наприклад, бітове значення 10000000 = 128 (сторінка щойно була використана) буде більшим за 01111111 = 127 (сторінка була використана на всіх попередніх інтервалах, крім останнього).

За необхідності вибору сторінки для заміщення береться сторінка із найменшим значенням лічильника С_u. Така сторінка буде LRU-сторінкою для останніх n періодів часу між обходами списку.

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

9.5.6. Буферизація сторінок

Ще однією важливою технологією заміщення сторінок є буферизація сторінок. При цьому в системі підтримуються два списки фреймів – модифікованих фреймів L_m і вільних фреймів L_f. У разі заміщення сторінку не вилучають із пам’яті, а її фрейм вносять в один із цих списків: у список L_m, якщо для неї біт М = 1, і у список L_f, якщо М = 0. Насправді сторінку фізично не вилучають із її фрейму: відповідний їй запис просто вилучають із таблиці сторінок, а інформацію з її фрейму поміщають у кінець відповідного списку.

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

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

Найважливішою властивістю цього алгоритму є те, що списки L_f і L_m працюють як кеші сторінок. Справді, сторінки, що відповідають фреймам із цих списків, продовжують перебувати в пам’яті, а отже, якщо знову виникає необхідність використати таку сторінку, усе, що потрібно зробити, – це повернути відповідний елемент назад у таблицю сторінок, оскільки всі дані цієї сторінки продовжують перебувати у відповідному фреймі.

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

Зазначимо, що використання буферизації сторінок дає змогу обмежитися найпростішим алгоритмом для безпосереднього вибору заміщуваної сторінки, наприклад алгоритмом FIFO. Сторінки, помилково заміщені FIFO-алгоритмом, потраплять не відразу на диск, а спочатку в один зі списків L_f або L_m, тому якщо вони незабаром знадобляться знову, то все ще міститимуться у пам’яті.

Деякі простіші реалізації об’єднують списки L_f i L_m в один. Такий список працює аналогічно до L_f, тільки у разі заміщення сторінки на початку списку при М = 1 вона буде спочатку записана на диск.

Буферизацію сторінок використовують майже в усіх сучасних операційних системах, приклади її реалізації в Linux і Windows ХР будуть показані нижче.

9.5.7. Глобальне і локальне заміщення сторінок

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

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

У більшості сучасних ОС реалізоване глобальне заміщення сторінок або змішаний варіант, за якого більшу частину часу використовують локальне заміщен­ня, а у разі нестачі пам’яті – глобальне.

9.5.8. Блокування сторінок у пам’яті

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

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

2. Процес А видає команду контролеру (вказавши як параметр адресу буфера) і призупиняється, чекаючи введення.

3. ОС перемикає контекст і передає керування процесу В.

4. Процес В генерує сторінкове переривання.

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

6. Внаслідок пошуку алгоритм вибирає для заміщення сторінку, де розташований буфер введення процесу А.

7. ОС заміщає сторінку, зберігаючи її дані на диску і завантажуючи у фрейм нову сторінку.

8. ОС перемикає контекст і передає керування знову процесу А.

9. Контролер починає запис даних за адресою, заданою на кроці 2.

10.Ця адреса тепер відповідає фрейму, у який завантажена сторінка процесу В, у результаті дані процесу В будуть перезаписані, і він швидше за все завершиться аварійно.

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

Використання блокування сторінок у пам’яті не обмежене описаною ситуацією. Приміром, код і дані ОС мають увесь час перебувати в основній пам’яті, тому всі відповідні сторінки варто заблокувати у пам’яті. Пам’ять, що не бере участі у заміщенні сторінок, називають невивантажуваною (nonpaged memory) на противагу вивантажуваній (paged memory).

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

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

9.5.9. Фонове заміщення сторінок

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

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

Фонове заміщення сторінок звичайно використовують разом із буферизацієї сторінок, у цьому разі сторінковий демон переносить фрейми у список L_f або зберігає на диску сторінки зі списку L_m.

9.6. Зберігання сторінок на диску

Дисковий простір, що використовують для зберігання сторінок, називають простором підтримки (backing store) або простором підкачування (swap space), а пристрій (диск), на якому він перебуває, – пристроєм підкачування (swap device). Цей пристрій повинен бути якомога продуктивнішим.

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

9.7. Пробуксовування і керування резидентною множиною

Дата добавления: 2014-01-05