7. Организация таблиц страниц. Политики замещения страниц.

Линейные таблицы страниц не подходят для больших адресных пространств. Например, для 32-битного адреса и 4Кб страниц адресное пространство 4Гб будет состоять из 2^20 страниц. При 4 байтах на запись таблицы страниц вся таблица займет 4Мб. Для 64-битного адреса при линейной организации таблицы страниц потребуется 2^54 байт. Неэффективно держать все записи таблицы страниц в ОП одновременно.

Способы организации таблиц

Многоуровневая таблица страниц

Достоинства:

• Дополнительный уровень косвенности.
• В ОП будут присутствовать лишь несколько записей таблицы страниц.

Недостатки:

• Падение производительности – каждый доступк памяти требует 3 (или более) доступов к физической памяти.
• Возрастает важность TLB.
• Возрастает важность соотношения попаданий (hit ration).

Инвертированная таблица страниц

Запись таблицы содержит:

1. Process ID (таблица разделяется между всеми процессами);
2. Номер виртуальной страницы;

Индекс в таблице представляет собой номер страничного кадра физической памяти.

При обращении осуществляется поиск:

1. для каждой записи в инвертированной таблице PID и VPN сравнивается с запрошенными.
2. Сравнение имеет линейную скорость (O(N)), и требует в среднем N/2 обращений к памяти, что очень медленно.

Хэшированная инвертированная таблица страниц

• Вводится дополнительная таблица, которая с помощью функции хэширования отображает PID и VPN на индекс записи таблицы страниц.
• Предусмотрена цепочка для разрешения коллизий. Для записи сравнивается PID и VPN с запрошенным. Если не совпадает, переходит на следующую запись.
• Распространена на 64-битных машинах.

Политика замещения страниц

При страничном прерывании может потребоваться освободить место для новой страницы. Нужно определить страницу, которую можно отправить во внешнюю память.
Алгоритмы (политики) замещения:

1. Случайный алгоритм;
2. First-In, First-Out (FIFO);
3. Not Recently Used (NRU);
4. Second Chance;
5. Часовой алгоритм;
6. Least Recently Used (LRU);
7. Working Set;

Случайный алгоритм

Страница для удаления выбирается случайно.

Недостаток: может быть удалена даже наиболее интенсивно используемая страница.

First-In, First-Out (FIFO)

Поддерживается очередь страниц. Новая страница добавляется в «хвост» очереди, а удаление страницы происходит из «головы» очереди.

Недостаток: возможна ситуация, когда наиболее часто используемые страницы оказываются ещё и наиболее давно загруженными.

Алгоритм замещения давно использовавшейся страницы (Not Recently Used)

Проверяются биты R (Referenced) и M (Modified). При этом R устанавливается при чтении, записи или выполнении страницы, M – только при записи. При первоначальной загрузке страницы в память оба бита сброшены. В алгоритме периодически (по таймеру) сбрасывается бит R.
В результате при возникновении страничного прерывания выделяют 4 класса страниц:

• 0 – не использованная, не модифицированная;
• 1 – не использованная, модифицированная (например, R := 0 по таймеру).
• 2 – использованная, не модифицированная;
• 3 – использованная, модифицированная.

Алгоритм удаляет случайную страницу из непустого класса с самым меньшим номером.

Алгоритм «Второй шанс» (Second Chance)

Модификация алгоритма FIFO.

При удалении страницы проверяется бит R. Если он сброшен, страница удаляется из «головы» очереди, если он установлен, то бит сбрасывается, страница помещается в «хвост» очереди и проверяется следующая страница в «голове» очереди.

Недостаток: много перемещений страниц.

Часовой алгоритм

Модификация Second Chance.

Страницы образуют циклический список. Есть указатель на текущую страницу. При страничном прерывании проверяется бит R текущей страницы. Если он сброшен, то страница удаляется на ее место заносится новая, а значение указателя увеличивается на 1. Если бит установлен, то значение указателя увеличивается на 1 и аналогичным образом проверяется следующая страница.

Наиболее давно использовавшаяся страница (Least Recently Used, LRU)

Страницы, использованные в течение последних нескольких
инструкций, с большой вероятностью будут использованы и в
нескольких следующих.

Реализация 1 (программная). Используется счетчик, увеличивающийся на 1 после каждой инструкции. Каждая запись в таблице страниц содержит поле, в которое записывается значение счетчика при последнем обращении к этой странице. При страничном прерывании находится и удаляется страница с минимальным значением счетчика.

Реализация 2 (аппаратная). Используется матрица n x n (n – число страничных кадров). При запросе k-ой страницы k-ая строка выставляется в 1, затем обнуляется k-ый столбец. При возникновении страничного прерывания удаляется страница, соответствующая строке с минимальным значением.