В ранних системах UNIX использовался процесс подкачки (swapper process), который перемещал процессы целиком между памятью и диском (когда все активные процессы не помещались в физической памяти). Linux (подобно другим современным версиям UNIX) больше не перемещает процессы целиком. Единицей управления памятью является страница, и почти все компоненты управления памятью работают с точностью до страниц. Подсистема подкачки также работает с точностью до страниц и тесно связана с алгоритмом Page Frame Reclaiming Algorithm, описанным далее в этом разделе.
Основная идея подкачки в Linux проста: процессу не обязательно находиться целиком в памяти для того, чтобы выполняться. Все, что нужно, — это пользовательская структура и таблицы страниц. Если они подкачаны в память, то процесс считается находящимся в памяти и может планироваться для выполнения. Страницы сегментов текста, данных и стека подкачиваются динамически (по одной) по мере появления ссылок на них. Если пользовательская структура и таблица страниц не находятся в памяти, то процесс не может выполняться до тех пор, пока процесс подкачки не доставит их в память.
Подкачка реализована частично ядром, а частично новым процессом, называемым демоном страниц (page daemon). Демон страниц — это процесс 2 (процесс 0 — это процесс idle, традиционно называемый своппером, а процесс 1 — это init (см. рис. 10.5)). Как и все демоны, демон страниц работает периодически. После пробуждения он осматривается, есть ли для него работа. Если он видит, что количество страниц в списке свободных слишком мало, то он начинает освобождать страницы.
Операционная система Linux является системой с подкачкой страниц по требованию (без упреждающей подкачки) и без концепции рабочего набора (хотя в ней есть системный вызов для указания пользователем страницы, которая ему может скоро понадобиться). Текстовые сегменты и отображаемые на адресное пространство памяти файлы подгружаются из соответствующих им файлов на диске. Все остальное выгружается либо в раздел подкачки (если он присутствует), либо в один из файлов подкачки (фиксированной длины), которые называются областью подкачки (swap area). Файлы подкачки могут динамически добавляться и удаляться, и у каждого есть свой приоритет. Подкачка страниц из отдельного раздела диска, доступ к которому осуществляется как к отдельному устройству, не содержащему файловой системы, более эффективна, чем подкачка из файла, по нескольким причинам. Во-первых, не требуется отображение блоков файла в блоки диска. Во-вторых, физическая запись может иметь любой размер, а не только размер блока файла. В-третьих, страница всегда пишется на диск в виде единого непрерывного участка, а при записи в файл подкачки это может быть и не так.
Страницы на устройстве подкачки или разделе подкачки не выделяются до тех пор, пока они не потребуются. Каждое устройство или файл подкачки начинается с битового массива, в котором сообщается, какие страницы свободны. Когда страница, у которой нет резервного хранения на диске, должна быть удалена из памяти, то из разделов (или файлов) подкачки, в которых еще есть свободное место, выбирается раздел (или файл) с наивысшим приоритетом и в нем выделяется страница. Как правило, раздел подкачки (если таковой имеется) имеет более высокий приоритет, чем любой файл подкачки. Таблица страниц обновляется, чтобы отразить тот факт, что страница больше не присутствует в памяти (то есть устанавливается бит «страница отсутствует»), и ее местоположение на диске записывается в элемент таблицы страниц.
Алгоритм замещения страниц
Алгоритм замещения страниц работает следующим образом. Система Linux пытается поддерживать некоторые страницы свободными, чтобы при необходимости их можно было предоставить. Конечно, этот пул страниц должен постоянно пополняться. Это делается при помощи алгоритма PFRA (Page Frame Reclaiming Algorithm).
Linux различает четыре разных типа страниц: неиспользуемые (unreclaimable), подкачиваемые (swappable), синхронизируемые (syncable) и отбрасываемые (discardable). Неиспользуемые страницы (которые включают зарезервированные или заблокированные страницы, стеки режима ядра и т. п.) не могут вытесняться в подкачку. Подкачиваемые страницы должны быть записаны обратно в область подкачки (или в раздел подкачки) перед тем, как их можно будет вновь использовать. Синхронизируемые страницы должны быть записаны на диск в том случае, если они были помечены как «грязные». И наконец, отбрасываемые страницы могут быть использованы немедленно.
Во время загрузки процесс init запускает страничные демоны kswapd (по одному на каждый узел памяти) и настраивает их на периодическое срабатывание. При каждом пробуждении kswapd проверяет, есть ли достаточное количество свободных страниц, для этого он сравнивает нижний и верхний пределы с текущим уровнем использования памяти в каждой области памяти. Если памяти достаточно, то он отправляется обратно спать, хотя может быть разбужен и раньше, если внезапно понадобятся дополнительные страницы. Если доступной памяти в одной из зон становится меньше нижнего предела, то kswapd инициирует алгоритм востребования страниц PFRA. Во время каждого прохода востребуется только определенное заданное количество страниц (обычно это 32 страницы). Это число ограничено, чтобы сдерживать объем ввода-вывода (количество операций записи на диск, порожденных при работе PFRA). И количество востребуемых страниц, и суммарное количество просмотренных страниц — это настраиваемые параметры.
При каждом выполнении PFRA сначала пытается востребовать легкодоступные страницы, после чего переходит к труднодоступным. Многие ведь стремятся сначала сорвать те плоды, что висят ниже. Отбрасываемые страницы и страницы, на которые нет ссылок, могут быть востребованы немедленно, для этого их необходимо перенести в список свободных страниц зоны. Затем он ищет такие страницы с резервным хранением, на которые не было ссылок в последнее время (при помощи временного алгоритма). Затем следуют совместно используемые страницы, которые не используются активно пользователями. Проблема с совместно используемыми страницами состоит в том, что если элемент страницы востребуется, то таблицы страниц всех адресных пространств (совместно использующих эту страницу) должны быть синхронно обновлены. Linux поддерживает эффективные древоподобные структуры данных для того, чтобы облегчить поиск всех пользователей совместно используемой страницы. Затем просматриваются обычные пользовательские страницы, и если принимается решение об их вытеснении, то они ставятся в очередь на запись в область подкачки. «Подкачиваемость» (swappines) системы, то есть отношение количества страниц с резервным хранением к количеству страниц, нуждающихся в вытеснении с использованием PFRA, — это настраиваемый параметр алгоритма. И наконец, если страница недействительна, отсутствует в памяти, используется совместно, заблокирована или используется для DMA, то она пропускается.
PFRA при выборе (в данной категории) старых страниц для вытеснения использует алгоритм, подобный алгоритму часов. В основе этого алгоритма лежит цикл, который сканирует список активных и неактивных страниц каждой зоны, пытаясь востребовать страницы различных типов (с разной срочностью). Значение срочности передается как параметр, который сообщает процедуре о том, сколько усилий нужно потратить для востребования страниц. Обычно он указывает, сколько страниц нужно обследовать до того, как прекратить работу.
Во время работы PFRA страницы переносятся между списками активных и неактивных описанным на рис. 10.11 способом. Для реализации некоторых эвристик и поиска страниц, на которые не было ссылок и которые вряд ли понадобятся в ближайшем будущем, алгоритм PFRA поддерживает два флага для каждой страницы: активная/неактивная и ссылки есть/нет. Этими двумя флагами можно обозначить четыре состояния (см. рис. 10.11). Во время первого сканирования набора страниц PFRA сначала сбрасывает их биты ссылок. Если во время второго прохода по странице обнаруживается, что на нее была ссылка, то она переводится в другое состояние, из которого вряд ли будет востребована. В противном случае страница переводится в такое состояние, в котором она будет вытеснена с большей вероятностью.