Материал: ОСиС. Лабораторная работа 10

Рассмотрим пример. Допустим, дана ссылочная строка 1 3 0 3 5 6 и число страниц — 3. Посмотрим, как работает алгоритм FIFO.

Изначально все слоты пусты, поэтому после первых 3-х проходов они будут заполнены {1, 3, 0}. Page_Fault = 3.

3: Frame = {1, 3, 0}, Page_Fault = 3 (без изменений). 5: Frame = {3, 0, 5}, Page_Fault = 4 (отказ страницы). 6: Frame = {0, 5, 6}, Page_Fault = 5 (отказ страницы).

Clock (Second-Chance)

При алгоритме «Часы» (или «Второй шанс») страницы-кандидаты на удаление рассматриваются в порядке циклического перебора. Заменяемая страница — та, к которой при циклическом рассмотрении не было доступа с момента ее последнего рассмотрения.

Алгоритм часов хранит в памяти круговой список страниц, при этом «рука» (указатель — Pointer) указывает на последнюю рассмотренную страницу в списке. Когда происходит отказ страницы, то бит R проверяется в местоположении руки. Если R равно 0, новая страница помещается на место страницы, на которую указывает «рука», и рука перемещается на одну позицию. В противном случае бит R очищается, затем стрелка часов увеличивается, и процесс повторяется, пока страница не будет заменена.

Допустим, дана ссылочная строка 0 4 1 4 2 4 3 4 2 4 0 4 1 4 2 4 3 4 и число страниц — 3. Посмотрим, как работает алгоритм.

Изначально все слоты пусты, поэтому после первых 3-х проходов они будут заполнены {0, 4, 1}, а массив второго шанса будет {0, 0, 0}.

4: Frame = {0, 4, 1}, Second_Chance = {0, 1, 0} [4 получил второй шанс], Pointer = 0 (обновлять страницу не нужно), Page_Fault = 3 (нет увеличения числа ошибок страницы).

2: Frame = {2, 4, 1}, Second_Chance = {0, 1, 0} [0 заменен на 2; у 0 второго шанса не было], Pointer = 1 (обновлено), Page_Fault = 4.

4: Frame = {2, 4, 1}, Second_Chance = {0, 1, 0}, Pointer = 1, Page_Fault =

4 (без изменений).

6

3: Frame = {2, 4, 3}, Second_Chance = {0, 0, 0} [4 воспользовался вторым шансом; но у 1 не было: заменен на 3], Pointer = 0 (поскольку третий элемент был заменен, указатель перемещается далее), Page_Fault = 5.

4: Frame = {2, 4, 3}, Second_Chance = {0, 1, 0} [4 получил второй шанс],

Pointer = 0, Page_Fault = 5.

2: Frame = {2, 4, 3}, Second_Chance = {1, 1, 0} [2 получил второй шанс],

Pointer = 0, Page_Fault = 5.

4: Frame = {2, 4, 3}, Second_Chance = {1, 1, 0}, Pointer = 0, Page_Fault =

5 (без изменений).

0: Frame = {2, 4, 0}, Second_Chance = {0, 0, 0}, Pointer = 0, Page_Fault =

6 (2 и 4 воспользовались вторым шансом).

4: Frame = {2, 4, 0}, Second_Chance = {0, 1, 0}, Pointer = 0, Page_Fault =

6 (4 получил второй шанс).

1: Frame = {1, 4, 0}, Second_Chance = {0, 1, 0}, Pointer = 1, Page_Fault =

7 ( Pointer обновлен, Page_Fault обновлен).

4: Frame = {1, 4, 0}, Second_Chance = {0, 1, 0}, Pointer = 1, Page_Fault =

7 (без изменений).

2: Frame = {1, 4, 2}, Second_Chance = {0, 0, 0}, Pointer = 0, Page_Fault =

8 (4 воспользовался вторым шансом).

4: Frame = {1, 4, 2}, Second_Chance = {0, 1, 0}, Pointer = 0, Page_Fault =

8 (4 получил второй шанс).

3: Frame = {3, 4, 2}, Second_Chance = {0, 1, 0}, Pointer = 1, Page_Fault = 9 (Pointer и Page_Fault обновлен).

4: Frame = {3, 4, 2}, Second_Chance = {0, 1, 0}, Pointer = 1, Page_Fault =

9 (без изменений).

LRU

LRU на самом деле является семейством алгоритмов.

Суть алгоритмов LRU (Least Recently Used) заключается в вытеснении давно неиспользуемой страницы.

7

Допустим, дана ссылочная строка 1 2 3 4 1 2 5 1 2 3 4 5 и число страниц

— 3. Посмотрим, как работает алгоритм LRU сначала в прямом и затем в обратном порядке (ReverseLRU).

Изначально все слоты пусты, поэтому после первых 3-х проходов они будут заполнены {1, 2, 3}. Page_Fault = 3.

4: Frame = {2, 3, 4}, Page_Fault = 4 (отказ страницы). 1: Frame = {3, 4, 1}, Page_Fault = 5 (отказ страницы). 2: Frame = {4, 1, 2}, Page_Fault = 6 (отказ страницы). 5: Frame = {1, 2, 5}, Page_Fault = 7 (отказ страницы). 1: Frame = {2, 5, 1}, Page_Fault = 7 (без изменений). 2: Frame = {5, 1, 2}, Page_Fault = 7 (без изменений). 3: Frame = {1, 2, 3}, Page_Fault = 8 (отказ страницы). 4: Frame = {2, 3, 4}, Page_Fault = 9 (отказ страницы). 5: Frame = {3, 4, 5}, Page_Fault = 10 (отказ страницы).

Теперь посмотрим, как работает алгоритм ReverseLRU.

Изначально все слоты пусты, поэтому после первых 3-х проходов они будут заполнены {3, 2, 1} (обратный порядок). Page_Fault = 3.

4: Frame = {4, 3, 2}, Page_Fault = 4 (отказ страницы). 1: Frame = {1, 4, 3}, Page_Fault = 5 (отказ страницы). 2: Frame = {2, 1, 4}, Page_Fault = 6 (отказ страницы). 5: Frame = {5, 2, 1}, Page_Fault = 7 (отказ страницы). 1: Frame = {1, 5, 2}, Page_Fault = 7 (без изменений). 2: Frame = {2, 1, 5}, Page_Fault = 7 (без изменений). 3: Frame = {3, 2, 1}, Page_Fault = 8 (отказ страницы). 4: Frame = {4, 3, 2}, Page_Fault = 9 (отказ страницы). 5: Frame = {5, 4, 3}, Page_Fault = 10 (отказ страницы).

Оба алгоритма приводят к одному результату (Page_Fault), но реализованы по-разному.

LFU

Суть алгоритма LFU (Least Frequently Used) заключается в вытеснении наименее часто используемой страницы.

8

Допустим, дана ссылочная строка 1 2 3 4 1 2 5 1 2 3 4 5 и число страниц

— 3. Посмотрим, как работает алгоритм LFU.

Изначально все слоты пусты, поэтому после первых 3-х проходов они будут заполнены {1, 2, 3}. Page_Fault = 3.

4: Frame = {2, 3, 4}, Page_Fault = 4 (отказ страницы). 1: Frame = {1, 3, 4}, Page_Fault = 5 (отказ страницы). 2: Frame = {2, 3, 4}, Page_Fault = 6 (отказ страницы). 5: Frame = {3, 4, 5}, Page_Fault = 7 (отказ страницы). 1: Frame = {1, 4, 5}, Page_Fault = 8 (отказ страницы). 2: Frame = {2, 4, 5}, Page_Fault = 9 (отказ страницы). 3: Frame = {3, 4, 5}, Page_Fault = 10 (отказ страницы). 4: Frame = {3, 5, 4}, Page_Fault = 10 (без изменений). 5: Frame = {3, 4, 5}, Page_Fault = 10 (без изменений).

Практическая часть Реализуем все рассмотренные ранее алгоритмы при помощи

фреймворка Qt (https://www.qt.io/, версия 5.7.1; GCC 6.3.0 от 15.04.2017), используя язык C++.

Код приведен в следующем пункте отчета. Запустим программу (рис. 1).

Рисунок 1 — Первый запуск Будем проверять работу на ссылочной строке «1 2 3 4 1 2 5 1 2 3 4 5» и

при числе страниц, равным 3.

9

Ссылочная строка может содержать только числа, разделенные пробелами, запятыми, точками с запятыми и точками. Т. е. выбранная нами ссылочная строка может выглядеть как «1, 2; 3, 4, 1; 2; 5. 1, 2,;,;,3 ;,;.;.; 4.,.5».

Проверим FIFO (рис. 2).

Рисунок 2 — Работа алгоритма FIFO при трех страницах Проверим Clock (рис. 3).

Рисунок 3 — Работа алгоритма Clock при трех страницах Проверим ReverseLRU (рис. 4).

10