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

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

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

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

50. Організація заміщення сторінок

Списки сторінок

Організація заміщення сторінок у Ьіпих ґрунтується на їх буферизації. Організо­вують два списки сторінок: список активних (ае1іуе_1і8І) — містить сторінки, які використовують процеси і визначає робочий набір процесів; список неактивних (іпае1іуе_1і8і) — містить сторінки, які не так важливі для процесів (не використо­вуються в цей момент часу). Модифікована сторінка перебуває в списку неактив­них якийсь час, перш ніж її збережуть

на диску.

Нові сторінки додають у початок списку неактивних сторінок. За нестачі па­м'яті частину сторінок переміщують з кінця списку активних сторінок у початок списку неактивних, а потім починають вивільнення сторінок із кінця списку не­активних сторінок

Обробка відображених, змінених і заблокованих сторінок

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

• Сторінка може бути відображена в адресний простір процесу або кількох про­цесів. Щоб вивільнити сторінку, відображення спочатку потрібно вилучити для кожного такого процесу.

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

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