Алгоритм замещения страниц работает следующим образом: система 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 существует еще один фоновый поток управления памятью. Данный поток либо пробуждается периодически для записи на диск грязных страниц либо явным образом тревожится ядром системы для записи грязных страниц из кэша страниц на диск
Система ввода-вывода ос linux.
Как правило все устройства ввода-вывода в linux выглядят как файлы и доступ к ним осуществляется с помощью тех же системных вызовов read и write, которые используются для обычных файлов. В некоторых случаях должны быть заданы параметры устройства, что делается при помощи специального системного вызова.
Общие понятия и концепции
В ОС linux реализован особый подход к управлению устройствами ввода-вывода. Данный подход заключается в интегрировании всех устройств ввода-вывода, т.н. файловую систему в виде специальных файлов (special files). Каждому устройству ввода-вывода назначается маршрут. Обычно в каталоге /dev, например диск может иметь маршрут /dev/hd1, принтер /dev/lp. Доступ к этим специальным файлам осуществляется так же, как и к любым другим файлам. Для этого не требуется никаких специальных команд или системных вызовов, например cp f1 /dev/lp. Данная команда скопирует данный файл на принтер, в результате чего файл будет распечатан. Программы могут открывать, читать и записывать в специальные файлы. Существует 2 типа специальных файлов – блочные и символьные. Блочный специальный файл состоит из последовательности пронумерованных блоков. Основное свойство блочного специального файла заключается в том, что к каждому его блоку можно адресоваться и получить доступ. Программа может открыть блочный файл и получить доступ к произвольному пронумерованному блоку. Символьные специальные файлы используются для устройств ввода-вывода символьного потока (клавиатура, мышь, принтер, сети и т.д.). С каждым специальным файлом связан драйвер устройства, осуществляющий работу с соответствующим устройством. У каждого драйвера есть так называемый номер старшего устройства (major device). Если драйвер поддерживает несколько устройств одного типа, то каждому такому устройству присваивается номер младшего устройства(minor device). Вместе взятые номера главного устройства и младшего устройства однозначно определяют каждое устройство ввода вывода.
