Алгоритм замещения страниц в ОС Linux.

Алгоритм замещения страниц работает следующим образом: система linux пытается поддерживать некоторые страницы свободными, чтобы их можно было предоставить при необходимости. Множество таких свободных страниц должно постоянно пополняться. Основным алгоритмом замещения страниц в linux является алгоритм PFRA (Page Frame Reclaming algorithm).

Подкачиваемость системы – это отношение количества страниц с резервным хранением к количеству страниц, нуждающихся в вытеснении. В алгоритме PFRA подкачиваемость является настраиваемым параметром. Прежде всего linux различает 4 разных типа страниц:

1) Неиспользуемые страницы – страницы, которые не могут вытесняться в подкачку

2) Подкачиваемые страницы – страницы, которые должны быть записаны в область подкачки перед тем, как их можно будет использовать.

3) Синхронизируемые страницы – страницы, которые должны быть записаны на диск в том случае, если они были помечены как грязные.

4) Отбрасываемые страницы – страницы, которые могут быть использованы немедленно.

Во время загрузки процесс init (приоритет 1) запускает страничные демоны kswapd и настраивает их на периодическое срабатывание. При каждом пробуждении поток kswapd проверяет, есть ли достаточное количество свободных страниц для этого он сравнивает нижний и верхний пределы с текущим уровнем использования памяти в каждой области памяти. Если памяти достаточно, то он отправляется обратно спать, хотя он может быть разбужен раньше, если внезапно понадобятся дополнительные страницы. Если доступной памяти в одной из зон становится меньше нижнего предела, то kswapd инициирует алгоритм востребования страниц PFRA. Во время каждого прохода востребуется только определенное заданное количество страниц. Это число ограничено, чтобы сдерживать объем ввода-вывода. При каждом выполнении алгоритма PRFA, он сначала пытается востребовать легкодоступные страницы, после чего переходит к труднодоступным. Востребованя ность страниц рассматривается в следующей очередности:

1) Отбрасываемые страницы и станицы, на которые нет ссылок.

2) Страницы с резервным хранением, на которые не было ссылок в последнее время

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

Linux поддерживает эффективные древоподобные структуры данных для того, чтобы облегчить поиск совместно используемой страницы.

4) Обычные пользовательские страницы.

Алгоритм PRFA при выборе старых страниц (в какой-либо из категорий) для вытеснения использует алгоритм, подобный алгоритму часов. В основе этого алгоритма лежит цикл, которые сканирует список активных и неактивных страниц каждой зоны, пытаясь востребовать страницы различных типов. Большое значение имеет параметр срочности. Значение срочности передается как параметр, который сообщает процедуре о том, сколько усилий нужно потратить для востребования страницы. Обычно он указывает, сколько страниц нужно обследовать до того, как прекратить работу. Во время работы алгоритма PRFA страницы переносятся между списками активных и неактивных страниц. Для реализации поиска страниц, на которые не было ссылок и которые вряд ли понадобятся в ближайшее время, алгоритм PRFA поддерживает 2 флага для каждой страницы:

1) активная и неактивная

2) ссылки есть или нет

Этими двумя флагами можно обозначить 4 состояния:

- во время 1-го сканирования набора страниц алгоритм prfa сначала сбрасывает их биты ссылок. Если во время второго прохода по странице обнаруживается, что на нее была ссылка, то она переводится в другое состояние из которого она вряд ли будет востребована. В противном случае страница переводится в такое состояние, в котором она будет вытеснена с большей вероятностью.

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

Алгоритм prfa содержит страницы в списке неактивных, хотя на них могут быть ссылки для того, чтобы предотвратить следующие ситуации:

Рассмотрим процесс, который делает периодические обращения к разным страницам. Страница, к которой в последний раз выполнялось обращение будет иметь установленный флаг доступа, однако, поскольку она не понадобится в течение следующего часа можно не считать ее кандидатом на востребование. Также в системе linux существует еще один фоновый поток управления памятью. Данный поток либо пробуждается периодически для записи на диск грязных страниц либо явным образом тревожится ядром системы для записи грязных страниц из кэша страниц на диск