Linux Kernel (Ядро линукса) (часть 3)

Списки давно неиспользуемых страниц (LRU)

Все страницы, принадлежащие адресному пространству процессов в режиме пользователя или кэшу страниц, собраны в два списка, называемые активным и неактивным; они также известны под общим названием списков давно неиспользуемых страниц (списков LRU). Первый список содержит, по большей части, страницы, к которым были обращения недавно, а второй включает в себя страницы, к которым в течение какого-то времени ни один процесс не обращался. Очевидно, что для утилизации следует брать страницы из неактивного списка.

Активный и неактивный списки страниц являются важнейшими структурами данных для алгоритма утилизации страничных кадров. Головы этих двунаправленных списков хранятся, соответственно, в полях active iist и inactive iist каждого дескриптора zone Поля nr active и nr inactive у одного дескриптора содержат количество страниц в этих списках. Поле iru iock является спин-блокировкой, которая защищает эти два списка от параллельного доступа в SMP-системах.

Если страница принадлежит одному из списков LRU, флаг PG iru в ее дескрипторе установлен. Кроме того, если страница принадлежит активному списку, установлен флаг PG_active, а если неактивному— этот флаг сброшен. Поле iru дескриптора страницы содержит указатели на следующий и предыдущий элементы списка LRU.

Для работы со списками давно неиспользуемых страниц существует несколько служебных функций:
- add page to active iist о — добавляет страницу в начало активного списка зоны и увеличивает поле nr active дескриптора зоны;
- add page to inactive iist — добавляет страницу в начало неактивного списка зоны и увеличивает поле nr inactive дескриптора зоны;
- dei page from active iist о — удаляет страницу из активного списка зоны и уменьшает поле nr active дескриптора зоны;
- dei page from inactive iist о — удаляет страницу из неактивного списка зоны и уменьшает поле nr inactive дескриптора зоны;
- dei_page_from_iru — проверяет флаг PG active у страницы и, в зависимости от результата, удаляет страницу из активного или неактивного списка, уменьшает поле nr active или nr inactive дескриптора зоны и, если необходимо, сбрасывает флаг PG active;
- activate page о — проверяет флаг PG active. Если он сброшен (страница находится в неактивном списке), функция переносит ее в активный список; вызывает функцию del_page_f rom_inactive_list , затем — функцию
add page to active list И, наконец, устанавливает флаг PG active. До переноса страницы функция получает спин-блокировку зоны iru iock;
- iru cache addo — если страница не включена ни в один список давно неиспользуемых страниц, эта функция устанавливает флаг PG iru, получает СПИН-блОКИрОВКу ЗОНЫ lrulock И ВЫЗЫВает фуНКЦИЮ add_page_to_ inactive iist , чтобы занести страницу в неактивный список зоны;
- iru_cache_add_activ — если страница не включена ни в один список давно неиспользуемых страниц, эта функция устанавливает флаги PG iru и PG active, получает спин-блокировку зоны lru lock и вызывает функцию add page to active list о, чтобы занести страницу в активный список зоны.
На самом деле, последние две функции немного сложнее. Они не заносят страницу в список давно неиспользуемых страниц немедленно, а накапливают страницы во временных структурах типа pagevec, каждая из которых может вмещать до 14 указателей на дескрипторы страниц. Страницы фактически переносятся в список давно неиспользуемых страниц только тогда, когда структура pagevec оказывается заполненной. Этот механизм повышает производительность системы, потому что спин-блокировка списка давно неиспользуемых страниц используется только при действительной модификации списков LRU.