Читайте также:
|
Алгоритм замещения страниц работает следующим образом: система linux пытается поддерживать некоторые страницы свободными, чтобы их можно было предоставить при необходимости. Множество таких свободных страниц должно постоянно пополняться. Основным алгоритмом замещения страниц в linux является алгоритм PFRA
Подкачиваемость системы – это отношение количества страниц с резервным хранением к количеству страниц, нуждающихся в вытеснении. В алгоритме 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 сначала сбрасывает их биты ссылок. Если во время второго прохода по странице обнаруживается, что на нее была ссылка, то она переводится в другое состояние из которого она вряд ли будет востребована. В противном случае страница переводится в такое состояние, в котором она будет вытеснена с большей вероятностью.
Дата добавления: 2014-12-19; просмотров: 285 | Поможем написать вашу работу | Нарушение авторских прав |